Sigh's blog

MLE due to empty containers?
By Sigh, history, 5 months ago, In English

I got MLE in this submission. After investigation it turned out that I created empty containers before a recursive call (in the get_delete_x_ans function), resulting in creation of many such containers when call stack is deep.

That sounds reasonable, but when I did the calculation, it seemed impossible that this mistake could lead to MLE when the mem limit is 512MB.

So the calculation goes:

My later accepted solution uses 175100KB, limit is ~524288KB, difference is 300000+KB = approx. 300MB.

So it means that the submission above created empty containers that take up 300MB space.

It will create 2 empty queue, each is 48 byte on a 64-bit machine.

Recursion depth is <=500000 from problem description. So total space of empty containers is 2 x 48B x 500000 = approx. 5x10^7 B = 50MB.

That's much less than 300MB, so if the calculation was correct, I shouldn't get MLE.

Can someone help point out what's wrong with my calculation above? Thanks!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

An empty queue (to be precise, an empty deque) allocates much more memory by default.

Compare 272637612 and 272637639, where the only difference is having an 100000-sized array of empty queues. This took 68700 more KB, so we can assume each queue took around 0.687 KB. I don't get where that 48 came from, but even sizeof(q) where q is a queue<int> shows 80 in custom invocation (C++20), but in reality the dynamically allocated part is not reflected in it. It costs far more than that.

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are right. The sizeof only accounts for static memory. That explains it.

    48B is what I got with sizeof(queue<int>()) from my local 64bit machine.

    Thanks for your help!

    → Reply