adamant's blog

WTF or another complain on compilers
By adamant, history, 6 years ago, In English

Okay, so compare these two submissions: 51053654 and 51053605

The only difference is that first one made via GNU C++17 and the second one via MS C++ 2017. Code is same, but first gets RE 16 and second one gets AC.

WTF, GNU C++??

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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

UB maybe?

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

    Can you see any? For me code seems pretty clear. I'd rather expect that somehow they optimize code differently which leads first one in stack limit. It's not very realistic though because I had a GCC version running into TL 18 (thus passing 16th test): 51022745

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

If depth of your dfs may be >= 1e6, then it's stack overflow. And in that case "WTF" can be easy explained by different stack size or/and different bytes-on-stack-per-recursive-call used by the compiler.

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

    Is it really stack overflow? Stack on codeforces is 256 mb: Link

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

      Note that test 16 is one of the test where memory consumption is maxed for your MSVC solution and it's >400mb with GCC. So maybe you actually use more than 256mb of stack in that case?

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

      What is actual max depth of recursion? If I interpret these submissions correctly: 51057215 51057182, 1 level of recursion eats 28 bytes on msvc and 64 bytes on GCC

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

        So, If I interpreted it correctly, the depth is 5e6 and so with msvc you use ~150mb+28*5e6=~290mb. with gcc you use 320mb of stack

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

      So, as we discussed with adamant elsewhere, the problem was indeed in the stack size.

      AC submission: 51059986

      So the problem can be avoided by creating new stack with increased max stack size. You can copypaste snippet at the end of the code to your template to forget about the stack size

      --

      One open question is why gcc require two times more memory

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

        Everything is fine with -O1 flag for C++17, adamant AC submission

        I thought that with -Os will be fine too, but it is not

        So I think that something from -O2 optimizations activates aligning on system stack by 64 bytes.

        UPD. Option -fconserve-stack with -O3 can be used, it gave 313 MB memory usage (~ 163 MB stack) and runtime is 3181 ms, faster than original solution on MSVC ( 3524 ms ), and faster than -O1 solution ( 3681 ms ). Submission

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

same thing((( 51079321 51026165.

Didn't think about stack size

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

Hi, please compare these two submissions: 51586126 and 51586141. The only difference is that the first one adding the inline specifier onto the tarjan function and gets AC, the second one without inline gets RE 16.

Any ideas?

→ Reply