support that. LF requires a mechanism to garbage collect
memory, such as hazard pointers13 or epoch reclamation; 4
these mechanisms can reduce performance by 5x. We do not
use these mechanisms, so the reported numbers for LF are
better than in reality.
Summary of results. On the real data structures (Section
4. 1), we find that NR outperforms other methods at many
threads under high operation contention, with the exception of NUMA-aware algorithms tailored to the data structure. The other methods, including lock-free algorithms,
tend to lose significant performance beyond a NUMA node.
We also find that NR consumes more memory than other
methods. On a real application’s data structures (Section
4. 2), NR outperforms alternatives by 2.6x–14x on workloads
with 10% updates, or by 1.1x– 4.4x on 100% updates.
Testbed. We use a Dell server with 512GB RAM and 56
cores on four Intel Xeon E7-4850v3 processors at 2.2GHz.
Each processor is a NUMA node with 14 cores, a 35MB
shared L3 cache, and a private L2/L1 cache of size
256KB/64KB per core. Each core has 2 hyper-threads for a
total of 112 hyper-threads. Cache lines have 64B.
4. 1. Real data structures
These experiments use two real data structures: a skip list
priority queue and a skip list dictionary. (Additional results
using two other data structures are given in Calciu, Sen
et al., 3 but these results are qualitatively similar to the ones
we present here.) A priority queue provides two update operations and one read-only operation: insert(i) inserts element i,
deleteMin() removes and returns the smallest element, and
findMin() returns the smallest element without removing it.
We implement these operations using a skip list to order the
elements and keep the minimum at the beginning of the
list. A dictionary provides operations to insert, lookup, and
remove elements, and we use a skip list to provide the dictionary. NR, FC, and FC+ internally use the same single-threaded implementation of a skip list; 15 FC uses the flat
combining implementation from Hendler et al. 5 For the LF,
we use the skip-list-based priority queue and skip list dictionary from Herlihy and Shavit. 7
We use the benchmark from the flat combining paper, 5
which runs a mix of generic add, remove, and read operations. We map these operations to each data structure as
shown here.
generic priorityqueue dictionary
add insert(rnd, v) insert(rnd, v)
remove deleteMin() delete(rnd)
read findMin() lookup(rnd)
Here, rnd indicates a key chosen at random and v is an arbitrary value. We use the same ratio of add and remove to
keep the data structure size approximately constant over
time, and the results aggregate these two operations as
“update operations.” We consider two ratios of update-to-read operations: 10%, 100% updates (90%, 0% reads). For
the priority queue, we choose random keys from a uniform
distribution. For the dictionary, we vary the operation contention by drawing the keys from two distributions: uniform (low contention) and zipf with parameter 1. 5 (high
contention).
Coupled data structures. In some applications, data
structures are read or updated together. For example, Redis
implements sorted sets using a hash table and a skip list,
which are updated atomically by each request. NR can provide these atomic updates, by treating the data structures as
a single larger data structure with combined operations.
Fake update operations. Some update operations become
readonly during execution (e.g., remove of a nonexistent
key). Black-box methods must know about read-only operations at invocation time. If updates become read-only often,
one can first attempt to execute them as read-only and, if not
possible, then execute them as updates (e.g., remove(key)
first tries to look up the key). This requires a simple wrapper
around remove(). We did not implement this.
4. EVALUATION
We have evaluated NR to answer five broad questions: How
does NR scale with the number of cores for different data
structures and workloads? How does NR compare with other
concurrent data structures? What is the benefit of NR to real
applications? How does NR behave on different NUMA
architectures? What are the benefits of NR’s techniques?
What are the costs of NR? Here, we highlight the most repre-
sentative results and focus on the first three questions; the
complete set of results are available in Calciu, Sen et al. 3 We
report on two classes of experiments:
• Real Data Structures (Section 4. 1): We run micro-
benchmarks on real data structures: a skip list priority
queue and a skip list dictionary.
• Real Application (Section 4. 2): We run macro-benchmarks
on the data structures of a real application: the Redis
storage server modified to use many threads.
We compare NR against other methods (baselines) shown
in Figure 4. Single Lock (SL) and Readers-Writer Lock (RWL)
are methods often used in practice; they work by protecting
the data structure with a SL or a single RWL. For RWL we use
the same readers-writer lock as NR (Section 3. 8). FC consists
of flat combining used to implement the entire data structure. FC can be used as a black-box method, but it can also
use data-structure-specific optimizations to combine operations for faster execution (hence its name); we use these
optimizations whenever possible. FC+ is an improvement of
FC by using a readers-writer lock to execute read-only operations more efficiently. Lock-Free Baseline (LF) is a lock-free
algorithm specialized for a specific data structure; this baseline is available only for some data structures. In the real
application (Redis), threads must atomically update multiple data structures but existing lock-free algorithms do not
Figure 4. Other methods for comparison (baselines).
Baseline Description
SL One big lock (spinlock)
RWL One big readers-writer lock
FC Flat combining
FC+ Flat combining with readers-writer lock
LF Lock-free algorithm