Slowdown bug affecting C++ (64 bit) on Codeforces

Revision en2, by pajenegod, 2024-03-02 18:26:41

Yesterday, investigating Strange TLE by cin using GNU C++20 (64), I found an easy and reproducable way to trigger a slowdown bug that I believe has been plaguing Codeforces for some time now. So I'm making this blog to raise awarness of it. MikeMirzayanov, please take a look at this!

Here is how to trigger the slowness bug:

  1. Take any problem with a relatively large input on Codeforces ($$$2 \cdot 10^5$$$ ints is enough).
  2. Take a random AC C++ submission that uses std::cin.
  3. Add the line vector<vector<int>> TLE(40000, vector<int>(7)); somewhere in global space.
  4. Submit using either C++20(64 bit) or C++17(64 bit).
  5. ???
  6. TLE

For example take tourist's solution to problem 1936-D - Bitwise Paradox. With the vector of death added to the code, it gets TLE on TC5 (taking $$$> 5$$$ s). While without the deadly vector, the submission takes 155 ms on TC5.

Here is a stand alone example with the slowdown (credit to kostia244). It runs 100 times slower with the vector of death.

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> TLE(40000, vector<int>(7));

int main() {
    string s;
    for(int i = 0; i < 17; i++) s += to_string(i) + " ";
    
    for (int j = 0; j < 60000; ++j) {
        istringstream ss(s);
        int x;
        while (ss >> x);
    }
}
What is causing this?
Other ways to trigger the slowdown bug
Other blogs on this topic
Tags tle, bug, slowdown, 64 bit, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English pajenegod 2024-03-02 19:00:00 0 (published)
en4 English pajenegod 2024-03-02 18:59:50 414 Tiny change: ' side.\n\nRemark: I'm no l' -> ' side.\n\n**Remark**: I'm no l'
en3 English pajenegod 2024-03-02 18:33:01 118 Tiny change: 'ntal issue. \n</spo' -> 'ntal issue on Codeforces' side. \n</spo'
en2 English pajenegod 2024-03-02 18:26:41 921 Tiny change: ' summary="Background">\nOver t' -> ' summary="Other blogs on this topic">\nOver t'
en1 English pajenegod 2024-03-02 17:57:47 3237 Initial revision (saved to drafts)