  Although a wide variety of handcrafted concurrent data structures have been
proposed, there is considerable interest in universal approaches (henceforth
called Universal Constructions or UCs) for building concurrent data structures.
These approaches (semi-)automatically convert a sequential data structure into
a concurrent one. The simplest approach uses locks that protect a sequential
data structure and allow only one process to access it at a time. The resulting
data structures use locks, and hence are blocking. Most work on UCs instead
focuses on obtaining non-blocking progress guarantees such as
obstruction-freedom, lock-freedom, or wait-freedom. Many non-blocking UCs have
appeared. Key examples include the seminal wait-free UC by Herlihy, a
NUMA-aware UC by Yi et al., and an efficient UC for large objects by Fatourou
et al.
  We borrow ideas from persistent data structures and multi-version concurrency
control (MVCC), most notably path copying, and use them to implement concurrent
versions of sequential persistent data structures. Despite our expectation that
our data structures would not scale under write-heavy workloads, they scale in
practice. We confirm this scaling analytically in our model with private
per-process caches.
