Fastest Data Structures in Computer Science

A benchmarked survey of the fastest known implementations across ten major data structure categories, drawing on real-world results from 2020–2026. The single biggest performance lever in modern data structure design is not algorithmic complexity — it is cache locality. Across every category, implementations that minimize cache misses and exploit SIMD instructions dominate benchmarks, often by 5–20x over theoretically equivalent alternatives.

The winners, category by category

Three principles that make data structures fast

SIMD-parallel metadata scanning. Pioneered by swiss-table and now used in hash maps, tries (adaptive-radix-tree Node16), Bloom filters, and b-tree node search. Transforms sequential comparisons into batch operations — checking 16 slots in 3 instructions.

Contiguous memory layouts. Flat arrays, SoA, packed nodes. These exploit hardware prefetchers and cache lines. B-trees beat red-black trees by 18x. Flat arrays outperform linked lists by 10–100x. The ecs-pattern operationalizes this at scale in game engines.

Branch elimination. Branchless partitioning in pdqsort/driftsort, branchless SIMD search in Algorithmica's B-tree, branchless merge loops. Modern CPUs pay enormous costs for branch mispredictions — eliminating them is consistently worth 20–50% performance.

FAA over CAS at contention hotspots. The principle that obsoleted the michael-scott-queue and produced LCRQ, SCQ, LPRQ, and wCQ: CAS-retry melts down under contention while FAA always succeeds. At 144 threads: FAA ~40 ns vs CAS ~75 ns. Combined with the 128-byte cache-line rule, this is the dominant lever in concurrent data structure design.

Optimistic readers that never write shared memory. The same insight at the ordered-map layer: ART-OLC and masstree beat the lock-free bw-tree by 1.5–4.5× because lock-freedom is not cache-coherence-freedom. Version-counter validation lets unbounded reader counts share clean cache lines. This unifies rcu, FAA-over-CAS, and modern concurrent ordered maps into a single design discipline: avoid writes to shared cache lines on the hot path.

The practical default stack

Use boost-unordered-flat-map or abseil-flat-hash-map for C++ hash maps (hashbrown in Rust). Note: in many workloads the hash function (foldhash, rapidhash) matters more than the table — see fastest-hash-map-2025. Use Abseil btree_map for production ordered containers; reach for bs-tree / algorithmica-s-tree / fb-plus-tree when squeezing the last 7–18× matters; reach for ART / HOT for in-memory database indexes — see fastest-ordered-maps. Use d-ary-heap for priority queues. Use ips4o for parallel sorting. Use binary-fuse-filter for set membership. Use csr-graph for graph analytics. For concurrent hash maps at scale, parlayhash hits 1,130 Mops at 128 threads. For concurrent queues, LCRQ + aggregating-funnels is the strict-FIFO MPMC ceiling; lmax-disruptor still wins for bounded pipeline tail latency; for read-dominated workloads rcu remains hard to beat. The most exciting frontier — learned-indexes — is already delivering production wins and may fundamentally reshape database indexing.

Allocation and memory layout

The single most underrated lever in data structure performance: the allocator dominates the container — switching glibc → mimalloc/jemalloc/tcmalloc swings benchmarks more than picking a "better" container does. Dynamic-array benchmarks make this concrete: C, Rust, and C++ vectors all land within ~10% of each other once allocators are matched, but switching allocators alone moves results 2–3×. Arena/bump allocators like bumpalo deliver 2–5x speedup for batch allocations. The soa-vs-aos pattern yields 1.4–12.7x speedup depending on struct size and access pattern. simdjson demonstrates the ceiling of SIMD-optimized design: 4x faster than RapidJSON, 25x faster than JSON for Modern C++.

Emerging frontiers

learned-indexes replace B-tree branching with piecewise-linear CDF approximation for O(log log N) lookup. cache-oblivious-structures optimize for every cache level simultaneously without knowing cache parameters. succinct-data-structures trade CPU cycles for near-information-theoretic space efficiency. elastic-hashing (Jan 2025) disproved Yao's 1985 conjecture on probe complexity, suggesting hash table design is not yet exhausted. These are not just academic — RadixSpline is in RocksDB, PGM-Index has production deployments, and SDSL-lite implements 40 research publications in usable C++ templates.