-is-this-fft-'s blog

Why does this submission get stack overflow?
By -is-this-fft-, history, 4 hours ago, In English

This is my in-contest submission for 2048F - Kevin and Math Class: 297343653. It got "runtime error on pretest 3", which I initially thought was some stupid bug. After the contest was over, I was surprised to see "exit code: -1073741571 (STATUS_STACK_OVERFLOW)". Stack overflow happens when the recursion goes too deep, but the stack limits on Codeforces are pretty generous, and recursion 2e5 calls deep is generally not an issue (imagine how annoying all DFS problems would be otherwise).

At first I thought that this must still be a bug that led to infinite recursion. But I verified locally that this is not the case, and I added an assertion to check that no more than 2e5 calls to solve(ll, ll) are performed in any one test case:

ll solve (ll l, ll r) {
  cnt++;
  assert(cnt < maxn);
// .. rest of the function ..

I also moved the references to tree and arr to global variables for good measure. Still a stack overflow: 297352244.

For what it's worth, both versions get accepted under C++20: 297353626, 297353915.

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

»
4 hours ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

Oh, that is weird. The same thing happened to me at F: an actual stack overflow. Just like you, I thought it was infinite recursion, but with minimal changes, the code passes. I do not think I ever got stack overflow which was not infinite recursion and was in intended complexity.

I made my function return array of 61 numbers representing dp values. I had similar recursive approach as you. Interestingly, when I replaced those with a vector, it passed.

Submission with returning array 297354881

Submission with returning vector 297353480

I guess it kinda makes sense as I used a lot of memory in my calls, and if I am not mistaken when I call function that returns struct, it gets stored in stack memory. But vector gets stored in heap. I could be totally wrong about that, so please correct me in that case.

→ Reply
  • »
    »
    4 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    In the implementation of libstdc++, the array<_Tp, _Nm>::_M_elems is defined as __array_traits<_Tp, _Nm>::_Type, and the latter is simply _Tp[_Nm].

    So you're indeed piling $$$61$$$ values on the stack which overflows.

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

      I used struct actually. But I think it's the same?

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

        Oh i don't look at your submission and assume you use std::array. You code nevertheless does the same thing as std::array.

        → Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

encountered stack overflow on many 5e5-1e6 recursion calls also on so many dp problems where its not possible to initialize the dp array globally because some states change in an amortized way not sure why cf doesnt increase the stack to 512 or 1024 , it wont cause any issues no ?

another thing about returning structs its so random to me i never understand struct memory or how it works sometimes really heavy structs dont take as much memory as structs that seem alot lighter

→ Reply
»
4 hours ago, # |
  Vote: I like it +23 Vote: I do not like it

It is simply worth increasing the stack in such situations. For example, if you double the stack, then the solution works: 297356923. C++ on Codeforces uses 256 MiB by default, in my solution I increased my stack to 512 MiB.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    What? That feels like something that should not be legal...

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

      Why? I'm just using the OS's capabilities. I just create a new thread, give 512 MiB stack memory to it, and order the main thread wait until the one I created completes. If the solution with this technique it does not exceed ML, then it should be legal, I think.

      CreateThread documentation.

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

        Yeah. But it's crazy that's possible. It kinda gives advantage. Though similar argument could be made about ios_base::sync_with_stdio(false);

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

          I also remembered another old technique for stack increasing. People wrote #pragma comment(linker, "/STACK:<Stack size in bytes>") in the source code and submit solution with Microsoft C++. But, Microsoft C++ compiler is generally slower than g++, and now there is no Microsoft C++ compiler on Codeforces.

          In general, the same can be said about pragmas, which sometimes make it possible to get AC with solution which should not fit TL according to the authors of the problem.

          P.S. All of C/C++ default IO is shit. Custom IO will be significantly faster (ofc only in proper implementation).

          → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    How to increase time limit?

    → Reply
»
88 minutes ago, # |
  Vote: I like it +10 Vote: I do not like it

I have an answer but this margin is to small to contain it. So I posted it in a separate blog: https://codeforces.net/blog/entry/137488

TL;DR: GCC 7 (32-bit) bad

→ Reply