Andrew Noyes 2642d453dc
All checks were successful
Tests / 64 bit versions total: 8331, passed: 8331
Tests / Debug total: 8329, passed: 8329
Tests / SIMD fallback total: 8331, passed: 8331
Tests / Release [clang] total: 8331, passed: 8331
Clang |Total|New|Outstanding|Fixed|Trend |:-:|:-:|:-:|:-:|:-: |0|0|0|0|:clap:
Tests / gcc total: 8331, passed: 8331
GNU C Compiler (gcc) |Total|New|Outstanding|Fixed|Trend |:-:|:-:|:-:|:-:|:-: |0|0|0|0|:clap:
Tests / Release [clang,aarch64] total: 5520, passed: 5520
Tests / Coverage total: 5571, passed: 5571
Code Coverage #### Project Overview No changes detected, that affect the code coverage. * Line Coverage: 97.75% (3080/3151) * Branch Coverage: 41.81% (18260/43676) * Complexity Density: 0.00 * Lines of Code: 3151 #### Quality Gates Summary Output truncated.
weaselab/conflict-set/pipeline/head This commit looks good
Remove unnecessary branch for interleaved range writes
2024-12-11 21:53:44 -08:00
2024-03-06 21:22:30 -08:00
2024-11-21 17:27:14 -08:00
2024-08-21 14:00:00 -07:00
2024-08-05 12:20:38 -07:00
2024-04-04 16:29:26 -07:00
2024-11-18 14:05:14 -08:00
2024-11-15 16:49:21 -08:00
2024-02-20 13:22:22 -08:00
2024-01-30 10:39:43 -08:00
2024-08-30 16:06:43 -07:00
2024-09-09 20:10:55 -07:00
2024-11-10 21:47:26 -08:00
2024-11-20 21:55:37 -08:00
2024-11-12 17:50:27 -08:00
2024-11-19 09:02:16 -08:00

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 20.0.0 (++20241120082228+86734c857724-1~exp1~20241120202359.554)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-20/bin

Microbenchmark

Skip list

ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
161.29 6,200,056.17 0.1% 3,014.03 831.04 3.627 504.59 0.0% 1.93 point reads
158.32 6,316,160.64 0.1% 2,954.16 815.80 3.621 490.17 0.0% 1.89 prefix reads
237.39 4,212,409.50 0.2% 3,592.41 1,233.96 2.911 629.31 0.0% 2.84 range reads
442.11 2,261,878.94 0.0% 4,450.57 2,314.25 1.923 707.92 2.1% 5.28 point writes
439.89 2,273,308.53 0.1% 4,410.22 2,302.29 1.916 694.74 2.1% 5.25 prefix writes
290.96 3,436,936.78 0.0% 2,315.38 1,528.68 1.515 396.69 3.3% 3.49 range writes
476.93 2,096,762.02 0.6% 6,999.33 2,484.94 2.817 1,251.73 1.3% 0.06 monotonic increasing point writes
131,736.57 7,590.91 1.1% 807,444.50 704,941.71 1.145 144,584.60 0.9% 0.01 worst case for radix tree
45.50 21,978,369.95 1.1% 902.00 232.36 3.882 132.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.36 80,885,626.43 0.2% 243.56 63.62 3.828 31.07 0.6% 0.15 point reads
14.18 70,502,196.81 0.1% 297.72 73.13 4.071 40.31 0.5% 0.17 prefix reads
33.44 29,901,623.04 0.1% 767.90 172.42 4.454 101.32 0.2% 0.40 range reads
19.48 51,342,564.70 0.3% 374.45 100.43 3.728 48.92 0.5% 0.23 point writes
37.46 26,694,471.44 0.1% 672.00 193.14 3.479 101.28 0.3% 0.45 prefix writes
38.78 25,784,784.34 0.0% 738.26 199.93 3.693 111.59 0.1% 0.47 range writes
76.05 13,148,995.74 0.7% 1,450.77 397.16 3.653 275.72 0.0% 0.01 monotonic increasing point writes
286,920.33 3,485.29 0.4% 4,117,948.00 1,521,352.00 2.707 714,833.00 0.1% 0.01 worst case for radix tree
95.66 10,453,798.72 0.5% 1,986.00 495.04 4.012 315.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.53508 seconds, 371.81 MB/s, Add: 3.81222 seconds, 150.919 MB/s, Gc ratio: 33.66%, Peak idle memory: 5.61007e+06

radix tree

Check: 0.957735 seconds, 1760.6 MB/s, Add: 1.19942 seconds, 479.678 MB/s, Gc ratio: 38.6069%, Peak idle memory: 2.05667e+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.804598 seconds, 2095.69 MB/s, Add: 0.671221 seconds, 857.147 MB/s, Gc ratio: 35.0034%, Peak idle memory: 0
Description
A data structure for optimistic concurrency control on ranges of bitwise-lexicographically-ordered keys.
Readme 25 MiB
v0.0.13 Latest
2024-08-26 21:24:21 +00:00
Languages
C++ 82.9%
TeX 8.1%
CMake 4.8%
Python 2.7%
Shell 0.9%
Other 0.6%