Andrew Noyes
8190d2f24e
Some checks failed
Tests / 64 bit versions total: 8220, passed: 8220
Tests / Debug total: 8218, failed: 28, passed: 8190
Tests / SIMD fallback total: 8220, passed: 8220
Tests / Release [clang] total: 8220, passed: 8220
Tests / gcc total: 8220, failed: 28, passed: 8192
Tests / Release [clang,aarch64] total: 5446, passed: 5446
Tests / Coverage total: 5497, failed: 28, passed: 5469
weaselab/conflict-set/pipeline/head There was a failure building this commit
71 lines
4.6 KiB
Markdown
71 lines
4.6 KiB
Markdown
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
|
|
```
|
|
|