Differences on local/global vector/c style array

[kimtaehong]

Hi.

While I was solving some problems, which I couldn't pass for the time limitations, I've found out that only difference btw others and mine was that

Mine used

vector<vector<int>>board(4001, vector<int>(4001))

in local function solution()

while others used

int board[4001][4001]

set in global.

I tried out using c-style int array board[4001][4001] set locally in

void solution() {
int board[4001][4001]
}

but this failed to initialize the int array,

I tried using vector of sized around 16 million at global, but this seems a bit slower than using c style array itself as global.

While I was searching for how their performance differs when accessing, I couldn't get an answer about it.

Most of them say that access time for these are negligible, or global/local variable access time vary by the computer's architecture.

Would anyone know why this happens?

Or recommend me of reading I could follow?

It would be of great help.

Thank you.

[jonnin]

a 2-d array is one block of memory, so it will have fewer cache misses.

a 2-d vector is like a ** allocated block, and each new statement in the allocation is putting that chunk apart from the others (potentially).

that isn't much on a small program, but it could be enough to slow you down.

also, if its in a local function you created and destroyed all that memory every call (the vectors are being constructed and destructed over and over). maybe make the local vectors static and re-time your code? That is probably the bigger hit than the cache issues, given the small size of the problem. Making local vectors inside worker functions that are called in a tight loop is a bad pattern, better to pass the vector in or make static or something else. If the vector is the result, be sure to return a pointer or reference to the static (or again, pass it in, by reference of course!), do not copy it every iteration to return it.

access is faster on the 2-d array for the same reason as the cache problem. to compute an offset in a 2-d array, its one hop, memory+offset. to compute it in a 2-d pointer array or vectors, its more: memory+offset of first dimension, and memory+offset of second dimension.

you can also just make a 1-d vector and access it manually as if 2-d.
vector <int> board(4001*4001);
board[anyrow*4001+anycol]; Its a tiny bit faster because it removes the cache problems and access is simpler as well.

conclusion: multi dimensional stuff is often less efficient than single dimensional stuff, sometimes significantly :)

Do not feel to bad about this. Your code is more modern, better written: globals are poor style, and c-arrays are out of favor as well though I personally still use them when I do not need anything that vector brings to the table. You stumbled into some gotchas but your overall code and style in the long run is going to be better than your peers' code if they are in the habit of using globals etc.