countblanklinestrue[t]#1

# Practically and Theoretically Efficient
Garbage Collection for Multiversioning

Yuanhao Wei<EMAIL_ADDRESS>0000-0002-5176-0961 Carnegie Mellon
UniversityUSA ,  Guy E. Blelloch<EMAIL_ADDRESS>0000-0003-0224-9187 Carnegie
Mellon UniversityUSA ,  Panagiota Fatourou<EMAIL_ADDRESS>0000-0002-6265-6895 FORTH ICS and University of CreteGreece and  Eric Ruppert
<EMAIL_ADDRESS>0000-0001-5613-8701 York UniversityCanada

(2023)

###### Abstract.

Multiversioning is widely used in databases, transactional memory, and
concurrent data structures. It can be used to support read-only transactions
that appear atomic in the presence of concurrent update operations. Any system
that maintains multiple versions of each object needs a way of efficiently
reclaiming them. We experimentally compare various existing reclamation
techniques by applying them to a multiversion tree and a multiversion hash
table.

Using insights from these experiments, we develop two new multiversion garbage
collection (MVGC) techniques. These techniques use two novel concurrent
version list data structures. Our experimental evaluation shows that our
fastest technique is competitive with the fastest existing MVGC techniques,
while using significantly less space on some workloads. Our new techniques
provide strong theoretical bounds, especially on space usage. These bounds
ensure that the schemes have consistent performance, avoiding the very high
worst-case space usage of other techniques.

††journalyear: 2023††copyright: rightsretained††conference: The 28th ACM
SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming;
February 25-March 1, 2023; Montreal, QC, Canada††booktitle: The 28th ACM
SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming
(PPoPP ’23), February 25-March 1, 2023, Montreal, QC, Canada††doi:
10.1145/3572848.3577508††isbn: 979-8-4007-0015-6/23/02††copyright: none††ccs:
Computing methodologies Concurrent algorithms

##  1\. Introduction

Multiversion concurrency control is used widely in database systems (Reed,
1978; Bernstein and Goodman, 1983; Papadimitriou and Kanellakis, 1984; Lee et
al., 2016; Neumann et al., 2015; Wu et al., 2017), transactional memory
(Perelman et al., 2010; Fernandes and Cachopo, 2011; Perelman et al., 2011;
Kumar et al., 2014; Keidar and Perelman, 2015), and shared data structures
(Basin et al., 2020; Fatourou et al., 2019; Nelson-Slivon et al., 2022; Wei et
al., 2021), mainly for supporting read-only transactions (abbreviated as
rtxs), including complex multi-point queries that appear atomic, while update
operations are executed concurrently. This is usually achieved by maintaining
a list of previous versions for each object, sorted by timestamps indicating
when the object was updated. An rtx gets a timestamp $t$ and traverses
objects’ version lists, to read the latest version at or before $t$.

Multiversion garbage collection (MVGC) is the problem of removing and
collecting obsolete versions. Suppose two consecutive versions in the version
list have timestamps $t_{1}$ and $t_{2}$. The version with timestamp $t_{1}$
is _needed_ if there is an ongoing rtx whose timestamp $t$ satisfies
$t_{1}\leq t<t_{2}$, and _obsolete_ otherwise. The latest version is always
needed. Efficient MVGC is an important problem in multiversioning systems (Lu
and Scott, 2013; Böttcher et al., 2019; Lee et al., 2016; Ben-David et al.,
2021; Fernandes and Cachopo, 2011; Neumann et al., 2015; Kim et al., 2019;
Nelson-Slivon et al., 2022; Wei et al., 2021), since keeping obsolete versions
can lead to excessive space usage.

The simplest approach to MVGC is to use epoch-based reclamation (EBR)
(Fernandes and Cachopo, 2011; Neumann et al., 2015; Kim et al., 2019; Nelson-
Slivon et al., 2022; Wei et al., 2021). EBR manages version lists quickly and
simply by removing only the earliest versions from the end of a version list
when no active rtxs need them. However, it cannot remove obsolete versions
from the middle of a version list and it may therefore maintain an unbounded
number of obsolete versions. In practice, this can lead to a blowup in space
when there are long-lived rtxs.

To avoid this problem, Lu and Scott designed an MVGC system GVM (Lu and Scott,
2013) that can remove intermediate versions by occasionally traversing all
version lists and removing obsolete versions. The HANA system uses a similar
approach (Lee et al., 2016). The problem with these approaches is that they
scan all lists even if they are rarely or never updated. Böttcher et al.
improve on these techniques in the Steam system (Böttcher et al., 2019) by
tying the scanning of lists to updates on the list. Experiments with Steam
(Böttcher et al., 2019) showed that removing intermediate versions can
significantly improve space usage and throughput compared to some previous
MVGC methods in workloads with lengthy rtxs and frequent updates. However,
none of these systems provide strong worst-case time bounds and for $P$
processes and $M$ version lists achieve bounds of at best $O(PM)$ space.

Ben-David et al. (Ben-David et al., 2021) recently gave a MVGC technique
(henceforth BBF+) that has the best known time and space bounds. It removes
intermediate versions without traversing the full list. It is wait-free,
maintains only a constant factor more versions than needed, and uses $O(1)$
steps on average per allocated version. To achieve this, BBF+ defined a range
tracking object to precisely identify obsolete versions. However, BBF+ has not
previously been implemented and it is unclear if it can be made time-efficient
in practice. It uses a sophisticated doubly-linked list implementation, which
we call TreeDL because it has an implicit tree laid over it.

We study the efficiency of several MVGC schemes in practice by implementing
and comparing them in a single system. Based on our experiments, we develop
two novel MVGC schemes that combine and extend techniques from both Steam and
BBF+ to provide protocols that are as space-efficient as BBF+ while achieving
time efficiency comparable to Steam and EBR (sometimes slightly better,
sometimes slightly worse). We use the MVGC schemes to unlink obsolete versions
from version lists, allowing them to be reclaimed by a garbage collector
later. The new schemes relax some of the worst-case time guarantees of BBF+ to
improve time performance in the common case. However, they maintain the strong
worst-case space bounds proved in (Ben-David et al., 2021). Our experimental
analysis reveals the practical merit of state-of-the-art techniques for MVGC.
It shows that their performance depends significantly on the workload and that
no one technique always dominates for both time and space. However, our new
schemes show the most consistent performance without any particularly adverse
workloads.

Starting from the state-of-the-art MVGC schemes in (Ben-David et al., 2021;
Böttcher et al., 2019), we had to combine, simplify and extend techniques to
obtain the two new MVGC schemes (as discussed in Section 3). They focus on
speeding up the removal of obsolete versions once they are identified. This is
an important part of MVGC. Our removal algorithms greatly sped up the
theoretically efficient BBF+ scheme. One of them was also used to come up with
a lock-free version of Steam. This version is much more efficient than the
original, which locked entire version lists, for the lock-free multiversion
data structures we use in our experiments. Our algorithms use the range
tracking (RT) object from BBF+ to identify obsolete versions. A main challenge
is that removing these versions can be concurrent with other operations on the
version list.

For the first new scheme, called DL-RT, we develop a simpler doubly-linked
list implementation supporting removal from the middle of version lists (see
Section 4). The implementation, called PDL (Practical Doubly-linked List),
sacrifices TreeDL’s guarantee of constant amortized time per operation and
instead guarantees $O(c)$ amortized time, where $c$ is the number of
concurrent removals of consecutive list nodes. This choice was driven by the
experimental insight that removing chains of adjacent nodes is very rare in
practice: in our experiments the average $c$ was no more than 1.01 across a
wide variety of workloads. Experiments show the new, simpler list is much
faster than the constant-time list TreeDL when $c$ is small.

Our second algorithm, SL-RT, further improves practical performance for many
common workloads, in which version lists tend to be very short, so that linear
searches are reasonably efficient. In this case, we use a singly-linked list,
which requires less space (no back pointers) and less time for updates due to
fewer pointer changes. GVM (Lu and Scott, 2013), Steam (Böttcher et al., 2019)
and HANA (Lee et al., 2016) also rely on this observation (Böttcher et al.,
2019). We develop a singly-linked list implementation, called SSL (Simple
Singly-linked List), in Section 5 and use it to implement version lists in SL-
RT. Unlike those in Steam and HANA it is lock-free, and unlike GVM, which is
lock-free, it does not require any mark bits on pointers. Such mark bits
require an extra level of indirection in languages that do not allow directly
marking pointers.

Our new list structures support sorted lists with appends on one end, and
deletes anywhere, and are likely of independent interest. We prove both
correct. Combining our new lists with the range tracking of (Ben-David et al.,
2021) significantly improves space in many workloads over previous MVGC
schemes. The range tracking object identifies list elements to remove (in DL-
RT) or lists to traverse and collect (in SL-RT) more accurately than
traversing a list on every update as in Steam or traversing all lists
periodically as in HANA and GVM.

In our experiments (Section 6), we implemented and studied several schemes: an
epoch-based collector (Wei et al., 2021), BBF+ (Ben-David et al., 2021), our
new MVGC schemes, and an optimized variant of Steam (Böttcher et al., 2019) we
developed using SSL. MVGC schemes encompass several mechanisms that may have a
crucial effect on their time or space overhead. We focussed on the following
mechanisms that our experiments showed to have high impact on performance: (1)
data structure for storing versions and (2) how to choose when to remove
obsolete versions.

Our experiments study these MVGC schemes in the context of multiversion
concurrent data structures. These are data structures that leverage version
lists to support atomic read-only transactions (e.g., range queries) alongside
single-key insert, delete and lookup operations. They can be used as database
indexes (Wang et al., 2018; Leis et al., 2013) and have gained a lot of recent
attention (Nelson-Slivon et al., 2022; Wei et al., 2021; Sheffi et al., 2022;
Kobus et al., 2022; Sheffi et al., 2022).

We experimentally compared the MVGC schemes on two quite different concurrent
data structures, a multiversion balanced binary search tree and a multiversion
hash table. As in previous work (Böttcher et al., 2019), we saw that
reclaiming intermediate versions is vital for reducing memory overhead
(space), especially when there are long rtxs or oversubscription (i.e., when
there are more threads than available logical cores). In particular, EBR,
which does not collect intermediate versions, requires up to 10 times more
space than the others. Perhaps surprisingly, and unexpected to us, Steam
sometimes has particularly bad space usage for trees even though it does
collect intermediate versions. We found this is due to versioned pointers
pointing to objects containing other versioned pointers, as described in
Section 6. This leads to cases that require as much as 8 times more space. We
found that SL-RT almost always performed best in terms of space.

Steam and EBR typically performed best in terms of update throughput, but for
rtx throughput the performance was mixed. For combined throughput there was
little difference among the schemes; sometimes Steam and EBR are better and
sometimes SL-RT and DL-RT are better. BBF+ is almost always the slowest.

In conclusion, the experiments indicate MVGC schemes using range tracking
avoid the high space anomalies of EBR and Steam, with throughput that is
similar on mixed workloads and only slightly worse on update-heavy workloads.

Many existing practical MVGC schemes are designed for database systems that
use multiversioning and are often heavily intertwined with other parts of
those multiversion systems. We believe many of the MVGC techniques are common
across both database systems and multiversion data structures. A previous
study (Böttcher et al., 2019) compares MVGC schemes in various database
systems (including (Böttcher et al., 2019; Lee et al., 2016; Larson et al.,
2013)) that use different transaction management protocols. For our
experiments, we controlled for these confounding factors by applying different
MVGC schemes to the same pair of multiversion data structures. We know of no
previous comprehensive, apples-to-apples comparison of MVGC techniques.

We summarize the paper’s contributions as follows.

  * •

Two novel MVGC schemes that borrow and extend ideas from state-of-the-art
space- and time-efficient MVGC schemes. The new schemes maintain the strong
worst-case space bounds provided by BBF+ (Ben-David et al., 2021), while
achieving throughput comparable to Steam (Böttcher et al., 2019) in most
cases.

  * •

An experimental analysis that fairly compares state-of-the-art MVGC schemes by
applying them to the same multiversion data structures. This sheds light on
the practical merit of the schemes, and the reasons that no single MVGC
approach is a clear winner in terms of both space and time.

  * •

Several insights that can drive the design of new MVGC schemes, as they have
for our new schemes.

  * •

A new lock-free doubly-linked list PDL that is efficient when used in MVGC,
and which may be useful elsewhere.

  * •

A new simple singly-linked list implementation SSL that is suitable for MVGC
and has better throughput than PDL.

##  2\. Background and Related Work

Multiversioning. In general, using multiversioning involves maintaining a
global timestamp representing the current time. Depending on the
implementation, this global timestamp can be incremented by rtxs (Wei et al.,
2021; Fatourou et al., 2019), update operations (Nelson-Slivon et al., 2022),
or system clocks (Kobus et al., 2022; Lim et al., 2017). Each update marks any
new object (or version of an object) with its timestamp, and adds the new
object to the head of the appropriate version list. Each rtx reads the global
timestamp and uses it to navigate the version lists. More specifically, an rtx
with timestamp $t$ traverses a version list until it finds a version whose
timestamp is at most $t$, and then reads the desired value from that version.
The details of how update operations and rtxs are implemented differ between
implementations, but this high-level picture is sufficient for our study of
MVGC.

A versioned CAS object (Wei et al., 2021) is a specific implementation of
multiversioning that we use in our experiments when comparing different MVGC
schemes. It is a CAS object that supports looking up older values previously
stored in it given a timestamp. Our experiments use these objects to add
support for rtxs to a CAS-based lock-free balanced binary search tree (Brown
et al., 2014) and a simple lock-free hash table.

Epoch-based reclamation (EBR). EBR (Fraser, 2004; Brown, 2015) is a memory
reclamation technique which divides the execution into epochs. Each operation
begins by reading and announcing the current epoch via an announcement array.
When all active processes have announced the current epoch, the global epoch
counter is incremented and a new epoch begins. This epoch counter is separate
from the timestamps used for multiversioning. EBR ensures that all active
operations started during either the current or the previous epoch, and
therefore any nodes removed during earlier epochs are safe to reclaim. This
idea can be extended to work for multiversioning by observing that a rtx will
never access any version that was overwritten before the start of the rtx.
Therefore, all versions that were overwritten before the previous epoch are
safe to reclaim, as they are no longer needed by any active rtxs and are also
not on the path to any needed versions.

Because EBR is simple and fast, variants of it are widely used for MVGC
(Fernandes and Cachopo, 2011; Neumann et al., 2015; Wei et al., 2021; Wu et
al., 2017). However, EBR-based MVGC schemes reclaim only the oldest versions
from the end of the version list, and not obsolete versions in the middle of
the list. As a result, EBR does not guarantee space bounds, and can result in
high space overhead, particularly if processes execute long rtxs, thus
preventing the epoch from being advanced, or if processors are oversubscribed.

Compaction-based reclamation. To address EBR’s weakness, compaction-based MVGC
schemes (Lu and Scott, 2013; Lee et al., 2016; Böttcher et al., 2019) identify
obsolete versions and remove them from version lists. A version’s _time
interval_ is the interval of timestamps when it was the latest version. In
compaction-based schemes, rtxs announce the timestamp they intend to use for
traversing the version lists. A version list is compacted by first reading the
announced timestamps, sorting them, and then traversing the version list to
identify and remove versions whose time intervals do not include any announced
timestamp. Since the versions are in order, the traversal takes constant time
per version. Steam (Böttcher et al., 2019) traverses and compacts a version
list whenever a new version is added to it. HANA (Lee et al., 2016) and GVM
(Lu and Scott, 2013) do not tie the compaction to adding versions, but instead
either go through all lists using background threads, or have the main threads
compact once in a while. These techniques have the disadvantage of traversing
a version list even if it contains few or no obsolete versions to be
collected. HANA and GVM even visit lists when no changes have been made to
them. GVM (Lu and Scott, 2013) and Steam (Böttcher et al., 2019) guarantee
that each version list contains $O(P)$ versions, where $P$ is the number of
processes, so $O(PM)$ versions are maintained for $M$ lists.

