Skip to content

Latest commit

 

History

History
346 lines (308 loc) · 19.8 KB

CPP_MAPS.md

File metadata and controls

346 lines (308 loc) · 19.8 KB

bbtree++ vs. C++ maps

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.

Summary

  • Integer keys: bbtree++ is typically 2-4× as fast as std::map and 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::map and 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::map there 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.

Integer keys

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×.

String keys

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.

String key types

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 → u64 leaf entry shrinks from 49 bytes to 33 and shifts by one memmove: 1M JSON-key inserts 214 → 132 ns; removes, upserts, bulk builds and builds of 32-entry maps 0.45-0.6×; pop_first 0.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_string are within 10% of std::string's or faster: with 12 bytes in place, 16% of JSON keys and most str-16 keys live on the heap, so a tie reads a line past the node, and data() 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-16 keys (median 16) in place: hits 15% faster at 1k and 9% at 1M JSON keys. A string → u64 leaf entry is 41 bytes, as the Rust crate's String, against 33: inserts 5-25% slower, walks of many maps 15-47%, pop_first 23%.
  • compact_string stays the 16-byte default: no cap, and nothing the 2-byte size wins is outside noise.

Memory, bytes per entry

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 → u64 entry in every order: a node is 32 bytes of links and colour beside the entry's 16, mimalloc's 48-byte size class. With std::string keys a node is 72 bytes, in the 80-byte class, plus a heap buffer for each key past 15 bytes.
  • bbtree++'s u64 entry 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 → u64 leaf entry is 33 bytes with compact_string, 41 with compact_string_24 and 49 with std::string. On str-16 the 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 than compact_string on every cell. With std::string keys bbtree++ takes 76.9 bytes per entry on 1M JSON keys (0.93× std::map) and 72-106 on str-16 at 1k.
  • The Rust crate takes the same bytes on every u64 cell; with its 24-byte String keys it takes 68.4 on 1M JSON keys.

On glibc's allocator

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=1 in the environment (glibc 2.35 and later) has malloc ask 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-in pooled_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.

Against abseil's B-tree

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×;
    • range64 on strings: 1.5×.
  • abseil is faster:
    • random u64 inserts at 1k: 1.35×;
    • pop_first on u64: 1.9-2.1×;
    • building many 4-entry maps: 1.3×.
  • About even: range64 on 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.

Against stx_btree

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' u64 lookups 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.
  • range64 at 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.

Setup

  • 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-json on bbtree++, abseil's B-tree, std::map and std::unordered_map, one run each in a fresh process, 95 s, load under 0.3 at the start, no compaction stall in the kernel. cpp is the C++ bench's own suite, which runs ci's 1M and 10M workloads on every map (ci itself runs only bbtree++ and std::map, as in the Rust bench).
  • String key types: bbtree-bench cpp --key str-16,str-json --size 1k,1M,1Mx4,100kx32 on 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.