The Gap Between Data Structure Theory and Libraries

Most data structure theory results of the past two years have not changed libraries. Theory and hardware measure different costs.

Proven Theory and Unchanged Code

Over the past two years, data structure theory resolved several questions that had remained open for decades. During the same period, implementations in standard libraries and major open source projects changed little. Delayed access to research does not explain this difference. Papers often optimize a quantity that differs from the one that determines running time.

Start with what was settled. The mechanics of each individual structure are covered separately in Core Data Structures.

One of the six reached code. Splitting the reasons the other five stalled gives three distinct causes.

Crossover Points Outside Reality

Duan, Mao, Mao, Shu, and Yin (2025) produced a new algorithm for the single-source shortest path (SSSP) problem. It is a deterministic algorithm running in $O(m\log^{2/3}n)$ time in the comparison-addition model. Here n is the vertex count and m is the edge count. This result was the first proof that Dijkstra's $O(m+n\log n)$ is not a lower bound for the problem. A follow-up paper in February 2026 reduced the bound to $O(m\sqrt{\log n\log\log n})$ on sparse graphs under the same premises.

Castro, Clementino, and de Freitas implemented the 2025 algorithm in C++ and compared it with Dijkstra (arXiv:2511.03007, verified 2026-09). They measured sparse random graphs, grids, and US road networks with up to 10 million vertices. Dijkstra was 3 to 4 times faster in every case. The paper estimates that a worst-case implementation needs far more than $10^{67}$ vertices to overtake Dijkstra.

The relevant question is the data size at which performance reverses. An asymptotic advantage appears only when n is sufficiently large. Big-O notation does not identify that threshold. Large constant factors can put it beyond physically reachable data sizes. In that case, the theoretical advantage does not guide implementation choice.

What Theory Counts and What Hardware Pays

Farach-Colton, Krapivin, and Kuszmaul (2025) presented elastic hashing for open addressing that never relocates elements. Insertion probes are $O(1)$ amortized and $O(\log\delta^{-1})$ in worst-case expectation. Here δ is the fraction of free space remaining. The same paper proves a matching lower bound, and along the way it disproves Yao's conjecture that uniform hashing is optimal.

Widely used hash table implementations still sit on linear probing and quadratic probing. The reason is that probe count is a proxy for cost rather than the cost itself. Consecutive probes in linear probing usually land in the same cache line, so several extra probes still cost a single memory access.

Guo, Pettie, and Wan (2026) acknowledge this distinction. Quadratic probing combines high locality of reference with a low probe count per search. These were empirical observations without theoretical guarantees. Their witness forest technique records chains of probe collisions as a tree.

Any fixed offset sequence has constant expected insertion cost up to a load factor of 35.74%. For quadratic probing, the corresponding threshold is 37.61%.

Elastic hashing splits the array into several regions and applies a different insertion rule in each. You cannot know in advance which region a probe will land in, so locality across consecutive probes is hard to expect. A structure that wins on the probe-count metric can lose on the cache-line metric. Neither paper measured cache misses, so this last point is an estimate.

Lock Waits Absent from the Sequential Model

Cache eviction algorithms were judged on miss ratio alone for a long time. By that measure LRU beats FIFO, and the comparison holds inside a single-threaded model. The problem is that LRU moves an object to the head of a shared ordered list on every hit. A write lock sits on the read path, so throughput does not scale with thread count.

The S3-FIFO authors report roughly 6 times the throughput of optimized LRU at 16 threads. SIEVE uses one queue and a hand pointer to achieve the same effect. At 16 threads, it recorded more than twice the throughput of LRU and TwoQ. Miss ratio calculations do not capture this difference. See FIFO Cache Eviction Replacing LRU for the structures.

In this case, a simple structure already used in practice appeared inferior under the theoretical model. Later evaluation showed that the criterion failed to capture actual costs. The gap between theory and practice can therefore arise even when theory does not advance first.

