Cache optimization with std::vector

[jesperd]

Hi,

This is a general question of how to optimize an array so that you get a better cache hit.

Lets say you have two arrays, for instance defined from the std::vector class.
Then you initialize them this way:

v1 : [1,2,3,4,5,6,7,8,9,10,11,0]

v2 : [9,11,3,10,7,0,5,1,2,4,6,8]

Then you run this code:

int index = 0;
do{
  index = v1[index];
}while(index != 0)

int index = 0;
do{
  index = v2[index];
}while(index != 0)

The question is, would the first while-loop with v1 perform best in time or are there no difference between v1 and v2?

I have tried to benchmarked v1 and v2 with a length of 100.000, but it seems there are no difference. As my point of view v1 should give the lowest computation time because it should give a better cache hit than v2, but I'm not sure it is right.

I am asking because I have an unsorted array like v2. I'm wonder if it could be a good idea to sort the array according to the indexes.

I know this is a philosophical question, but maybe you know where to find information about cache performance related to this problem,

[PanGalactic]

See this 9-part article, What every programmer should know about memory, on LWN: http://lwn.net/Articles/250967/

It is very in-depth.

[jesperd]

Thanks PanGalactic.

It was what I just needed :-)

Thank you for your help.

[paeez]

hi dear all

I am a new member , I did not know how can I ask my question ! for this reason send reply to your . my question is about store one char array with 2 for loop to one char 2D array . I write the code and did not give any error but I could not see the result .

would you please answer my question ?

Regards