1

I recently ran across a comment which is as follows:

Multi-dimensional arrays take a lot of time for array access. To increase their caching and access speed, it is advised to keep the indices from smaller to larger i.e. declaring rmq array like rmq[11][11][1002][1002] rather than rmq[1002][1002][11][11].

I tried a code to test the same. In Code 1:

int pre_compute[18][100001];    //global variable

int main(){
    /*some precomputations on pre_compute array 
    of the order of size of the array*/

    /*Run 10^8 queries on pre_compute array,
    O(1) per query.*/
}

Code 2:

int pre_compute[100001][18];    //global variable

int main(){
    /*exact same precomputations on pre_compute array as done in Code 1 
    of the order of size of the array*/

    /*Run 10^8 queries on pre_compute array,
    O(1) per query.*/
}

Both the codes are identical except for the distribution of the array. Still there was a big execution time difference between the two codes. The first code took an average of 0.40 secs on my PC, whereas the other code took an average of 1.42 secs.

What can be a possible reason for such a big execution time difference between two implementations of an array?

Sahil Arora
  • 875
  • 2
  • 8
  • 27
  • 5
    this may help: http://stackoverflow.com/questions/16699247/what-is-cache-friendly-code , http://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra – kmdreko Jun 21 '16 at 16:18
  • 1
    @vu1p3n0x The latter of those is pretty-much *exactly* the problem and the description of what is happening in the inconveniently omitted code that actually uses the declared arrays. Nice job. – WhozCraig Jun 21 '16 at 16:26
  • Please ask such providing a [MCVE] next time, or post one here if you disagree the duplicate answers your question. – πάντα ῥεῖ Jun 21 '16 at 16:32
  • In addition, any performance related question should be accompanied with the command-line used to build the test, more explicitly, what optimizations were used to build the program. Too many times these types of questions come up, and it is discovered that the poster is testing an unoptimized and / or "debug" build, making the results meaningless. – PaulMcKenzie Jun 21 '16 at 16:40

1 Answers1

2

This is exactly the difference between row-major and column-major ordered matrices.

The difference is explained on Wikipedia:

In row-major order, consecutive elements of the rows of the array are contiguous in memory; in column-major order, consecutive elements of the columns are contiguous.

C and C++ are row-major, so they can leverage caching of rows because of spacial locality. This explains the dramatic increase in speedup.

Technically, if you want to save a lot of time, it might be better to represent your multidimensional arrays as 1D arrays. :)

erip
  • 16,374
  • 11
  • 66
  • 121
  • 1
    As Fortran is Column Major order, porting Fortran->C without dealing with the issue can cause performance issues. – EvilTeach Jun 21 '16 at 16:32
  • @EvilTeach Yep - absolute nightmare. – erip Jun 21 '16 at 16:32
  • 1
    Representing the multidimensional array as a 1d array won't really change anything or save any time if your access patterns are row major. Performance improvement would come if you changed your access pattern from column major to row-major OR you use column-major access and go with the 1d representation with indexing computations to effect column-major storage order. – Avi Berger Jun 21 '16 at 16:39