Блог пользователя Nozarashi

Автор Nozarashi, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +36 Проголосовать: не нравится

          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;
          }