“Colonies, performance and why you should care"
summary
An unordered container called plf::colony provides pointer-stable elements that are unaffected by inserts or erases, reuses freed slots via a stack and frees empty blocks to the OS, trading contiguous layout for chained blocks. It implements a jump-counting skipfield to make iterator ++ O(1) without branch-heavy boolean scans. Benchmarks show colony wins for medium–high modification workloads (better than vector/deque), saving memory dramatically—reported ~34×, ~172× and ~340× less at 1%, 5% and 10% per-frame churn—and a companion plf::stack boosts push/pop speed.
AI-written summary · about
chapters (15)
- 0:00Introduction and background
- 2:23Game development and vectors
- 3:49Limitations of std::vector
- 5:08Analyzing game data requirements
- 7:44Memory and performance constraints
- 10:08Common vector workarounds
- 12:12Introducing the Colony container
- 14:45Colony implementation details
- 17:55Jump counting skip field
- 22:19Algorithm comparisons
- 27:06Benchmarking raw performance
- 32:11Simulated game scenarios
- 38:13Colony use cases summary
- 39:29The future of software performance
- 43:52Q&A
related talks
13mMissing Optimizations on Node-based Containers
58mRefresher on Containers, Algorithms and Performance
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 31mNew (& Old) C++ Standard Library Containers - How to Choose the Right Container in C++26 and Beyond
01h 04mBetter Code: Data Structures
01h 01mGetting Allocators out of Our Way
01h 26mFrictionless Allocators
01h 00mOLD VERSION: The Fine Details Behind C++ Containers And Algorithms