C++ : vector of vector and cache locality

Question

I am looking for a library/solution that will alleviate the rather important number of cache miss I am experiencing in my program

class Foo{
    std::vector<Foo*> myVec;

    // Rest of the class
};

int main(){
     // Some code
     std::vector<Foo*> myVecOfFoo;
}

So, the first thing I did was to create a std::vector<Foo> and every single Foo* points toward this vector. It helped a lot. My main issue is with std::vector<Foo*> myVec;. Each one of these vectors' internal array is located in a different part of the memory. In the same way that I created a single std::vector<Foo> so that all my Foo are contiguous in memory, I would like all my std::vector<Foo*> myVec; to be aligned in memory (Actually, the internal arrays). How?

Notes : An important point is that the size of myVec varies between instances of Foo. Otherwise I could trivially build a single std::vector<Foo*> and write getters/setters. Also, I have std::shared_ptr<Foo> instead of Foo* because I am not a savage, but it makes the understanding of the example easier. Finally, I guarantee that the ownership forms a DAG, so I don't have cycles in my shared pointers.

Answer 1

Replace std::vector<Foo*> with a pair of

std::vector<Foo*>::const_iterator begin;
std::vector<Foo*>::const_iterator end;

Make a single std::vector<Foo*>, and place all pointers into it. Then parcel out contiguous blocks of pointers to individual instances of Foo by setting their begin and end iterators.

This may require a preprocessing step, when you build your graph with std::vector<Foo*> from instances of a "node" class, e.g.

class FooNode {
    Foo *myFoo;
    std::vector<Foo*> myVec;
};

Once your nodes are connected, walk through the graph, and collect myVecs into one big vector. Once you are done with all individual vectors, walk the preliminary graph again, and set begin and end positions into myFoos. You can compute positions by adding the size of FooNode's vector to the current position. This will work, as long as your walks through the graph are identical.