Generic programming for structure-aware algorithms
summary
Benchmark shows a deque-of-chunks layout runs four times slower than a flat vector on the test machine; GCC auto-vectorization fails on the flattening-iterator pattern. The work builds a hierarchical iterator and chunking iterator, exposes segment begin/end and major/minor iterators, and wraps algorithms (accumulate/reduce group ~10 algos) with a meta-algorithm so the implementation uses two-loop segment-aware code. The hierarchical versions remove most overhead for large segments and match flat-performance; observer and timeout hooks also work.
AI-written summary · about
chapters (15)
- 0:00Generic structure-aware algorithms
- 1:29Nested data structures performance
- 3:14Segmented data structures
- 6:25Flat iterators for nested sequences
- 7:51STL flattening nested structures
- 14:16Flattening iterator design
- 18:52Flattening iterators performance
- 21:01Structure-aware iterators
- 24:16Meta algorithm for hierarchical reduction
- 27:29Extending meta algorithms
- 36:32Find and copy with hierarchical algorithms
- 45:52Artificial segmentation of sequences
- 51:51Instrumenting algorithms with observers
- 55:46Chunking iterators for parallelism
- 1:00:17Q&A
related talks
01h 00mSTL Features And Implementation Techniques
01h 01mHigh performance data structures in boost
42mFaster programs with your compilers autovectorization feature
48m[a bit noisy] Optimizing Generic Algorithms
50mDesigning and Implementing a new Allocator model
01h 00mModern C++: C++ Patterns to Make Embedded Programming More Productive
59mBetter Algorithm Intuition
01h 07mWriting Data Parallel Algorithms on GPUs