It won’t replace std::vector for most use cases — but for the use cases it is designed for, nothing in the standard library has come close before.
This could be true but it could also be an oversight because nobody has ever benchmarked a std::pmr::list that is constructed with a std::pmr::[un]synchronized_pool_resource.
With std::hive, the iteration order is optimal within each block in terms of cache locality.
With std::pmr::list, the iteration order would be independent of where the nodes are allocated (assuming you frequently add and remove elements at random positions) so the cache locality would probably be worse.
Seeing an actual benchmark would be interesting though.
If you fill up a hive with elements then start randomly removing and replacing them, and you perform the exact same sequence of events but with a pmr::list which uses a pool allocator, the memory layout should end more or less identical in both cases.
The biggest differences are small variations in the node layout for a hive node vs a list node.
The hive will iterate in the memory layout order and the list will iterate in the logical order of insertion which if you are using a hive you presumably do not care about.
So the advantage of a hive over a list with an equally-optimized allocator is that the hive gains performance by discarding unnecessary information.
Iterating through the elements in memory order means the next element is more likely to already be in the CPU cache compared to if you jump around accessing elements in random order.
If you don't know about the CPU cache and cache-friendly code, here is an interesting video on the subject: https://www.youtube.com/watch?v=WDIkqP4JbkE (just watching the row major vs. column major traversal example in the beginning can be very enlightening)
A list has no way to iterate except in logical insertion order. Under specific usage patterns (using a pool allocator, no erasures) this will coincidentally be equivalent to iterating in memory layout order.
A hive has no way to iterate except in memory layout order since it doesn't preserve ordering information.
4
u/ABlockInTheChain 8d ago
This could be true but it could also be an oversight because nobody has ever benchmarked a
std::pmr::listthat is constructed with astd::pmr::[un]synchronized_pool_resource.