std::sort on container of pointers

Question

I want to explore the performance differences for multiple dereferencing of data inside a vector of new-ly allocated structs (or classes).

struct Foo
{
    int val;
    // some variables
}

std::vector<Foo*> vectorOfFoo;

// Foo objects are new-ed and pushed in vectorOfFoo
for (int i=0; i<N; i++)
{
   Foo *f = new Foo;
   vectorOfFoo.push_back(f);
}

In the parts of the code where I iterate over vector I would like to enhance locality of reference through the many iterator derefencing, for example I have very often to perform a double nested loop

for (vector<Foo*>::iterator iter1 = vectorOfFoo.begin(); iter!=vectorOfFoo.end(); ++iter1)
{
   int somevalue  = (*iter)->value;

}

Obviously if the pointers inside the vectorOfFoo are very far, I think locality of reference is somewhat lost.

What about the performance if before the loop I sort the vector before iterating on it? Should I have better performance in repeated dereferencings?

Am I ensured that consecutive ´new´ allocates pointer which are close in the memory layout?

Answer 1

If you want to improve the locality of reference for your objects then you should look into Pool Allocation.

But that's pointless without profiling.

Answer 2

It depends on many factors.

First, it depends on how your objects that are being pointed to from the vector were allocated. If they were allocated on different pages then you cannot help it but fix the allocation part and/or try to use software prefetching.

You can generally check what virtual addresses malloc gives out, but as a part of the larger program the result of separate allocations is not deterministic. So if you want to control the allocation, you have to do it smarter.

In case of NUMA system, you have to make sure that the memory you are accessing is allocated from the physical memory of the node on which your process is running. Otherwise, no matter what you do, the memory will be coming from the other node and you cannot do much in that case except transfer you program back to its "home" node.

You have to check the stride that is needed in order to jump from one object to another. Pre-fetcher can recognize the stride within 512 byte window. If the stride is greater, you are talking about a random memory access from the pre-fetcher point of view. Then it will shut off not to evict your data from the cache, and the best you can do there is to try and use software prefetching. Which may or may not help (always test it).

So if sorting the vector of pointers makes the objects pointed by them continuously placed one after another with a relatively small stride - then yes, you will improve the memory access speed by making it more friendly for the prefetch hardware.

You also have to make sure that sorting that vector doesn't result in a worse gain/lose ratio.

On a side note, depending on how you use each element, you may want to allocate them all at once and/or split those objects into different smaller structures and iterate over smaller data chunks.

At any rate, you absolutely must measure the performance of the whole application before and after your changes. These sort of optimizations is a tricky business and things can get worse even though in theory the performance should have been improved. There are many tools that can be used to help you profile the memory access. For example, cachegrind. Intel's VTune does the same. And many other tools. So don't guess, experiment and verify the results.

Answer 3

Just to answer your last question: no, there is no guarantee whatsoever where new allocates memory. The allocations can be distributed throughout the memory. Depending on the current fragmentation of the memory you may be lucky that they are sometimes close to each other but no guarantee is - or, actually, can be - given.