Range-tracking. BBF+ (Ben-David et al., 2021) uses a range tracking object to
directly identify obsolete versions, avoiding the traversal of the entire
list. A range tracking object tracks a set of non-current versions, each of
which has been assigned an integer range indicating its time interval. A
version in the range tracking object can be reclaimed if its interval does not
intersect any of the timestamps announced by rtxs. In RangeTracker (the
linearizable range tracking implementation of (Ben-David et al., 2021)), each
thread $p$ appends non-current versions in a local list. If the size of $p$’s
list becomes $P\log P$, $p$ performs a flush. The flush appends $p$’s local
list to a shared FIFO queue $Q$ (of lists) (Fatourou and Kallimanis, 2014). It
then dequeues two lists from $Q$, merges their contents and compares the
merged list against a sorted sequence of the current announcements to
determine which versions are still needed. The list of needed versions is
enqueued to $Q$, and the set of obsolete versions is returned so that they can
be removed from their lists. A flush phase requires $O(P\log P)$ steps and is
performed once every $\Theta(P\log P)$ times an element is inserted in the
local list. RangeTracker thus ensures amortized constant time for each
operation it supports.

Removing from Lists. After identifying an obsolete version, it must be spliced
out of its list. Steam (Böttcher et al., 2019) and HANA (Lee et al., 2016) use
locks to safely do so. GVM (Lu and Scott, 2013) uses a variant of Harris’s
lock-free singly-linked list (Harris, 2001). This works since lists are always
traversed from their head. However, BBF+ requires safely removing obsolete
nodes from the middle of a list, given only a pointer to the node. To do this
safely and efficiently, BBF+ uses TreeDL, a custom wait-free doubly-linked
list. TreeDL uses an implicit binary tree whose in-order traversal gives the
list nodes in order. List nodes that are leaves of the tree are not adjacent
in the list and can therefore be removed safely and concurrently. If only
leaves are removed, then leaves that store versions that are still needed by
rtxs may prevent obsolete versions at internal nodes from being removed,
resulting in high space bounds. Thus, TreeDL provides intricate helping
mechanisms that also permit the removal of internal list nodes in the tree.
This is done with care to ensure list consistency and low space usage.

Other reclamation schemes. A recent improvement on EBR is version-based
reclamation (Sheffi et al., 2021). It bounds memory by restarting long running
operations, and has very recently been applied to a multiversion data
structure (Sheffi et al., 2022). Other memory reclamation schemes have been
proposed, but they do not solve the MVGC problem (Herlihy et al., 2005;
Michael, 2004; Ramalhete and Correia, 2017; Wen et al., 2018), or require
special support, in hardware (Alistarh et al., 2014; Dragojević et al., 2011)
or through the operating system (Brown, 2015; Singh et al., 2021). BBF+ uses
Hazard pointers (Michael, 2004) and a recent implementation (Anderson et al.,
2021) of reference counting (Correia et al., 2021; Detlefs et al., 2001;
Herlihy et al., 2005) to deallocate nodes that have been spliced out of the
lists. Our new MVGC schemes rely on the automatic Java garbage collector to
deallocate unreachable nodes.

Other lock-free list structures. We designed SSL and PDL as special-purpose
lock-free linked lists for representing version lists. They avoid the extra
level of indirection of Valois’s singly-linked list (Valois, 1995), which
places auxiliary nodes between real nodes. Harris’s singly-linked list (Harris
et al., 2002) and others that build on it (Fomitchev and Ruppert, 2004;
Michael, 2002) also add a level of indirection when implemented in Java, since
they require a mark bit on list pointers. Besides TreeDL, discussed above,
other existing lock-free doubly-linked list implementations are quite complex
because they support more operations than we need for version lists (Sundell
and Tsigas, 2008; Shafiei, 2015) or rely on multi-word CAS instructions
(Attiya and Hillel, 2013; Greenwald, 2002), which are not widely available in
hardware (although they can be simulated in software (Harris et al., 2002;
Guerraoui et al., 2020)).

##  3\. Proposed MVGC Schemes

We propose two new MVGC schemes, DL-RT and SL-RT. As with BBF+, we use the
RangeTracker to identify which versions in the middle of a list can be
removed. Our new schemes can be applied in the same way as BBF+; namely, rtxs
announce and unannounce their timestamps using the operations provided by the
RangeTracker, and whenever a version is overwritten by a newer version, it is
passed to the RangeTracker along with its time interval. The two new schemes
preserve the correctness conditions (e.g., linearizability, sequential
consistency) of the multiversion data structure they are applied to.

Our first scheme, DL-RT is based on a novel doubly-linked list implementation,
called PDL, whereas SL-RT employs a new, simple implementation of a singly-
linked list, called SSL. The lists are sorted by a key field (e.g., the
version timestamp). PDL supports the following operations, introduced in (Ben-
David et al., 2021; Wei et al., 2021): 1) tryAppend(x,y) attempts to append a
new element y at the end of the list, given that x is currently the last list
element; 2) remove(x) removes the element x from the list (and is used for
garbage collection); 3) peekHead returns the last element of the list (i.e.,
the current version); 4) search(key) returns the latest element of the list
whose key is less than or equal to key (i.e., the version that was current
when key was the current timestamp). Consistent with how MVGC uses version
lists, PDL assumes a remove is called only once on each node, and not on the
head node.

The list interface above supports versioned CAS objects, as described in (Wei
et al., 2021). In this case, a CAS operation $op$ that wants to change the
value from v to $\texttt{v}^{\prime}$ calls peekHead, and checks if the value
stored in the latest version is v. If so, $op$ calls tryAppend to add a
version containing the value $\texttt{v}^{\prime}$ after v. If tryAppend
fails, a concurrent CAS must have successfully changed the value of the CAS
object to something different from v. Then, $op$ returns false.

To avoid some of the intricacies of TreeDL we designed our novel
implementation PDL based on a simple idea: to remove a node we mark it and
then traverse outwards to the first unmarked node in either direction and make
them point to each other. PDL ensures that at most $L-R+P$ nodes in total are
in the version lists at the end of an execution containing a total of $L$
appends and $R$ removes. This bound is better than the $2(L-R)+O(P\log
L_{max})$ bound provided by TreeDL (Ben-David et al., 2021), where $L_{max}$
is the maximum number of appends on a single version list. In terms of time,
PDL ensures that tryAppend and peekHead maintain the $O(1)$ bound of TreeDL,
but the number of steps for remove is $O(c)$, where $c$ is the number of
concurrent removals of consecutive nodes in the list. The average value of $c$
was at most 1.01 in each of our experiments. Thus, from a practical
perspective, relaxing the time bound for remove to $O(c)$ is a good
compromise.

SSL is a singly-linked list implementation, and thus lacks back pointers. In a
doubly-linked list, a version can be removed by accessing only the node’s
immediate neighbourhood. To remove a node from a singly-linked list, we must
find its predecessor in the list by traversing the list from the head. Thus,
instead of focusing on removing individual nodes, SSL supports a compact
routine that traverses the entire list, removing obsolete nodes. Experiments
showed that, in many cases, the version lists tend to be short, so traversing
a list is often inexpensive. Indeed, in most experiments, SL-RT, which employs
SSL, exhibits better throughput than DL-RT. SSL ensures the same $L-R+P$ bound
on the number of nodes contained in the version lists as PDL.

PDL and SSL are presented in Sections 4 and 5. Due to lack of space, their
correctness proofs and complexity bounds are in the appendices. We used PDL to
develop DL-RT, and SSL to develop SL-RT, as well as STEAM+LF, a lock-free
version of Steam that we describe below. Specifically, instead of using TreeDL
for implementing the version lists as in BBF+, DL-RT employs PDL and SL-RT
employs SSL. RangeTracker (Ben-David et al., 2021) is used by both DL-RT (to
decide when to splice out an individual node), and by SL-RT (to decide when to
traverse and compact a version list).

RangeTracker is proved in (Ben-David et al., 2021) to use $O(H+P^{2}\log P)$
space, where $H$ is the maximum number of needed versions at any point during
the execution. We call the left and right pointers of nodes in PDL and the
left pointers of nodes in SSL, access pointers. A node is reachable in PDL or
in SSL at some point in time, if it can be reached starting from the list head
and following access pointers. Recall that both PDL and SSL ensure that at
most $L-R+P$ nodes in total remain reachable in the version lists. This bound
and the bound for RangeTracker imply the following.

###### Theorem 1.

Consider an implementation of a concurrent multi-versioning data structure
that uses DL-RT or SL-RT for garbage collection. At any time $t$ of an
execution, the total number of versions that are reachable in the version
lists is $O(H+P^{2}\log P$), where $H$ is the maximum, over all times before
$t$, of the number of needed versions.

If the number of needed versions is large at some point in an execution, this
will only influence the size of the version lists for a limited number of
steps. More specifically, if the number of needed versions remains below some
quantity $h$ in a suffix of an execution, then the number of reachable
versions in Theorem 1 will eventually be $O(h+P^{2}\log P)$.

##  4\. Doubly-Linked List

Algorithm 1 provides the pseudocode for PDL. Each node stores a left and right
pointer, as well as a mark bit to facilitate deletions. It also stores a key
key and a value val, which are set when the node is created and never change.
List elements are appended to the right end of the list and a head pointer
points to the rightmost node. The list initially contains a sentinel node with
key $-\infty$, which remains at the left end of the list at all times.

⬇

1class Node {

2 int key; Value val; bool mark; // initially false

3 Node* left, right; } OMIT CONSTRUCTOR TO SAVE SPACE

4 Node(Key k, Value v) { // constructor

5 val = v; key = k; mark = false;

6 left = null; right = null; } }

7class DoublyLinkedList {

8 Node* head; OMIT CONSTRUCTOR TO SAVE SPACE

9 DoublyLinkedList() { // constructor

10 head = new Node(-inf, $\bot$); } // sentinel node

11

12 Value peekHead() { return head->val; }

13 Value search(int k) {

14 Node* x = head;

15 while(x->key > k) {

16 x = x->left; }

17 return x->val; } }

18 bool tryAppend(Node* x, Node* y) {

19 Node* w = x->left;

20 // first, help tryAppend(w, x) if necessary

21 if(w != null) CAS(&(w->right), null, x);

22 y->left = x;

23 if(CAS(&head, x, y)) {

24 CAS(&(x->right), null, y);

25 return true;

26 } else return false; }

27 void remove(Node* x) {

28 x->mark = true;

29 Node* left = x->left;

30 Node* right = x->right;

31 Node* leftRight, rightLeft;

32 while(true) {

33 while(left->marked) left = left->left;

34 while(right->marked) right = right->right;

35 rightLeft = right->left;

36 leftRight = left->right;

37 if(left->marked || right->marked) continue;

38 if(!CAS(&right->left, rightLeft, left)) continue;

39 if(!CAS(&left->right, leftRight, right)) continue;

40 break; } }

Algorithm 1. Doubly linked list implementation (PDL).

The peekHead operation simply reads head and returns the node’s val field. A
search(k) starts at head and follows left pointers until reaching a node whose
key is at most k.

A tryAppend(x,y) attempts to append a new node y after a node x that has
previously been read from the head pointer. It updates the left pointer of y
to x (line 22) and swings the head pointer from x to y using a CAS (line 23).
If swinging the head fails, the operation returns false. Otherwise, tryAppend
attempts to update the right pointer of x to y using the CAS at line 24. If
swinging the head succeeds, but tryAppend pauses before updating x’s right
pointer, the list is left in an inconsistent state. So, before any subsequent
tryAppend adds a node beyond y, it first helps complete the append of node y
by updating x’s right pointer (line 21). The use of CAS (lines 21 and 24) to
initialize x’s right pointer ensures that the pointer is initialized only
once.

A remove(x) first marks the node x. (Line 28 does this with a simple write,
since a marked node remains marked forever.) It then seeks the nearest
unmarked nodes on either side and updates them to point to each other using
CAS instructions. If either CAS fails (or if the validation at line 37 that
the two nodes are still unmarked fails) the remove operation tries again to
find the nearest unmarked nodes, continuing outwards from where the previous
attempt left off. Once both pointers are updated, the remove terminates.

headuwvxyz

Figure 2. An example state of the list. A remove(v) has completed. A pending
remove(w) and remove(y) have performed the CAS at line 38 successfully but not
the CAS at line 39. A search may be visiting any of the nodes shown.

PDL does not maintain perfect consistency between left and right pointers: a
remove may update one but pause or die before updating the other. Moreover, to
keep the implementation lightweight, a remove does not help other nearby
remove operations to make the list consistent before applying its own changes;
it simply makes its changes (which may, incidentally, help other remove
operations take effect). See Figure 2 for an example. In addition, a search
concurrent with remove operations may traverse removed nodes. Thus, a careful
proof is needed to show some fairly weak invariants suffice for
linearizability (Herlihy and Wing, 1990). We sketch the proof in Section 4.1;
for details see Appendix A.

###  4.1. Correctness

We show that any execution $\alpha$ of the doubly-linked list is linearizable.
We assume the following preconditions. When tryAppend(x,y) is called, y is a
new node that has never been used as the second argument of tryAppend before
and it is not the sentinel node. Moreover, x has been read from head and y’s
key is greater than or equal to x’s key. There is at most one call to
remove(x) for each x, and it can be called only after a call to tryAppend(x,*)
has returned true.

If x and y are pointers to nodes, we use the notation
$\texttt{x}\leftarrow\texttt{y}$ to indicate that y->left = x and
$\texttt{x}\rightarrow\texttt{y}$ to indicate that x->right = y. We use
$\texttt{x}\leftsquigarrow\texttt{y}$ to indicate there is a path of left
pointers from y to x. We say that x is added to the list when the head pointer
is set to x. Since there is at most one call to tryAppend with x as the second
argument, there is at most one step in $\alpha$ that sets head to x. We define
a total order on nodes that are added to the list during $\alpha$:
$\texttt{x}\prec\texttt{y}$ if the head pointer was set to x before it was set
to y in $\alpha$.

The following invariant captures some relationships between a node and its
neighbours. Essentially, it says that left pointers always point to older
nodes and right pointers point to newer nodes. Moreover, if one of those
pointers skips over a node, the skipped node must be marked for deletion. To
prove these invariants, we also need similar claims for the local variables
left and right of pending removes.

###### Invariant 2.

Let $C$ be a configuration and y be a node.

  1. (1)

If y has been added to the list (and is not the sentinel), then y->left is
also a node that was added to the list and y->left $\prec\texttt{y}$. For all
w, if $\texttt{{y}->left}\prec\texttt{w}\prec\texttt{y}$ then w is marked.

  2. (2)

If y->right was non-null in a configuration at or before $C$, then in $C$
y->right is a node that was added to the list and
$\texttt{{y}->right}\succ\texttt{y}$. For all w, if
$\texttt{y}\prec\texttt{w}\prec\texttt{{y}->right}$ then w is marked.

  3. (3)

