Re: [PATCH RFC 0/2] rcu skiplists v2

[Chris Mason <clmason@fusionio.com>]

Quoting Mathieu Desnoyers (2013-06-26 19:02:18)
> > The IOMMU part of the patch is updated slightly, but still not using all
> > the new bits in the API.  This is mostly because the IOMMU part is going
> > to change later on and I'm really only using it for testing now.
> > 
> > For benchmarking, the IOMMU numbers are slightly higher than last time,
> > but not more than 5% or so.  This is because the bottleneck is still
> > skiplist_insert_hole(), which I haven't really changed in this round.
> > 
> > Most of my benchmarking now is with the skiplist_test module, which has
> > expanded to a few new cases.  For random operations, my performance is
> > slightly slower than rbtree when single threaded.
> > 
> > Random lookups on 10 million items: (inserts are similar)
> > 
> > rbtree       random lookup time 4 s 327 ms
> > skiplist-rcu random lookup time 5 s 175 ms 
> 
> These benchmarks are only considering averages.
> 
> I'm worried that the skiplist approach has chances to create long chains
> (probabilistically non-zero). Clearly, the lack of bound is something
> the RT guys might frown upon. I'd be curious to see how long the worse
> chains encountered can be on, say, 1000 machines stress-testing this for
> a week.

Correct, the probability part may run into problems for RT.  I haven't
put in instrumentation for worst case.  I think my retries (goto again)
for concurrent update are a bigger RT problem, but they can be cut down
significantly.

> 
> FWIW, my benchmark of RCU Judy array with ranges in similar conditions:
> 
> - Using 32-bit key length
> - I first populated 10M ranges of len = 1, sequentially.
> - Then, I run a reader threads for 10s, which perform random lookups
>   (all successful) in keys from 0 to 10M.

Similar, I had 64 bit keys and the lookups were totally random (not all
successful).  I doubt it matters too much for these numbers.

Also, my benchmarks were not just inserting keys but keys pointing to
things.  So a lookup walked the tree and found an object and then
returned the object.  radix can just return a key/value without
dereferencing the value, but that wasn't the case in my runs.

> > Single threaded rbtree does consistently win across all sizes of lists:
> > 
> > skiplist-rcu thread 0 time 0 s 287 ms
> > rbtree thread       0 time 0 s 215 ms
> 
> Are the 287ms and 215ms numbers you get for skiplist-rcu and rbtree the
> total for 10M add/delete, or is it per operation, or is it a different
> number of operations altogether ? Also, how many items are present in
> the data structures in average ?

The 287 and 215ms were total run time for the mixed bag of operations.
It had lookups, single  delete then re-insert and bulk (128 keys) delete
then re-insert.  There were always the same number of items present
(10M).

It looks like you have some strong numbers here, especially considering
that my test was all in kernel vs userland rcu.

-chris