Taming the performance Beast
summary
Benchmarks compare std::vector, deque, list, set and unordered_set on an Apple LLVM 2.6 GHz machine using ints and the standard allocator, measuring traversal, find, build and erase. Key findings: vector 1x baseline; list ≈8x slower to traverse and unordered_set similar; set ≈18x slower to traverse; for searches unordered_set wins for large N while a sorted vector (reserve + sort) competes up to ~200 elements; building a sorted vector is ~15× faster than node-based builds; removing arbitrary elements favors sorted vector up to hundreds, while removing front favors deque/list; always benchmark and consider allocators.
AI-written summary · about
chapters (28)
- 0:00Introduction
- 1:08Data Structures
- 8:53Disclaimer
- 10:50First benchmark
- 21:57Cache locality
- 24:13Finding an element
- 25:17Set
- 34:45Creating a suited collection
- 35:42What is a set
- 35:57Performance of a set
- 37:03Performance of lists
- 38:36Memory allocation
- 40:54Unnoted
- 41:20Removing elements
- 43:14Lists
- 43:36Sorted List
- 46:33Vectors
- 47:37Vector degrades
- 47:49Vector leads a pack
- 48:10Vector will explode
- 48:40Data structure
- 49:34Container
- 50:31More expensive
- 51:59Optimization
- 53:19Elements
- 53:51Queues
- 54:42Tree
- 58:59Questions
related talks
01h 01mHigh performance data structures in boost
01h 01mWant fast C++? Know your hardware!
01h 02mBack to Basics: Almost Always Vector
46mA little order
57mA Long Journey of Changing std::sort Implementation at Scale
01h 14mEfficiency with Algorithms, Performance with Data Structures
01h 00mIntroduction to Hardware Efficiency in Cpp
09mTrees in C++