rrnewton
commented
10 years ago TODO item: explore the variations of this test more. Random insertion orders, work between insertions, and figure out how much of the space falls into this performance divot.
Microbenchmarks like this with no actual work can be especially good at finding perverse contention situations.
I'm not 100% certain, but SLM2 and SLM3 are probably best run with one thread taking the lead and doing all the real work (uncontended) and the other threads following along and fizzling concurrently.
Even if this is not actually a bug, it still may be a good example of a place where judicious back-off would help.
The concurrent skiplist algorithm shouldn't have particular bad behavior when inserting either sorted or reverse sorted inputs, should it?
Yet with more than one thread writing the keys [n,n-1..1] simultaneously (slm3), there's a major slowdown that doesn't exist when each thread writes [1..n] in order (slm2).
One rev you can use for reproducing is 19934df2706e45adf195c68c1818e5b240cf3e43.
CC @aturon