For any call to remove(y) in progress, the local variables left and right are
nodes that have been added to the list and
$\texttt{left}\prec\texttt{y}\prec\texttt{right}$. Moreover, for all w, if
$\texttt{left}\prec\texttt{w}\prec\texttt{right}$ then w is marked.

  4. (4)

The left pointer of the sentinel node is null.

The head pointer is initialized to the sentinel node, and can only be updated
on line 23 to a non-null pointer. This fact, Invariant 2 and the preconditions
of the operations imply that a null pointer is never dereferenced.

Because remove operations update left pointers concurrently, and may splice
out multiple nodes at once, there is a danger that one remove may undo the
effects of another. For example, suppose we have four nodes
$\texttt{w}\leftarrow\texttt{x}\leftarrow\texttt{y}\leftarrow\texttt{z}$. If a
remove(x) updates y->left to w and a concurrent remove(y) updates z->left to
x, then x would remain reachable. The following lemma ensures that this cannot
happen. (In fact, it is more general in that it applies even when the four
nodes are not consecutive in the list.)

###### Lemma 3.

Suppose $\texttt{w}\prec\texttt{x}\prec\texttt{y}\prec\texttt{z}$ and
$\texttt{w}\leftarrow\texttt{y}$ at some time during the execution. Then there
is never a time when $\texttt{x}\leftarrow\texttt{z}$.

Invariant 2 can be used to show that each time a left pointer changes, it
points to an older node.

###### Lemma 4.

If line 38 does a CAS(z->left, y, w), then $\texttt{w}\preceq\texttt{y}$.

The _abstract list_ $AL$ in a configuration is the sequence of nodes reachable
from the head by following left pointers. The next three lemmas ensure that a
node x is removed from $AL$ once remove(x) has terminated, and only if
remove(x) has been invoked. Lemma 5 implies that updates to a left pointer
only remove elements from $AL$: the list after the update is a subsequence of
the list prior to the update.

###### Lemma 5.

If a CAS at line 38 changes z->left from y to w, then
$\texttt{w}\leftsquigarrow\texttt{y}$ in the preceding configuration $C$.

###### Lemma 6.

When a node is removed from $AL$, it is marked.

###### Lemma 7.

When remove(x) terminates, x is not in $AL$.

These lemmas can be used to verify that the following linearization is
correct. We linearize a successful tryAppend when it updates the head pointer.
We linearize a remove(x) when a CAS at line 38 causes x to be removed from
$AL$. If several nodes are removed by a single CAS, we order them in
decreasing order by $\prec$. Thus, at all times, the abstract list $AL$ agrees
with the update operations linearized so far. The following lemma, which
requires a technical proof, allows us to linearize search operations.

###### Lemma 8.

Let $C$ be a configuration and x be the local variable of a pending search(k)
in $C$. There was a time between the invocation of the search and $C$ when x
was in $AL$ and either x was the first node in $AL$ or its predecessor in $AL$
had a key greater than k.

Thus, we can linearize search(k) when the returned node x is the first in $AL$
with key at most k.

A tryAppend takes $O(1)$ steps. A search is wait-free, and remove is lock-
free. A remove(x) operation takes $O(c)$ steps, where $c$ is the length of the
chain of adjacent nodes containing x that are marked before the remove ends.
Here, y and z are _adjacent_ if, during the remove(x),
$\texttt{y}\leftarrow\texttt{z}$ or $\texttt{y}\rightarrow\texttt{z}$.

##  5\. Singly-Linked List Compaction

⬇

1class Node { Node* left; int ts; Value val;}

2class AnnScan { List<int> A; int t; }

3AnnScan* scanAnnounce() {

4 AnnScan* newScan = new AnnScan;

5 repeat twice {

6 AnnScan* old = GlobalAnnScan;

7 newScan.t = GlobalTimeStamp;

8 read Announce[1..P] one by one, and sort into newScan.A;

9 if CAS(&GlobalAnnScan, oldScan, newScan) return newScan; }

10 return GlobalAnnScan }

11void compact(List<int> A, int t, Node* h) { // A is sorted

12 A.appendFront(-1); // padding

13 int i = index of last element of A;

14 Node* cur = h;

15 while(cur != sentinel) {

16 Node* next = cur->left;

17 // skip nodes whose timestamps exceed threshold t

18 if(cur->ts > t) {

19 cur = next;

20 } else {

21 while(A[i] >= cur->ts) i\--;

22 if(A[i] >= next->ts) { // next is needed

23 cur = next;

24 } else { // next is not needed

25 Node* newNext = next->left;

26 while(A[i] < newNext->ts) {

27 newNext = newNext->left; }

28 while(!CAS(&(cur->left), next, newNext)) {

29 next = cur->left;

30 if(next->ts <= newNext->ts) break; }

31 cur = cur->left; } } } }

32bool tryAppend(Node* x, Node* y) {

33 y->left = x;

34 return CAS(&head, x, y); }

35Value search(int k) {

36 Node* x = head;

37 while(x->ts > k) {

38 x = x->left; }

39 return x->val; }

Algorithm 3. Singly linked list (SSL) compaction routine.

We now describe our simple singly-linked list SSL designed to store version
lists (Algorithm 3). Each list node stores a version and has an associated
timestamp ts and a pointer left to a preceding version. A head pointer stores
the most recently appended node. Like PDL, SSL provides a tryAppend and search
operation. Nodes are appended to the list with timestamps in non-decreasing
order, so that the list is always sorted by timestamp. Instead of a remove
operation that splices out individual nodes, SSL provides a compact operation
that traverses the whole list splicing out obsolete nodes. We assume the list
initially contains a sentinel node with timestamp $-\infty$, which always
remains at the list’s tail.

The compact operation is given a sorted list A of timestamps announced by
rtxs, a threshold timestamp t that was read from the global timestamp counter
and a node h read from the head pointer of a version list, which specifies
where to begin traversing the list to compact. We describe below exactly how
these arguments are obtained so that any rtx that is concurrent with the
compact or begins after the compact will have a timestamp that is either in A
(because the rtx’s announcement is in A) or greater than or equal to t
(because the rtx grabs its timestamp after t has been read from the global
counter). The following definition describes the nodes that compact should
retain. A node x is _needed w.r.t. to A and t_ (abbreviated
$needed(\texttt{A},\texttt{t})$) if (1) $\texttt{x}.\texttt{ts}>\texttt{t}$,
or (2) x is the last appended node with timestamp at most t, or (3) for some
list element $\texttt{A}[i]$, x is the last appended node whose timestamp is
less than or equal to $\texttt{A}[i]$.

Since both the version list and A are sorted by timestamp, compact makes a
pass across both the version list and A using an algorithm similar to merging
two sorted arrays to determine which nodes of the list can be removed. When a
removable node is found, it is spliced out of the list by a CAS instruction on
its predecessor’s next field. If multiple consecutive nodes are all found to
be removable, a single CAS attempts to splice them all out of the list at
once.

In more detail, the variables i and cur of compact are used as pointers into A
and the version list, respectively, starting at the highest reserved timestamp
and the most recent version. Lines 18–19 skip past nodes in the version list
whose timestamps are greater than t. Line 21 finds the appropriate element of
A to compare to the timestamp of cur. Lines 22–23 skip past a node if it is
needed for the timestamp A[i]. Lines 25–30 handle the removal of next if it is
found to be unnecessary. The compact routine first finds the first needed node
after next and stores a pointer to it in newNext (lines 25–27). It then tries
to splice out a block of consecutive nodes, including next, by changing
cur->left from next to newNext at line 28. If the CAS fails, it repeatedly
tries to update cur->left to newNext until it succeeds or finds that cur->left
points to a node whose timestamp is less than or equal to newNext’s. Once the
block of nodes is removed, the compact routine proceeds down the list (line
31).

We now discuss how to obtain the arguments for a compact. Each process
performing a rtx writes its timestamp into a global array Announce. If a
process simply copies the global timestamp into t and copies Announce element
by element into a local copy A before calling compact(A,t,h), updates to the
list may behave strangely. Because the copies are not made atomically, two
concurrent compact operations may disagree about the set of needed nodes: for
example, if there are 4 nodes
$\texttt{x}_{1},\texttt{x}_{2},\texttt{x}_{3},\texttt{x}_{4}$ in the list with
timestamps $1,2,3,4$, one compact may think
$\texttt{x}_{1},\texttt{x}_{3},\texttt{x}_{4}$ are needed while the other
thinks $\texttt{x}_{1},\texttt{x}_{2},\texttt{x}_{4}$ are needed. The two
operations may get poised to splice out $\texttt{x}_{2}$ and $\texttt{x}_{3}$,
respectively. If they then perform their CAS steps to splice out the nodes,
node 2 will be removed by the CAS of the first operation and then become
reachable again when the CAS of the second operation occurs. We wish to avoid
this situation to maintain good worst-case space bounds. A similar problem may
occur if the copy h of the head pointer used as the starting point of a
compact is not obtained at the same time as A and t.

This problem could be avoided by taking an atomic snapshot of the global
timestamp, Announce and head, but that is too expensive. It suffices that the
intervals of time that different processes use to copy the global timestamp
and Announce are non-overlapping. This can be guaranteed using a more
lightweight synchronization mechanism. (See the scanAnnounce routine in
Algorithm 3.) Whenever a process $p$ reads the global timestamp and Announce
into local copies t and A, it attempts to install an AnnScan object, which
stores the pair $(\texttt{A},\texttt{t})$, into a shared variable
GlobalAnnScan using a CAS. If $p$’s CAS fails, $p$ tries again to make a local
copy and install it in GlobalAnnScan. If $p$’s second CAS on GlobalAnnScan
also fails, some other process must have stored an AnnScan object there that
it obtained after $p$’s first failed CAS, so $p$ can simply use the AnnScan
object it finds in GlobalAnnScan, since it is guaranteed to be recent. Before
calling compact(A,t,h), a process gets a snapshot of just two variables,
GlobalAnnScan (for the values of A and t) and head (for the value of h).

The lock-free compact routine allows multiple processes to splice nodes out of
the list concurrently, while other processes executing search traverse the
list. A careful proof of linearizability is in Appendix B. We linearize
tryAppend operations when they update head and search operations when they
read head. We also show that compact and search are wait-free and that after a
compact(A,t,h) routine terminates, all nodes reachable from the head of the
list that were appended to the list before h are
$needed(\texttt{A},\texttt{t})$.

##  6\. Experiments

We experimentally compared throughput and memory usage of state-of-the-art
MVGC schemes and our new schemes. We tested DL-RT, SL-RT, BBF+, STEAM+LF, and
an epoch-based scheme EBR. We implemented all for two different multiversion
data structures and used the benchmarking suite from (Wei et al., 2021). Only
the MVGC code varies. Our code is publicly available on GitHub (mvg, [n. d.]).

###  6.1. Setup

Machine/Compiler. Our experiments ran on a 64-core Amazon Web Service
c6i-metal instance with 2x Intel(R) Xeon(R) Platinum 8375C (32 cores, 2.9GHz
and 108MB L3 cache), and 256GB memory. Each core is 2-way hyperthreaded,
giving 128 hyperthreads. The machine runs Ubuntu 22.04.1 LTS. Our experiments
were written in Java and we used OpenJDK 19.0.1 with heap size set to 64GB. We
found that overall, the runtime overhead of Java’s garbage collector is small,
usually accounting for less than 5% of the overall time in most workloads. We
also tried running on smaller heap sizes down to 10GB and did not see much
difference in performance. For each data point in our graphs, we ran the
processes for 25 seconds to warm up the JVM and then measured 5 runs, each of
5 seconds. We report the average of those 5 runs. Error bars indicate
variance. To measure memory usage, at the end of each run, we measure the
amount of reachable memory used by the multiversion data structure. This
includes metadata maintained by the data structure’s MVGC scheme.

Data Structures. We apply MVGC schemes to CAS-based implementations of two
concurrent data structures by replacing each CAS object with a versioned CAS
object, as in (Wei et al., 2021). This adds support for linearizable rtxs on
top of the usual insert, delete, and lookup operations. Our experiments test a
hash table and a chromatic tree (Brown et al., 2014), which have quite
different characteristics, as the experiments will show.

The hash table is based on separate chaining. Each chain is a sorted linked
list of elements. The lists are immutable: to insert or delete an element, we
use path copying to create a new copy of the list, and change the hash table
entry to point to the new copy using CAS. For short chains, path copying
yields a simple, efficient list implementation that avoids the need for the
mark bits on pointers that are used in many lock-free lists. In our
experiments, we pick the size of the hash table so that the load factor is
about $0.5$, so chains are very short on average. An important property of
this structure is that vCAS objects never point indirectly to other vCAS
objects—i.e., the head pointer of the list is a vCAS object but none of the
links are. The experiments run by Böttcher et al. (Böttcher et al., 2019) also
had this property. The hashtable workload has similarities with many database
workloads where the table entries are versioned but not the index (Neumann et
al., 2015; Wu et al., 2017).

The chromatic tree is a binary search tree with a lazy version of the red-
black balancing scheme. Unlike the hash table, in a chromatic tree, or any
concurrent tree, the vCAS objects _do_ point indirectly to others. In
particular, a node points to its child, which can contain other vCAS objects.
This has a significant impact on some of the experimental results, since not
collecting a node soon enough means that its children will not be collectible.
This represents an interesting aspect that does not show up in previous
database MVGC work.

Both data structures support inserts and deletes, and rtxs. On the trees we
support range queries—i.e., returning the keys within a range. For hash tables
we support returning the value of multiple keys. All operations are
linearizable.

Optimizations. We use a backoff scheme in all implementations to reduce
contention on the global timestamp counter. A process reads the counter and
if, after some variable delay, the counter has increased, it simply uses the
incremented value. Otherwise, it updates the counter using CAS. When using
version lists as in (Wei et al., 2021), reading an object requires first
reading the location of the head of its version list, and then reading the
version the head points to. As suggested in (Wei et al., 2021), we avoid this
level of indirection by satisfying the _recorded-once_ property they define
and placing the timestamp and pointer to the next older version in the object
itself.

We tuned parameters of the range tracking object (Ben-David et al., 2021),
including the number of lists to dequeue from the shared queue $Q$ in a flush
and the number of elements per list. When adding a list to $Q$, we omit
already obsolete versions from it.

The authors of Steam (Böttcher et al., 2019) suggest a heuristic of
periodically scanning timestamps announced by rtxs, instead of scanning every
time a list is compacted. This optimization does not preserve the $O(P)$ bound
on the size of a version list but it is crucial for performance. In STEAM+LF
we apply this optimization and we scan announcements every 1ms.

Workload. In our experiments, we vary the following parameters: (a) size of
the multiversion data structure (denoted by $n$), (b) operation mix, (c) size
of rtxs, (d) number of threads, and (e) the distribution from which keys are
drawn. In most experiments, we prefill each data structure with either
$n=100K$ or $n=10M$ keys. These sizes are chosen to illustrate performance
when the data set fits and does not fit into the L3 cache. We perform a mix of
operations, consisting of inserts and deletes (done in equal numbers), as well
as read transactions. Keys for operations and the initial values of the data
structure are drawn randomly from the range $[1,2n]$, ensuring that the size
of the data structure remains approximately $n$ throughout the experiment.

Our rtxs search for all keys in the range $(a,a+s)$ where $a$ is drawn
uniformly at random from the range $[1,r-s]$ ($\mathit{s}$ is the rtx size).
The trees search by using the ordering while hash tables search by checking
each individual key in the range. For insert and delete operations, we draw
keys from both the uniform distribution and Zipfian distribution with
parameter 0.99, which is the default in the YCSB benchmark (Cooper et al.,
2010).

