Predicate RCU

Predicate RCU (PRCU) is a variant of RCU
offering a wait-for-readers (aka synchronize_rcu) operation that
can complete 10x-100x faster than standard RCU's wait-for-readers.
PRCU achieves this by allowing wait-for-readers to wait only for the
completion of a subset of pre-existing RCU read-side critical sections,
instead of all readers. The subset is specified using a user-defined
predicate. (Some PRCU variants require an iterable predicate
representation, which is described later.)

PRCU thus facilitates using RCU as a general-purpose synchronization
mechanism. PRCU is particularly suitable for algorithms with scalable,
fine-grained, concurrent update operations that have wait-for-readers
on their critical path. In such cases standard wait-for-readers
quickly becomes a dominating bottleneck, but it is often possible to
define predicates so that wait-for-readers times drastically decrease
and remove the bottleneck.

PRCU is described in detail in the paper

Predicate RCU: An RCU for Scalable Concurrent Updates, PPoPP 2015
Maya Arbel and Adam Morrison (Technion)

PRCU implementations

Running make builds libraries implementing the three PRCU algorithms
described in the paper:

  • EER-PRCU evaluates the predicate for each reader. Compared to Userspace RCU, wait-for-readers time decreases by 10x and read overhead is comparable.

  • D-PRCU exploits the domain of values, requires an iterable predicate (see below) for good performance. wait-for-readers time decreases by 100x, but read overhead increases, especially if readers specify the same values.

  • DEER-PRCU uses the domain of data structure values, but waits for each reader. Requires an iterable predicate for good performance. Compared to Userspace RCU, wait-for-readers time decreases by 10x and read overhead is comparable.

Using PRCU

We follow the API of the paper:

  1. Initialize RCU by calling prcu_init(int num_threads).
  2. Each thread must call prcu_register(int id), where id is an integer from the range {0,..., num_threads-1}.
  3. Read-side critical sections are encapsulated in prcu_enter(int value)/prcu_exit(int value), where value is what the predicate evaluates.
  4. wait-for-readers is implemented via a prcu_wait_for_readers(predicate pred, int min, range_predicate pred_next, predicate_info pred_info) call, where pred is a regular (non-iterable predicate), min is the first buckets, pred_next is the predicate bucket iterator starting at min (see below).

Iterable predicates

D-PRCU and DEER-PRCU use an iterable predicate, which is represented as the set
of values for which it holds. (As opposed to a function taking a value and
returning true/false.) Our representation of iterable predicates consists of
a min bucket---the first hash bucket for which the predicate holds---and a
pred_next function that implements an iterator over the buckets for which
the predicate holds, starting at min.

Technically, pred_next takes a current bucket and the pred_info structure,
and return the next bucket. The pred_info can be used to additional data
from the caller of wait-for-readers to pred_next. See the comments in
prcu.h for further information.

PRCU example: Citrus

As an example of using PRCU, we provide an implementation of the Citrus RCU-based
concurrent binary search tree that is modified to work with PRCU (citrus.c).
The Citrus tree implementation provides the standard set insert/delete/contains
API. It can also be compiled with the Userspace RCU library by defining EXTERNAL_RCU.

The Citrus tree algorithm is described in detail in the following paper:

Concurrent Updates with RCU: Search Tree as an Example, PODC 2014
Maya Arbel and Hagit Attiya (Technion)

The Citrus code contains an example an iterable predicate.

Citrus usage tips

  1. Initialize the tree by calling init(int max_key), where max_key is the largest key used by any operation. If unknown use a negative number to use the default max integer value.
  2. Initialize PRCU and register each thread, as described above.
  3. Run with a scalable memory allocator, for example jemalloc.


Copyright 2015
Maya Arbel (mayaarl [at] cs [dot] technion [dot] ac [dot] il).
Adam Morrison (mad [at] cs [dot] technion [dot] ac [dot] il).

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see