Two-Phase Grace Sharing Userspace RCU

This week we interrupt our regular topic of queues to talk about userspace RCU.

Andreia and I came up with two new algorithms for doing simple Userspace RCU (URCU) with "grace sharing", using only the C11/C++1x memory model and its atomics API.
Grace sharing is an important feature of URCU because without it the scalability of calls to synchronize_rcu() will be at best flat.
We wrote a small brief announcement about the two algorithms and you can get it here:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/gracesharingurcu-2016.pdf

The first and simplest is "Grace Version" which we called "Readers Version" on a previous post:
http://www.concurrencyfreaks.com/2016/09/a-simple-userspace-rcu-in-java.html
The second one, which we never talked about before, is called "Two-Phase".

Why have two algorithms for doing the same thing, Grace Version and Two-Phase?

Well, because Grace Version requires each thread to have a unique id so that it has a unique entry in an array. This means that in your application you need to know how many threads are doing read-side critical sections. This isn't always easy in practice, so, in those cases, you can use the Two-Phase algorithm. The main advantage of the Two-Phase algorithm is that it can use any kind of ReadIndicator.
I've blabered about ReadIndicators before, and if you want to know more about those you can look at my CppCon talk from last year:
https://www.youtube.com/watch?v=FtaD0maxwec
and on this post:
http://www.concurrencyfreaks.com/2014/11/a-catalog-of-read-indicators.html

In the Two-Phase algorithm any ReadIndicator can be used, particularly, one of our favourites which is an array of atomic counters where each reader does fetch-and-add to increment based on a hash of its thread's id, and decrement when leaving the read-side critical section.
This idea isn't new, and two-phased protocols have been used by Bullet-Proof URCU and even our Left-Right technique uses it:
https://github.com/urcu/userspace-rcu
http://www.concurrencyfreaks.com/2013/12/left-right-concurrency-control.html
For such ReadIndicators, no thread registration is needed, which is much more versatile and a much more friendly API to be able to deploy URCU in your application.
However, in our Two-Phase algorithm the grace periods can be shared by multiple threads simultaneously calling synchronize_rcu(), which provides a better scalability for the "updaters" (threads calling synchronize_rcu(). We never thought about this approach before because for Left-Right it doesn't make sense to use an URCU like that, seen that there can only be one updater (writer) at any given time.

How does the Two-Phase algorithm works?

The best is to read the paper, but the main idea is simple: start from the usual two-phase protocols using two ReadIndicators (like Classical Left-Right) and then exit from each of the loops if the version has advanced enough to guarantee that some other updater has seen the opposite ReadIndicator as being empty.
If none of this makes sense, then just go and take a look at the Left-Right paper to see where these ideas came from  ;)
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/left-right-2014.pdf

Benchmarking:

On the first plot we're comparing just pure readers: how fast can you do rcu_read_lock()/unlock(). The results show that both our Grace Version and Two-Phase using one entry per thread have the same (nearly linear) scalability, with the Two-Phase using an array of counters being close below. Notice that neither the Two-Phase CountersArray nor the Bullet-Proof need thread registration, while the other implementations do.



The second plot shows what happens when we're just calling synchronize_rcu() without any ongoing readers. This scenario is interesting to see the overhead in synchronization.
Our three algorithms behave more or less the same, while the previous URCU implementations are way below.
This isn't a completely fair comparison because URCU Bullet-Proof and URCU Default do other things like handle call_rcu() and others, which incurs overheads, but anyways, if you don't need anything else besides rcu_read_lock()/unlock() and synchronize_rcu(), then our implementations will do great.


The third plot shows the effects os grace sharing: there are two readers threads and the rest are updaters. The read-site critical sections are long, at least long enough not to notice the difference in overhead of the different algorithms (seen on plot above).
The main effect here is the sharing of the grace period and it's easy to see that Bullet-Proof is the only one that is incapable of sharing the grace period.



In essence, if all you need is an URCU with the APIs rcu_read_lock(), rcu_read_unlock() and synchronize_rcu(), then our algorithms are the best in all tested scenarios, so feel free to copy them in your code base, or use one of the implementations we have in github:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/papers/gracesharingurcu/URCUTwoPhase.hpp
https://github.com/pramalhe/ConcurrencyFreaks/tree/master/CPP/papers/gracesharingurcu


And now, back to queues...

URCU ReadersVersion in C++

On the previous post we showed a new Userspace RCU (URCU) algorithm that can be implemented with just a atomics and the Java/C11/C++1x memory model.
Here is the implementation in C++:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/papers/gracesharingurcu/URCUGraceVersion.hpp

Not only is this code simple enough to just copy/paste into your codebase, but it has a pretty good throughput and scales well.
This seems to be the best basic implementation of an URCU (with just atomics) in all possible scenarios. There may be other implementations that surpass it, but they would definitely have to use some non-portable trickery, which URCUs usually do, stuff like using POSIX signals, or some CPU special instructions, or some Kernel API.
Anyways, if you're interested in portable low-overhead memory reclamation for C/C++ that is wait-free population oblivious for readers and blocking for updaters, yet capable of aggregating grace periods, then this should do the trick for you!

We did a simple benchmark against two of the URCU implementations in the userspace urcu lib http://liburcu.org/ and we'll make the benchmark available in a couple weeks, but in the meantime here are some plots below.
We compared against the Bullet-Proof URCU and the default URCU. More details in this readme https://github.com/urcu/userspace-rcu

The first plot shows just readers, i.e. calls to rcu_read_lock()/rcu_read_unlock(), where the read-side critical section is just an atomic load on a global variable. This means the read-side critical section is as short as possible, and that if there is any contention is caused by the overhead in rcu_read_lock()/rcu_read_unlock(). As you can see from the plots, all three scale well, but the ReadersVersion is the one that scales better.




The second plot shows just calls to synchronize_rcu() and none of the methods scale (more on this in another post) but at least they don't dropoff as the number of threads increases, and ReadersVersion is about 10x faster than the other two URCUs.



The third plot shows again calls to synchronize_rcu() but this time there are two other thread that are continuously doing rcu_read_lock/rcu_read_unlock. The read-side critical section is very long, it consists of reading an array with 100000 entries, which means the time is dominated by the waiting for the readers and not by the synchronization mechanism inside synchronize_rcu().
Again here, ReadersVersion scales well because it aggregates grace periods, and so does the default urcu but doesn't have as good scalability as that. Bullet-Proof has no mechanism for sharing grace periods, and therefore, has no scalability on this kind of scenario.