I was solving the Planets Queries I problem in CSES (a standard binary lifting problem).

After getting a few TLE on one of the test cases, I finally got AC, but it took 1.00 seconds to pass that test case, which is way too close. On checking other submissions with exact same logic, and investigating a bit more, I changed vector<vector<int>> declaration in my code to static int array declaration, and my code, with everything being exact same, worked in 0.60 seconds.

Usually there shouldn't be such a drastic difference. While solving codeforces problem, I have observed that vectors and static array take the same time, and sometimes vectors are faster.

Can anyone explain the reason behind this? Thanks.

Submission using vector<vector<int>> : https://cses.fi/paste/7d2b7a0b66df52a2ea28b6/

Submission using static int array : https://cses.fi/paste/6d8b9ef1a192caa1ea28f1/

Update: In my implementation, I did vector<vector<int>> node(31, vector<int>>(n+1)) instead of vector<vector<int>> node(n+1, vector<int>>(31)), basically swap i and j, the same test case now passes in 0.55 seconds.

Basically in my original implementation, let's say I call dp[i][j], I was fixing j and iterating over i, which is horrible from cache locality POV. It doesn't help that vector allocates multiple heap blocks instead of one continous block. (There was a recent blog on this topic, refer that) Instead of this, fixing i and iterating over j, is much more cache friendly and makes a drastic difference in time.

It doesn't make a drastic difference in static arrays since unlike vector, they are not fragmented. (I am not exactly sure about the reason, will research a bit and then update)

For comparison, I did the same thing with my static array implementation, and now the static array implementation runs in 0.55 seconds as well. There isn't any time difference here.