By tuning the number of threads, we can vary the amount of contention, and
also study the effects of oversubscription. We see that these have a big
impact on how MVGC algorithms perform since they lead to longer version lists.

Legend for all figures: |
---|---

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.03 | 1.05 | 1.15 | 1.39
DL-RT | 1.08 | 1.08 | 1.17 | 1.47
BBF+ | 1.08 | 1.08 | 1.2 | 1.52
Steam+LF | 1.52 | 1.54 | 1.67 | 1.95
EBR | 1.05 | 1.05 | 1.28 | 2.32

Figure 4. Tree with 100K keys, 40 update threads, 40 small rtx threads, 40
large rtx threads.

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.0 | 1.0 | 1.04 | 1.42
DL-RT | 1.0 | 1.0 | 1.04 | 1.5
BBF+ | 1.0 | 1.01 | 1.05 | 1.51
Steam+LF | 1.29 | 1.29 | 1.3 | 1.49
EBR | 1.0 | 1.01 | 1.11 | 2.32

Figure 5. Tree with 10M keys, 40 update threads, 40 small rtx threads, 40
large rtx threads.

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.02 | 1.06 | 1.34 | 2.14
DL-RT | 1.05 | 1.08 | 1.65 | 4.6
BBF+ | 1.05 | 1.08 | 1.61 | 4.76
Steam+LF | 1.64 | 1.68 | 1.93 | 2.51
EBR | 1.01 | 1.09 | 2.26 | 73.63

Figure 6. Hash table with 100K keys, 40 update threads, 40 small rtx threads,
40 large rtx threads.

(a) Tree with 100K keys

(b) Tree with 10M keys

Figure 7. Workload with each thread performing 50% updates, 49% lookups, and
1% read transactions of size 1024. Figure 8. Hash table with 100K keys, each
thread performs 50% updates, 49% lookups, and 1% rtxs of size 1024.

###  6.2. Evaluation

Figures 4–8 give a cross section of our experimental results. There was no
qualitative difference between experiments on the uniform and Zipfian
distributions, so we just include the Zipfian here. More graphs are given in
Appendix C. All experiments cover all five GC techniques. Some show rtx and
update throughput separately by placing rtxs and updates on separate threads.
This highlights the performance differences on updates, since the rtx
throughput tends to be affected less. Other graphs aggregate throughput by
having each thread perform a mix of both types of operations, which is more
indicative of a real workload. Based on the experiments, no one algorithm
always outperforms the others; relative performance depends on various factors
described below.

Space. We first consider space usage. Perhaps the most interesting aspect of
space is how poorly STEAM+LF performs on trees relative to hash tables. This
is explained by our previous discussion of vCAS objects indirectly pointing to
other vCAS objects in the chromatic tree but not the hash table. STEAM+LF
generally keeps around 1.5 to 2 versions per version list (see tables of
Figures 4 and 5) because if there is an ongoing rtx when a new version is
added, the existing version is still needed by the rtx and cannot be
collected. Soon after, when all current rtxs finish, it becomes obsolete, but
STEAM+LF will not compact the list until that location is updated again. This
is sometimes called the _dusty corners problem_ (Larson et al., 2013) because
corners (i.e., version lists) that are visited infrequently will be cleaned
infrequently. This delay only causes a space overhead factor of at most 2 when
there is no indirection, but can be much worse with indirection. In
particular, the old version that is not collected can point to another node
containing versioned objects, and that node and its versions will not be
collected. This effect can be seen for the chromatic trees in Figures 4 and
7(a). Even for small rtxs, STEAM+LF performs much worse than the others. The
experiments in the original Steam paper (Böttcher et al., 2019) used a typical
database implementation where only table entries are multiversioned, so
versions do not indirectly point to one another and they did not see this
issue as severely as we do.

EBR does not suffer from dusty corners since a version can be removed as soon
as all active rtxs at the time of an update have completed, although it has
other problems discussed below. The other three algorithms lack dusty corners
since a version is removed as soon as the range tracker identifies it, which
can be much sooner than the next update.

The space usage of EBR suffers badly for update-heavy workloads with large
rtxs and with oversubscription. See, e.g., Figures 5, 6, and 7(a). With large
rtxs the epochs become long, and update-heavy workloads can create many
versions during an epoch that cannot be collected until a following epoch.
Oversubscription can further prolong an epoch if a thread in the epoch is
delayed. Indeed, this is exactly the problem that removing intermediate
versions is trying to solve. Thus, although EBR does fine in many “nice”
situations it does very badly in adverse conditions. Figure 6 indicates EBR
can use more than an order of magnitude more memory than all the other MVGC
schemes in such conditions.

A third observation is that DL-RT, SL-RT, and BBF+ behave as expected in terms
of space. In particular, the theory indicates the memory is bounded by three
terms: the space needed for the current versions, a constant times the number
of needed old versions, and a function of the number of threads. In Figure
7(a) for a small data structure of size 100K the third term dominates as the
number of threads increases for all three algorithms. In Figure 7(b) for a
larger data structure of size 10M the first two terms dominate making it hard
to see the increase of space with more threads.

In almost all cases DL-RT, SL-RT, and BBF+ require less space than EBR or
STEAM+LF. Importantly, although EBR or STEAM+LF use slightly less memory than
the other three in some cases, the memory usage for the other three is much
more predictable and never has any particularly bad cases.

Finally, we observe that BBF+ almost always uses more memory than DL-RT, since
in BBF+ some nodes are obsolete but not collectable. DL-RT almost always uses
more memory than SL-RT because of the additional back pointers in the version
lists, and also because SL-RT is able to preemptively splice out versions when
traversing a list even before they are returned by the range-tracker. As
discussed, the advantages of SL-RT come at the cost of losing time guarantees.

Throughput. We now consider throughput. Varying the GC algorithms affects rtx
and update throughput differently. We first consider rtx throughput. The rtx
code is the same for all GC schemes, but there are at least two indirect
effects.

Firstly, a scheme that compacts version lists less effectively tends to have
longer version lists, so rtxs have to follow more version links. This explains
the very poor performance of very large rtxs on the hash table with EBR
(Figure 6).

Secondly, rtxs are running concurrently with updates and, although they do not
communicate with one another directly, there can be indirect effects, such as
cache-line interference or faster updates increasing the lengths of version
lists. It is hard to draw general conclusions about these effects, but they
are likely contributing to the minor variances.

The differences in update throughput among the algorithms is higher than for
rtxs. This is to be expected since the code for updates differ
significantly—e.g., some traverse whole version lists, and some have to apply
operations to the range-tracker data structure. Firstly, we observe that BBF+
almost always does worse than all the others, often significantly. This is the
main motivation for designing the DL-RT and SL-RT algorithms. There are a few
data points where BBF+ is faster than SL-RT but in these cases the rtx
throughput is significantly faster for SL-RT. Secondly, STEAM+LF and EBR
mostly dominate the others, although the difference is usually small. This is
expected, given the extra cost of maintaining the range-tracker data
structure. Thirdly, comparing our two new algorithms, DL-RT and SL-RT, in all
graphs except Figure 6, the version lists were short enough that traversing
from the beginning was faster than maintaining back pointers and hence SL-RT
performs better. Even though the average version list length in Figure 6 is
small for SL-RT, the lists that get frequently updated tend to be long and SL-
RT traverses an average of 17.9 version list nodes before reaching the one it
wishes to splice out

Summary. Our evaluation shows that there is no definitively best MVGC scheme
and we provide several insights into the types of workload and data structures
each scheme is most suitable for. While the performance of different schemes
is often similar, particularly in terms of throughput, there are a few
important exceptions. In particular, EBR uses up to 10 times more memory than
the other schemes in workloads with long rtxs and Steam uses 8 times more
memory in hierarchical data structures like trees. Our new schemes (SL-RT and
DL-RT) are consistently faster than BBF+ and do not incur exceptionally high
space usage in any workload.

###### Acknowledgements.

We thank the anonymous referees for their helpful comments. This research was
supported by NSERC; NSF grants CCF-1901381, CCF-1910030, CCF-1919223, and
CCF-2119069; and the Hellenic Foundation for Research and Innovation (HFRI)
under the “Second Call for HFRI Research Projects to support Faculty members
and researchers” (project number: 3684).

## References

  * (1)
  * mvg ([n. d.]) [n. d.].  https://github.com/cmuparlay/ppopp23-mvgc.
  * Alistarh et al. (2014) Dan Alistarh, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. 2014\.  StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation. In _Proc. 9th European Conference on Computer Systems_. 25:1–25:14.  https://doi.org/10.1145/2592798.2592808
  * Anderson et al. (2021) Daniel Anderson, Guy E. Blelloch, and Yuanhao Wei. 2021\.  Concurrent deferred reference counting with constant-time overhead. In _Proc. 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_. 526–541.
  * Attiya and Hillel (2013) Hagit Attiya and Eshcar Hillel. 2013.  Built-in coloring for highly-concurrent doubly-linked lists.  _Theory of Computing Systems_ 52, 4 (2013), 729–762.
  * Basin et al. (2020) Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. 2020.  KiWi: A Key-Value Map for Scalable Real-Time Analytics.  _ACM Trans. Parallel Comput._ 7, 3, Article 16 (June 2020), 28 pages.  https://doi.org/10.1145/3399718
  * Ben-David et al. (2021) Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. 2021\.  Space and Time Bounded Multiversion Garbage Collection. In _Proc. 35th International Symposium on Distributed Computing_. 12:1–12:20.  A full version is available from https://arxiv.org/abs/2108.02775.
  * Bernstein and Goodman (1983) Philip A. Bernstein and Nathan Goodman. 1983.  Multiversion Concurrency Control–Theory and Algorithms.  _ACM Trans. Database Syst._ 8, 4 (Dec. 1983), 465–483.  https://doi.org/10.1145/319996.319998
  * Böttcher et al. (2019) Jan Böttcher, Viktor Leis, Thomas Neumann, and Alfons Kemper. 2019.  Scalable garbage collection for in-memory MVCC systems.  _Proceedings of the VLDB Endowment_ 13, 2 (2019), 128–141.
  * Brown et al. (2014) Trevor Brown, Faith Ellen, and Eric Ruppert. 2014\.  A General Technique for Non-Blocking Trees. In _Proc. ACM Symposium on Principles and Practice of Parallel Programming_. 329–342.  https://doi.org/10.1145/2555243.2555267
  * Brown (2015) Trevor Alexander Brown. 2015\.  Reclaiming Memory for Lock-Free Data Structures: There Has to Be a Better Way. In _Proc. ACM Symposium on Principles of Distributed Computing_. 261–270.  https://doi.org/10.1145/2767386.2767436
  * Cooper et al. (2010) Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010\.  Benchmarking Cloud Serving Systems with YCSB. In _Proc. 1st ACM Symposium on Cloud Computing_. 143–154.  https://doi.org/10.1145/1807128.1807152
  * Correia et al. (2021) Andreia Correia, Pedro Ramalhete, and Pascal Felber. 2021\.  OrcGC: automatic lock-free memory reclamation. In _Proc. 26th ACM Symposium on Principles and Practice of Parallel Programming_. 205–218.
  * Detlefs et al. (2001) David L. Detlefs, Paul A. Martin, Mark Moir, and Guy L. Steele. 2001\.  Lock-Free Reference Counting. In _Proc. 20th ACM Symposium on Principles of Distributed Computing_. 190–199.  https://doi.org/10.1145/383962.384016
  * Dragojević et al. (2011) Aleksandar Dragojević, Maurice Herlihy, Yossi Lev, and Mark Moir. 2011.  On the Power of Hardware Transactional Memory to Simplify Memory Management. In _Proc. 30th ACM Symposium on Principles of Distributed Computing_. 99–108.  https://doi.org/10.1145/1993806.1993821
  * Ellen et al. (2010) Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010.  Non-Blocking Binary Search Trees. In _Proc. 29th ACM Symposium on Principles of Distributed Computing_ (Zurich, Switzerland). 131–140.  https://doi.org/10.1145/1835698.1835736
  * Fatourou and Kallimanis (2014) Panagiota Fatourou and Nikolaos D Kallimanis. 2014.  Highly-efficient wait-free synchronization.  _Theory of Computing Systems_ 55, 3 (2014), 475–520.
  * Fatourou et al. (2019) Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. 2019\.  Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In _Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures_. 275–286.  https://doi.org/10.1145/3323165.3323197
  * Feldman et al. (2020) Yotam M. Y. Feldman, Artem Khyzha, Constantin Enea, Adam Morrison, Aleksandar Nanevski, Noam Rinetzky, and Sharon Shoham. 2020.  Proving Highly-Concurrent Traversals Correct.  _Proc. ACM Program. Lang._ 4, OOPSLA, Article 128 (Nov. 2020), 29 pages.  https://doi.org/10.1145/3428196
  * Fernandes and Cachopo (2011) Sérgio Miguel Fernandes and João Cachopo. 2011.  Lock-Free and Scalable Multi-Version Software Transactional Memory. In _Proc. 16th ACM Symposium on Principles and Practice of Parallel Programming_. 179–188.  https://doi.org/10.1145/1941553.1941579
  * Fomitchev and Ruppert (2004) Mikhail Fomitchev and Eric Ruppert. 2004.  Lock-Free Linked Lists and Skip Lists. In _Proc. 23rd ACM Symposium on Principles of Distributed Computing_. 50–59.  https://doi.org/10.1145/1011767.1011776
  * Fraser (2004) Keir Fraser. 2004\.  _Practical Lock-freedom_.  Technical Report UCAM-CL-TR-579. University of Cambridge, Computer Laboratory.
  * Greenwald (2002) Michael Greenwald. 2002\.  Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In _Proc. 21st ACM Symposium on Principles of Distributed Computing_. 260–269.
  * Guerraoui et al. (2020) Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi. 2020.  Efficient Multi-Word Compare and Swap. In _Proc. 34th International Symposium on Distributed Computing_ _(LIPIcs, Vol. 179)_.
  * Harris (2001) Timothy L. Harris. 2001\.  A pragmatic implementation of non-blocking linked-lists. In _Proc. International Symposium on Distributed Computing_. Springer, 300–314.
  * Harris et al. (2002) Timothy L. Harris, Keir Fraser, and Ian A. Pratt. 2002\.  A practical multi-word compare-and-swap operation. In _Proc. International Symposium on Distributed Computing_ _(LNCS, Vol. 2508)_. 265–279.
  * Herlihy et al. (2005) Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. 2005.  Nonblocking Memory Management Support for Dynamic-Sized Data Structures.  _ACM Trans. Comput. Syst._ 23, 2 (May 2005), 146–196.  https://doi.org/10.1145/1062247.1062249
  * Herlihy and Wing (1990) Maurice P. Herlihy and Jeannette M. Wing. 1990.  Linearizability: A correctness condition for concurrent objects.  _ACM Transactions on Programming Languages and Systems_ 12, 3 (1990), 463–492.
  * Keidar and Perelman (2015) Idit Keidar and Dmitri Perelman. 2015.  Multi-versioning in Transactional Memory.  In _Transactional Memory. Foundations, Algorithms, Tools, and Applications_. LNCS, Vol. 8913. Springer, 150–165.  https://doi.org/10.1007/978-3-319-14720-8_7
  * Kim et al. (2019) Jaeho Kim, Ajit Mathew, Sanidhya Kashyap, Madhava Krishnan Ramanathan, and Changwoo Min. 2019\.  MV-RLU: Scaling Read-Log-Update with Multi-Versioning. In _Proc. 24th International Conference on Architectural Support for Programming Languages and Operating Systems_. 779–792.  https://doi.org/10.1145/3297858.3304040
  * Kobus et al. (2022) Tadeusz Kobus, Maciej Kokociński, and Paweł T. Wojciechowski. 2022\.  Jiffy: A Lock-Free Skip List with Batch Updates and Snapshots. In _Proc. 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 400–415.  https://doi.org/10.1145/3503221.3508437
  * Kumar et al. (2014) Priyanka Kumar, Sathya Peri, and K. Vidyasankar. 2014\.  A TimeStamp Based Multi-version STM Algorithm. In _Proc. International Conference on Distributed Computing and Networking_. 212–226.
  * Larson et al. (2013) Per-Åke Larson, Mike Zwilling, and Kevin Farlee. 2013\.  The Hekaton Memory-Optimized OLTP Engine.  _IEEE Data Eng. Bull._ 36, 2 (2013), 34–40.
  * Lee et al. (2016) Juchang Lee, Hyungyu Shin, Chang Gyoo Park, Seongyun Ko, Jaeyun Noh, Yongjae Chuh, Wolfgang Stephan, and Wook-Shin Han. 2016\.  Hybrid Garbage Collection for Multi-Version Concurrency Control in SAP HANA. In _Proc. International Conference on Management of Data_. 1307–1318.  https://doi.org/10.1145/2882903.2903734
  * Leis et al. (2013) Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013\.  The adaptive radix tree: ARTful indexing for main-memory databases. In _Proc. 29th IEEE International Conference on Data Engineering_. 38–49.
  * Lim et al. (2017) Hyeontaek Lim, Michael Kaminsky, and David G Andersen. 2017\.  Cicada: Dependably fast multi-core in-memory transactions. In _Proc. ACM International Conference on Management of Data_. 21–35.
  * Lu and Scott (2013) Li Lu and Michael L Scott. 2013.  Generic multiversion STM. In _Proc. International Symposium on Distributed Computing_ _(LNCS, Vol. 8205)_. 134–148.
  * Michael (2004) M.M. Michael. 2004\.  Hazard pointers: safe memory reclamation for lock-free objects.  _IEEE Transactions on Parallel and Distributed Systems_ 15, 6 (2004), 491–504.  https://doi.org/10.1109/TPDS.2004.8
  * Michael (2002) Maged M. Michael. 2002\.  High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. In _Proc. 14th ACM Symposium on Parallel Algorithms and Architectures_. 73–82.  https://doi.org/10.1145/564870.564881
  * Nelson-Slivon et al. (2022) Jacob Nelson-Slivon, Ahmed Hassan, and Roberto Palmieri. 2022\.  Bundling linked data structures for linearizable range queries. In _Proc. 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 368–384.  https://doi.org/10.1145/3503221.3508412
  * Neumann et al. (2015) Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015\.  Fast serializable multi-version concurrency control for main-memory database systems. In _Proc. ACM SIGMOD International Conference on Management of Data_. 677–689.
  * O’Hearn et al. (2010) Peter W. O’Hearn, Noam Rinetzky, Martin T. Vechev, Eran Yahav, and Greta Yorsh. 2010.  Verifying Linearizability with Hindsight. In _Proc. 29th ACM Symposium on Principles of Distributed Computing_. 85–94.
  * Papadimitriou and Kanellakis (1984) Christos H. Papadimitriou and Paris C. Kanellakis. 1984.  On Concurrency Control by Multiple Versions.  _ACM Transactions on Database Systems_ 9, 1 (1984), 89–99.
  * Perelman et al. (2011) Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, and Idit Keidar. 2011.  SMV: Selective Multi-Versioning STM. In _Proc. International Symposium on Distributed Computing_ _(LNCS, Vol. 6950)_. 125–140.
  * Perelman et al. (2010) Dmitri Perelman, Rui Fan, and Idit Keidar. 2010.  On Maintaining Multiple Versions in STM. In _Proc. ACM Symposium on Principles of Distributed Computing_. 16–25.
  * Ramalhete and Correia (2017) Pedro Ramalhete and Andreia Correia. 2017.  Brief Announcement: Hazard Eras–Non-Blocking Memory Reclamation. In _Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures_. 367–369.  https://doi.org/10.1145/3087556.3087588
  * Reed (1978) D. Reed. 1978.  _Naming and synchronization in a decentralized computer system_.  Technical Report LCS/TR-205. EECS Dept., MIT.
  * Shafiei (2015) Niloufar Shafiei. 2015\.  Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. In _Proc. 19th Int. Conference on Principles of Distributed Systems_ _(LIPIcs, Vol. 46)_. 35:1–35:17.
  * Sheffi et al. (2021) Gali Sheffi, Maurice Herlihy, and Erez Petrank. 2021\.  VBR: Version Based Reclamation. In _Proc. 35th International Symposium on Distributed Computing_ _(LIPIcs, Vol. 209)_. 35:1–35:18.  https://doi.org/10.4230/LIPIcs.DISC.2021.35
  * Sheffi et al. (2022) Gali Sheffi, Pedro Ramalhete, and Erez Petrank. 2022\.  EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation.  https://doi.org/10.48550/ARXIV.2210.17086
  * Singh et al. (2021) Ajay Singh, Trevor Brown, and Ali Mashtizadeh. 2021.  NBR: Neutralization Based Reclamation. In _Proc. 26th ACM Symp. on Principles and Practice of Parallel Programming_. 175–190.  https://doi.org/10.1145/3437801.3441625
  * Sundell and Tsigas (2008) Håkan Sundell and Philippas Tsigas. 2008.  Lock-free deques and doubly linked lists.  _J. Parallel and Distributed Computing_ 68, 7 (2008), 1008–1020.
  * Valois (1995) John D. Valois. 1995\.  Lock-free linked lists using compare-and-swap. In _Proc. 14th ACM Symposium on Principles of Distributed Computing_. 214–222.
  * Wang et al. (2018) Ziqi Wang, Andrew Pavlo, Hyeontaek Lim, Viktor Leis, Huanchen Zhang, Michael Kaminsky, and David G Andersen. 2018.  Building a Bw-tree takes more than just buzz words. In _Proceedings of the 2018 International Conference on Management of Data_. 473–488.
  * Wei et al. (2021) Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun. 2021.  Constant-Time Snapshots with Applications to Concurrent Data Structures. In _Proc. ACM Symposium on Principles and Practice of Parallel Programming_. 31–46.  A full version is available from https://arxiv.org/abs/2007.02372.
  * Wen et al. (2018) Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018.  Interval-Based Memory Reclamation. In _Proc. 23rd ACM Symp. on Principles and Practice of Parallel Programming_. 1–13.  https://doi.org/10.1145/3178487.3178488
  * Wu et al. (2017) Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017.  An Empirical Evaluation of In-memory Multi-version Concurrency Control.  _Proc. of the VLDB Endowment_ 10, 7 (March 2017), 781–792.

