std::list iteration performance for under 1000 elements

Soul Studios
Sun Apr 24 22:52:00 GMT 2016

Hi guys,
I was wondering if any of you could explain this performance for me:

(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?

Benchmarking is done with templates, so there's no different code 
between std::deque and std::list (with the exception of std::list using 
push_front rather than push_back, for these tests) - and subsequent 
changes to the benchmark code have made no difference to the restuls.

Anyway, if anyone here is a GCC developer and has an understanding of 
why this happens, I'd be appreciative.


More information about the Gcc mailing list