When Theory Did Reach the Code

The gap does not always persist. The Ribbon filter cut the space overhead of static filters down to near the information-theoretic lower bound. RocksDB has offered it since version 6.15 as a policy that can be selected in place of the Bloom filter.

The RocksDB team published its cost calculation. At a 1% false positive rate, Bloom uses about 10 bits per key and Ribbon about 7. Construction cost rises from 32ns to 140ns per key, and query cost rises from 500ns to 600ns.

The team used hardware prices and power rates to calculate the break-even point. It concluded that Ribbon costs less when a filter stays in memory for more than an hour.

Three conditions explain adoption. The interfaces match, so only the policy object changes. The added cost occurs during background compaction, while memory savings persist. The same properties helped port SIEVE to five open source cache libraries with fewer than 20 changed lines on average.

The third case changed a parameter rather than an algorithm. Ma and coauthors (2025) modeled the construction of a Sparse Neighborhood Graph (SNG) as a martingale. From that model they proved a maximum degree of $O(n^{2/3+\epsilon})$ and an expected search path length of $O(\log n)$.

They then derived a closed-form rule for the truncation parameter that controls graph sparsification. With the parameter sweep gone, index construction became 5.9 times faster on average and 15.4 times faster at peak. Adoption cost was low because the graph structure stayed as it was and only the tuning procedure was replaced. The background is in Complexity of Graph-Based Approximate Nearest Neighbor Search.

Where This Argument Does Not Hold

This post uses six papers and two implementation reports. It does not survey library adoption rates. The description "barely moved" refers to these cases rather than a statistic.

The SSSP measurement also rests on a single independent implementation. The paper itself states that a substantial reduction in constant factors is required before the result can displace established methods. That is not a claim that the algorithm is useless forever.

Some results should not be asked about a gap at all. The fingerprint filter optimality proof (FOCS 2025) is not a result that asks for a code change, but one that removes the reason to make one. Kuszmaul, Liang, and Zhou fixed the dynamic filter lower bound at $n\log\varepsilon^{-1}+n\log e-o(n)$ bits as ε goes to zero. The fingerprint technique introduced by Carter and coauthors in 1978 attains that bound exactly. This lineage is covered in Cuckoo Hashing and Fingerprint Filters.

The proven load factor of 37.61% is below the approximately 0.7 used in practice. Safety between these values has empirical support but no corresponding proof. Quadratic probing implementations work in a range that these proofs do not cover.

What to Check Before Adopting

Deciding whether to put a new theoretical result into code follows an order. Turning the cases above into conditions gives this flow.

flowchart TD
    A[New theoretical result] --> B{Is the crossover n<br/>within my data size}
    B -->|No| X[Hold<br/>SSSP, 10 to the 67th vertices]
    B -->|Yes| C{Is the improved metric<br/>my bottleneck}
    C -->|No| Y[Hold<br/>probe count vs cache lines]
    C -->|Yes| D{Is there concurrent access}
    D -->|Yes| E{Was the cost outside the<br/>sequential model measured}
    D -->|No| F{Which stage carries<br/>the added cost}
    E -->|No| Y
    E -->|Yes| F
    F -->|Background construction| G[Adopt<br/>Ribbon filter]
    F -->|Query path| H[Re-measure against the savings]

Each branch corresponds to one row in the table below.

The first three rows are properties of the theoretical result, and the last two are properties of your own codebase. Failing on the first group means waiting for a better result, while failing on the second means redesigning how you adopt it.

Summary

Since 2025, research has resolved open addressing bounds, the dynamic filter space lower bound, and the sorting barrier. Three factors limit adoption in libraries. The crossover can exceed realistic data sizes, the optimized metric can differ from runtime cost, or the model can omit lock waits.

Ribbon filter and the SNG parameter rule preserve interfaces and move added costs to background work. These results reached production code. Before considering the improvement size, identify its crossover point and the stage that incurs the additional cost.