I have used dashmap, which has sort of like the popular high-performance replacement for RwLock<HashMap<K, V>>. Are there any similar crates for BTreeMap? I was working on implementing a C++ data structure called Masstree in Rust, it would also be something you would use instead of RwLock<BTreeMap>, but I can't find any good crates to study as reference material for rust code patterns.
I know that it is a niche use case, so please don't bother with 'why? it's unnecessary' replies :'D
You could check out crossbeam_skiplist, it isn't btree-based but it's a concurrent sorted map nonetheless.
That and the IndexSetBTreeMap from indexset were the only similar things I could find. But in benchmarks they seem to be performing worse than the initial unoptimized masstree for some reason, I was looking for references for highly optimized alternatives, someone suggessted congee but it's also different and has a big constraint on key length (fixed 8-byte)
Timer precision: 30 ns
concurrent_maps fastest │ slowest │ median │ mean │ samples │ iters
├─ 01_single_get │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 100 48.15 ns │ 122.3 ns │ 48.32 ns │ 49.08 ns │ 100 │ 6400
│ │ ╰─ 1000 55.04 ns │ 137.5 ns │ 55.99 ns │ 56.82 ns │ 100 │ 6400
│ ├─ masstree │ │ │ │ │
│ │ ├─ 100 20.38 ns │ 46.05 ns │ 20.53 ns │ 20.99 ns │ 100 │ 25600
│ │ ╰─ 1000 26.24 ns │ 26.64 ns │ 26.32 ns │ 26.31 ns │ 100 │ 12800
│ ╰─ skipmap │ │ │ │ │
│ ├─ 100 48.15 ns │ 51.78 ns │ 48.32 ns │ 49.58 ns │ 100 │ 6400
│ ╰─ 1000 100.7 ns │ 174.6 ns │ 101.3 ns │ 102 ns │ 100 │ 3200
├─ 02_single_insert │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 100 453 ns │ 637.1 ns │ 490.6 ns │ 505.7 ns │ 100 │ 800
│ │ ╰─ 1000 529.3 ns │ 1.047 µs │ 584.5 ns │ 606.1 ns │ 100 │ 800
│ ├─ masstree │ │ │ │ │
│ │ ├─ 100 94.51 ns │ 279.5 ns │ 98.57 ns │ 118.2 ns │ 100 │ 3200
│ │ ╰─ 1000 117 ns │ 305.5 ns │ 120.1 ns │ 125.6 ns │ 100 │ 3200
│ ╰─ skipmap │ │ │ │ │
│ ├─ 100 173.3 ns │ 368.4 ns │ 218 ns │ 214.8 ns │ 100 │ 3200
│ ╰─ 1000 151.1 ns │ 381.6 ns │ 161.8 ns │ 164.3 ns │ 100 │ 800
├─ 03_concurrent_reads │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 1 180.6 µs │ 434 µs │ 188.8 µs │ 202.3 µs │ 100 │ 100
│ │ ├─ 2 368.4 µs │ 884.9 µs │ 442.8 µs │ 456 µs │ 100 │ 100
│ │ ├─ 4 926.2 µs │ 1.475 ms │ 1.074 ms │ 1.077 ms │ 100 │ 100
│ │ ╰─ 8 2.361 ms │ 3.36 ms │ 2.715 ms │ 2.773 ms │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 1 76.23 µs │ 138 µs │ 100.6 µs │ 99.19 µs │ 100 │ 100
│ │ ├─ 2 105.3 µs │ 225.6 µs │ 152.6 µs │ 153 µs │ 100 │ 100
│ │ ├─ 4 172.5 µs │ 347.9 µs │ 222.6 µs │ 227.7 µs │ 100 │ 100
│ │ ╰─ 8 263.1 µs │ 566 µs │ 306 µs │ 320.6 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 1 150 µs │ 293.6 µs │ 162.8 µs │ 170.9 µs │ 100 │ 100
│ ├─ 2 197.3 µs │ 372.4 µs │ 224.5 µs │ 236.4 µs │ 100 │ 100
│ ├─ 4 276.7 µs │ 540.3 µs │ 332.5 µs │ 335 µs │ 100 │ 100
│ ╰─ 8 404.8 µs │ 583.5 µs │ 438 µs │ 457.7 µs │ 100 │ 100
├─ 04_concurrent_writes │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 1 97.91 µs │ 180.9 µs │ 102.8 µs │ 106.5 µs │ 100 │ 100
│ │ ├─ 2 166.6 µs │ 308.9 µs │ 205.6 µs │ 208.6 µs │ 100 │ 100
│ │ ╰─ 4 266.2 µs │ 494.1 µs │ 317.1 µs │ 320.8 µs │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 1 40.87 µs │ 101.5 µs │ 53.82 µs │ 54.9 µs │ 100 │ 100
│ │ ├─ 2 63.84 µs │ 378.9 µs │ 86.93 µs │ 91.07 µs │ 100 │ 100
│ │ ╰─ 4 108.5 µs │ 331.1 µs │ 137.5 µs │ 142.3 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 1 62.1 µs │ 103.2 µs │ 67.4 µs │ 69.59 µs │ 100 │ 100
│ ├─ 2 93.73 µs │ 231 µs │ 107.3 µs │ 113 µs │ 100 │ 100
│ ╰─ 4 132.7 µs │ 244 µs │ 158.6 µs │ 159.5 µs │ 100 │ 100
I suppose the benchmarks are these, correct?
It seems you're benchmarking the insertion/read of 8 bytes strings, but isn't that exactly the threshold for the optimization that masstree has? All the other maps are forces to pay the cost of a Vec allocation and indirection when comparing, while yours doesn't. Sure, in practice it might help depending on your usecase, but it won't help if you want to compare the underlying algorithm of the map.
The patterns you use while reading/inserting also seem to minimize collisions. You never have threads reading and writing the same key, they mostly read/write sequential non-overlapping ranges of keys. It would be more interesting to see what happens when they read/write the same range of keys, or random keys.
Finally, 4 threads seem very few for benchmarking a concurrent algorithm. A good concurrent data structure should be able to scale to tens of threads at least, though I can see why this might be difficult to benchmark on consumer hardware.
Yes, the implementation is still in very early stages and currently I am working out how to fix some major memory leak issues due to not properly handling memory reclamation. For example, the current code crashes for write heavy workloads with higher number of threads. Which is why I was looking for other references to see how to properly work this out. The original implementation uses an epoch based reclamation model, but I decided to go with a hyaline based reclamation model using a newer crate called seize. This made it harder to follow the original reference but also improved read performance quite a bit, so I am trying to stick to it.
The benchmarks may regress a lot (or improve) after the memory reclamation is implemented properly. So the current benchmarks may not be a fair comparison :'D
My point was that the benchmarks themselves are not very fair or representative of real situations. Fixing issue is the crate will not change this.
Of course, I will just add longer length keys that will force masstree through multiple layers, more complex and realistic access patterns and contention cases where threads write to overlapping keys. That should give a more objective view of the current situation, but the real problem from an implementation perspective is that the 'better' benchmarks don't really matter when there are major soundness issues in the implementation. Sorry if you got the impression that 'I have a better thing here' :'D
Yeah, you were right, here's the proper benchmark results. It ironically does better ONLY on single threads (consistently) compared to the other concurrent data structures at its current state. But about the inline 8-byte key optimization, it wasn't really my fault here. The original paper for the algorithm specifically optimizes for this use case . The other implementations have to allocate keys on the heap.
concurrent_maps fastest │ slowest │ median │ mean │ samples │ iters
├─ 01_get_by_key_size │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 8B 186.3 µs │ 300.7 µs │ 200.2 µs │ 229.3 µs │ 100 │ 100
│ │ ├─ 16B 189.6 µs │ 219.8 µs │ 191.4 µs │ 193.7 µs │ 100 │ 100
│ │ ├─ 24B 192.8 µs │ 451.4 µs │ 196.4 µs │ 209 µs │ 100 │ 100
│ │ ╰─ 32B 181.9 µs │ 204.5 µs │ 185.5 µs │ 186.9 µs │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 8B 80.99 µs │ 104.7 µs │ 82.78 µs │ 83.96 µs │ 100 │ 100
│ │ ├─ 16B 92.29 µs │ 107.5 µs │ 94.15 µs │ 95.22 µs │ 100 │ 100
│ │ ├─ 24B 91.86 µs │ 110.4 µs │ 92.98 µs │ 94.24 µs │ 100 │ 100
│ │ ╰─ 32B 93.33 µs │ 107.2 µs │ 94.24 µs │ 95.64 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 8B 268.7 µs │ 293.9 µs │ 272.9 µs │ 273.6 µs │ 100 │ 100
│ ├─ 16B 269.8 µs │ 300.7 µs │ 273.1 µs │ 274.8 µs │ 100 │ 100
│ ├─ 24B 271.9 µs │ 292.7 µs │ 275.4 µs │ 276.6 µs │ 100 │ 100
│ ╰─ 32B 252.9 µs │ 280.4 µs │ 256.6 µs │ 258.2 µs │ 100 │ 100
├─ 02_insert_by_key_size │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 8B 522.8 µs │ 545 µs │ 530.3 µs │ 530.4 µs │ 100 │ 100
│ │ ├─ 16B 521.3 µs │ 548.7 µs │ 527.9 µs │ 528.1 µs │ 100 │ 100
│ │ ├─ 24B 519.3 µs │ 571.8 µs │ 526 µs │ 526.8 µs │ 100 │ 100
│ │ ╰─ 32B 507.8 µs │ 526.1 µs │ 514.1 µs │ 514.5 µs │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 8B 63.89 µs │ 74.37 µs │ 64.21 µs │ 65.07 µs │ 100 │ 100
│ │ ├─ 16B 200.3 µs │ 218.2 µs │ 202.4 µs │ 203.4 µs │ 100 │ 100
│ │ ├─ 24B 209.2 µs │ 237.1 µs │ 212.1 µs │ 213.3 µs │ 100 │ 100
│ │ ╰─ 32B 219.1 µs │ 241 µs │ 222 µs │ 223.2 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 8B 163.4 µs │ 187.9 µs │ 166.1 µs │ 167.2 µs │ 100 │ 100
│ ├─ 16B 162.6 µs │ 185.3 µs │ 165.4 µs │ 166.3 µs │ 100 │ 100
│ ├─ 24B 162.8 µs │ 180 µs │ 165.7 µs │ 166.4 µs │ 100 │ 100
│ ╰─ 32B 148.8 µs │ 179.6 µs │ 151.5 µs │ 152.6 µs │ 100 │ 100
├─ 03_concurrent_reads_scaling │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 1 9.176 ms │ 14.37 ms │ 11.79 ms │ 11.94 ms │ 100 │ 100
│ │ ├─ 2 12.43 ms │ 23.12 ms │ 14.95 ms │ 15.56 ms │ 100 │ 100
│ │ ├─ 4 15.15 ms │ 33.08 ms │ 26.59 ms │ 26.46 ms │ 100 │ 100
│ │ ├─ 8 37.2 ms │ 67.1 ms │ 53 ms │ 53.11 ms │ 100 │ 100
│ │ ├─ 16 101.5 ms │ 136.8 ms │ 117.9 ms │ 118.3 ms │ 100 │ 100
│ │ ╰─ 32 216.8 ms │ 269.3 ms │ 249.3 ms │ 248.6 ms │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 1 7.631 ms │ 11.48 ms │ 9.847 ms │ 9.454 ms │ 100 │ 100
│ │ ├─ 2 9.673 ms │ 20.49 ms │ 18.49 ms │ 18.31 ms │ 100 │ 100
│ │ ├─ 4 18.56 ms │ 42.79 ms │ 41.85 ms │ 36.72 ms │ 100 │ 100
│ │ ├─ 8 51.31 ms │ 97.08 ms │ 92.97 ms │ 82.56 ms │ 100 │ 100
│ │ ├─ 16 106.3 ms │ 213.4 ms │ 174.9 ms │ 174.5 ms │ 100 │ 100
│ │ ╰─ 32 248.2 ms │ 457.4 ms │ 337.3 ms │ 348.6 ms │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 1 11.14 ms │ 15.18 ms │ 12.96 ms │ 12.97 ms │ 100 │ 100
│ ├─ 2 15.04 ms │ 18.8 ms │ 16.78 ms │ 16.83 ms │ 100 │ 100
│ ├─ 4 19.08 ms │ 39.03 ms │ 32.73 ms │ 32.42 ms │ 100 │ 100
│ ├─ 8 34.58 ms │ 69.68 ms │ 54.76 ms │ 54.17 ms │ 100 │ 100
│ ├─ 16 95.51 ms │ 145.6 ms │ 118.7 ms │ 117.8 ms │ 100 │ 100
│ ╰─ 32 202.2 ms │ 279.8 ms │ 246.6 ms │ 244.9 ms │ 100 │ 100
├─ 04_concurrent_reads_long_keys │ │ │ │ │
│ ├─ indexset_32b │ │ │ │ │
│ │ ├─ 1 4.244 ms │ 7.161 ms │ 5.7 ms │ 5.582 ms │ 100 │ 100
│ │ ├─ 2 6.093 ms │ 14.03 ms │ 8.055 ms │ 9.284 ms │ 100 │ 100
│ │ ├─ 4 10.26 ms │ 20.93 ms │ 15.69 ms │ 15.52 ms │ 100 │ 100
│ │ ├─ 8 25.89 ms │ 42.76 ms │ 33.75 ms │ 33.95 ms │ 100 │ 100
│ │ ╰─ 16 63.39 ms │ 85.28 ms │ 73.51 ms │ 73.81 ms │ 100 │ 100
│ ├─ masstree_32b │ │ │ │ │
│ │ ├─ 1 3.508 ms │ 6.493 ms │ 5.132 ms │ 5.243 ms │ 100 │ 100
│ │ ├─ 2 5.308 ms │ 12.58 ms │ 10.88 ms │ 10.09 ms │ 100 │ 100
│ │ ├─ 4 12.05 ms │ 25.92 ms │ 18.81 ms │ 18.41 ms │ 100 │ 100
│ │ ├─ 8 27.45 ms │ 58.21 ms │ 43.32 ms │ 44.05 ms │ 100 │ 100
│ │ ╰─ 16 65.8 ms │ 119.5 ms │ 87.25 ms │ 90.71 ms │ 100 │ 100
│ ╰─ skipmap_32b │ │ │ │ │
│ ├─ 1 5.047 ms │ 7.937 ms │ 6.049 ms │ 6.182 ms │ 100 │ 100
│ ├─ 2 7.509 ms │ 14.68 ms │ 8.992 ms │ 9.616 ms │ 100 │ 100
│ ├─ 4 15.9 ms │ 25.97 ms │ 19.78 ms │ 19.82 ms │ 100 │ 100
│ ├─ 8 23.76 ms │ 39.68 ms │ 32.59 ms │ 32.86 ms │ 100 │ 100
│ ╰─ 16 57.95 ms │ 78.34 ms │ 68.41 ms │ 68.82 ms │ 100 │ 100
But there's a twist... the C++ implementation used a custom memory allocator (this is way out of my skill levels to even try). Iif we just change the global memory allocator to mimalloc it becomes the faster implementation in all the same benches. The standard global allocator is simply not optimal for the allocation patterns this data structure uses.
Timer precision: 30 ns
concurrent_maps fastest │ slowest │ median │ mean │ samples │ iters
├─ 01_get_by_key_size │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 8B 174.9 µs │ 193.3 µs │ 176.5 µs │ 177.8 µs │ 100 │ 100
│ │ ├─ 16B 181.8 µs │ 205.2 µs │ 183.9 µs │ 185.6 µs │ 100 │ 100
│ │ ├─ 24B 178.2 µs │ 196.6 µs │ 179.6 µs │ 181.3 µs │ 100 │ 100
│ │ ╰─ 32B 175.1 µs │ 194.5 µs │ 177.8 µs │ 178.9 µs │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 8B 74.53 µs │ 98.02 µs │ 75.68 µs │ 77.33 µs │ 100 │ 100
│ │ ├─ 16B 89.61 µs │ 106.2 µs │ 91.18 µs │ 92.05 µs │ 100 │ 100
│ │ ├─ 24B 90.55 µs │ 105 µs │ 91.85 µs │ 92.86 µs │ 100 │ 100
│ │ ╰─ 32B 90.57 µs │ 103.5 µs │ 91.28 µs │ 92.32 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 8B 256 µs │ 278.8 µs │ 257.8 µs │ 259.9 µs │ 100 │ 100
│ ├─ 16B 272.3 µs │ 292.1 µs │ 275.2 µs │ 276.9 µs │ 100 │ 100
│ ├─ 24B 251.7 µs │ 278.9 µs │ 254.6 µs │ 256.6 µs │ 100 │ 100
│ ╰─ 32B 248.5 µs │ 269.7 µs │ 251.6 µs │ 253 µs │ 100 │ 100
├─ 02_insert_by_key_size │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 8B 463.1 µs │ 491.1 µs │ 468.4 µs │ 468.8 µs │ 100 │ 100
│ │ ├─ 16B 461.6 µs │ 484.5 µs │ 466.5 µs │ 466.4 µs │ 100 │ 100
│ │ ├─ 24B 453.4 µs │ 503.9 µs │ 455.2 µs │ 458.3 µs │ 100 │ 100
│ │ ╰─ 32B 444.8 µs │ 469.1 µs │ 447.8 µs │ 449.2 µs │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 8B 35.71 µs │ 59.89 µs │ 35.87 µs │ 37.86 µs │ 100 │ 100
│ │ ├─ 16B 104.4 µs │ 130.6 µs │ 105.9 µs │ 107.4 µs │ 100 │ 100
│ │ ├─ 24B 109.3 µs │ 156 µs │ 111.6 µs │ 112.7 µs │ 100 │ 100
│ │ ╰─ 32B 111.9 µs │ 137.7 µs │ 114.1 µs │ 115.4 µs │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 8B 145.2 µs │ 172.7 µs │ 151 µs │ 151.6 µs │ 100 │ 100
│ ├─ 16B 145.4 µs │ 165.6 µs │ 147.2 µs │ 148.3 µs │ 100 │ 100
│ ├─ 24B 134.4 µs │ 185.3 µs │ 138.1 µs │ 139 µs │ 100 │ 100
│ ╰─ 32B 132.1 µs │ 163.3 µs │ 135.1 µs │ 136 µs │ 100 │ 100
├─ 03_concurrent_reads_scaling │ │ │ │ │
│ ├─ indexset │ │ │ │ │
│ │ ├─ 1 5.518 ms │ 8.801 ms │ 7.008 ms │ 6.983 ms │ 100 │ 100
│ │ ├─ 2 7.033 ms │ 11.95 ms │ 9.189 ms │ 9.18 ms │ 100 │ 100
│ │ ├─ 4 9.854 ms │ 16.06 ms │ 13.06 ms │ 13.05 ms │ 100 │ 100
│ │ ├─ 8 15.53 ms │ 19.93 ms │ 17.26 ms │ 17.39 ms │ 100 │ 100
│ │ ├─ 16 28.25 ms │ 33.93 ms │ 30.72 ms │ 30.72 ms │ 100 │ 100
│ │ ╰─ 32 52.93 ms │ 62.44 ms │ 57.55 ms │ 57.69 ms │ 100 │ 100
│ ├─ masstree │ │ │ │ │
│ │ ├─ 1 4.536 ms │ 6.213 ms │ 5.623 ms │ 5.51 ms │ 100 │ 100
│ │ ├─ 2 5.712 ms │ 9.303 ms │ 7.342 ms │ 7.341 ms │ 100 │ 100
│ │ ├─ 4 8.088 ms │ 13.08 ms │ 10.28 ms │ 10.2 ms │ 100 │ 100
│ │ ├─ 8 11.39 ms │ 20.9 ms │ 15.05 ms │ 14.99 ms │ 100 │ 100
│ │ ├─ 16 23.39 ms │ 31.51 ms │ 26.93 ms │ 26.98 ms │ 100 │ 100
│ │ ╰─ 32 46.32 ms │ 57.52 ms │ 51.09 ms │ 51.07 ms │ 100 │ 100
│ ╰─ skipmap │ │ │ │ │
│ ├─ 1 6.382 ms │ 9.79 ms │ 8.071 ms │ 8.088 ms │ 100 │ 100
│ ├─ 2 8.853 ms │ 13.66 ms │ 9.742 ms │ 9.976 ms │ 100 │ 100
│ ├─ 4 10.99 ms │ 16.41 ms │ 13.12 ms │ 13.27 ms │ 100 │ 100
│ ├─ 8 16.04 ms │ 27.1 ms │ 17.48 ms │ 17.75 ms │ 100 │ 100
│ ├─ 16 28.47 ms │ 35.69 ms │ 30.92 ms │ 30.93 ms │ 100 │ 100
│ ╰─ 32 53.7 ms │ 63.41 ms │ 58.27 ms │ 58.18 ms │ 100 │ 100
├─ 04_concurrent_reads_long_keys │ │ │ │ │
│ ├─ indexset_32b │ │ │ │ │
│ │ ├─ 1 2.796 ms │ 4.567 ms │ 3.624 ms │ 3.552 ms │ 100 │ 100
│ │ ├─ 2 4.125 ms │ 6.036 ms │ 5.065 ms │ 5 ms │ 100 │ 100
│ │ ├─ 4 5.825 ms │ 11.37 ms │ 7.323 ms │ 7.463 ms │ 100 │ 100
│ │ ├─ 8 7.756 ms │ 11.95 ms │ 9.196 ms │ 9.293 ms │ 100 │ 100
│ │ ╰─ 16 14.75 ms │ 18.04 ms │ 16.43 ms │ 16.47 ms │ 100 │ 100
│ ├─ masstree_32b │ │ │ │ │
│ │ ├─ 1 2.673 ms │ 4.032 ms │ 3.081 ms │ 3.049 ms │ 100 │ 100
│ │ ├─ 2 3.55 ms │ 7.098 ms │ 3.964 ms │ 4.233 ms │ 100 │ 100
│ │ ├─ 4 5.237 ms │ 7.709 ms │ 6.256 ms │ 6.32 ms │ 100 │ 100
│ │ ├─ 8 6.397 ms │ 10.04 ms │ 8.479 ms │ 8.474 ms │ 100 │ 100
│ │ ╰─ 16 12.91 ms │ 21.11 ms │ 15.57 ms │ 15.67 ms │ 100 │ 100
│ ╰─ skipmap_32b │ │ │ │ │
│ ├─ 1 3.693 ms │ 5.395 ms │ 4.08 ms │ 4.107 ms │ 100 │ 100
│ ├─ 2 4.691 ms │ 6.9 ms │ 5.123 ms │ 5.366 ms │ 100 │ 100
│ ├─ 4 4.911 ms │ 9.255 ms │ 7.031 ms │ 6.947 ms │ 100 │ 100
│ ├─ 8 8.064 ms │ 12.75 ms │ 10.18 ms │ 10.18 ms │ 100 │ 100
│ ╰─ 16 14.81 ms │ 18.8 ms │ 16.64 ms │ 16.68 ms │ 100 │ 100
Hi, sorry to bother again, but since you already had a look at the benchmark methodologies, I was wondering if you could take another look at the source to suggest further fairness issues. I have tried to address your points with fixed-size keys (no per-op heap allocation for any of the impls), multiple key sizes, overlapping/random/Zipfian patterns, and thread sweeps up to 32. I would HIGHLY appreciate it if you could take a look and see whether it's currently fair enough or if I could tighten things up more. Because currently I am getting unusually good results for read ops in comparison to std RwLock, Mutex and against both SkilList and indexset:
This bench was particularly desinged to stress layering and lengthier key variations. The unusually high performance for masstree with mimalloc (even standard global allocator too) doesn't make sense. I think I am doing something that is still giving this impl an unfair advantage, but I can't figure it out :'D
concurrent_maps fastest │ slowest │ median │ mean │ samples │ iters
╰─ 14_concurrent_reads_long_keys_shared_prefix_deep │ │ │ │ │
├─ indexset_32b │ │ │ │ │
│ ├─ 1 1.011 ms │ 2.578 ms │ 1.052 ms │ 1.239 ms │ 100 │ 100
│ ├─ 2 1.825 ms │ 2.892 ms │ 2.152 ms │ 2.162 ms │ 100 │ 100
│ ├─ 4 2.46 ms │ 3.139 ms │ 2.609 ms │ 2.627 ms │ 100 │ 100
│ ├─ 8 2.545 ms │ 3.978 ms │ 2.726 ms │ 2.795 ms │ 100 │ 100
│ ╰─ 16 4.308 ms │ 5.697 ms │ 4.701 ms │ 4.755 ms │ 100 │ 100
├─ masstree_32b │ │ │ │ │
│ ├─ 1 486.5 µs │ 1.046 ms │ 504.1 µs │ 529.2 µs │ 100 │ 100
│ ├─ 2 716.1 µs │ 1.489 ms │ 740.3 µs │ 774.9 µs │ 100 │ 100
│ ├─ 4 739 µs │ 1.168 ms │ 786.8 µs │ 808.2 µs │ 100 │ 100
│ ├─ 8 866.8 µs │ 1.433 ms │ 1.128 ms │ 1.117 ms │ 100 │ 100
│ ╰─ 16 1.286 ms │ 1.855 ms │ 1.374 ms │ 1.416 ms │ 100 │ 100
╰─ skipmap_32b │ │ │ │ │
├─ 1 1.621 ms │ 3.745 ms │ 1.673 ms │ 1.915 ms │ 100 │ 100
├─ 2 2.121 ms │ 3.89 ms │ 2.85 ms │ 2.862 ms │ 100 │ 100
├─ 4 2.69 ms │ 3.792 ms │ 2.889 ms │ 3.037 ms │ 100 │ 100
├─ 8 2.611 ms │ 3.974 ms │ 3.339 ms │ 3.253 ms │ 100 │ 100
╰─ 16 4.682 ms │ 5.523 ms │ 4.865 ms │ 4.904 ms │ 100 │ 100
concurrent_maps fastest │ slowest │ median │ mean │ samples │ iters
╰─ 15_mixed_long_keys_zipfian_shared_prefix │ │ │ │ │
├─ indexset_32b │ │ │ │ │
│ ├─ 1 1.391 ms │ 2.792 ms │ 1.809 ms │ 1.807 ms │ 100 │ 100
│ ├─ 2 1.759 ms │ 3.159 ms │ 2.503 ms │ 2.51 ms │ 100 │ 100
│ ├─ 4 2.411 ms │ 3.231 ms │ 2.788 ms │ 2.789 ms │ 100 │ 100
│ ├─ 8 3.192 ms │ 3.748 ms │ 3.414 ms │ 3.425 ms │ 100 │ 100
│ ╰─ 16 4.438 ms │ 6.314 ms │ 5.046 ms │ 5.057 ms │ 100 │ 100
├─ masstree_32b │ │ │ │ │
│ ├─ 1 974.7 µs │ 1.774 ms │ 1.529 ms │ 1.472 ms │ 100 │ 100
│ ├─ 2 1.637 ms │ 2.354 ms │ 1.941 ms │ 1.93 ms │ 100 │ 100
│ ├─ 4 1.997 ms │ 2.724 ms │ 2.308 ms │ 2.327 ms │ 100 │ 100
│ ├─ 8 2.734 ms │ 3.693 ms │ 3.123 ms │ 3.134 ms │ 100 │ 100
│ ╰─ 16 3.258 ms │ 10.35 ms │ 3.909 ms │ 4.425 ms │ 100 │ 100
╰─ skipmap_32b │ │ │ │ │
├─ 1 2.379 ms │ 3.976 ms │ 3.372 ms │ 3.209 ms │ 100 │ 100
├─ 2 3.197 ms │ 4.169 ms │ 3.752 ms │ 3.723 ms │ 100 │ 100
├─ 4 3.433 ms │ 4.377 ms │ 3.856 ms │ 3.841 ms │ 100 │ 100
├─ 8 3.861 ms │ 5.108 ms │ 4.624 ms │ 4.666 ms │ 100 │ 100
╰─ 16 6.243 ms │ 8.001 ms │ 6.653 ms │ 6.7 ms │ 100 │ 100
BTreeMap:
╰─ 12_concurrent_reads_long_keys_shared_prefix_deep │ │ │ │ │
├─ masstree_32b │ │ │ │ │
│ ├─ 1 471 µs │ 1.344 ms │ 493.1 µs │ 551.3 µs │ 100 │ 100
│ ├─ 2 681.7 µs │ 1.347 ms │ 734.8 µs │ 745.7 µs │ 100 │ 100
│ ├─ 4 718.6 µs │ 1.139 ms │ 784.7 µs │ 802.9 µs │ 100 │ 100
│ ├─ 8 771.3 µs │ 1.51 ms │ 1.101 ms │ 1.064 ms │ 100 │ 100
│ ╰─ 16 1.259 ms │ 1.994 ms │ 1.368 ms │ 1.42 ms │ 100 │ 100
├─ mutex_btreemap_32b │ │ │ │ │
│ ├─ 1 785.7 µs │ 1.537 ms │ 827.3 µs │ 841.4 µs │ 100 │ 100
│ ├─ 2 2.521 ms │ 4.294 ms │ 3.745 ms │ 3.681 ms │ 100 │ 100
│ ├─ 4 6.341 ms │ 8.777 ms │ 7.442 ms │ 7.382 ms │ 100 │ 100
│ ├─ 8 13.83 ms │ 19.51 ms │ 16.79 ms │ 16.91 ms │ 100 │ 100
│ ╰─ 16 32.67 ms │ 34.39 ms │ 33.29 ms │ 33.3 ms │ 100 │ 100
╰─ rwlock_btreemap_32b │ │ │ │ │
├─ 1 799 µs │ 1.766 ms │ 826.9 µs │ 966.5 µs │ 100 │ 100
├─ 2 1.192 ms │ 1.978 ms │ 1.422 ms │ 1.454 ms │ 100 │ 100
├─ 4 1.569 ms │ 2.003 ms │ 1.656 ms │ 1.672 ms │ 100 │ 100
├─ 8 2.065 ms │ 2.545 ms │ 2.147 ms │ 2.168 ms │ 100 │ 100
╰─ 16 3.023 ms │ 3.47 ms │ 3.108 ms │ 3.131 ms │ 100 │ 100