Strange TLE by cin using GNU C++20 (64)...Again?

Правка en3, от tatianyi, 2024-05-10 10:38:35

This time, Auroraa_ is solving 524E - Rooks and Rectangles. After some trial, he got

this code

and then received TLE: 260160406

He was surprised, so he tried it again with exact same code, with C++17 (32). You know what? The AC magic happened again: 260161644.

At first glance, we do think some code has triggered undefined behaviours like Access out of bounds. But Auroraa_ denied that, because all the data could be fit in int32_t.

Then came the dramatic scene: by simply changing the code vector<int>v1[N], v2[N]; to vector<long long>v1[N], v2[N];, the strange TLE problem disappeared: 260164936.

After that, my further investigation(260199113) pointed out that the block causes TLE is:

for (int i = 1; i <= q; i++) {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	vec.push_back({ x1, y1, x2, y2, i });
}

It took over 2000ms(260199205) to write data into this vec. And only took about 100ms(260199447) to do the same thing if we just changed vector<int>v1[N], v2[N]; to vector<long long>v1[N], v2[N];. The weirdest thing is, there is no direct connection between v1,v2 and vec.


Recalling the process just described, coincidentally, this modification process is really similar to the blog Strange TLE by cin using GNU C++20 (64), and some weird subtle changes to (surprisingly) fix it.

And like this blog Slowdown bug affecting C++ (64 bit) on Codeforces, this time we encountered a Pandora's Box that just used a different magic number to open. Although MikeMirzayanov has updated the CF system to

Windows Server 2022

, there is still something fishy here.

The new version of GCC and OS passed the "test" on You won't believe how this simple trick defeated the unexplained bug destroying every top LGM; also included other languages such as Rust. The script mentioned there does not work for Rust now (both in custom test and on my Windows 11 computer).

I translate the script to C++:

#include "bits/stdc++.h"

int main() {
    constexpr size_t n = 30000;
    auto vec = std::vector<std::vector<int>>(n);
    for (size_t i = 10000; i < 20000; i++) {
        vec.resize(i);
        for (size_t j = 0; j < i; j++) {
            vec[j].reserve(7);
        }
        auto start = std::chrono::system_clock::now();
        for (size_t j = 0; j < 10000; j++) {
            vec[i - 1].reserve(7);
            vec[i - 1].shrink_to_fit();
        }
        auto elapsed = std::chrono::duration<double, std::milli>(std::chrono::system_clock::now() - start).count();
        if (elapsed > 40) {
            std::cout << i << " " << elapsed << "\n";
        }
    }
}

and also the bomb:

#include "bits/stdc++.h"

int main() {
    constexpr size_t n = 30000;
    constexpr size_t evil = 17182;
    auto vec = std::vector<std::vector<int>>(n);
    vec.resize(evil);
    for (size_t i = 0; i < evil; i++) {
        vec[i].reserve(7);
    }
    for (size_t i = 0; i < size_t(1e6); i++) {
        vec[evil - 1].reserve(7);
        vec[evil - 1].shrink_to_fit();
    }
}

And it generated the output Used: 5514 ms, 0 KB

As usual, I change constexpr size_t evil = 17182; to constexpr size_t evil = 17183;, and then Used: 93 ms, 0 KB

OOPS, MikeMirzayanov! Did you forget to upgrade compilers after migrating the CF system to Windows Server 2022? If that's true, please, upgrade those compilers to UCRT version, and I suggest you could simply use the one with LLVM for the simplest configuration for clang18 with GCC's libstdc++.

Теги c++, bug, compiler, 32 bit vs 64 bit, 64 bit, tle, slowdown, mingw

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский tatianyi 2024-05-17 19:16:15 225 Tiny change: Tiny difference between msvc and mingw64-gnu
en9 Английский tatianyi 2024-05-17 15:23:08 100 Tiny change: add Clang in the installation command.
en8 Английский tatianyi 2024-05-17 14:43:27 244 UPUPD change: msvc compiler also not suitable for this
en7 Английский tatianyi 2024-05-17 14:16:28 1209 Add a combined version that automatically finds the bomb.
en6 Английский tatianyi 2024-05-16 02:26:26 192 Tiny change: Headers for easy cross-platform.
en5 Английский tatianyi 2024-05-13 15:06:03 38 Tiny change.
en4 Английский tatianyi 2024-05-10 20:14:32 3365 Further investigation for MinGWs and MSYS2.
en3 Английский tatianyi 2024-05-10 10:38:35 164 (published)
en2 Английский tatianyi 2024-05-10 10:34:09 6695 Change: 'vector bomb'
en1 Английский tatianyi 2024-05-10 09:30:16 4047 Initial revision (saved to drafts)