thanks for your answers!
benjamin bunny, i know that std::vector and standard arrays behave in a similar way. i wouldn't have these l2 problems if i didn't have a vector of vectors as swiftcoder pointed out. reading each thestruct::d in a sorted vector<thestruct> results in a very non-linear acccess pattern.
(thinking loudly here...)
so i have to restructure my data and maybe make one struct containing a,b,c and another struct containing d1,..dn and then have two vectors. one of the first struct and one of the second. if i sort the first vector i lose the correspondence of the two vectors. so i need something like a pointer in the first struct (a,b,c,pointer) into the second struct.
struct s1 { float a,b,c; pointer p; }struct s2 { std::vector<float> d; }vector<s1> vec1(N);vector<s2> vec2(N);
iterating over the first struct i always have a pointer indirection into the second struct when i want to access the d elements. this indirection is again not linear and cache unfriendly... another possibility would be to reorder the second vector based on the new sorted order of the first one...... this sucks.
having two vectors containing data of what is actually a single struct is also very unintuitive...
i could also precompute the dot product for each element of the second vector and then while iterating over the first sorted vector look up the result of the dot product in a table based on pointer p (which would be small enough to more likely fit into L2....) this way i would only access vec1 and vec2 in a linear predictable way... the only thing non-linear would be the lookup of the precomputed dot-product.. which should be L2 friendly.
is this the way to go ? i know my desciption here is quite confusing.. i tried my best.....
haven't already thought through how this will affect my implementation... but breaking down the structs intwo two smaller structs (thus avoiding std::vector<std::vector<> > seems desirable....)
does this sound reasonable (i'll go ahead and try implementing a benchmark... trying to judge by the numbers).
thanks again!
simon.