variance's blog

TLE vs RTE in C++20
By variance, history, 3 years ago, In English

Consider submissions 151556965 and 151558044. They are the same, except that the first is in C++20 and the second is C++17. The solutions fail because the bounds for the problem are N <= 2e5, but I used MAXN = 20005 for the length of an array (the problem involved reading in an array of length N).

Thus we get RTE on the C++17 submission (as expected) due to accessing memory out-of-bounds. But why does the first one TLE?

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

»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

You get UB in both cases (as expected).

As for what leads to TLE when I run your solution on my Linux system after compiling it with GCC 11.2.0:

  • Both N and a are allocated in the .bss section and N is placed right behind a. So an off-by-one write to a overwrites N and happens to put a really large value there (someting like 1000000000 or 999999998 for the failed testcase). So the loop runs a lot more iterations than expected and this is slow.
  • Now why there's no segfault? The heap is allocated right behind .bss and can be resized via brk/sbrk syscalls on Linux (stackoverflow provides some additional information). So writing there only corrupts heap, but doesn't immediately trigger a segfault if the heap is large enough.
  • But aren't 1000000000 loop iterations enough to write beyond any moderately sized heap and trigger a segfault? Now the explanation is that std::cin >> a[i] stops writing to a[i] after reaching the end of the input data from stdin. As a result the program:
    1. fills the whole array a
    2. overwrites N with something very large
    3. overwrites a part of the heap as long as there's data coming from stdin
    4. keeps trying to unsuccessfully read from stdin without causing further memory corruption for the remaining loop iterations

Something similar is probably happening on Codeforces with C++20. But UB is unpredictable and you can never expect any specific behaviour.

→ Reply