splaylist

A self-balancing skip list for Rust: an ordered map (SplayMap) and set (SplaySet) whose node heights adapt to the access pattern, so frequently used keys are promoted to taller towers and become cheaper to reach.

A skip list keeps keys in a sorted linked list with stacked "express lane" forward pointers, giving O(log n) search, insert, and remove on average. A splay list (Aksenov et al., 2020) adds adaptivity: each node counts how often it is accessed, and the structure periodically reshapes itself so the expected search cost tracks the entropy of the access distribution rather than a flat log n. In practice that lowers splaylist's own cost on skewed reads; it does not make it faster than BTreeMap (see Benchmarks).

This crate is the safe-Rust descendant of a C sl.h splay list. It contains no unsafe code (#![forbid(unsafe_code)]): nodes live in a single arena Vec and links are array indices, so there are no raw pointers, no manual lifetimes, and no memory-reclamation hazards.

[dependencies]
splaylist = "0.1"

Example

use splaylist::SplayMap;

let mut map = SplayMap::new();
map.insert(3, "three");
map.insert(1, "one");
map.insert(2, "two");

assert_eq!(map.get(&2), Some(&"two"));

// Always iterates in ascending key order, however the towers have adapted.
let keys: Vec<_> = map.keys().copied().collect();
assert_eq!(keys, [1, 2, 3]);

// Entry API, ranges, and the usual collection traits are all available.
*map.entry(1).or_insert("?") = "ONE";
let mid: Vec<_> = map.range(2..).map(|(k, _)| *k).collect();
assert_eq!(mid, [2, 3]);

Benchmarks

Honest summary up front: BTreeMap is faster than every skip list measured here, including this one. Skip lists lose to cache-friendly B-trees on modern hardware — that is a known, expected result, not a defect. Pick splaylist when you want a skip list with access-frequency adaptation, not as a drop-in speed upgrade over the standard library.

Methodology (see comparison/benches/compare.rs): keys and the full access sequence are generated once from a fixed seed and replayed verbatim against every implementation; u64 -> u64, N = 100_000; Criterion with lto = "thin", codegen-units = 1. The skewed workload sends ~80% of lookups to a scattered random 1% of keys (clustering them at the low end would be cheap in any skip list and would not isolate adaptation); every map is warmed with the identical read sequence first, and splaylist is additionally allowed to reach adapted steady state (its background rebalance cost is not charged to the measured lookups). Reproduce with cd comparison && cargo bench.

Median time per operation on one x86-64 Linux machine (lower is better; your numbers will differ):

crossbeam-skiplist is a concurrent, lock-free structure; measuring it single-threaded charges it atomic/epoch overhead it would amortize across threads, so treat its column as context, not a head-to-head.

What the numbers show:

• BTreeMap wins across the board by roughly 5–6x on lookups. If raw ordered-map speed is all you need, use it.
• Among skip lists, splaylist is competitive: fastest insert and iteration of the three, slightly slower point lookups.
• Adaptation helps, modestly. splaylist's own skewed-lookup latency is ~13% better than its uniform latency (~229 ns vs ~263 ns) because hot keys climb into taller towers. The benefit grows as the hot set gets more concentrated and shrinks as access flattens; it does not close the gap to BTreeMap.

When should I use it?

splaylist is deliberately single-threaded. SplayMap is Send when K and V are, but it is not Sync: reads update interior access counters. For shared concurrent access use crossbeam-skiplist.

Features

All optional features are off by default except std.

splaylist = { version = "0.1", default-features = false, features = ["serde"] }

How adaptation works

Every get records an access against the node it finds (a cheap interior mutation through a Cell). Structural reshaping — promoting hot nodes and demoting cold ones by one level at a time toward the target height K − 1 − log2(total / hits) — happens during mutating operations on a fixed interval, and can be forced with SplayMap::rebalance. The interval is set via SplayMap::with_config; splay_interval: 0 disables adaptation entirely, leaving a plain randomized skip list.

The seed is configurable too, so a map's structural evolution is fully deterministic for tests and reproducible benchmarks.

Correctness and testing

• #![forbid(unsafe_code)] — the whole crate is safe Rust.
• Property-based tests use Hegel (Hypothesis under the hood). A stateful model test drives SplayMap/SplaySet through random operation sequences against BTreeMap/BTreeSet oracles and asserts agreement after every step (in default, aggressive, and disabled adaptation modes), plus range and into_iter equivalence. They live in hegel-tests/ (a separate crate, since hegeltest needs a Hypothesis server); run with cd hegel-tests && cargo test.
• Example-based integration and unit tests run on every cargo test and are self-contained (no server required).
• Internal unit tests assert the structural invariants (level 0 is a complete, strictly-ascending, doubly-linked list; every upper level is a sorted subsequence) hold under churn, that hot keys end up taller than cold ones, and — as a regression guard — that heavy adaptation never collapses search cost below O(log n).
• A cargo fuzz differential target lives in fuzz/.
• cargo miri test is clean (no undefined behaviour), and cargo deny guards the dependency tree.
• Comparison benchmarks against other Rust ordered maps live in comparison/ (see Benchmarks).

Minimum supported Rust version

The MSRV is 1.70. Raising it is a minor-version change.

License

Licensed under either of Apache-2.0 or MIT at your option. The C ancestor is dual-licensed ISC OR MIT.