BTree benchmark gnuplot.
There is a balanced btree in the lock-free literature - but this btree
is something I threw together off the top of my head a little while ago
just to get something tree-like out there; it's add-only, and unbalanced.
This is a *preliminary* result. I've literally just got the gnuplot
output working, and the benchmark is only a few days old - my concern is
that the locking benchmarks may be underplaying their performance - I
may have them performing four locks per iteration when they should only
be performing two - but I need to think more about how the benchmark
works, whether or not what they're doing now is fair; it's not obviously
Either way I think it won't matter - you can see in the final chart just
how poorly locking scales compared to non-locking - even if locking
doubled in performance, they'd all still be half the speed of lock-free.
This of course is not THE btree, the balanced lock-free normal
add-and-delete btree, but it's hopefully gives a good indication of what
general performance can be expected.
Having said all that, a lock-free hash, a real one, ought to scale
pretty much linearly, so it'll put the btree in the shade =-)