OleschY's blog

Inconsistent times and TLE with C++17 (64bit) vs. C++17
By OleschY, history, 4 years ago, In English

Hi, while submitting 1535F - String Distance for the previous educational round I did observe a strange behaviour. I submitted the absolutely same code several times:

image

As you can see, submitting with C++17 was AC every single time. Submitting with C++17 (64bit) lead to timeouts on different testcases, like 18, 27 or 32 but also to several AC with all testcases 18,27,32 only needing <300ms in 64bit. I read my code about 20 times now checking for out of bounds errors or stupid mistakes. I have no random numbers generated. I also did several tests by generating a big number of random testcases with both 64bit and 32bit locally, but I couldn't reproduce this behaviour. I got consistent times all around. Now I'm clueless and want to ask whether someone has an idea why this happens.

Some details about the code

Thank you for your help!

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

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Maybe there are different types of testing machines and depending on which one gets assigned to test your submissions, you get different times. If you can't reproduce it locally, it's mainly a question for CF staff.

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

    So, what is the best way to reach CF staff? I searched the website, there seems to be no support-channel and no staff-site (or I just can't find them). Do I just tag Mike (and get lost in the flood of tags he probably gets regularly)?

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

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

        Hi MikeMirzayanov there seems to be an inexplicable and seemingly random (from testcase to testcase) difference in execution time for the same submission in C++17 vs C++17 (64bit). Me and pajenegod tested locally and could absolutely not reproduce this behaviour, it only happens in CF-System. Could your team have a look into it? More detailed info is in the blog itself.

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

          I wouldn't put too much emphasis on C++17 vs C++17 (64bit).

          The issue is that your code submitted in C++17 (64bit) gets AC or TLE seemingly at random. Your AC submissions come in far below the TL (250ms / 2s), so the issue cannot simply be explained by small random fluctuations.

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it 
long long nAll;
vector<pair<string, string>> in(nAll);

This is weird thing to have in global space. But it is not technically wrong.

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

    Oh dear, that was good old copy-paste (I moved the input to global to do the local checks with random data)... To be sure I checked, but 64bit is still failing after fixing this.

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

I did some more digging into this, and I got ahold of the test cases. The test cases are generated in packs of 9, which explains why there is a pattern of TLE at 18, 27, 36.

I tried to run your program locally, both with sanitizers and debug flags. Locally everything simply works, no issues at all. It runs pretty quickly too, not even close to TLE. So my best guess is that something is wrong on CF's side.

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

One observation. If we remove reference & from this loop: for(vector<string>& strs : strGroups), the code never gets TLE. Now it looks more like UB, but I wasn't able to find something illegal.

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

    I find it funny that we can have multiple red coders look at a piece of C++ code and can't tell if there's UB or not. I wonder why writing a comprehensive UB sanitizer is such a hard problem?

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

An update on this issue. I've tried two additional things.

  1. I tested creating a mashup on CF where I manually increased the TL. It seems like the 64 bit C++ program randomly either gets AC in 0.2 s or 11 s. It takes consistently either 0.2 s or 11 s, and nothing in between.

  2. On my windows laptop (which I believe to be similar spec compared to CF servers), I downloaded pbox.me (package manager by Mike) and installed the exact version of the 64 bit C++ compiler that CF uses. I've also gotten a hold of all the problematic test cases. Even doing all of this, I have not been able to recreate the issue locally.

I have no clue what could explain the program randomly running ~50 times slower. I've read the code, I've ran sanitizers. As far as I can tell there is no UB going on.

→ Reply