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

WTF or another complain on compilers
Автор adamant, история, 6 лет назад, По-английски

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++??

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

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

UB maybe?

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

    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

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

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.

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

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

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

      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?

      → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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

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

        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

        → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
        ← Rev. 6   Проголосовать: нравится +21 Проголосовать: не нравится

        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

        → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

same thing((( 51079321 51026165.

Didn't think about stack size

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

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?

→ Ответить