libart++

Count cachelines, not comparisons

A lookup's real cost is its cold cacheline loads — every other instruction hides behind them. Big-O in comparisons flatters comparison trees; measured in cachelines, a B-tree lookup is O(log n) dependent misses. libart++ is engineered so each level of descent costs at most ONE cold line — and the level count is bounded by your key's bytes, not your data's size.

Measured, not promised

One templated benchmark engine drives every contestant through identical code — same keys, same op sequence, same checksums — so there are no per-library benchmark deviations. Upstream libart is vendored; absl::btree_map and std::map use heterogeneous lookup. Reproduce with -DARTPP_BENCHMARKS=ON.

Point lookups (the operation maps exist for)

Every lookup costs the cachelines its descent touches — and artpp is built so each level of descent touches at most one cold line: the node kind is in the tagged pointer (no header read to route), a compressed run lives in that line instead of a separate node, and a small leaf can ride in the routing node's own line rather than a line of its own. Against libart that's 2.0× on sequential integers, 1.37× uniform, 1.32× clustered, and 1.18× on dictionary words; against the comparison-based maps, 1.9–4.3× over absl::btree_map and 2.1–7.6× over std::map.

lower_bound (the ordered query a hash map can't answer — and libart has no API for)

Positioning to the next-greater key (predecessor/successor, range starts) is what an ordered map is for — and it's the line where the field thins out: a hash map can't do it at all, and upstream libart exposes no lower_bound either (shown as unsupported above). Among the containers that can, artpp leads: 1.5× faster than absl::btree_map on clustered strings, 1.24× on uniform and 1.6× on sequential integers, and on par on dictionary words — versus std::map, up to 2.1×. The descent is the same shape as a point lookup, so the same one-line-per-level economics apply.

Inserts (build time is allocator-bound — so compare the allocator)

A bulk build is dominated by where the nodes come from, so the honest insert comparison holds the tree fixed and swaps the allocator. The flagship line_pool — a contiguous reservation handed out by a bump frontier with exact-size free lists, no per-node malloc — builds the same tree 1.1–1.4× faster than std::allocator, the allocator's contribution cleanly isolated (both rows are on every insert chart). Held to the same malloc class, artpp and libart build at similar rates: artpp leads on sequential and runs even on clustered, and libart's flatter node growth leads on the deeply-shared dictionary, where a radix does the most splitting — the up-front structuring that buys the lookup, scan, and ordered-iteration wins above. Net with the pool: builds beat absl::btree_map (1.7–2.8×) and std::map (2.4–7.2×) on every workload.

Ordered scans (bucket mode keeps pace with B-trees)

Bucket mode scans the packed (suffix, value) pages contiguously: 2.2× faster than libart on dictionary keys (2.6 vs 5.6 ns/element), and on clustered strings it edges absl::btree_map itself (6.5 vs 8.9 ns/element). For the absolute crown on dense integer keys, a B-tree's fully contiguous leaves lead — so pick bucket mode when a workload both looks up and scans, and the default radix when it's lookup-dominated.

Methodology: Apple M5, clang -O3, quiet machine, one process. The artpp::map rows run the library's flagship allocator — line_pool over an anonymous mapping (4-byte u32-index branch handles, bump placement laying children near parents); the std::allocator row shows zero-setup behavior. Workloads: 236k dictionary words, 885k clustered strings, 1M uniform & sequential uint64 (typed APIs; libart receives the identical big-endian bytes). Point-lookup latency is the fastest of five repetitions per contestant. Full data: results.csv · engine: bench/engine.hpp. A separate machine-calibrated ratio gate guards artpp-vs-libart regressions in CI fashion.

Built for the keys real systems use

Real keys are rarely a bare integer — they're strings, 32-byte hashes, UUIDs, composite tuples: bytes that don't fit in a CPU register. A radix descent reads only the few bytes that distinguish a key, touching a bounded number of cache lines however large the map or the key. Here are random 32-byte keys scaled from one million to one hundred million — artpp, upstream libart, unodb (the canonical C++ ART), the comparison trees, and a hash map.

Grow the map 100× and artpp's lookup barely moves — ~52 → 90 ns on these std::string keys — while absl::btree_map climbs 505 → 1,471 and std::map 807 → 1,966: each level is a full-key compare over cold cache lines, O(log n) of them. The radix reads only the bytes that distinguish a key, so it scales best of the field (1.75× across the growth vs 2.4–2.9× for the trees) and at 100M is 16× over absl::btree_map and 22× over std::map.

Variable-length (string) keys — fastest, ordered or not

Variable-length keys (names, paths, the dictionary words above, or the 32-byte strings here) are the radix's home turf: a hash must consume the whole key, so at 100M artpp (90 ns) edges even std::unordered_map (100 ns) while staying fully ordered — lower_bound in 159 ns vs 1,489 (btree) and 2,169 (std::map), where the hash map and libart answer no ordered query at all. unodb — the canonical C++ ART (art_map derives from it) — handles these via key_view but trails ~4× (352 ns; its iterator reconstructs the key).

Fixed-size inline keys — the fastest ordered map

Store the same 32 bytes as a fixed std::array (a hash, UUID, or POD id — inline, no per-key allocation) and it's honest in the other direction: hashing a cheap inline key is hard to beat, so std::unordered_map wins pure point lookups (55 ns vs artpp 67) — but it answers nothing else. artpp is the fastest ordered map by a wide margin: hit 67 ns vs btree 1,057 and std::map 1,422 (16–21×), lower_bound 165 ns vs 947 / 1,078, and at 100M it even passes the B-tree on ordered scan. art_map would be faster still on a key this size — but its key must be ≤ 16 bytes, so a 32-byte key doesn't compile.

The C++ ART field, by capability

Bottom line, stated straight: a hash map is faster for pure point lookups on fixed-size keys, and a register-specialized ART (art_map) faster still on ≤16-byte integers — but the moment keys are variable-length, or you need lower_bound / ordered scans / ranges, artpp is the fastest option, and the only one that's header-only, dependency-free, portable, and keys anything.

Methodology: Apple M5 (128 GB), clang -O3, idle machine, one process; each container built and measured in isolation. Random insertion; point ops are the fastest of repeated passes. The two regimes differ only in key storage — std::map/btree/unordered_map hold std::string (heap) vs std::array<unsigned char,32> (inline, unsigned ⇒ same byte order); artpp/libart/unodb key on the identical bytes either way. artpp uses line_pool to ~50M 32-byte keys then std::allocator (no 4 GB terminal cap) to 100M — lookups within noise between them. unodb's scan reconstructs the key (not compared on scan). Source: bench_buffer.cpp + bench_buffer_array.cpp / bench_buffer_unodb.cpp.

The "++" is earned: vs the original libart

libart++ is measured head-to-head against armon/libart — the canonical C ART — in every chart on this page, and holds a dedicated, thermally-fair ratio gate against it (contestants interleaved per rep, baseline-tracked). The structural edge: libart loads each node's header before it can route; artpp routes from the tagged pointer itself.

Engineered like a standard library component

The goal is a container you could submit for review: exact contracts, exhaustive tests, honest documentation.

Thirty seconds of code

artpp::map<int64_t, std::string> m;
m.insert(-5, "negative");    // big-endian, sign-flipped
m.insert( 7, "positive");    // encoding: byte order ==
                              // numeric order, free
for (const auto& [k, v] : m)  // → -5, then 7
    log(k, v);

ARTPP_PSIO_KEY(double)        // order-preserving codec, one macro

artpp::map<double, std::string> m;
m.insert(-3.5, "a");          // IEEE sign-transform: byte
m.insert( 0.0, "b");          // order becomes numeric
m.insert( 2.25, "c");         // order — negatives and all
for (const auto& [k, v] : m) // → -3.5, 0.0, 2.25
    log(k, v);
// reflected structs, optionals, variants key the same way

artpp::line_pool pool("store.bin");  // mmap'd file
using A = artpp::pool_alloc<uint64_t>;
artpp::map<std::string_view, uint64_t,
           artpp::mode::none, A> t{A{&pool}};
// branches cost 4 bytes; the whole store is one
// relocatable range — moves are a memcpy

// dictionary-shaped keys? pack the tails:
artpp::map<std::string_view, uint64_t,
           artpp::mode::buckets> dict;
// 77 ns dictionary lookups — 3.5x faster
// than std::map; scans rival absl::btree

Get started in one minute

Header-only. Copy include/artpp, or:

# CMake ≥ 3.20
FetchContent_Declare(artpp GIT_REPOSITORY https://github.com/gofractally/libartpp.git)
FetchContent_MakeAvailable(artpp)
target_link_libraries(your_target PRIVATE artpp::artpp)

# or hack on it directly
git clone https://github.com/gofractally/libartpp && cd libartpp
cmake -B build && cmake --build build -j && ctest --test-dir build
cmake -B build -DARTPP_BENCHMARKS=ON      # the compare suite from this page

Requirements: a C++20 compiler, little-endian target (ARM64/x86-64; NEON and SSE2 paths included). Nothing else. Full API reference and contracts: the README.