##  Appendix A Proofs for the Doubly-Linked List

See 2

###### Proof.

Initially, the only node is the sentinel node and its right pointer is null,
and there is no pending call to remove, so the claim holds vacuously. We show
that every step preserves each of the three claims of the invariant.

  1. (1)

To prove that claim 1 is preserved, we must only consider steps that can add a
node to the list or change the left pointer of a node.

When a node y is added to the list at line 23 of a call to tryAppend(x,y),
y->left has been set to x at line 22. By the preconditions, this is the unique
call of the form tryAppend(*,y), so a pointer to y has not previously been
written into shared memory. So, no process could have updated y->left and it
is therefore still x. By the precondition of tryAppend, x is a node that has
previously been read from head, so it has been added to the list and
$\texttt{x}\prec\texttt{y}$. Since the CAS on head changes it from x directly
to y, there are no nodes w satisfying
$\texttt{x}\prec\texttt{w}\prec\texttt{y}$.

The only instructions that update a left pointer are lines 22 and 38. As
mentioned above, a node y has not been added to the list yet when line 22 of
tryAppend(x,y) updates y->left, so there is nothing more to prove.

Suppose an execution of line 38 of a remove(x) sets y->left to v. Then, v and
y are the values of the remove’s local variables left and right. By induction
hypothesis 3, v has been added to the list and
$\texttt{v}\prec\texttt{x}\prec\texttt{y}$ and every node w satisfying
$\texttt{v}\prec\texttt{w}\prec\texttt{y}$ is marked. Thus, after the CAS,
every node w satisfying $\texttt{y->left}\prec\texttt{w}\prec\texttt{y}$ is
marked.

  2. (2)

To prove that claim 2 is preserved, we must only consider steps that can
change the right pointer of a node. The only instructions that set a right
pointer to a non-null value are lines 21, 24 and 39.

First, consider line 24 of a tryAppend(x, y), which sets x->right to y. Since
head was changed directly from x to y on line 23, y has been added to the list
and $\texttt{x}\prec\texttt{y}$, and there are no nodes w satisfying
$\texttt{x}\prec\texttt{w}\prec\texttt{y}$.

Next, consider an execution of line 39 of a remove(y) sets x->right to z.
Then, x and z are the values of the local variables left and right. By the
induction hypothesis, $\texttt{x}\prec\texttt{y}\prec\texttt{z}$ and every
node w satisfying $\texttt{x}\prec\texttt{w}\prec\texttt{z}$ is marked. Thus,
after the CAS, every node w satisfying
$\texttt{x}\prec\texttt{w}\prec\texttt{{x}->right}$ is marked.

Finally, consider a CAS step $s$ at line 21 of tryAppend(y,*) that changes
x->right from null to y. By the precondition of tryAppend, y has been added to
the list. The tryAppend read x from y->left at line 19 before $s$. Since x is
not null at line 21, y cannot be the sentinel node, by induction hypothesis 4.
So x is a node that has been added to the list and $\texttt{x}\prec\texttt{y}$
by induction hypothesis 1. We prove the remainder of the claim by showing that
there is no w such that $\texttt{x}\prec\texttt{w}\prec\texttt{y}$.

Since x->right is null in the configuration before $s$, it follows from
induction hypothesis 2 that

(1) $\texttt{{x}->right}=\mbox{null at all times before }s.$

Node x cannot be marked when $s$ occurs: before a remove(x) could have marked
x, a tryAppend(x,*) must have returned true (by the precondition for remove),
and that tryAppend would have set x->right to a non-null value at line 24,
contrary to (1).

To derive a contradiction, suppose there is some w such that
$\texttt{x}\prec\texttt{w}\prec\texttt{y}$. Consider the minimal such w with
respect to the total order $\prec$. (I.e., w is the successor of x in the
order $\prec$.) Since $\texttt{x}\leftarrow\texttt{y}$ at line 19 before $s$,
$w$ is marked, by induction hypothesis 1. This means that a remove(w) has been
invoked before $s$. By the precondition of remove, a
tryAppend(w,$\texttt{w}^{\prime}$) returned true before $s$, for some
$\texttt{w}^{\prime}$. Consider line 19 of that tryAppend. When it occurs, x
is unmarked (since it is still unmarked at $s$). By induction hypothesis 1,
$\texttt{{w}->left}\succeq\texttt{x}$ (since x is unmarked) and
$\texttt{{w}->left}\preceq\texttt{x}$ (since x is the predecessor of w in the
order $\prec$). Thus, line 19 reads x from w->left. Line 21 of that
tryAppend(w,$\texttt{w}^{\prime}$) (which also occurs before $s$) will perform
a CAS(x->right, null, w), violating (1). This contradiction proves that there
is no w such that $\texttt{x}\prec\texttt{w}\prec\texttt{y}$.

  3. (3)

We prove that claim 3 is preserved by all updates to the local variables left
and right in a remove operation.

By the precondition of remove(y), y is not the sentinel node. Moreover, a call
to tryAppend(y,*) has returned true, so by the preconditions of tryAppend, we
know that y has been added to the list before the remove begins. Moreover, the
tryAppend executed line 24, after which y->right is non-null. So, by induction
hypothesis 2, y->right points to a node that has been added to the list.

So, when the local variable left in the remove(y) operation is initialized on
line 29 to the value read from y->left, the claim follows from induction
hypothesis 1. Similarly, when the local variable right is initialized on line
30, the claim follows from induction hypothesis 2.

When the local variable left is advanced from x to $\texttt{x}^{\prime}$ at
line 33 in a remove(y), we have $\texttt{x}^{\prime}\leftarrow\texttt{x}$.
Since x is marked, so it is not the sentinel node, since the precondition to
remove ensures that the sentinel node is never marked. By induction hypothesis
1, $\texttt{x}^{\prime}\prec\texttt{x}$ and each node w satisfying
$\texttt{x}^{\prime}\prec\texttt{w}\prec\texttt{x}$ is marked. By induction
hypothesis 3, $\texttt{x}\prec\texttt{y}$ and each node w satisfying
$\texttt{x}\prec\texttt{w}\prec\texttt{y}$ is marked. Moreover, by the test on
line 33, x is marked. The claim follows.

A symmetric argument shows that advancing the local variable right at line 34
also preserves the invariant.

  4. (4)

Finally we show that claim 4 is preserved because no step can change the left
pointer of the sentinel node. Line 22 of tryAppend changes the left field of a
non-sentinel node, by the precondition to tryAppend. Consider a CAS step at
line 38 of remove(y) that changes z->left. By induction hypothesis 3,
$\texttt{y}\prec\texttt{z}$, so z cannot be the sentinel node (which is the
minimum element in the ordering $\prec$).

∎

See 3

###### Proof.

To derive a contradiction, suppose the claim is false.

Since there is a node x between w and y in the total order $\prec$, the head
pointer takes the value x between the times it takes the values w and y. Thus,
y is not added to the list by a tryAppend(w,y) operation, so the initial value
of y->left is not w. So, there is a CAS on line 38 of a remove operation that
changes y->left to w. This CAS was preceded by a test at line 37 that found y
was not marked. At that time, the local variables left and right of the remove
are equal to w and y. By Invariant 2.3, x is marked since
$\texttt{w}\prec\texttt{x}\prec\texttt{y}$. Thus, x is marked before y.

An identical argument shows that a CAS at line 38 of a remove operation
changes z->left to x and at the execution of line 37 before that CAS, x is not
marked and y is marked, so y is marked before x. This is a contradiction. ∎

See 4

###### Proof.

To derive a contradiction, suppose $\texttt{w}\succ\texttt{y}$. Consider the
configuration $C$ when y is read from z->left on line 36 prior to the CAS. At
$C$, w and z are the values of the local variables left and right of the
remove. By Invariant 2.3, $\texttt{w}\prec\texttt{z}$. In $C$, we have
$\texttt{{z}->left}=\texttt{y}\prec\texttt{w}\prec\texttt{z}$. By Invariant
2.1, w is marked in $C$. This contradicts the fact that w is unmarked when
line 37 is executed after $C$. ∎

$\preceq$zyBefore CASAfter CASvxwvxw$\prec$$\prec$$\preceq$$\preceq$y$\prec$z

Figure 9. Proof of Lemma 5 and Lemma 16.

Recall that $\texttt{x}\leftsquigarrow\texttt{z}$ if x can be reached from z
by following left pointers. More formally,
$\texttt{x}\leftsquigarrow\texttt{z}$ if (a) $\texttt{x}=\texttt{z}$ or (b)
for some y, $\texttt{y}\leftarrow\texttt{z}$ and
$\texttt{x}\leftsquigarrow\texttt{y}$.

