std::list iteration performance for under 1000 elements

[Florian Weimer]

On 04/25/2016 12:51 AM, Soul Studios wrote:
> Hi guys,
> I was wondering if any of you could explain this performance for me:
> www.plflib.org/colony.htm#benchmarks
>
> (full disclosure, this is my website and benchmarks - I just don't under
> the std::list results I'm getting at the moment)
>
> If you look at the iteration performance graphs, you'll see that
> std::list under gcc (and MSVC, from further testing) has /really good/
> forward-iteration performance for under 1000 elements (fewer elements
> for larger datatypes).
> Why is this. Everything I know about std::list's (non-contiguous memory
> allocation, cache effect) implementation tells me it should have
> terrible iteration performance. But for under 1000 elements it's often
> better than std::deque?

Such questions should probably go to the help list.

You should look at this with perf, preferably counting cache misses.  I 
suspect that for working sets which fit into the first-level cache of 
the CPU, the simpler iterators for std::list are faster than std::deque 
because the additional memory accesses in std::list are cheaper than the 
fairly complicated iterator implementation in std::deque.

Florian