Refresher on Containers, Algorithms and Performance in C++ - Vladimir Vishnevskii - CppCon 2022

Improve C++ performance by mastering containers, algorithms, and memory indirection, and learn how to optimize for multicore parallelism, cache efficiency, and memory layout.

Key takeaways

The complexity of containers can be improved by minimizing memory indirection, especially for std::list and std::vector.
Multicore parallelism is beneficial for CPU-intensive code, but introduces overhead.
Cache efficiency is important, especially for platforms with caches like x86-64, but not all platforms have caches.
std::list and std::vector have different memory layouts, with std::vector having a continuous storage that is cache-friendly.
Flat multi-set and flat map containers are available for optimized memory usage.
Algorithm selection depends on the specific use case, with unordered hash-based containers being suitable for insertion, deletion, and search operations.
Minimizing memory indirection by flattening data structures can improve performance.
std::list is slow for insertion and deletion due to shifting of items.
std::vector remains a good choice for large datasets.
Cache locality is important, and the CPU spends most of its time waiting for memory access.
Algorithm execution time can be measured using time complexity, and different algorithms may have different complexities.
Pre-allocating memory can improve performance by reducing the need for reallocation.
The execution strategy of algorithms can be specified and can affect performance.
Using the proper container and algorithm for the specific problem can significantly improve performance.
Measuring and profiling code is important to optimize performance.
Third-party containers and libraries, such as Abseil, can provide better performance than standard containers.
Parallel execution can improve performance, but may introduce overhead and should be tested.

Refresher on Containers, Algorithms and Performance in C++ - Vladimir Vishnevskii - CppCon 2022

More talks