See 5

###### Proof.

Refer to Figure 9. Let x be the minimum node (with respect to $\prec$) such
that $\texttt{x}\succeq\texttt{w}$ and $\texttt{x}\leftsquigarrow\texttt{y}$
in $C$. (This minimum is well-defined, since there exists a node x that
satisfies both of these properties: $\texttt{y}\succeq\texttt{w}$ by Lemma 4
and $\texttt{y}\leftsquigarrow\texttt{y}$ holds trivially.) Since
$\texttt{x}\leftsquigarrow\texttt{y}\leftarrow\texttt{z}$, we have
$\texttt{x}\prec\texttt{z}$ by Lemma 2.1.

Let v be the value of x->left in $C$. By Invariant 2.1,
$\texttt{v}\prec\texttt{x}$. It must be the case that
$\texttt{v}\prec\texttt{w}$; otherwise we would have
$\texttt{v}\succeq\texttt{w}$ and $\texttt{v}\leftsquigarrow\texttt{y}$, which
would contradict the fact that x is the _minimum_ node that satisfies these
two properties.

To derive a contradiction, suppose $\texttt{w}\prec\texttt{x}$. Then we have
$\texttt{v}\prec\texttt{w}\prec\texttt{x}\prec\texttt{z}$. We also have
$\texttt{w}\leftarrow\texttt{z}$ after the CAS and
$\texttt{v}\leftarrow\texttt{x}$ in $C$, which contradicts Lemma 3. Thus,
$\texttt{w}\succeq\texttt{x}$. By definition of x,
$\texttt{x}\succeq\texttt{w}$ and $\texttt{x}\leftsquigarrow\texttt{y}$ in
$C$. Thus, $\texttt{x}=\texttt{w}$ and $\texttt{w}\leftsquigarrow\texttt{y}$.
∎

See 6

###### Proof.

A node can only be removed from the abstract list by a CAS step on a left
pointer. Consider a CAS at line 38 that changes z->left from y to w. By
Invariant 2.1 and Lemma 5, only nodes x satisfying
$\texttt{w}\prec\texttt{x}\prec\texttt{y}$ can be removed from the abstract
list by this CAS. Since w and y are the values of the local variables left and
right in the remove operation that performs the CAS, Invariant 2.3 ensures
that all such nodes x are marked when the CAS occurs. ∎

To ensure that we can linearize remove operations, we show that a remove(x)
successfully removes x from the abstract list. The remove can only terminate
when it performs a successful CAS on the left pointer of some node appended to
the list after x. The following lemma shows that when that happens, x is no
longer in the abstract list.

See 7

###### Proof.

Since the remove(x) terminates, it performs a successful CAS on a left pointer
at line 38. Let w and z be the values of the remove’s local variables left and
right when the CAS occurs. The CAS updates z->left to w. By Invariant 2.3,
$\texttt{w}\prec\texttt{x}\prec\texttt{z}$.

To derive a contradiction, suppose that x is still in the abstract list in the
configuration $C$ after this CAS.

Since x is in the abstract list and
$\texttt{{z}->left}\prec\texttt{x}\prec\texttt{z}$, there must be nodes
$\texttt{v}^{\prime}$ and v in the abstract list such that
$\texttt{x}\leftsquigarrow\texttt{v}^{\prime}\leftarrow\texttt{v}\leftsquigarrow\texttt{head}$
with $\texttt{v}^{\prime}\prec\texttt{z}\prec\texttt{v}$. Refer to Figure 10.
More formally, let v be the minimum node (with respect to the order $\prec$)
such that $\texttt{v}\succeq\texttt{z}$ and
$\texttt{v}\leftsquigarrow\texttt{head}$ in $C$. Let
$\texttt{v}^{\prime}=\texttt{v->left}$. It follows from the definition of v
that $\texttt{v}^{\prime}\prec\texttt{z}$. If v were equal to z, then since x
is in the abstract list, x would have to be reachable by following left
pointers from w, which would violate 2.1, since $\texttt{w}\prec\texttt{x}$.
Thus, $\texttt{v}\succ\texttt{z}$.

So, we have
$\texttt{w}\prec\texttt{x}\preceq\texttt{v}^{\prime}\prec\texttt{z}\prec\texttt{v}$
and $\texttt{w}\leftarrow\texttt{z}$ and
$\texttt{v}^{\prime}\leftarrow\texttt{v}$, which violates Lemma 3. ∎

whead$\texttt{v}^{\prime}$zvx

Figure 10. Proof of Lemma 7.

We now specify the linearization points of update operations so that we
maintain the invariant that, for all configurations $C$, the abstract list
$L_{C}$ in that configuration is exactly the list that would be obtained by
performing the operations linearized before $C$ in their linearization
ordering. We linearize a successful tryAppend operation (i.e., one that
returns true) when it updates the head pointer at line 23. We linearize a
remove(x) when a CAS at line 38 removes x from the abstract list. This step
may be performed by the remove itself or by another remove operation. By Lemma
5, n will remain out of the abstract list forever once it is removed. By Lemma
6, only marked nodes are removed from the abstract list when a left pointer is
updated. By Lemma 7, there is a well-defined linearization point for each
remove operation that terminates, and it is before the remove terminates. By
Lemma 6, it is also after the remove operation performs line 28, so the
linearization point is during the execution interval of the remove. Thus, the
linearization is consistent with the abstract list.

A CAS of a left pointer may remove several nodes from the abstract list, and
therefore be used as the linearization point of several remove operations.
When linearizing such a batch of remove operations, we order them in
decreasing order by $\prec$. In other words, we remove the batch of nodes from
right to left. Thus, when a CAS on a left pointer splices several nodes out of
the abstract list, we can think of the abstract list as undergoing a sequence
of changes by performing those remove operations one by one. This will be
important, because it is sometimes necessary to linearize searches in the
_middle_ of such a batch of remove operations.

We now describe how to linearize search operations. It is a common technique
to argue that each node visited by a search  _was_ in the data structure at
some time during the search (e.g., (Ellen et al., 2010; O’Hearn et al.,
2010)). Such proofs often rely on the fact that once a node is removed from
the data structure, its pointers can no longer be changed. This does not hold
for our data structure, but we can still establish the required property using
Lemmas 3 and 5. (An alternative approach would be to use the forepassed
condition defined in (Feldman et al., 2020).)

See 8

###### Proof.

Consider any search(k) operation in the execution. We prove the claim holds
for every configuration $C$ during the search by induction on the number of
steps the search has performed.

For the base case, consider the configuration $C$ after the search is invoked
and executes line 14, x is initialized to head, so it is the first node in the
abstract list in $C$.

For the induction step, we must just verify that steps that modify the local
variable x preserve the claim. Consider an execution of line 16 that advances
the search from node x to $\texttt{x}^{\prime}$, and let $C$ be the
configuration after that step. Then, in $C$,
$\texttt{x}^{\prime}\leftarrow\texttt{x}$. By the test at line 15,
$\texttt{{x}->key}>\texttt{k}$.

First, consider the case where x is in $L_{C}$. Since
$\texttt{x}^{\prime}\leftarrow\texttt{x}$ in $C$, $\texttt{x}^{\prime}$ is
also in $L_{C}$ and its predecessor x in $L_{C}$ has a key greater than k.
Thus, the claim is satisfied at $C$.

So, for the remainder of the proof, assume x is not in $L_{C}$. By the
induction hypothesis, there was an earlier time during the search when x was
in the abstract list. So there was a CAS step $s$ during the search that
removed x from the abstract list.

Lemma 5 implies that if $\texttt{x}^{\prime}\leftsquigarrow\texttt{x}$ after
some CAS on a left pointer, then
$\texttt{x}^{\prime}\leftsquigarrow\texttt{x}$ before that CAS too. Since
$\texttt{x}^{\prime}\leftsquigarrow\texttt{x}$ in $C$, it follows that
$\texttt{x}^{\prime}\leftsquigarrow\texttt{x}$ holds in all configurations
between the addition of x to the abstract list and $C$. In particular, this
means that $\texttt{x}^{\prime}\leftsquigarrow\texttt{x}$ in the configuration
before $s$. So $\texttt{x}^{\prime}$ is in the abstract list in that
configuration. We consider the two possible cases.

$C$:head$\texttt{x}^{\prime}$yzx$\texttt{z}^{\prime}$$\texttt{x}^{\prime}$x$C^{\prime}$:

Figure 11. Proof of Lemma 8.

  * •

Suppose $s$ removes both x and $\texttt{x}^{\prime}$ from the abstract list.
Then $s$ removes some sequence of nodes from the abstract list by updating the
left pointer of some node z. Since we linearize a batch of remove operations
from right to left, z is the predecessor of $\texttt{x}^{\prime}$ in the
abstract list just before the linearization of remove($\texttt{x}^{\prime}$).
It follows from Lemma 5 that $\texttt{x}\leftsquigarrow\texttt{z}$ in the
configuration before $s$. By the precondition that the list is always sorted,
we have $\texttt{{z}->key}\geq\texttt{{x}->key}>\texttt{k}$. Thus, the claim
is satisfied just before the linearization point of the
remove($\texttt{x}^{\prime}$).

  * •

Suppose $\texttt{x}^{\prime}$ is still in the abstract list in the
configuration $C^{\prime}$ following $s$. If $\texttt{x}^{\prime}$ is the
first element of $L_{C^{\prime}}$, then the claim holds.

Otherwise, there is some y such that in $C^{\prime}$,
$\texttt{x}^{\prime}\leftarrow\texttt{y}\leftsquigarrow\texttt{head}$. To
derive a contradiction, suppose $\texttt{y}\prec\texttt{x}$. Then there must
be nodes z and $\texttt{z}^{\prime}$ such that
$\texttt{y}\preceq\texttt{z}\prec\texttt{x}\prec\texttt{z}^{\prime}$ and
$\texttt{y}\leftsquigarrow\texttt{z}\leftarrow\texttt{z}^{\prime}\leftsquigarrow\texttt{head}$
in $C^{\prime}$. (See Figure 11: at some point in the path from head to y,
there must be consecutive nodes $\texttt{z}\leftarrow\texttt{z}^{\prime}$ such
that $\texttt{z}\prec\texttt{x}\prec\texttt{z}^{\prime}$ since x is not in the
abstract list.) So we have
$\texttt{x}^{\prime}\prec\texttt{x}\prec\texttt{x}\prec\texttt{z}^{\prime}$
and $\texttt{z}\leftarrow\texttt{z}^{\prime}$ in $C^{\prime}$ and
$\texttt{x}^{\prime}\leftarrow\texttt{x}$ in $C$. This violates Lemma 3.
Hence, $\texttt{y}\succeq\texttt{x}$. We cannot have $\texttt{y}=\texttt{x}$,
since y in in $L_{C^{\prime}}$ and x is not. So, $\texttt{y}\succ\texttt{x}$.
By the precondition that nodes are appended with non-decreasing keys, this
means that $\texttt{{y}->key}\geq\texttt{{x}->key}>\texttt{k}$. So,
$\texttt{x}^{\prime}$ is in $L_{C^{\prime}}$ and its predecessor y has a key
greater than $k$, as required.

∎

Suppose a search(k) returns the value of a node x. By the exit condition on
line 15, $\texttt{vx->key}\leq\texttt{k}$. Lemma 8 says there is a time during
the search when x is in the abstract list and its predecessor in the list has
a key greater than k. Thus, at that time, x is the first node in the abstract
list whose key is less than or equal to k. We choose that time as the
linearization point of the search.

##  Appendix B Correctness of the Singly-Linked List

We assume that the following preconditions are satisfied.

  1. (1)

If tryAppend(x,y) is invoked, then x has been read from head, and no other
tryAppend(*,y) has been invoked.

  2. (2)

If a node x is appended to the list before y,
$\texttt{x}.\texttt{ts}\leq\texttt{y}.\texttt{ts}$.

  3. (3)

While a search(t) is in progress, t appears in Announce.

  4. (4)

At all times after a compact(A,t,*) is invoked and for all i, either
$\texttt{Announce}[\texttt{i}]\in\texttt{A}$ or
$\texttt{Announce}[\texttt{i}]\geq\texttt{t}$.

These conditions are satisfied naturally in MVGC applications. Since compact
takes its parameters from an AnnScan object (A,t), scanAnnounce ensures that t
was copied from shared memory before A. Since the global timestamp is non-
decreasing, any value stored in Announce[i] after that entry was copied into
Awill be greater than t. (We assume rtxs announcing a timestamp copy the
global timestamp into Announce atomically, as described in (Wei et al., 2021).
An optimization that avoids this is described in Appendix B.2.)

As in Section 4.1, we say a node is appended to the list when a pointer to the
node is stored in head. We consider the sentinel node to be appended to the
list when the list is created. We also use the notation
$\texttt{x}\leftarrow\texttt{y}$ and $\texttt{x}\prec\texttt{y}$ as in Section
4.1. We first prove some simple facts about the algorithm.

###### Invariant 9.

  1. (1)

If y has been appended to the list and is not the sentinel node and
$\texttt{w}\leftarrow\texttt{y}$ then w is a node that has been appended to
the list and $\texttt{w}\prec\texttt{y}$.

  2. (2)

If a CAS at line 28 changes y->left from x to w, then
$\texttt{w}\prec\texttt{x}$.

  3. (3)

A compact never sets cur, next or newNext to null.

###### Proof.

We show that each step preserves the invariant. Assume the invariant holds
prior to the step. We need only consider steps that append a node,
successfully CAS a left pointer and update the local variables cur, next and
newNext.

First, consider a step that appends a node y to the list (line 34). If
$\texttt{w}\leftarrow\texttt{y}$ when y is appended to the list by a CAS at
line 34, then head is changed from w directly to y. Thus, w is a node that was
appended to the list before y.

The only step that changes a left pointer after it is initialized is a
successful CAS at line 28. Suppose this step changes y->left from x to w.
Then, x and w are the values of local variables next and newNext when the CAS
occurs. Prior to the CAS, w has been reached from y by following left
pointers, first at line 16 and then at lines 25–27. Moreover, before advancing
from one node to the next by reading a left pointer (at line 16, 25 or 27),
the algorithm first checks (at line 15, 22 or 26, respectively) that the
former node is not the sentinel, either explicitly, or by checking that the
node’s ts field is greater than A[i]. Since the invariant holds before the
CAS, w has been appended and $\texttt{w}\prec\texttt{x}\prec\texttt{y}$.

As mentioned in the previous paragraph, when we set next at line 16 or set
newNext at lines 25 or 27 by reading the left field of a node, we first check
that that node is not the sentinel. Since the invariant holds before reading
this left field, the value we store in next or newNext is non-null. Similarly,
if next is updated at line 29, the test at line 15 guarantees that cur is not
the sentinel, so its left pointer is non-null.

We check that all steps that set the cur variable give it a non-null value.
The cur variable is set to the value read from head at line 14, and head is
never null. Lines 19 and 23 copy the value next into cur, and this value is
non-null, by the induction hypothesis. Line 31 sets cur to the value read from
the left field of a node that is known not to be the sentinel (by the test at
line 15), so its left field is non-null by the induction hypothesis. ∎

It follows from Invariant 9 that all pointers dereferenced in compact are non-
null.

The following technical lemma shows that compact updates i appropriately to
carry out the test of whether node next is needed.

###### Lemma 10.

