nskybytskyi's blog

Why you may want to use two-layer dp not only to decrease the memory usage
By nskybytskyi, history, 3 years ago, In English

I was upsolving AtCoder Beginner Contest 195 problem F, aka "Coprime Present" where you need to count subsets (of a special set of size < 72) with pairwise coprime elements.

My solution is a bitmask dp over prime factors that were used and a prefix of the set. My first submission.

Fairly straightforward, nothing smart, $$$O(N \cdot 2^n)$$$ time and memory. However, I was disappointed by the memory usage of 600+ Mb. Therefore, I implemented a two-layer version of the same dp. Here is my second submission.

The difference is minimal, I just take layer_number & 1, and don't forget to clear the previous layer before proceeding to the next one

Obviously, it uses way less memory, only 30 Mb. What surprised me is that the running time has also decreased, from 472 ms to just 147 ms, for an improvement by a factor of 3!

I have two hypotheses on why this happens:

  • two layers fit into the better cache level, facilitating memory lookups;

  • memory allocation itself takes some time (there must be a reason why people write custom allocators, right?).

Can someone more experienced please tell me what actually happens there?

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

Comments Comments (16)
| Write comment?
»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Memory allocation

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Yeah, 30 Mb is too much to fit into cache on any level, so it's purely memory allocation related speedup.

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

      meme

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +16 Vote: I do not like it

        Good one :)
        BTW, L4 cache exists, but that's another story :)

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      It's not about cache, it's about memory allocation. It's obvious that one layer wouldn't fit into cache, so there is no difference in that regard.

      UPD: I didn't understand your message at first, but it seems that you meant the same thing as me :) Hope this comment with clarify our statements.

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

        I just edited my comment to make it more clear :)

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

        I don't know how accurate it is, but "sudo perf record -e cache-misses solution" shows 5 times more cache-misses on first solution over the second on my machine (this counters may work different on different cpus, and obviously they may have different caches).

        PS. Hm, cache misses % almost the same — 75% for both solutions. Because second solution has not only 5 times less cache misses, but also 5 times less cache references.

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    The problem is not in memory allocation itself, but more in high memory utilization. So it seems to me that it is actually more closer to caching issues rather than expensive allocations.

    Two submission examples:

    First — huge amount of memory is allocated once on each run, but when it's unused, running time is low (17 ms on the smallest test).

    Second — huge amount of memory is allocated, but gradually, and previous layers of dp are being freed. So at the same time only two layers are allocated and maximum running time is same as in two-layer solution (170ms), but total allocated memory size is still huge.

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

      I think that I just don't understand how this works, why allocating huge memory and not using it is fast, godbolt says that allocation happens so no compier help on that side.

      Maybe in the second example compiler optimized something too? However I'm not sure that's possible based on my knowledge. On the other hand, maybe computer decides to give the same memory block each allocation, so it's indeed equivalent of 2 layers dp?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +31 Vote: I do not like it

        C++ new int64_t[...] and delete operate on heap memory. Since requested memory blocks are of the same size, it indeed works almost exactly as a small fixed pool of arrays.

        As for difference in time, it is simply due to difference in number of active memory pages. The more pages your process touches, the more frequently page fault happens. Allocating huge unused array is fast because actual page allocation happens lazily.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it
          some calls of first submission
          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it +3 Vote: I do not like it

            So, the biggest offenders are not the page faults per se, but the initializations of new pages?

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

Obviously, it uses way less memory, only 30 Mb. What surprised me is that the running time has also decreased, from 472 ms to just 147 ms, for an improvement by a factor of 3!

Improved by a factor of 3, not 3!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

upd: deleted

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

memory allocation itself takes some time (there must be a reason why people write custom allocators, right?).

That's more important when you have a huge number of allocations (not same as total allocated memory). For example allocations of some tree nodes.

→ Reply