bbtree++'s unsync map (bbtree::unsync::bbtree_map) was measured against
abseil's B-tree (absl::btree_map), std::map and std::unordered_map.
COMPARISON.md compares it with the Rust original; see Setup for details.
All times are nanoseconds per operation (per entry for iterate and the
many-map cells), and memory is bytes per entry: smaller is better.
std::unordered_map is a hash map, shown for reference only: it keeps no
key order, so it iterates in no particular order and has no range64 or
pop_first. The ordered maps are the real competitors.
- Integer keys: bbtree++ is typically 2-4× as fast as
std::mapand the fastest ordered map on lookups, sequential inserts, walks, upserts, removals and bulk builds. - String keys: with its best compact string bbtree++ is typically
1.5-3× as fast as
std::mapand abseil's B-tree, and slower mainly on building many 4-entry maps. - Memory: bbtree++ takes 0.4-0.7×
std::map's bytes per entry. - On glibc's allocator: instead of mimalloc, bbtree++ takes 2.2× as
long to walk a large map and 3.6× to bulk-build one, and still leads
abseil's B-tree and
std::mapthere on every cell measured; glibc's huge-page tunable or the opt-in pooled allocator takes most of that back. std::unordered_map, unordered and for reference only, stays faster on lookups and random inserts, as expected of a hash map.
u64 keys and values, nanoseconds per operation (iterate: per entry);
smaller is better. Bold marks the fastest ordered map of each row.
| cell | bbtree++ | absl btree | std::map | std::unordered_map |
|---|---|---|---|---|
| u64_u64_random_insert_1k | 23.5 | 17.1 | 21.4 | 10.3 |
| u64_u64_sequential_insert_1k | 6.44 | 15.4 | 27.8 | 10.5 |
| u64_u64_get_hit_1k | 9.54 | 24.0 | 23.0 | 7.78 |
| u64_u64_get_miss_1k | 8.95 | 22.1 | 23.8 | 10.4 |
| u64_u64_iterate_1k | 0.214 | 0.855 | 3.05 | 0.883 |
| u64_u64_range64_1k | 84.0 | 84.7 | 255 | — |
| u64_u64_random_remove_1k | 33.2 | 40.0 | 51.7 | 12.1 |
| u64_u64_entry_upsert_1k | 23.8 | 34.5 | 36.9 | 16.0 |
| u64_u64_pop_first_1k | 14.4 | 7.54 | 9.84 | — |
| u64_u64_bulk_build_1k | 2.05 | 4.96 | 30.7 | 10.6 |
| u64_u64_random_insert_1M | 79.5 | 92.9 | 198 | 58.2 |
| u64_u64_sequential_insert_1M | 9.41 | 34.6 | 80.1 | 57.0 |
| u64_u64_get_hit_1M | 74.2 | 108 | 210 | 25.9 |
| u64_u64_get_miss_1M | 49.2 | 94.8 | 193 | 26.7 |
| u64_u64_iterate_1M | 0.630 | 1.63 | 53.7 | 17.3 |
| u64_u64_range64_1M | 224 | 220 | 3190 | — |
| u64_u64_random_remove_1M | 85.6 | 94.4 | 284 | 83.4 |
| u64_u64_entry_upsert_1M | 57.4 | 83.9 | 201 | 44.0 |
| u64_u64_pop_first_1M | 17.4 | 8.39 | 43.9 | — |
| u64_u64_bulk_build_1M | 3.90 | 7.10 | 90.2 | 59.4 |
| u64_u64_random_insert_10M | 241 | 240 | 691 | 192 |
| u64_u64_get_hit_10M | 183 | 315 | 466 | 37.3 |
| u64_u64_get_miss_10M | 140 | 315 | 471 | 42.7 |
bbtree++'s iterate rows fold over the map (fold; PORTING.md,
iteration), as the Rust bench's do, where the other C++ maps have only
iterators to step. A range-for over bbtree++ takes about 0.7 ns an entry at
1k (PORTING.md, forward steps), so against abseil's 0.86 the walk by
iterators leads by 1.2×, not 4×.
Nanoseconds per operation (iterate and many maps: per entry); smaller is
better. bbtree++ runs each cell
with the compact string that is fastest on it, named in the row:
compact_string (16 bytes, a 4-byte size, up to 12 bytes in place, the
default), compact_string<2> (16 bytes, a 2-byte size, 14 in place: short
for basic_compact_string<std::uint16_t, 14>, which has no alias) or
compact_string_24 (24 bytes, 20 in place). String key types,
below, has every variant and std::string on every cell. The other maps have
std::string keys. bbtree++'s column comes from the string key types'
run, the other maps' from the main run (Setup). Bold marks the fastest
ordered map of each row.
| cell | bbtree++ | compact string | absl btree | std::map | std::unordered_map |
|---|---|---|---|---|---|
| str-16_u64_random_insert_1k | 36.7 | compact_string<2> |
104 | 108 | 21.2 |
| str-16_u64_sequential_insert_1k | 14.6 | compact_string |
50.1 | 116 | 24.7 |
| str-16_u64_get_hit_1k | 29.6 | compact_string_24 |
74.2 | 81.5 | 21.2 |
| str-16_u64_get_miss_1k | 19.9 | compact_string_24 |
77.9 | 81.0 | 21.1 |
| str-16_u64_iterate_1k | 0.422 | compact_string<2> |
1.28 | 3.52 | 2.25 |
| str-16_u64_range64_1k | 111 | compact_string |
167 | 328 | — |
| str-16_u64_random_remove_1k | 59.7 | compact_string |
113 | 112 | 25.8 |
| str-16_u64_entry_upsert_1k | 39.5 | compact_string<2> |
113 | 105 | 31.7 |
| str-16_u64_pop_first_1k | 15.7 | compact_string<2> |
30.9 | 16.1 | — |
| str-16_u64_bulk_build_1k | 8.28 | compact_string |
19.3 | 126 | 22.3 |
| str-json_struct32_build_many_1Mx4 | 58.3 | compact_string |
45.3 | 46.2 | 40.3 |
| str-json_struct32_get_many_1Mx4 | 72.6 | compact_string_24 |
72.3 | 99.3 | 56.7 |
| str-json_struct32_iterate_1Mx4 | 3.10 | compact_string |
3.45 | 4.78 | 4.34 |
| str-json_struct32_build_many_100kx32 | 49.2 | compact_string |
95.4 | 83.3 | 49.7 |
| str-json_struct32_get_many_100kx32 | 48.5 | compact_string<2> |
66.9 | 84.0 | 48.6 |
| str-json_struct32_iterate_100kx32 | 5.36 | compact_string |
17.0 | 24.8 | 21.1 |
| str-json_u64_random_insert_1M | 132 | compact_string |
355 | 454 | 143 |
| str-json_u64_get_hit_1M | 189 | compact_string_24 |
407 | 629 | 143 |
| str-json_u64_get_miss_1M | 132 | compact_string<2> |
422 | 655 | 110 |
The 1Mx4 and 100kx32 rows are the tiny suite's: a million maps of 4
entries and 100k maps of 32, keys and 32-byte values.
basic_compact_string<Size, ShortCapacity> in three forms against
std::string keys in bbtree++'s unsync map, nanoseconds per operation
(iterate and many maps: per entry); smaller is better. A compact string is 16 or 24 bytes and moves as
bytes (PORTING.md, compact_string); each cell turns its keys into
compact strings before it times anything. Bold marks the fastest of each
row.
| cell | std::string |
compact_string (16 B, 4-byte size, 12 in place) |
compact_string<2> (16 B, 2-byte size, 14 in place) |
compact_string_24 (24 B, 20 in place) |
|---|---|---|---|---|
| str-16_u64_random_insert_1k | 54.8 | 38.4 | 36.7 | 38.1 |
| str-16_u64_sequential_insert_1k | 28.6 | 14.6 | 15.6 | 17.8 |
| str-16_u64_get_hit_1k | 33.7 | 33.5 | 31.8 | 29.6 |
| str-16_u64_get_miss_1k | 19.7 | 20.5 | 22.1 | 19.9 |
| str-16_u64_iterate_1k | 0.452 | 0.437 | 0.422 | 0.492 |
| str-16_u64_range64_1k | 145 | 111 | 114 | 120 |
| str-16_u64_random_remove_1k | 106 | 59.7 | 60.5 | 60.3 |
| str-16_u64_entry_upsert_1k | 67.6 | 40.1 | 39.5 | 41.1 |
| str-16_u64_pop_first_1k | 73.6 | 16.6 | 15.7 | 18.7 |
| str-16_u64_bulk_build_1k | 15.6 | 8.28 | 9.11 | 8.90 |
| str-json_struct32_build_many_1Mx4 | 71.2 | 58.3 | 60.5 | 60.4 |
| str-json_struct32_get_many_1Mx4 | 73.4 | 75.9 | 73.8 | 72.6 |
| str-json_struct32_iterate_1Mx4 | 5.44 | 3.10 | 3.54 | 5.20 |
| str-json_struct32_build_many_100kx32 | 93.6 | 49.2 | 51.5 | 58.4 |
| str-json_struct32_get_many_100kx32 | 55.2 | 50.5 | 48.5 | 54.3 |
| str-json_struct32_iterate_100kx32 | 7.58 | 5.36 | 5.36 | 6.34 |
| str-json_u64_random_insert_1M | 214 | 132 | 136 | 158 |
| str-json_u64_get_hit_1M | 225 | 200 | 209 | 189 |
| str-json_u64_get_miss_1M | 149 | 141 | 132 | 145 |
- Writes: a string →
u64leaf entry shrinks from 49 bytes to 33 and shifts by onememmove: 1M JSON-key inserts 214 → 132 ns; removes, upserts, bulk builds and builds of 32-entry maps 0.45-0.6×;pop_first0.2×. - Iteration: 0.67×
std::string's for maps of 4, 0.75× for maps of 32. A first layout with 15 bytes in place decoded the size in eight instructions and walked 1.2-1.4× slower; PORTING.md, compact_string, has the measurement. - Lookups with
compact_stringare within 10% ofstd::string's or faster: with 12 bytes in place, 16% of JSON keys and moststr-16keys live on the heap, so a tie reads a line past the node, anddata()branches on the form. Not profiled further. - A 2-byte size buys 2 bytes in place: 90% of JSON keys against 84%. Misses in 1M maps came out from 9% faster to 11% slower across runs, and the rest within run-to-run noise: no gain outside noise. Strings are capped at 65,535 bytes.
- 24 bytes hold most
str-16keys (median 16) in place: hits 15% faster at 1k and 9% at 1M JSON keys. A string →u64leaf entry is 41 bytes, as the Rust crate'sString, against 33: inserts 5-25% slower, walks of many maps 15-47%,pop_first23%. compact_stringstays the 16-byte default: no cap, and nothing the 2-byte size wins is outside noise.
The heap bytes a map holds after its build, divided by its entries:
bbtree-bench-memory cpp, which counts the bytes mimalloc hands out
(mi_usable_size) and frees, one run each. The counts don't depend on
the machine's load. bbtree++'s string rows have the compact string that
suits the keys (see above): compact_string_24 (bbtree-unsync-compact-24,
24 bytes, up to 20 in place) for str-16, whose keys it mostly holds in
place, and the default compact_string (bbtree-unsync-compact, 16 bytes,
a 4-byte size, up to 12 in place) for JSON keys. The other maps have
std::string keys.
| cell | bbtree++ | absl btree | std::map | std::unordered_map | bbtree++ ÷ std::map |
|---|---|---|---|---|---|
| u64_u64_random_insert_1k | 27.7 | 20.8 | 48.0 | 42.3 | 0.58 |
| u64_u64_sequential_insert_1k | 24.6 | 18.1 | 48.0 | 42.3 | 0.51 |
| u64_u64_bulk_build_1k | 19.5 | 18.1 | 48.0 | 42.3 | 0.41 |
| u64_u64_random_insert_1M | 26.9 | 21.4 | 48.0 | 44.6 | 0.56 |
| u64_u64_sequential_insert_1M | 23.6 | 17.6 | 48.0 | 44.6 | 0.49 |
| u64_u64_bulk_build_1M | 18.5 | 17.6 | 48.0 | 44.6 | 0.38 |
| u64_u64_random_insert_10M | 26.9 | 21.4 | 48.0 | 42.1 | 0.56 |
| str-16_u64_random_insert_1k | 67.2 | 74.0 | 98.0 | 92.2 | 0.69 |
| str-16_u64_sequential_insert_1k | 68.3 | 62.6 | 98.0 | 92.2 | 0.70 |
| str-16_u64_bulk_build_1k | 48.8 | 62.6 | 98.0 | 92.2 | 0.50 |
| str-json_u64_random_insert_1M | 51.0 | 58.7 | 82.7 | 79.3 | 0.62 |
- std::map pays 48 bytes for a
u64→u64entry in every order: a node is 32 bytes of links and colour beside the entry's 16, mimalloc's 48-byte size class. Withstd::stringkeys a node is 72 bytes, in the 80-byte class, plus a heap buffer for each key past 15 bytes. - bbtree++'s
u64entry is its 16 bytes and a 2-byte inline key: 18.5 bytes in the full leaves of a bulk build, 23.6 after ascending inserts, 26.9 after random ones, which leave leaves about 70% full. abseil's nodes keep no inline keys and are 1-6 bytes per entry smaller. - String keys: a string →
u64leaf entry is 33 bytes withcompact_string, 41 withcompact_string_24and 49 withstd::string. Onstr-16the 24-byte form saves the heap buffers of the keys it holds in place: 67.2 against the 16-byte form's 71.6 after random inserts and 48.8 against 55.2 in a bulk build, but 68.3 against 65.5 after sequential inserts. On JSON keys it takes 61.5 against 51.0. The 2-byte-size variant is 1-2.4 bytes smaller thancompact_stringon every cell. Withstd::stringkeys bbtree++ takes 76.9 bytes per entry on 1M JSON keys (0.93× std::map) and 72-106 onstr-16at 1k. - The Rust crate takes the same bytes on every
u64cell; with its 24-byteStringkeys it takes 68.4 on 1M JSON keys.
Every other table here runs on mimalloc, as the Rust bench does.
bbtree-bench-system runs the same cells on the system's allocator, glibc
2.39 here, on 4 KiB pages. 1M u64 entries, nanoseconds per operation
(iterate and bulk build: per entry), one run each in one window; bold
marks the fastest ordered map on glibc.
| cell | bbtree++, mimalloc | bbtree++, glibc | bbtree++, glibc, pooled | absl btree, glibc | std::map, glibc |
|---|---|---|---|---|---|
| u64_u64_iterate_1M | 0.630 | 1.42 | 0.834 | 2.75 | 81.4 |
| u64_u64_bulk_build_1M | 3.90 | 13.9 | 6.18 | 14.6 | 178 |
| u64_u64_random_insert_1M | 79.5 | 102 | 82.0 | 123 | 343 |
| u64_u64_get_hit_1M | 74.2 | 76.0 | 69.0 | 146 | 250 |
| u64_u64_get_miss_1M | 49.2 | 51.2 | 50.0 | 150 | 245 |
| u64_u64_range64_1M | 224 | 324 | 249 | 327 | 4917 |
- Nodes aligned to a cache line (alignment) took the glibc column
from 2.25 to 1.42 ns a walked entry, 23.2 to 13.9 a bulk-built one, 137
to 102 a random insert and 424 to 324 a
range64, in this window: a 1 KiB page aligned to 1 KiB took 2 KiB of glibc's heap. Building 1M maps of 4 entries went from 301 to 178 ns an entry, and a 1M map's peak RSS from 85.5 to 61.8 MB. - What is left is the 4 KiB pages.
GLIBC_TUNABLES=glibc.malloc.hugetlb=1in the environment (glibc 2.35 and later) hasmallocask for huge pages, with no change to the program; measured before the alignment changed, it alone took random inserts from 138 to 102 ns and bulk builds from 24.9 to 10.8, and with the alignment the default allocator matched the pool on these six cells. The opt-inpooled_allocator(packed pages) gets huge pages without the variable. - On mimalloc the pool runs the same instructions as the global allocator; only bulk builds were slower with it in every pair of runs, the extra time spent where the pool's fresh chunks are faulted in. It stays opt-in for that, and for what it costs small maps.
String figures are bbtree++'s with its best compact string.
- bbtree++ is faster:
- lookups: 1.45-2.5× on u64, 2.5-3.9× on 16-byte strings, 2.15-3.2× on 1M JSON strings;
- string writes (inserts, upserts, removes, bulk builds,
pop_first): 1.9-2.85×; - sequential inserts: 2.4-3.7×;
- iterating: 3-4× at 1k, 2.6× at 1M, 3.2× for 100k maps of 32;
- u64 upserts and bulk builds: 1.45-2.4×; u64 removes 1.1-1.2×;
range64on strings: 1.5×.
- abseil is faster:
- random u64 inserts at 1k: 1.35×;
pop_firston u64: 1.9-2.1×;- building many 4-entry maps: 1.3×.
- About even:
range64on u64, random u64 inserts at 10M (bbtree++ 1.17× at 1M), and lookups in 4-entry maps.
The Rust original has the 1k insert gap too: COMPARISON.md has
bbtree (Rust) at 36.4 ns on 1k random u64 inserts against BTreeMap's
17.9, so that gap comes from the design, not bbtree++. Building many
small maps pays a full 1 KiB root page a map, where abseil sizes its root
leaf to its entries (FUTURE_WORK.md).
std::unordered_map, there for reference, beats every ordered map on
lookups, random inserts and upserts, as expected of a hash map; not on sequential inserts, which bbtree++ appends
to its last leaf, or on 1M random removes.
stx_btree is another C++20
form of bbtree (measured on 2026-11-08, before the review round's changes,
which the table below does not have), of its tree core and both maps (no file maps, store, sets,
entry API or bulk builds). Its unsync map ran in this bench's cells through
the bench's opt-in stx-unsync map (configure the bench with
-DBBTREE_BENCH_STX_DIR=<an stx_btree checkout>; bbtree-bench cpp --key u64,str-json,str-16 --map bbtree-unsync,stx-unsync), one run each, load
under 0.3, mimalloc, std::string keys for both. Nanoseconds per operation (iterate and many maps: per entry);
smaller is better; bold marks the faster. Rows differing by more than 10%:
| cell | bbtree++ | stx_btree |
|---|---|---|
| str-16_u64_entry_upsert_1k | 69.0 | 82.9 |
| str-16_u64_get_miss_1k | 22.3 | 25.5 |
| str-16_u64_iterate_1k | 0.418 | 1.17 |
| str-json_struct32_build_many_1Mx4 | 72.9 | 133 |
| str-json_struct32_get_many_100kx32 | 61.4 | 54.7 |
| str-json_struct32_iterate_100kx32 | 7.41 | 10.1 |
| str-json_struct32_iterate_1Mx4 | 5.31 | 13.3 |
| u64_u64_entry_upsert_1M | 69.9 | 83.0 |
| u64_u64_get_hit_1k | 15.3 | 13.1 |
| u64_u64_get_miss_1M | 66.4 | 57.2 |
| u64_u64_get_miss_1k | 14.1 | 12.1 |
| u64_u64_iterate_1M | 0.743 | 1.48 |
| u64_u64_iterate_1k | 0.218 | 1.07 |
| u64_u64_pop_first_1M | 16.8 | 20.1 |
| u64_u64_random_remove_1M | 91.1 | 101 |
| u64_u64_range64_1M | 257 | 231 |
The rest of the 39 cells are within 10%. The two ports' algorithms match nearly line for line; where stx_btree leads:
- Lookups (1.15-1.2×), at 1k and 1M misses: a standalone probe of both maps'
u64lookups gives 13.3 against 12.9 ns for hits and 12.8 against 13.0 for misses, 16 more instructions a hit in bbtree++; the bench's 1k cells show 15-25% across runs, the bench's build of the lookup (not its algorithm) the likelier cause. The adapter treats both alike: neither lookup is inlined into the bench's loop; each is a call to a function that holds half the cell's samples. A vectorized count of the leaf's last slots (55 two-byte slots leave 7 for a scalar tail) cut the count's instructions by a third and changed nothing: lookups wait on their loads, not on the count. range64at 1M (1.1×): within the cell's run-to-run range; bbtree++'s runs of it took 232-309 ns.
Sequential inserts were 1.25-1.3× slower until appends checked the shared
prefix out of line (PORTING.md, loops that store into a page); now
1.06-1.09×.
range64 was 1.25-1.8× slower before bbtree++'s steps were inlined whole
(PORTING.md, forward steps): stx_btree's scan loop keeps its position in
registers, bbtree++'s kept it in memory. Now they are even at 1k.
What bbtree++ took from the comparison (PORTING.md): packed pages
(pooled_allocator), install rules checked by a moved install,
short windows by overlapping loads, the shared scan's
check of the levels it keeps, and unwritten scratch arrays
in the shared map.
- Machine and build: as in COMPARISON.md (Ryzen 9 5950X, Clang 15,
--preset bench, mimalloc 3.3.2 with huge pages), abseil 20250814.2; measured on 2026-11-10, in the same windows as COMPARISON.md; the memory table is from 2026-11-08 and was checked unchanged, byte for byte. - Every map, every size:
bbtree-bench small tiny cpp --key u64,str-16,str-jsonon bbtree++, abseil's B-tree,std::mapandstd::unordered_map, one run each in a fresh process, 95 s, load under 0.3 at the start, no compaction stall in the kernel.cppis the C++ bench's own suite, which runsci's 1M and 10M workloads on every map (ciitself runs only bbtree++ andstd::map, as in the Rust bench). - String key types:
bbtree-bench cpp --key str-16,str-json --size 1k,1M,1Mx4,100kx32on bbtree++'s maps, one run each, 23 s. - Memory:
bbtree-bench-memory cpp, as its section says; the counts were the same byte for byte on a rerun after the second round.