main
CI / pre-commit (push) Successful in 3m7s
CI / test (arm64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 22, https://minio.weaselab.dev/public/aarch64/msan-toolchain-22.1.8.tar.zst, debug-arm64, ubuntu-latest-arm64) (push) Successful in 4m21s
CI / release (arm64, , ubuntu-latest-arm64) (push) Successful in 3m42s
CI / test (amd64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 21, https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst, debug, ubuntu-latest-amd64) (push) Successful in 5m1s
CI / test (amd64, -DCMAKE_CXX_FLAGS=-DUSE_64_BIT=1, 21, , 64-bit-versions, ubuntu-latest-amd64) (push) Successful in 3m37s
CI / test (amd64, -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++, 21, , gcc, ubuntu-latest-amd64) (push) Successful in 3m35s
CI / test (amd64, -DUSE_SIMD_FALLBACK=ON, 21, , simd-fallback, ubuntu-latest-amd64) (push) Successful in 3m32s
CI / release (amd64, -DMSAN_TOOLCHAIN_PATH=/opt/msan, ubuntu-latest-amd64) (push) Successful in 6m3s
CI / coverage (push) Successful in 4m11s
Reviewed-on: #105
Merge pull request 'ci: run MSan on arm64' (#74) from weaselbot/conflict-set:weaselbot/issue-73 into main
Merge pull request 'Run the maxVersion "borrowed range version" check (#95)' (#106) from weaselbot/conflict-set:weaselbot/issue-95 into main
Merge pull request 'SkipList: guard memcpy/memcmp against null pointers in keyAfter and friends' (#105) from weaselbot/conflict-set:weaselbot/issue-96 into main
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
Description
A data structure for optimistic concurrency control on ranges of bitwise-lexicographically-ordered keys.
Readme
Apache-2.0
7.6 MiB
1 Watchers
1 Forks