andrew
9b7199567b
CI / pre-commit (push) Successful in 1m59s
CI / release (arm64, ubuntu-latest-arm64) (push) Successful in 1m51s
CI / test (-DCMAKE_BUILD_TYPE=Debug, debug) (push) Successful in 2m11s
CI / test (-DCMAKE_CXX_FLAGS=-DUSE_64_BIT=1, 64-bit-versions) (push) Successful in 2m11s
CI / test (-DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++, gcc) (push) Successful in 2m1s
CI / test (-DUSE_SIMD_FALLBACK=ON, simd-fallback) (push) Successful in 2m10s
CI / release (amd64, ubuntu-latest-amd64) (push) Successful in 4m13s
CI / coverage (push) Successful in 2m48s
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 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
|
|
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|
|
| 171.37 | 5,835,467.28 | 0.5% | 2,915.46 | 629.31 | 4.633 | 502.91 | 0.0% | 0.01 | `point reads`
|
|
| 168.16 | 5,946,774.62 | 0.5% | 2,859.73 | 619.03 | 4.620 | 488.59 | 0.0% | 0.01 | `prefix reads`
|
|
| 245.86 | 4,067,294.63 | 0.3% | 3,508.97 | 904.82 | 3.878 | 627.73 | 0.0% | 0.01 | `range reads`
|
|
| 381.14 | 2,623,691.76 | 0.2% | 5,127.16 | 1,402.60 | 3.655 | 830.59 | 1.7% | 0.01 | `point writes`
|
|
| 376.24 | 2,657,887.07 | 0.3% | 5,062.85 | 1,381.07 | 3.666 | 811.68 | 1.6% | 0.01 | `prefix writes`
|
|
| 257.09 | 3,889,688.44 | 3.8% | 3,010.09 | 949.42 | 3.170 | 521.34 | 2.9% | 0.01 | `range writes`
|
|
| 629.71 | 1,588,026.28 | 4.0% | 6,809.60 | 2,320.32 | 2.935 | 1,247.08 | 1.3% | 0.01 | `monotonic increasing point writes`
|
|
| 126,164.50 | 7,926.16 | 1.7% | 772,460.25 | 463,264.67 | 1.667 | 141,512.00 | 0.2% | 0.01 | `worst case for radix tree`
|
|
| 15.33 | 65,217,669.23 | 0.4% | 299.00 | 56.45 | 5.297 | 64.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.81 | 78,088,759.03 | 0.7% | 187.38 | 47.15 | 3.974 | 33.70 | 0.5% | 0.01 | `point reads`
|
|
| 16.77 | 59,626,501.14 | 0.4% | 277.61 | 61.74 | 4.497 | 44.76 | 0.4% | 0.01 | `prefix reads`
|
|
| 42.45 | 23,556,818.87 | 0.4% | 856.96 | 156.09 | 5.490 | 126.22 | 0.2% | 0.01 | `range reads`
|
|
| 15.76 | 63,453,196.94 | 0.3% | 249.89 | 58.04 | 4.306 | 33.21 | 0.5% | 0.01 | `point writes`
|
|
| 29.71 | 33,662,499.39 | 0.1% | 509.14 | 109.33 | 4.657 | 70.26 | 0.5% | 0.01 | `prefix writes`
|
|
| 35.77 | 27,956,388.03 | 0.8% | 614.18 | 131.72 | 4.663 | 85.57 | 0.1% | 0.01 | `range writes`
|
|
| 80.13 | 12,480,456.47 | 1.5% | 1,279.04 | 294.90 | 4.337 | 234.68 | 0.1% | 0.01 | `monotonic increasing point writes`
|
|
| 360,748.00 | 2,772.02 | 2.6% | 4,401,835.00 | 1,318,754.00 | 3.338 | 728,537.00 | 0.0% | 0.01 | `worst case for radix tree`
|
|
| 90.69 | 11,027,103.45 | 1.0% | 1,686.00 | 333.80 | 5.051 | 284.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.42779 seconds, 368.253 MB/s, Add: 4.64942 seconds, 120.586 MB/s, Gc ratio: 28.8784%, Peak idle memory: 5.51735e+06
|
|
```
|
|
|
|
## radix tree
|
|
|
|
```
|
|
Check: 0.891163 seconds, 1829.69 MB/s, Add: 1.23064 seconds, 455.579 MB/s, Gc ratio: 42.9417%, Peak idle memory: 2.28333e+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.858484 seconds, 1899.33 MB/s, Add: 0.632886 seconds, 885.868 MB/s, Gc ratio: 41.252%, Peak idle memory: 0
|
|
```
|
|
|