If the test on line 22 fails, then either i is the index of the last entry of
A or $\texttt{cur->{ts}}\leq\texttt{{A}[i+1]}$.

###### Proof.

Let $C$ be the configuration after the test on line 22 fails. Consider the
configuration $C_{i}$ after the last time the local variable i was updated
prior to $C$. If this was when i was initialized at line 13, then i is the
index of the last element of A, which makes the claim true. Otherwise, i was
updated at line 21. Then, $\texttt{A[i+1]}\geq\texttt{cur->{ts}}$ held at
$C_{i}$. Between $C_{i}$ and $C$, we argue that changes to cur can only cause
cur->ts to decrease. If cur is updated at line 19 or 23 it is changed to the
value read from the left pointer of the previous cur node at line 16.
Similarly, line 31 updates cur to the value read from the left pointer of the
previous cur node. By Lemma 9 and precondition 2, updating cur between $C_{i}$
and $C$ by traversing left pointers cannot cause cur->ts to increase. Thus, at
$C$, we still have $\texttt{cur->ts}\leq\texttt{{A}[i+1]}$. ∎

We say that $(\texttt{A},\texttt{t})$ _is written before_
$(\texttt{A}^{\prime},\texttt{t}^{\prime})$ if an AnnScan object
$(\texttt{A},\texttt{t})$ is stored in GlobalAnnScan before
$(\texttt{A}^{\prime},\texttt{t}^{\prime})$. The following lemma is proved
using the fact that creating the earlier copy completes before creating the
later copy begins, because of the way we use CAS to update GlobalAnnScan.
This, in turn, guarantees that once a node becomes unneeded, it is never
needed by a later AnnScan pair.

###### Lemma 11.

Suppose $(\texttt{A}_{1},\texttt{t}_{1})$ is written before
$(\texttt{A}_{2},\texttt{t}_{2})$. For any node x, if x is
$needed(\texttt{A}_{2},\texttt{t}_{2})$ then x is
$needed(\texttt{A}_{1},\texttt{t}_{1})$.

###### Proof.

Since every CAS on GlobalAnnScan tries to install a newly created object,
there is no ABA problem on GlobalAnnScan. Thus, GlobalAnnScan is not updated
between the time it is read on line 6 and the time a successful CAS is applied
to it on line 9. Thus, $(\texttt{A}_{1},\texttt{t}_{1})$ is stored in
GlobalAnnScan before the process that stores $(\texttt{A}_{2},\texttt{t}_{2})$
begins reading the values $(\texttt{A}_{2},\texttt{t}_{2})$ from the Announce
array and the global timestamp. Thus, $t_{1}\leq t_{2}$. Moreover, if some
value $\texttt{t}<\texttt{t}_{1}$ appears in $\texttt{A}_{2}$, then it must
also appear in $\texttt{A}_{1}$ since we assume values written into the
Announce array are atomically copied from the global timestamp.

Assume x is $needed(\texttt{A}_{2},\texttt{t}_{2})$. We consider several
cases.

If $\texttt{x}.\texttt{ts}>\texttt{t}_{1}$, then x is also
$needed(\texttt{A}_{1},\texttt{t}_{1})$, by definition.

If $\texttt{x}.\texttt{ts}\leq\texttt{t}_{1}$ and x is the last appended node
with timestamp at most $\texttt{t}_{2}$, then it is also the last appended
node with timestamp at most $\texttt{t}_{1}$ since
$\texttt{t}_{1}\leq\texttt{t}_{2}$. Thus, x is
$needed(\texttt{A}_{1},\texttt{t}_{1})$.

Otherwise, $\texttt{x}.\texttt{ts}\leq\texttt{t}_{1}$ and x is the last
appended node with timestamp at most $\texttt{A}_{2}[\texttt{i}]$ for some i.
If $\texttt{A}_{2}[\texttt{i}]\geq\texttt{t}_{1}$, then x is also the last
appended node with timestamp at most $\texttt{t}_{1}$, and is therefore
$needed(\texttt{A}_{1},\texttt{t}_{1})$. If
$\texttt{A}_{2}[\texttt{i}]<\texttt{t}_{1}$ then the value
$\texttt{A}_{2}[\texttt{i}]$ must also appear in $\texttt{A}_{1}$. So, again x
is $needed(\texttt{A}_{1},\texttt{t}_{1})$. ∎

The following key lemma describes how a compact(A,t,*) works: it traverses
nodes that are $needed(\texttt{A},\texttt{t})$ and splices out those nodes
that are not $needed(\texttt{A},\texttt{t})$. The proof is necessarily quite
technical because, even though the set of needed nodes can only be reduced
when GlobalAnnScan is updated, there many compact routines simultaneously
traversing a version list, whose arguments are $(\texttt{A},\texttt{t})$ pairs
read from GlobalAnnScan at different times–some out of date and some more
current.

###### Lemma 12.

If an invocation of compact(A,t,h) sets its local variable cur to a node
$\texttt{x}\neq\texttt{h}$, then x is $needed(\texttt{A},\texttt{t})$. If an
invocation of compact(A,t,h) performs a successful CAS that stores v in
x->left, then x is $needed(\texttt{A},\texttt{t})$ (unless
$\texttt{x}=\texttt{h}$) and v is $needed(\texttt{A},\texttt{t})$ and for all
w satisfying $\texttt{v}\prec\texttt{w}\prec\texttt{x}$, w is not
$needed(\texttt{A},\texttt{t})$.

###### Proof.

We prove the lemma by induction on steps: we assume the lemma is true in a
prefix of an execution and show that it remains true when an additional step
$s$ is appended to the prefix. We first prove a couple of technical claims
that will be used several times in the induction step.

###### Claim 12.1.

If $\texttt{x}\leftarrow\texttt{z}$ at some time before $s$ and either
$\texttt{x}.\texttt{ts}\leq\texttt{A}[\texttt{j}]<\texttt{z}.\texttt{ts}$ for
some j or $\texttt{z}.\texttt{ts}>\texttt{t}$, then x is
$needed(\texttt{A},\texttt{t})$.

###### Proof of Claim.

We consider several cases.

  1. (1)

If $\texttt{x}.\texttt{ts}>\texttt{t}$, then x is
$needed(\texttt{A},\texttt{t})$ by definition.

  2. (2)

If x is the last appended node whose timestamp is at most t, then x is
$needed(\texttt{A},\texttt{t})$ by definition.

  3. (3)

Suppose $\texttt{x}.\texttt{ts}\leq\texttt{t}<\texttt{z}.\texttt{ts}$ but x is
not the last node whose timestamp is at most t. Let y be the last appended
node whose timestamp is at most t. By definition, y is
$needed(\texttt{A},\texttt{t})$. Since $\texttt{z}.\texttt{ts}>\texttt{t}$, we
have $\texttt{x}\prec\texttt{y}\prec\texttt{z}$ by precondition 2. By the
hypothesis of the claim, some invocation
compact($\texttt{A}^{\prime}$,$\texttt{t}^{\prime}$) set z->left to x before
$s$. By the induction hypothesis, x is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ but y is not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$. Since y is
$needed(\texttt{A},\texttt{t})$ but not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, $(\texttt{A},\texttt{t})$
is written before $(\texttt{A}^{\prime},\texttt{t}^{\prime})$, by Lemma 11.
Since x is $needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, x is also
$needed(\texttt{A},\texttt{t})$, again by Lemma 11.

  4. (4)

If x is the last appended node whose timestamp is at most A[j] (for some j),
then x is $needed(\texttt{A},\texttt{t})$, by definition.

  5. (5)

Otherwise,
$\texttt{x}.\texttt{ts}\leq\texttt{A}[\texttt{j}]<\texttt{z}.\texttt{ts}$ for
some j, but x is not the last appended node with timestamp at most
$\texttt{A}[\texttt{j}]$. This case is very similar to Case 3. Let y be the
last appended node whose timestamp is at most $\texttt{A}[\texttt{j}]$. By
definition, y is $needed(\texttt{A},\texttt{t})$. Since
$\texttt{z}.\texttt{ts}>\texttt{A}[\texttt{j}]$, we have
$\texttt{x}\prec\texttt{y}\prec\texttt{z}$ by precondition 2. By the
hypothesis of the claim, some invocation
compact($\texttt{A}^{\prime}$,$\texttt{t}^{\prime}$) set z->left to x before
$s$. By the induction hypothesis, x is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ but y is not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$. Since y is
$needed(\texttt{A},\texttt{t})$ but not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, $(\texttt{A},\texttt{t})$
is written before $(\texttt{A}^{\prime},\texttt{t}^{\prime})$, by Lemma 11.
Since x is $needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, x is also
$needed(\texttt{A},\texttt{t})$, again by Lemma 11.

∎

###### Claim 12.2.

If $s$ is an execution of line 28 or 31, let v and x be the nodes stored in
newNext and cur, respectively, in the configuration before $s$. Then
$\texttt{v}\prec\texttt{x}$ and v is $needed(\texttt{A},\texttt{t})$ and for
all w satisfying $\texttt{v}\prec\texttt{w}\prec\texttt{x}$, w is not
$needed(\texttt{A},\texttt{t})$.

###### Proof of Claim.

The node v was reached from x by following left pointers, at line 16 and then
at lines 25–27. By Invariant 9, $\texttt{v}\prec\texttt{x}$. Let
$\texttt{x}=\texttt{w}_{1},\texttt{w}_{2},\ldots,\texttt{w}_{k}=\texttt{v}$ be
the sequence of nodes traversed to get from x to v. By the tests on lines 22
and 26,
$\texttt{w}_{k}.\texttt{ts}\leq\texttt{A}[\texttt{i}]<\texttt{w}_{k-1}.\texttt{ts}$.
Since $\texttt{w}_{k}$ was read from $\texttt{w}_{k-1}$ before $s$, Claim 12.1
implies that $\texttt{v}=\texttt{w}_{k}$ is $needed(\texttt{A},\texttt{t})$.

It remains to show that all nodes w satisfying
$\texttt{v}\prec\texttt{w}\prec\texttt{x}$ are not
$needed(\texttt{A},\texttt{t})$. Since the test at line 18 failed,
$\texttt{x}.\texttt{ts}\leq\texttt{t}$. So a node $\texttt{w}\prec\texttt{x}$
cannot be the last appended node with timestamp at most t, nor can w have a
timestamp greater than t. To complete the proof that w is not
$needed(\texttt{A},\texttt{t})$, we must show that it is not the last appended
node with timestamp at most A[j] for any j. We do this in two parts, first
considering $\texttt{j}>\texttt{i}$ and then $\texttt{j}\leq\texttt{i}$.
(Recall that $\texttt{A[0]}=-1$.)

Since x is the value of cur when the test at line 22 fails, it follows from
Lemma 10 that either i is the index of the last element of A or
$\texttt{{x}->{ts}}\leq\texttt{A}[\texttt{i}+1]$. Thus, any node
$\texttt{w}\prec\texttt{x}$ cannot be the last appended node whose timestamp
is at most $\texttt{A}[j]$ for any $\texttt{j}>\texttt{i}$, since then i would
not be the last index and so
$\texttt{x}.\texttt{ts}\leq\texttt{A}[\texttt{i}+1]\leq\texttt{A}[\texttt{j}]$.

To derive a contradiction, suppose that there is some w such that
$\texttt{v}\prec\texttt{w}\prec\texttt{x}$ and w is
$needed(\texttt{A},\texttt{t})$. Since we have already eliminated all other
possibilities, this means that for some $j\leq i$, w is the last appended node
whose timestamp is at most $\texttt{A}[\texttt{j}]$. Since
$\texttt{w}.\texttt{ts}\leq\texttt{A}[\texttt{j}]\leq\texttt{A}[\texttt{i}]<\texttt{w}_{k-1}.\texttt{ts}$,
we must have $\texttt{v}=\texttt{w}_{k}\prec\texttt{w}\prec\texttt{w}_{k-1}$.
(In particular, this means that $\texttt{w}_{k-1}$ cannot be
$needed(\texttt{A},\texttt{t})$.) Since $\texttt{w}_{k}$ was read before $s$
from $\texttt{w}_{k-1}$->left, the induction hypothesis implies that some
compact($\texttt{A}^{\prime}$,$\texttt{t}^{\prime}$) did a CAS that set
$\texttt{w}_{k-1}$->left to $\texttt{w}_{k}$ and $\texttt{w}_{k-1}$ is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ but w is not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$. Since $\texttt{w}_{k-1}$ is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ but not
$needed(\texttt{A},\texttt{t})$, Lemma 11 implies that the AnnScan object
$(\texttt{A}^{\prime},\texttt{t}^{\prime})$ is written before
$(\texttt{A},\texttt{t})$. Since w is not
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, it follows from Lemma 11
that w is not $needed(\texttt{A},\texttt{t})$. This contradiction completes
the proof of the claim. ∎

Now we are ready to prove that step $s$ preserves the truth of the lemma. We
need only consider steps $s$ that update the cur variable of a compact routine
or perform a successful CAS at line 28.

Now, suppose $s$ executes line 19 to change the cur pointer from node z to x.
Then x was read from x->left at line 16. By the test at line 18,
$\texttt{z}.\texttt{ts}>\texttt{t}$. So, by Claim 12.1, x is
$needed(\texttt{A},\texttt{t})$.

Now, suppose $s$ executes line 23 to change the cur pointer from node z to x.
Then, x was read from x->left at line 16. Since the while loop at line 21
terminated, we have $\texttt{z}.\texttt{ts}>\texttt{A}[i]$. By the test at
line 22, we have $\texttt{x}\leq\texttt{A}[i]$. So, by Claim 12.1, x is
$needed(\texttt{A},\texttt{t})$.

Now, suppose $s$ performs a successful CAS at line 28 that changes x->left to
v. Then x and v are the values of the local variables cur and newNext,
respectively, when the CAS occurs. Since x is stored in cur, x is
$needed(\texttt{A},\texttt{t})$, by the induction hypothesis. Claim 12.2 says
that v is $needed(\texttt{A},\texttt{t})$ and any node w satisfying
$\texttt{v}\prec\texttt{w}\prec\texttt{x}$ is not
$needed(\texttt{A},\texttt{t})$.

Finally, suppose $s$ executes line 31 to change the cur pointer from node z to
w. Let y be the node stored in newNext. By Claim 12.2,
$\texttt{y}\prec\texttt{z}$ and y is $needed(\texttt{A},\texttt{t})$. We argue
that, prior to $s$, a node $\texttt{x}\preceq\texttt{y}$ was stored in z->left
by considering two cases. If the loop at lines 28–30 terminated because the
CAS at line 28 succeeded, then that CAS stored y in z->left. Otherwise, the
test at line 30 was true, so the node x read from z->left on line 29 satisfied
$\texttt{x}.\texttt{ts}\leq\texttt{y}.\texttt{ts}$. Since the test at line 18
failed, $\texttt{z}.\texttt{ts}\leq\texttt{t}$. Since
$\texttt{y}\prec\texttt{z}$,
$\texttt{y}.\texttt{ts}\leq\texttt{z}.\texttt{ts}\leq\texttt{t}$ by
precondition 2. Since y is $needed(\texttt{A},\texttt{t})$, it must be the
last appended node with its timestamp. Therefore,
$\texttt{x}.\texttt{ts}\leq\texttt{y}.\texttt{ts}$ implies that
$\texttt{x}\preceq\texttt{y}$. Thus, in either case, a node
$\texttt{x}\preceq\texttt{y}$ was stored in z->left before $s$. By Lemma 9,
the node w that $s$ reads in z->left satisfies $\texttt{w}\preceq\texttt{x}$.
We show that w is $needed(\texttt{A},\texttt{t})$ by considering two cases. If
$\texttt{w}=\texttt{y}$, we already know that y is
$needed(\texttt{A},\texttt{t})$. If $\texttt{w}\neq\texttt{y}$, we have
$\texttt{w}\preceq\texttt{x}\preceq\texttt{y}\prec\texttt{z}$. Assume the CAS
that stored w in x->left was performed by a
compact($\texttt{A}^{\prime}$,$\texttt{t}^{\prime}$). By the induction
hypothesis, y is not $needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ since
$\texttt{w}\prec\texttt{y}\prec\texttt{z}$ and a CAS in
compact($\texttt{A}^{\prime}$,$\texttt{t}^{\prime}$) stored w in z->left.
Since y is $needed(\texttt{A},\texttt{t})$, Lemma 11 implies that
$(\texttt{A},\texttt{t})$ was written before
$(\texttt{A}^{\prime},\texttt{t}^{\prime})$. Since w is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$, it follows from Lemma 11
that w is $needed(\texttt{A},\texttt{t})$. ∎

