Missing Optimizations on Node-based Containers

By Elliot Goodrich

For many functions which iterate over elements of a node-based container (such as std::list and std::map), the bottleneck is frequently due to accessing data from memory while chasing pointers. In bidirectional containers, these functions may be rewritten to reduce the number of data dependencies, thereby allowing modern processors to perform more operations in parallel.

In this session we will rewrite a few methods of std::list to demonstrate some of these techniques and benchmark them against current standard library implementations.