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.

Hmmm, getting contiguous memory might be difficult with variable sizing. I would maybe look into arena allocation if it is that important. — mascoj
– mascoj, Commented Feb 14, 2017 at 15:39
One thing I can think of is to use a custom allocator that stores all the data together in memory. Doing so though limits how many Foo's you can have. — NathanOliver
– NathanOliver, Commented Feb 14, 2017 at 15:40
Isn't there a hint command for the vector such that it keeps size within hint boundaries or just forces its parent class to extend? — huseyin tugrul buyukisik
– huseyin tugrul buyukisik, Commented Feb 14, 2017 at 15:41
If you don't know the maximum number of instances of Foo then you will have to consider what happens when you need to grow your contiguous storage to accommodate new instances. Any naive implementation will invalid all references, iterators and pointers to all instances of Foo. An additional complication occurs when destroying instances of Foo out of order, leaving holes your in your storage (if this matters). Perhaps a proxy class can be used, storing the index of the Foo instance, but then you introduce a new level of indirection that might not be acceptable. — François Andrieux
– François Andrieux, Commented Feb 14, 2017 at 15:45

Sergey Kalinichenko · Accepted Answer · 2017-02-14 18:56:59Z

3

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.

edited Feb 14, 2017 at 18:56

answered Feb 14, 2017 at 16:00

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

B. D Over a year ago

I really liked this answer, but Francois Andrieux mentionned that if I ever add items in the std::vector<Foo*> beyond the capacity, every single iterator is invalidated

Sergey Kalinichenko Over a year ago

@Fezvez That's right! This is precisely the reason why your structure must remain static after the preprocessing step is over. I added more specifics about constructing the graph from FooNodes, which postpones taking iterators from the vector until you are sure that there are going to be no further modifications.

Collectives™ on Stack Overflow

C++ : vector of vector and cache locality

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related