v5.1.0

Three changes since 5.0.1: index_bytes() is new, segmented_map tears itself down in the opposite order, and segmented_map works with fancy pointers.

index_bytes()

In 4.x a bucket was one slot, so bucket_count() * sizeof(bucket_type) was exactly the memory of the index. In 5.0 a bucket is a group of sixteen slots, and bucket_type is only the 24 bytes a probe compares. The sixteen value indices sit in the same block without being part of the type. So the product now reads 24 bytes per slot where the index really uses 5.5, measured with a counting allocator on map<uint64_t, uint64_t> at a million entries. index_bytes() gives the real number for both bucket types. doc/upgrading-to-5.md has the details and the formula for 5.0.0 and 5.0.1.

segmented_map destroys its values last first

segmented_map destroyed its values first to last and freed its blocks first to last. Now it does both last to first, the same order a built-in array uses. clear() and a shrinking resize() go the same way. I found this through Bonxai, whose root map measured segmented_map 1.8x slower than std::unordered_map for a 46k-root voxel grid. All of that difference came from builds that follow a teardown in the same process. With glibc, a map whose values own heap memory handed that memory back to the kernel while it was destroyed front to back, and the next build had to fault every page of it in again.

Measured on a Ryzen 9 7950X, clang 22 and gcc 16, glibc 2.43. segmented_map built from empty, destroyed and built again in one process, one binary per header, median of three passes. Times in ms, 5.0.1 → 5.1.0:

	build after a teardown	teardown
std::string keys, 1M, clang	79.7 → 43.7	20.5 → 13.1
value owning a 96 byte allocation, 1M, clang	73.9 → 28.2	21.5 → 12.2
value owning a 96 byte allocation, 200k, gcc	11.7 → 3.6	3.5 → 2.2
uint64_t → uint64_t, 1M, clang	24.7 → 24.4	1.43 → 1.35

So it is 1.8x to 2.3x for string keys and 2.6x to 3.2x when the values own an allocation. Integer maps don't move. In Bonxai's case the build went from 342 ms to 230 ms, where std::unordered_map takes 248. The harness is scripts/ab/teardown_order.sh.

Unfortunately this has a price. After a segmented_map is destroyed, its memory now stays resident until the process allocates again or calls malloc_trim(0): 114 MB for a million string keys, where 5.0.1 gave all of it back immediately. std::unordered_map behaves the same way. Also, if your value type has a destructor with side effects, you will see those effects in reverse insertion order now. map and set store their values in a std::vector and are unchanged. I have only measured glibc. jemalloc, tcmalloc and mimalloc have different trim policies, so your numbers may differ.

segmented_map with fancy pointers

With an allocator whose pointer is a class, e.g. boost::interprocess::offset_ptr, the const paths of segmented_map did not compile: begin() const, cbegin(), end() const and the conversion from a mutable iterator. Thanks to @bigerl for the fix in #298.

Same hash values and same iteration order as 5.0.1. The inline namespace follows the version, so this is v5_1_0.