A data structure for optimistic concurrency control on ranges of bitwise-lexicographically-ordered keys.

Intended as an alternative to FoundationDB's skip list.

Hardware for all benchmarks is an AMD Ryzen 9 7900 with (2x32GB) 5600MT/s CL28-34-34-89 1.35V RAM.

$ clang++ --version

Ubuntu clang version 21.1.8 (6ubuntu1)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-21/bin

Microbenchmark

Skip list

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
165.93	6,026,520.04	0.1%	3,107.03	610.42	5.090	558.59	0.0%	1.98	point reads
163.08	6,132,046.57	0.1%	3,036.76	599.68	5.064	539.35	0.0%	1.95	prefix reads
250.26	3,995,834.21	0.1%	3,722.71	920.25	4.045	692.00	0.0%	2.99	range reads
359.64	2,780,581.63	0.1%	4,523.64	1,322.63	3.420	720.22	2.1%	4.30	point writes
358.20	2,791,726.93	0.1%	4,484.57	1,317.23	3.405	705.00	2.0%	4.28	prefix writes
193.91	5,157,081.29	0.1%	2,224.10	713.33	3.118	377.17	3.3%	2.32	range writes
422.03	2,369,513.38	1.1%	6,855.96	1,551.55	4.419	1,227.82	1.4%	0.05	monotonic increasing point writes
142,467.00	7,019.17	3.8%	812,047.33	508,535.40	1.597	151,246.50	1.0%	0.01	worst case for radix tree
37.66	26,554,217.74	0.8%	701.00	138.80	5.050	102.00	0.0%	0.01	create and destroy

Radix tree (this implementation)

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
12.25	81,664,669.29	0.4%	233.49	44.94	5.196	31.23	0.7%	0.15	point reads
13.35	74,903,950.49	0.1%	271.75	49.10	5.534	40.21	0.4%	0.16	prefix reads
31.37	31,874,583.62	0.1%	700.39	115.43	6.067	100.83	0.2%	0.37	range reads
19.55	51,153,057.80	0.1%	366.51	71.90	5.098	47.92	0.5%	0.23	point writes
36.92	27,088,344.17	0.1%	645.11	135.72	4.753	100.31	0.4%	0.44	prefix writes
36.84	27,143,553.08	0.1%	691.04	135.42	5.103	114.01	0.1%	0.45	range writes
74.62	13,400,467.72	0.9%	1,418.37	274.20	5.173	273.39	0.1%	0.01	monotonic increasing point writes
352,671.00	2,835.50	15.3%	3,687,535.00	1,287,119.00	2.865	712,030.00	0.1%	0.01	〰️ worst case for radix tree (Unstable with ~1.0 iters. Increase minEpochIterations to e.g. 10)
96.63	10,348,729.42	1.2%	1,766.00	355.53	4.967	283.00	0.0%	0.01	create and destroy

"Real data" test

Point queries only. Gc ratio is the ratio of time spent doing garbage collection to time spent adding writes or doing garbage collection. Lower is better.

skip list

Check: 4.69875 seconds, 347.017 MB/s, Add: 3.39475 seconds, 165.153 MB/s, Gc ratio: 38.7414%, Peak idle memory: 5.51852e+06

radix tree

Check: 0.976745 seconds, 1669.37 MB/s, Add: 1.20464 seconds, 465.411 MB/s, Gc ratio: 39.4158%, Peak idle memory: 2.0226e+06

hash table

(The hash table implementation doesn't work on range queries, and its purpose is to provide an idea of how fast point queries can be)

Check: 0.864589 seconds, 1885.92 MB/s, Add: 0.634604 seconds, 883.47 MB/s, Gc ratio: 41.184%, Peak idle memory: 0