We linearize successful tryAppend operations when they CAS the head pointer of
the list. We linearize a search operation when it reads the head at line 36.
The following theorem guarantees that every search operation returns the
correct response.

###### Theorem 13.

If a search(k) operation returns the value from the last node appended to the
list before the linearization point of the search whose timestamp is at most
k.

###### Proof.

The search returns the value from the node stored in the local variable x.

If x is the value read from head at line 36, then x is the last node appended
to the list before the linearization point of the search, and its timestamp is
at most t since the test at line 37 failed.

Otherwise, there is a configuration $C$ during the search just before x is
read from the left pointer of some node z at line 38. By the test at line 37,
we know that $\texttt{{x}->{ts}}\leq\texttt{t}<\texttt{{z}->{ts}}$. To derive
a contradiction, suppose x is not the last appended node whose timestamp is at
most k. Let y be the last appended node whose timestamp is at most k. Then,
$\texttt{x}\prec\texttt{y}\prec\texttt{z}$.

By Lemma 12, there is an invocation of compact(A,t) before $C$ such that y is
not $needed(\texttt{A},\texttt{t})$. We consider two cases.

If $\texttt{k}\in\texttt{A}$, then y is not the last appended node whose
timestamp is at most k, since y is not $needed(\texttt{A},\texttt{t})$. This
is the desired contradiction.

Otherwise, $\texttt{k}\notin\texttt{A}$. At $C$, k is the in the Announce
array, by precondition 3. By precondition 4, this means that
$\texttt{k}\geq\texttt{t}$. Since y is not $needed(\texttt{A},\texttt{t})$,
$\texttt{{y}->{ts}}\leq\texttt{t}$, and there is a node appended after y whose
timestamp is also at most t. Since $\texttt{k}\geq\texttt{t}$, there is
another node appended after y whose timestamp is at most k. Again, this is a
contradiction. ∎

###  B.1. Analysis

We now consider progress properties. We use Invariant 9 to prove wait-freedom
and that search does not fall off the end of the list.

###### Lemma 14.

The compact and search routines are wait-free. A search never sets its local
variable x to null.

###### Proof.

We first show that compact is wait-free. Each iteration of the outer loop
updates cur at line 19, 23 or 31 to a value read from cur->left at line 16 or
31. Consider the sequence of values $\texttt{x}_{1},\texttt{x}_{2},\ldots$
assigned to the cur variable of the compact routine. By Invariant 9, all the
values are non-null and we have
$\texttt{x}_{1}\succ\texttt{x}_{2}\succ\cdots$. Since there are finitely many
nodes that precede $\texttt{x}_{1}$ in the order $\prec$, the loop will
terminate.

We must also check that the inner loops terminate. Due to the test at line 15,
cur is not the sentinel node when the loop at line 21 is executed. Thus,
$\texttt{cur->{ts}}\geq 0$, so when the index i reaches 0,
$\texttt{A}[0]=-1<\texttt{cur->{ts}}$ and the loop terminates. (This argument
also ensures that we never use an out-of-bounds index for A.)

Each iteration of the loop at lines 26–27 sets newNext to an earlier node in
the order $\prec$, by Invariant 9. So, it must terminate.

Each time the test at line 28 fails, some other operation has performed a
successful CAS on cur->left. By Invariant 9, each such CAS changes cur->left
to an earlier node in the order $\prec$, so it must eventually terminate.

We now show that search is wait-free and does not set x to null. Line 36
initializes x to the node read from head, which has been appended (by
definition). If line 38 changes x, then the node previously stored in x was
not the sentinel, since its timestamp was greater than $\texttt{k}\geq 0$.
Thus, the value read from its left pointer is non-null, by Lemma 9.

If the sequences of nodes visited by the search is
$\texttt{x}_{1},\texttt{x}_{2},\ldots$, then by Lemma 9, we have
$\texttt{x}_{1}\succ\texttt{x}_{2}\succ\cdots$. Since there are only finitely
many nodes that precede $\texttt{x}_{1}$ in the order $\prec$, the loop must
terminate. ∎

For PDL, we proved Lemmas 3 and 5 to show that CAS steps on left pointers can
only remove nodes; they cannot cause a remove node to return to the list. We
now prove analogous results for SSL.

###### Lemma 15.

Suppose $\texttt{w}\prec\texttt{x}\prec\texttt{y}\prec\texttt{z}$ and
$\texttt{w}\leftarrow\texttt{y}$ at some time during the execution. Then there
is never a time when $\texttt{x}\leftarrow\texttt{z}$.

###### Proof.

To derive a contradiction, suppose the claim is false.

Since there is a node x between w and y in the total order $\prec$, the head
pointer takes the value x between the times it takes the values w and y. Thus,
y is not added to the list by a tryAppend(w,y) operation, so the initial value
of y->left is not w. So, there is a CAS on line 28 of a compact(A,t,h)
operation that changes y->left to w. Similarly, there is a CAS of a
compact(A,t,h) operation that changes z->left to x. By Lemma 12, x is
$needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$ but not
$needed(\texttt{A},\texttt{t})$. By Lemma 11,
$(\texttt{A}^{\prime},\texttt{t}^{\prime})$ is written before
$(\texttt{A},\texttt{t})$. Since the arguments of compact are obtained by
taking a snapshot of GlobalAnnScan and head, this means that
$\texttt{h}^{\prime}$ was stored in head before h, so
$\texttt{h}^{\prime}\preceq\texttt{h}$. Thus,
$\texttt{w}\prec\texttt{x}\preceq\texttt{h}^{\prime}\preceq\texttt{h}$, so
$\texttt{w}\neq\texttt{h}$. By Lemma 12, w is $needed(\texttt{A},\texttt{t})$
but not $needed(\texttt{A}^{\prime},\texttt{t}^{\prime})$. This contradicts
Lemma 11. ∎

###### Lemma 16.

If a CAS at line 28 changes z->left from y to w, we have
$\texttt{w}\leftsquigarrow\texttt{y}$ in the preceding configuration $C$.

###### Proof.

Refer to Figure 9. Let x be the minimum node (with respect to $\prec$) such
that $\texttt{x}\succeq\texttt{w}$ and $\texttt{x}\leftsquigarrow\texttt{y}$
in $C$. (This minimum is well-defined, since there exists a node x that
satisfies both of these properties: $\texttt{y}\succeq\texttt{w}$ by Lemma 4
and $\texttt{y}\leftsquigarrow\texttt{y}$ holds trivially.) Since
$\texttt{x}\leftsquigarrow\texttt{y}\leftarrow\texttt{z}$, we have
$\texttt{x}\prec\texttt{z}$ by Lemma 9.

Let v be the value of x->left in $C$. By Lemma 9, $\texttt{v}\prec\texttt{x}$.
It must be the case that $\texttt{v}\prec\texttt{w}$; otherwise we would have
$\texttt{v}\succeq\texttt{w}$ and $\texttt{v}\leftsquigarrow\texttt{y}$, which
would contradict the fact that x is the _minimum_ node that satisfies these
two properties.

To derive a contradiction, suppose $\texttt{w}\prec\texttt{x}$. Then we have
$\texttt{v}\prec\texttt{w}\prec\texttt{x}\prec\texttt{z}$. We also have
$\texttt{w}\leftarrow\texttt{z}$ after the CAS and
$\texttt{v}\leftarrow\texttt{x}$ in $C$, which contradicts Lemma 15. Thus,
$\texttt{w}\succeq\texttt{x}$. By definition of x,
$\texttt{x}\succeq\texttt{w}$ and $\texttt{x}\leftsquigarrow\texttt{y}$ in
$C$. Thus, $\texttt{x}=\texttt{w}$ and $\texttt{w}\leftsquigarrow\texttt{y}$.
∎

Lemma 16 allows us to prove that the compact routine permanently removes
unneeded nodes.

###### Proposition 17.

Suppose a compact(A,t,h) routine on a version list has terminated prior to
some configuration $C$. Then all nodes x satisfying
$\mbox{sentinel}\prec\texttt{x}\prec\texttt{h}$ that are reachable from the
head of the version list in $C$ are $needed(\texttt{A},\texttt{t})$.

###### Proof.

To derive a contradiction, assume that some node x is reachable from head in
$C$ and x is not $needed(\texttt{A},\texttt{t})$. Consider the sequence of
values
$\texttt{h}=\texttt{y}_{1},\texttt{y}_{2},\ldots,\texttt{y}_{\ell}=\mbox{sentinel}$
that are assigned to the local variable cur during the compact(A,t,h) routine.
Since each is read from the left pointer of the previous one,
$\texttt{y}_{\ell}\prec\texttt{y}_{\ell-1}\prec\cdots\prec\texttt{y}_{1}$.
Since x is not $needed(\texttt{A},\texttt{t})$, Lemma 12 implies that x does
not appear in this sequence. So, for some $j$,
$\texttt{y}_{j+1}\prec\texttt{x}\prec\texttt{y}_{j}$.

Now, let
$\texttt{head}=\texttt{z}_{1},\texttt{z}_{2},\ldots,\texttt{z}_{k}=\texttt{x}$
be the path from head to x by following left pointers. Consider the maximum
$i$ such that $\texttt{z}_{i}\succeq\texttt{y}_{j}$. (Such an $i$ exists,
since
$\texttt{z}_{1}=\texttt{head}\succeq\texttt{h}=\texttt{y}_{1}\succeq\texttt{y}_{j}$.)
So, we have
$\texttt{y}_{j+1}\prec\texttt{x}=\texttt{z}_{k}\prec\texttt{z}_{k-1}\prec\cdots\texttt{z}_{i+1}\prec\texttt{y}_{j}\leq\texttt{z}_{i}$.
Now, $\texttt{y}_{j+1}\leftarrow\texttt{y}_{j}$ at some time during the
compact (before $C$). If $\texttt{y}_{j}$ were equal to $\texttt{z}_{i}$, then
in $C$,
$\texttt{$\texttt{z}_{i}$->left}=\texttt{$\texttt{y}_{j}$->left}\preceq\texttt{y}_{j+1}$
by Invariant 9, and this would contradict the fact that
$\texttt{$\texttt{z}_{i}$->left}=\texttt{z}_{i+1}\succ\texttt{y}_{j+1}$. So,
we have
$\texttt{y}_{j+1}\prec\texttt{z}_{i+1}\prec\texttt{y}_{j}\prec\texttt{z}_{i}$.
However, $\texttt{y}_{j+1}\leftarrow\texttt{y}_{j}$ at some time before $C$
and $\texttt{z}_{i+1}\leftarrow\texttt{z}_{i}$ in $C$. This contradicts Lemma
15. ∎

The head of a version list represents the current version, so it is not
obsolete. Thus, when a node is added to the range tracker data structure, it
is no longer the head of its list. Once a process receives a node x returned
by the range tracker, it gets up-to-date copies $\texttt{A},\texttt{t}$ and h
of the announcements, global timestamp and the list’s head and invoke
compact(A,t,h). Since x was already returned by the range tracker, x will not
be $needed(\texttt{A},\texttt{t})$ and $\texttt{x}\prec\texttt{h}$.
Proposition 17 ensures that x is permanently removed from its version list
before the compact terminates. Thus, aside from the lists where compact
routines are still pending, all nodes that have been returned by the range
tracker are no longer reachable from the head of the list.

###  B.2. Reserving Timestamps

Both BBF+ and our singly-linked list compaction algorithm from Section 5 use
atomic copy (a primitive which allows us to atomically read from one memory
location and write to another) to announce timestamps in a wait-free manner.
Instead, in our experiments, we use a lighter-weight lock-free scheme for
announcing timestamps which consist of (A1) reading the current timestamp,
(A2) announcing it, and (A3) checking if the current timestamp is still equal
to the announced value and, if not, going back to step A1. This means that a
process scanning the announcement array might see a very old timestamp get
announced, which breaks the monotonicity property required for the correctness
of our singly-linked list. We fix this by having all processes work on
updating a global scan of the announcement array as described in Section 5.
When reading the announcement array, we ignore any timestamp that (1) is
smaller than the timestamp at which the current global scan was taken and (2)
does not appear in the current global scan. This is safe because any announced
timestamp satisfying these two conditions will fail the check in step A3, and
not be used. This change to how we scan announcement arrays ensures that the
global scan satisfies the monotonicity property required by our singly-linked
list. This announcement scanning technique is also used in our implementation
of STEAM+LF, BBF+, and SL-RT.

##  Appendix C Additional Experiments

Figures 12–16 showcase the same workloads as Figures 4–8, but with keys drawn
from uniform rather than zipfian distribution.

Legend for all figures: |
---|---

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.06 | 1.07 | 1.24 | 1.66
DL-RT | 1.07 | 1.08 | 1.23 | 1.63
BBF+ | 1.07 | 1.08 | 1.23 | 1.64
Steam+LF | 1.51 | 1.53 | 1.68 | 2.06
EBR | 1.02 | 1.04 | 1.33 | 2.0

Figure 12. Tree with 100K keys, 40 update threads, 40 small rtx threads, 40
large rtx threads

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.0 | 1.01 | 1.09 | 1.63
DL-RT | 1.01 | 1.01 | 1.07 | 1.57
BBF+ | 1.01 | 1.01 | 1.06 | 1.55
Steam+LF | 1.43 | 1.43 | 1.46 | 1.68
EBR | 1.01 | 1.01 | 1.07 | 1.71

Figure 13. Tree with 10M keys, 40 update threads, 40 small rtx threads, 40
large rtx threads

Average Version List Lengths
---
| Size of
---
large rtxs
$2^{8}$ | $2^{13}$ | $2^{16}$ | $2^{18}$
SL-RT | 1.04 | 1.15 | 2.35 | 5.46
DL-RT | 1.05 | 1.14 | 2.42 | 25.27
BBF+ | 1.05 | 1.12 | 2.5 | 19.39
Steam+LF | 1.64 | 1.76 | 2.74 | 5.57
EBR | 1.01 | 1.19 | 3.34 | 451.99

Figure 14. Hash table with 100K keys, 40 update threads, 40 small rtx threads,
40 large rtx threads

(a) Tree with 100K keys

(b) Tree with 10M keys

Figure 15. Workload with each thread performing 50% updates, 49% lookups, and
1% read transactions of size 1024. Figure 16. Hash table with 100K keys, each
thread performs 50% updates, 49% lookups, and 1% read transactions of size
1024