Nozarashi's blog

Why is C++ 14 better than C++ 20 in memory management here?
By Nozarashi, history, 3 years ago, In English

Hello all, I participated in Codeforces Round #765 (Div. 2). I implemented a 0/1 Trie for {D. Binary Spiders} => {https://mirror.codeforces.com/contest/1625/problem/D}

When I used C++20 {https://mirror.codeforces.com/contest/1625/submission/142523361} it got an MLE verdict and the memory required is 262144 KB.

However when I changed it to C++14 {https://mirror.codeforces.com/contest/1625/submission/142523239} it got an AC verdict and the memory required is 161068 KB.

Why does this happen, how can the same code require so much more memory in C++20? Can anyone help me? Kinda seems like black magic to me.

Thank you!

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nozarashi (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

It's because it's 64 bit. Use arena allocation instead of new to save space.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Can you expand a bit on what arena allocation is and why it only affects the 64 bit version of the compilers?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      You don't understand why you have the memory problem.

      On one of this compilers pointers will be represented by (and thus require) 32 bits and 64 on the other. Now think how does that affect your code.

      After realizing that, google what arena allocation is. Then implement a solution for this problem using this idea.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did a quick calculation, the size of my node struct is 16 bytes. There are 3e5 * 30 number of nodes in the worst case which amounts to 140625 KB = 140 MB, but the 64 bit compiler is showing an MLE verdict even for a 256 MB allowance. Other than the Trie nodes, not much memory is being used.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +36 Vote: I do not like it

          If your calculation is correct, how come you're using 160 MB on 32 bit C++14? The reason why you're getting MLE is because new has a large memory overhead. You can try it yourself with custom invocation.

          The code below uses almost 32 MB on custom invocation, even though only 16 MB was requested. To get rid of this overhead, allocate a large memory buffer and then write your own replacement of new which increments a counter and returns a new address each time. This idea is called Arena allocation.

          using ull = unsigned long long;

struct _16bytes {
    _16bytes* a[2];
};

int main() {
    ull q;
    for (int i=0; i<1000000; i++) {
        q ^= reinterpret_cast<ull>(new _16bytes());
    }
    return q == 0;
}
          → Reply