Bizarre slowdown when using cin on a 64-bit compiler

Правка en1, от defnotmee, 2022-01-14 21:47:17

Hello codeforces! I've come to ask help in a time of great mystery.

I was helping to debug a problem where the code would pass the 2s TL when on a 64-bit compiler but would get confortably under 1s on a 32-bit one when some really bizarre things started to happen.

First, pinning down where the problematic parts were, it turns out this was the thing consuming practically the whole time limit:

set<ll> s;
for (int i(0); i < k; ++i) {
    int pp;
    cin >> pp;

Im not joking. Also k <= 3e5 btw.

It really shouldnt be a big deal, and normally that part should take less than 140ms, but both on C++20 (64) and C++17 (64) make it take from 1900ms to 2000ms.

I made a submission that outputs the time taken to do the input, the inserting, and the ammount of elements in the set; and with that even more weird stuff appears. Look at the result:



In this test case until the 90000-ish iteration there are distinct elements and after that the input time starts to raise aggressively, while the insert time grows at a basically unaltered pace. Maybe they start repeating a relatively big number, but even then, it goes from 30ms to read 50000 guys to 500ms. It's insane.

If you want, take a look at the version of the output when using 32-bit for comparison (the numbers will actually be a bit inflated because you need to get the timings with std::chrono):



Ending thoughts

  • The problematic test case is case 6, however case 5 has the same input size and the set ends up with more items (see 142732612). Why is the problem only with test 6???

  • If instead of reading a variable and instantly inserting it into the set, you first input an array and then insert it into the set, no tragedy happens (142732784).

  • How can the input go so wrong? A 20x slowdown out of nowhere should not be happening.

  • Is there a way to get the raw test data from the authors or something similar to see what actually was on test 6 so we can try to replicate it?

  • Thanks qwexd for doing nothing.

Теги bug, cin, 32 bit vs 64 bit, somethingsomething


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский defnotmee 2022-01-14 21:47:17 3567 Initial revision (published)