Stay up-to-date with everything C++!
Content directly fetched from the subreddit just for you.
Join our group for discussions : @programminginc
Powered by : @r_channels
Post #25221
21
Neoclassical C++: segmented iterators revisited (1)
Hi,
I written a blog post revisiting Matt Austern's great Segmented Iterators and Hierarchical Algorithms paper (2000) and benchmarking an experimental implementation I've been playing with in Boost.Container.
Quick idea:
I benchmarked several "simple" STL algorithms on a Boost deque, and the speedup is way bigger than Austern's original estimation when modern auto-vectorizers enter them game.
Article link: https://boostedcpp.net/2026/05/18/neoclassical-c-segmented-iterators-revisited-1/
Happy to receive feedback!
https://redd.it/1th1e21
@r_cpp
Hi,
I written a blog post revisiting Matt Austern's great Segmented Iterators and Hierarchical Algorithms paper (2000) and benchmarking an experimental implementation I've been playing with in Boost.Container.
Quick idea:
std::deque and friends are internally segmented (blocks of contiguous memory), but STL-like iterators hide that, so every ++it has to check for a block boundary. Austern's proposal splits the iterator into a segment_iterator (walks blocks) + local_iterator (inside one block), so algorithms can run a tight loop per block and only do bookkeeping at the boundaries.I benchmarked several "simple" STL algorithms on a Boost deque, and the speedup is way bigger than Austern's original estimation when modern auto-vectorizers enter them game.
Article link: https://boostedcpp.net/2026/05/18/neoclassical-c-segmented-iterators-revisited-1/
Happy to receive feedback!
https://redd.it/1th1e21
@r_cpp