The Gap Between Data Structure Theory and Libraries

Most data structure theory results of the past two years have not changed any library. The cause is not implementer inertia. Theory counts one cost and hardware pays another.

Proven Theory and Unchanged Code

Over the past two years, several questions that had stayed open for decades in data structure theory were closed. During the same period, the data structure implementations in standard libraries and major open source projects barely moved. Explaining that gap as a lag in information is wrong. The quantity a paper optimizes and the quantity that dominates running time are different to begin with.

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 against Dijkstra (arXiv:2511.03007, verified 2026-09). Across sparse random graphs, grids, and US road networks up to 10 million vertices, Dijkstra was 3 to 4 times faster in every case. The paper estimates that the vertex count would have to vastly exceed $10^{67}$ before the worst-case implementation overtakes Dijkstra.

What matters here is not which algorithm wins but where the crossover point sits. An asymptotic advantage appears only once n is large enough, and big-O notation hides where that threshold is. When constant factors are large, the crossover moves to a size that is physically unreachable, and the theoretical advantage then tells you nothing about which code to write.

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) concede this point in their opening paragraph. They write that quadratic probing is attractive because it combines high locality of reference with a low probe count per search. Those were empirical observations rather than theoretical guarantees. They then introduce a witness forest technique that records chains of probe collisions as a tree. The conclusion is that any fixed offset sequence has constant expected insertion cost up to a load factor of 35.74%, and quadratic probing up to 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 that S3-FIFO delivered roughly 6 times the throughput of an optimized LRU implementation at 16 threads. SIEVE achieves the same effect with one queue and a hand pointer, and recorded more than twice the throughput of LRU and TwoQ at 16 threads. This difference appears nowhere in a miss ratio calculation. The structural details are covered in FIFO Cache Eviction Replacing LRU.

The direction here is the reverse of the two previous cases. Theory did not run ahead of practice. A simple structure already in use looked inferior in theory, and the evaluation criterion turned out to be the wrong one. Gaps do not arise only when theory leads practice.

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 own cost calculation. At a 1% false positive rate, Bloom uses about 10 bits per key and Ribbon about 7. In exchange, construction rises from 32ns to 140ns per key and queries from 500ns to 600ns. The team plugged in hardware prices and power rates to compute a break-even point, and concluded that Ribbon is cheaper once a filter stays in memory for more than an hour.

Three conditions made the transfer possible. The interface is identical, so only the policy object changes. The added cost falls on compaction, which is a background stage, while the savings occur in memory that is resident at all times. SIEVE was ported into five open source cache libraries with fewer than 20 lines of change on average for the same reason.

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 rests on six papers and two implementation reports. It is not a survey of library adoption rates, so "barely moved" is an observation over 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.

In other cases the gap sits on the theory side. The proven load factor of 37.61% falls well short of the 0.7 or so used in practice, and the range in between remains safe only empirically. Code that uses quadratic probing runs fine in a region the proofs do not reach.

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.

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, data structure theory has settled open addressing bounds, the dynamic filter space lower bound, and the sorting barrier in sequence. Three reasons keep those results out of libraries. The crossover sits outside realistic data sizes, the improved metric differs from the one that dominates running time, or the model has no lock waits. Results that keep the interface and push the added cost into a background stage, such as the Ribbon filter and the SNG parameter rule, did reach production code. When a new result appears, check where its crossover point sits and which stage pays the added cost before looking at the size of the improvement.