11institutetext: Chalmers University of Technology, Gothenburg, Sweden

# How to Relax Instantly: Elastic Relaxation of Concurrent Data Structures

Kåre von Geijer 11 0009-0007-4823-6855 Philippas Tsigas 11 0000-0001-9635-9154

###### Abstract

The sequential semantics of many concurrent data structures, such as stacks
and queues, inevitably lead to memory contention in parallel environments,
thus limiting scalability. Semantic relaxation has the potential to address
this issue, increasing the parallelism at the expense of weakened semantics.
Although prior research has shown that improved performance can be attained by
relaxing concurrent data structure semantics, there is no one-size-fits-all
relaxation that adequately addresses the varying needs of dynamic executions.

In this paper, we first introduce the concept of elastic relaxation and
consequently present the Lateral structure, which is an algorithmic component
capable of supporting the design of elastically relaxed concurrent data
structures. Using the Lateral, we design novel elastically relaxed, lock-free
queues and stacks capable of reconfiguring relaxation during run time. We
establish linearizability and define upper bounds for relaxation errors in our
designs. Experimental evaluations show that our elastic designs hold up
against state-of-the-art statically relaxed designs, while also swiftly
managing trade-offs between relaxation and operational latency. We also
outline how to use the Lateral to design elastically relaxed lock-free
counters and deques.

###### Keywords:

concurrent data structures lock-free relaxed semantics

##  1 Introduction

As hardware parallelism advances with the development of multicore and
multiprocessor systems, developers face the challenge of designing data
structures that efficiently utilize these resources. Numerous concurrent data
structures exist [12], but theoretical results such as [6] demonstrate that
many common data structures, such as queues, have inherent scalability
limitations as threads must contend for a few access points. One of the most
promising solutions to tackle this scalability issue is to relax the
sequential specification of data structures [26], which permits designs that
increase the number of memory access points, at the expense of weakened
sequential semantics.

The $k$ out-of-order relaxation formalized in [11] is a popular model [25, 8,
16, 29] that allows relaxed operations to deviate from the sequential order by
up to $k$; for example, for the dequeue operation on a FIFO queue, any of the
first $k+1$ items can be returned instead of just the head. This error, the
distance from the head for a dequeue, is called the rank error. The advantage
of relaxation is that multiple items can be inserted and removed at once,
reducing contention at a few select access points. Furthermore, while other
relaxations, such as quiescent consistency [5] are incompatible with
linearizability [13], k-out-of-order relaxation can easily be combined with
linearizability, as it modifies the semantics of the data structure instead of
the consistency. Despite extensive work on out-of-order relaxation [8, 11, 25,
14, 28, 23, 29], almost all existing methods are static, requiring a fixed
relaxation degree during the data structures’ lifetime.

In applications with dynamic workloads, such as bursts of activity with
throughput constraints, it is essential to be able to temporarily sacrifice
sequential semantics for improved performance in times of high contention.
This is the problem tackled in this paper, to specify and design relaxed data
structures where the relaxation is reconfigurable during run-time, which we
term elastic relaxation. Elastically relaxed data structures enable the design
of instance-optimizing systems, an area that is evolving extremely rapidly
across various communities [17]. The trade-off between rank error and
throughput is highlighted in [28] and [23], where their shortest-path
benchmarks show that increased relaxation leads to higher throughput, but at
the expense of additional required computation.

Several relaxed data structures are implemented by splitting the original
concurrent data structure into disjoint sub-structures, and then using load-
balancing algorithms to direct different operations to different sub-
structures. In this paper, we base our elastic designs on the relaxed 2D
framework presented in [25], which has excellent scaling with both threads and
relaxation, as well as provable rank error bounds. The key idea of the 2D
framework is to superimpose a window (Win) over the sub-structures, as seen in
green in Figure 2 for the 2D queue, where operations inside the window can
linearize out of order. The Win${}^{\textit{tail}}$ shifts upward by 0ptwhen
it is full, and Win${}^{\textit{head}}$ shifts upward when emptied, to allow
further operations. The size of the window dictates the rank error, as a
larger one allows for more reorderings.

Figure 1: The 2D queue has two windows defining the operable area for the
enqueue and dequeue operations.

Figure 2: By adding a Lateral to the 2D queue, changes in width at
Win${}^{\textit{tail}}$ can be tracked and adjusted to by
Win${}^{\textit{head}}$.

The algorithmic design concept we propose in this paper is the Lateral
structure that can extend the 2D structures to encompass elastic relaxation.
The Lateral is added as a side structure next to the set of sub-structures in
order to keep track of the elastic changes, as shown in Figure 2. We show how
to incorporate the Lateral into the window mechanism that the 2D framework
introduced while achieving a deterministic rank error bound. Although we chose
to use the 2D framework as a base for our designs, the Lateral can also
accommodate other designs, such as the distributed queues from [8], the
k-queue from [16], and the k-stack from [11].

####  1.0.1 Contributions.

This work takes crucial steps toward designing reconfigurable relaxed
concurrent data structures with deterministic error bounds, capable of
adjusting relaxation levels during run-time.

  * •

Firstly, we introduce the concept of elastic relaxation, where the rank error
bound can change over time. In addition, we introduce a generic algorithmic
extension, the Lateral, to efficiently extend many relaxed data structure
designs to support elasticity.

  * •

We design and implement two elastically relaxed queues and a stack based on
the Lateral, as well as outline how to incorporate it into other data
structures such as counters and deques.

  * •

We establish rank error bounds for our elastic designs, as well as prove their
correctness.

  * •

We present an extensive evaluation of our proposed data structures,
benchmarking against non-relaxed data structures and statically relaxed ones.
These evaluations show that the elastic designs significantly outscale non-
relaxed data structures and perform as well as the statically relaxed ones,
while also supporting elastic relaxation.

  * •

Finally, we showcase the elastic capabilities of our design by implementing a
simple controller for a producer consumer application. By dynamically
adjusting the relaxation, it is able to control the producer latency during
bursts of activity with minimal overhead.

####  1.0.2 Structure.

Section 2 introduces related work, as well as gives a short description of the
structures on which we base our elastic designs. Section 3 introduces elastic
relaxation and our novel data structures, which we then prove correct and
provide worst-case bounds for in Section 4. Section 5 experimentally evaluates
the new algorithms, both comparing them to earlier non-elastic data structures
as well as testing their elastic capabilities. Section 6 contains a few
closing remarks.

##  2 Related Work

One of the earliest uses of relaxed data structures is from 1993 by Karp and
Zhang in [15] where they used process-local work queues, only occasionally
synchronizing to redistribute items randomly. These queues functioned as
heuristics in their branch-and-bound algorithm to dictate the order of
exploration in the problem space — which to this day is a prevalent
application of relaxation as it does not impede correctness [23, 21, 8].
Although their paper used the idea of relaxation to improve performance, the
concept of semantic relaxation was not defined, introduced, or properly
explored.

More recently, relaxed data structures have emerged as a promising technique
to boost concurrency [26] and are formally analyzed in for example [11, 1, 9,
2]. They have demonstrated exceptional throughput on highly parallel
benchmarks [25, 28, 7, 8], and have shown to be suitable in heuristics for
e.g. graph algorithms [21, 23].

Henzinger et al. specified quantitative relaxation in [11] as a framework for
defining relaxed data structures with a hard bounded error. These relaxations,
such as $k$ out-of-order are easily extendably to elastic relaxation by
letting the bound change during run-time. The paper also introduces the
relaxed $k$-segment stack, which in turn builds upon the earlier relaxed FIFO
queue from [16]. The size of these segments ($k$) is similar to the
0ptdimension in the 2D framework [25], and it can therefore be extended to be
elastic with our Lateral.

Another direction of relaxed data structures forgoes the hard bound from [11]
and instead relies on randomness to only give probabilistic guarantees, and
was formalized in [1] as an extension to [11]. A successful design of these
probabilistically relaxed data structures is the MultiQueue [24, 28] which
builds upon The Choice of Two [19]. It is a relaxed priority queue which
enqueues items into random sub-queues, while dequeuing the highest priority
item from a random selection of two sub-queues. This can similarly be applied
to FIFO queues such as the d-RA in [8] or stacks. While not providing upper
bounds on relaxation, the relaxation of the MultiQueue has been extensively
analysed in [2].

The SprayList from [3] is another relaxed priority queue, but does not use
multiple sub-queues. Instead, it builds upon a concurrent skip-list and does a
random walk over items at each delete-min, returning one of the top
$\mathcal{O}(p\log^{3}p)$ items with high probability, where $p$ is the number
of threads. The properties of this random walk can be adjusted at run-time,
essentially making it elastically relaxed, although with a probabilistic rank
error guarantee instead of a bound. However, experiments from [28, 24, 23]
suggest that the SprayList is outperformed by the MultiQueue, for which there
is no known efficient elastic design.

Many concurrent queues aim for high throughput, yet the RCQs, detailed in
[14], targets reduced wait-time by leveraging the LCRQ framework [20]. It
achieves similar throughput to fetch-and-add methods but with significantly
lower wait-times, especially in oversubscribed, nearly empty queues. While
offering a new perspective on concurrent queue design, the RCQ lacks a
mechanism to adjust its relaxation feature.

####  2.0.1 2D Framework

The 2D framework for $k$ out-of-order relaxed data structures from [25]
(hereby called the static 2D designs) outscales other implementations from the
literature such as [16, 11, 8] with threads, while unifying designs across
stacks, queues, deques, and counters. Furthermore, its throughput scales
monotonically with $k$. It achieves this, as shown in Figure 2, by
superimposing a window (Win) over multiple disjoint concurrent (nonrelaxed)
sub-structures which defines which of them are valid to operate on.

The 2D window has a 0pt(always the number of sub-structures in the static
designs) and a 0pt, which together govern the relaxation profile. At any
point, it is valid to insert an item on a row $r$ where
$r\leq\textit{Win}^{\textit{}}_{\textit{max}}$, or delete an item on row $r$
where
$r>\textit{Win}^{\textit{}}_{\textit{min}}\equiv\textit{Win}^{\textit{}}_{\textit{max}}-0pt$,
while keeping linearization order in the sub-structures. To maximize data
locality, each thread tries to do as many operations as possible on the same
sub-structure in a row, only moving due to contention or from reaching
Win${}^{\textit{}}_{\textit{max}}$ or Win${}^{\textit{}}_{\textit{min}}$.

If an operation cannot find a valid sub-structure, it will try to shift the
window. For example, if a thread tries to insert an item into the 2D queue and
sees all sub-queues at Win${}^{\textit{tail}}_{\textit{max}}$, it will try to
shift the window up by atomically incrementing
Win${}^{\textit{tail}}_{\textit{max}}$ (and implicitly
Win${}^{\textit{tail}}_{\textit{min}}$) by $0pt$, after which it restarts the
search for a valid sub-queue.

The 2D stack is similar to the 2D queue, but as both insert (push) and delete
(pop) operate on the same side of the data structure, only one window is used.
This leads to Win${}^{\textit{}}_{\textit{max}}$ no longer increasing
monotonically, but instead decreasing under heavy delete workloads, and
increasing under insert heavy ones. Furthermore,
Win${}^{\textit{}}_{\textit{max}}$ shifts by $0pt/2$ instead of $0pt$, which
approximately makes it fair for future push and pop operations. The framework
also covers deques and counters, using the same idea of a window to define
valid operations.

##  3 Design of Elastic Algorithms

Static $k$ out-of-order relaxation is formalized in [11] by defining and
bounding a transition cost (rank error) of the “get” methods within the
linearized concurrent history. Elastic relaxation allows the relaxation
configuration to change over time, which will naturally change the bound $k$
as well. Therefore, we define elastic out-of-order data structures as static
out-of-order, but allow the rank error bound to be a function of the
relaxation configuration history during the lifetime of the accessed item. In
the simplest case, such as the elastic queue from Section 3.1, the rank error
bound for every dequeued item is a function of the 0ptand 0ptduring which the
item was enqueued (which is the same as when it is dequeued).

To elastically extend the 2D algorithms, we want the width and depth of the 2D
windows be adjustable during run-time, which would enable fine-grained control
of the relaxation profile. Our designs let these parameters change every
window shift, and then update them atomically with Win${}^{\textit{max}}$.
Changing 0ptis practically simple by including it as a window variable
Win${}^{\textit{}}_{\textit{depth}}$ (although it has implications on the
error bounds). Changing the 0ptefficiently requires more attention. We create
a maximum number of sub-structures at initialization time (each taking up only
a couple bytes of memory), and then use the Lateral structure to keep track of
which sub-structures have been inserted into for which rows as seen in Figure
2.

###### Definition 1

A Lateral to a relaxed data structure is a set of nonoverlapping adjacent
ranges of rows, where each range has a corresponding width bound.

Furthermore, we call the Lateral consistent if the width bound of each node
properly bounds the width of the corresponding rows in the main structure. The
exact implementation of the Lateral will vary depending on what performance
properties are desired, but the overarching challenge is to keep it consistent
while also being fast to read and update, as well as promising good rank error
bounds. For our 2D designs, we found that it is essential to only update the
Lateral (at most) once every window.

###  3.1 Elastic Lateral-as-Window 2D Queue

This first elastic Lateral-as-Window queue (LaW queue) merges the window into
the Lateral, and can be applied to most data strucutures from the 2D framework
[25] with small changes. The pseudocode is shown in Algorithm 1. First, we add
a Lateral queue that is implemented as a Michael-Scott queue [18], for which
the code omits the standard failable Enqueue and Dequeue methods. The Lateral
nodes are windows, where each window contains
Win${}^{\textit{}}_{\textit{max}}$, Win${}^{\textit{}}_{\textit{depth}}$, and
Win${}^{\textit{}}_{\textit{width}}$. The Win${}^{\textit{tail}}$ and
Win${}^{\textit{head}}$ then become the head and tail nodes in the Lateral.
Every shift of Win${}^{\textit{tail}}$ enqueues a new window in the Lateral
(line 1), and every shift of Win${}^{\textit{head}}$ dequeues a window (line
1).

0.1

0.2

0.3

0.4struct  _Window_

0.5 Window* next;

0.6 uint max;

0.7 uint depth;

0.8 uint width;

0.9

0.10

0.11global struct  _Lateral_

0.12 Window* head;

0.13 Window* tail;

0.14

0.15

// Try to atomically enqueue new directly after expected

0.16 method Lateral.Enqueue(expected, new);

0.17

// Try to atomically dequeue expected if it is the head

0.18 method Lateral.Dequeue(expected);

0.19

0.20method  _Lateral.ShiftTail(old_window)_

0.21 depth $\leftarrow$ depth${}_{\text{shared}}$;

0.22 new_window $\leftarrow$ {

0.23 width: width${}_{\text{shared}}$,

0.24 depth: depth,

0.25 max: old_window.max + depth

0.26 };

0.27 Lateral.Enqueue(old_window, new_window);

0.28

0.29

0.30function  _ShiftHead(current_head)_

0.31 Lateral.Dequeue(current_head);

0.32

0.33

Algorithm 1 Pseudocode for the Lateral in the elastic LaW queue

As shown in ShiftTail (line 1), Win${}^{\textit{}}_{\textit{depth}}$ and
Win${}^{\textit{}}_{\textit{width}}$ can be updated from global variables
every shift, which enables the elasticity. The main drawback of this design is
that the relaxation only changes at the tail, and must propagate through the
queue to reach the head. The Lateral also takes up more memory than two simple
global windows, and require a bit more overhead to update than shifting the
windows with a simple compare-and-swap.

Other than the pseudocode in Algorithm 1, the remaining logic from the static
2D queue require only small adjustments. Mainly, items must always be inserted
within the window, so each items gets enqueued at
$\textit{max}(\textit{Win}^{\textit{put}}_{\textit{max}}-\textit{Win}^{\textit{put}}_{\textit{depth}},\textit{last\\_item.row})+1$,
which create needed gaps in sub-queues as seen in Figure 2. Furthermore,
Win${}^{\textit{head}}$ cannot pass Win${}^{\textit{tail}}$, and dequeues can
simply return empty if the Lateral is empty.

###  3.2 Elastic Lateral-plus-Window 2D Queue

The elastic Lateral-plus-Window 2D queue (elastic LpW queue) solves two
shortcomings of the previous elastic LaW queue. Firstly, it allows the head to
change relaxation independently of the tail by letting both windows change
Win${}^{\textit{}}_{\textit{depth}}$ at window shifts. Second, it does not
have to allocate a new Lateral node every Win${}^{\textit{tail}}$ shift, and
instead only creates Lateral nodes when
Win${}^{\textit{tail}}_{\textit{width}}$ changes. However, it comes at the
expense of having to decouple the window and Lateral components, and uses a
128-bit shared atomic struct for each window.

The pseudocode for the Lateral and windows is presented in Algorithm 2 and
shows that the Win${}^{\textit{head}}$ and Win${}^{\textit{tail}}$ structs now
are global variables, both containing max, depth, and width. The Lateral is
again implemented as a Michael-Scott queue [18] where we omit the Enqueue and
Dequeue implementations.

0.1

0.2

0.3

0.4global struct  _TailWindow_

0.5 uint64 max;

0.6 uint16 depth;

0.7 uint16 width;

0.8 uint16 next_width;

0.9

0.10

0.11global struct  _HeadWindow_

0.12 uint64 max;

0.13 uint16 depth;

0.14 uint16 width;

0.15

0.16

0.17struct  _LateralNode_

0.18 LateralNode* next;

0.19 uint row;

0.20 uint width;

0.21

0.22

0.23global struct  _Lateral_

0.24 LateralNode* head;

0.25 LateralNode* tail;

0.26

0.27

// Try to atomically enqueue new directly after expected

0.28 method Lateral.Enqueue(expected, new);

0.29

// Try to atomically dequeue expected if it is the head

0.30 method Lateral.Dequeue(expected);

0.31

0.32method  _Lateral.SyncTail(window)_

0.33 tail $\leftarrow$ Lateral.tail;

0.34 if  _tail.row $\leq$ window.max _ then

0.35 new_tail $\leftarrow$ {

0.36 row: window.max + 1,

0.37 width: window.next_width

0.38 };

0.39 Lateral.Enqueue(tail, new_tail);

0.40

0.41

0.42

0.43function  _ShiftTail(old_window)_

0.44 if window.width $\neq$ window.next_width Lateral.SyncTail(old_window) ;

0.45

0.46 depth $\leftarrow$ depth${}_{\text{shared}}$;

0.47 new_window $\leftarrow$ {

0.48 width: old_window.next_width,

0.49 next_width: width${}_{\text{shared}}$,

0.50 depth: depth,

0.51 max: old_window.max + depth

0.52 };

0.53

0.54 CAS(&TailWindow, old_window, new_window);

0.55

0.56

0.57function  _ShiftHead(old_window)_

0.58

0.59 while  _true_ do

0.60 head $\leftarrow$ Lateral.head();

0.61 if head.max $>$ old_window.max break;

0.62 Lateral.Dequeue(head);

0.63

0.64

0.65 new_window $\leftarrow$ {

0.66 width: old_window.width,

0.67 max: max(TailWindow.max,

0.68 old_window.max + depth${}_{\text{shared}}$)

0.69 };

0.70

0.71 if  _head.row = old_window.max + 1_ then

0.72 new_window.width $\leftarrow$ head.width;

0.73 head $\leftarrow$ head.next;

0.74

0.75 if  _head.row $<$ new_window.max _ then

0.76 new_window.max $\leftarrow$ head.row - 1;

0.77

0.78 new_window.depth $\leftarrow$ new_window.max - old_window.max;

0.79

0.80 CAS(&TailWindow, old_window, new_window);

0.81

0.82

Algorithm 2 Lateral and window code for the elastic LpW queue

Shifting Win${}^{\textit{tail}}$ is done during a pending enqueue call when
the window has become full (line 2). It reads the desired depth and width from
shared variables, and use them in the next window. However, the width is not
used immediately, but instead written to a next_width field in the future
window, which is then used in the successive shift as the new width. This
delay is introduced to ensure that a Lateral node will be enqueued with the
new width before this width is used in an enqueue. Enqueueing the Lateral node
is done before the window shift when $\textit{next\\_width}\neq\textit{width}$
(line 2), ensuring that the head of the queue will be aware of changes in
width before they occur.

Similarly, Win${}^{\textit{head}}$ is shifted during a dequeue call when all
sub-queues in the width has reached the window max. The shift starts by
dequeueing all Lateral nodes below the current
Win${}^{\textit{head}}_{\textit{max}}$, as they represent stale changes in
width. The shift optimistically reads a shared depth variable which is used
for the next window (line 2), unless the Lateral head node overlaps the new
range (line 2). If the Lateral head is on the bottom row of the new window
(line 2), then the new window will adapt to the width change encoded by the
head. Otherwise, the new Win${}^{\textit{head}}_{\textit{max}}$ is limited to
not overlap a Lateral node (line 2). This ensures that all nodes within a
window were pushed within the same width, which is used at dequeues to
calculate which row the dequeued node was at.

At the cost of separating the Lateral and the window, this LpW queue is able
to change depth independently for the head and the tail. However, the width is
still only ever changed at Win${}^{\textit{tail}}$ which
Win${}^{\textit{head}}$ has to adapt to by using the Lateral. We have designed
this to be efficient on modern x86-64 machines where CAS only has hardware
support for up to 128 bits, which then becomes the upper size limits for our
window structs. One can allocate the sizes differently depending on the need
of the application, but if 128 bits is not enough, or a machine without
128-bit CAS support is used, the elastic LaW-queue might be more suitable.

###  3.3 Elastic Lateral-plus-Window 2D Stack

This elastic Lateral-plus-Window 2D stack (elastic LpW stack) uses the same
methods as the elastic LpW queue to make the static 2D stack elastic. The
pseudocode for the Lateral and window is found in Algorithm 3 and uses a
global shared window struct, which is updated with CAS at window shifts (line
3), and a Treiber stack [27] as a Lateral for all changes in width. The
nonmonotonic nature of the window means that the width bound of a row can
change many times, requiring the Lateral to be stabilized before every window
shift (line 3).

0.1

0.2

0.3

// Example size of fields to fit 128 bits

0.4 global struct  _Window_

0.5 uint32 max;

0.6 uint16 depth;

0.7 uint16 push_width;

0.8 uint16 pop_width;

0.9 uint16 last_push_width;

enum last_shift;

$\triangleright$ UP or DOWN

0.10 uint31 version;

0.11

0.12

0.13method  _Window.Min(self)_

0.14 return self.max - self.depth;

0.15

0.16

0.17function  _Shift(dir, old_window)_

0.18 Lateral.Stabilize(old_window);

0.19

0.20 new_window $\leftarrow$ {

0.21 push_width: width${}_{\text{shared}}$,

0.22 last_push_width: old_window.push_width,

0.23 depth: depth${}_{\text{shared}}$,

0.24 last_shift: dir,

0.25 version: old_window.version + 1

0.26 };

0.27

0.28 if  _dir $=$ UP_ then

0.29 new_window.max $\leftarrow$ old_window.max + new_window.depth$/2$;

0.30

0.31 else

0.32 new_window.max $\leftarrow$ old_window.Min() + new_window.depth$/2$;

0.33

0.34

0.35 new_window.pop_width $\leftarrow$ max(new_window.push_width,
Lateral.width(new_window.Min()));

0.36

0.37 CAS(&Window, old_window, new_window);

0.38

0.39

0.40global struct  _Lateral_

0.41 LateralNode* top;

0.42 uint64 version;

0.43

0.44

0.45struct  _LateralNode_

0.46 LateralNode* next;

0.47 uint row;

0.48 uint width;

0.49

0.50

0.51method  _Lateral.Width(self, row)_

0.52 return max(node.width for node in self where node.row $>$ row);

0.53

0.54

0.55method  _Lateral.Stabilize(self, win)_

0.56 read_lat $\leftarrow$ new_lat $\leftarrow$ self.read();

0.57 if  _Window $\neq$ win or read_lat.version $=$ win.version_ then

return ;

$\triangleright$ Already completed

0.58

// Phase 1: Update local Lateral

0.59 new_lat.top $\leftarrow$ read_lat.top.Update(win);

0.60

// Phase 2: Push new top if changed width

0.61 upper_bound $\leftarrow$ max(win.max, stack.row for stack in
substacks[win.push_width..win.last_push_width]);

0.62 if  _win.push_width $>$ win.last_push_width and new_lat.top.row $<$
win.Min()_ then

node’ $\leftarrow$ {

$\triangleright$ New top node

0.63 row: win.Min(),

0.64 width: win.last_push_width,

0.65 next: new_lat.top

0.66 };

new_lat.top $\leftarrow$ node’;

$\triangleright$ Push width change

0.67

0.68 else if  _win.push_width $<$ win.last_push_width and new_lat.top.row $<$
upper_bound_ then

node’ $\leftarrow$ {

$\triangleright$ New top node

0.69 row: upper_bound,

0.70 width: win.last_push_width,

0.71 next: new_lat.top

0.72 };

new_lat.top $\leftarrow$ node’;

$\triangleright$ Push width change

0.73

0.74

0.75 if  _new_lat $\neq$ read_lat_ then

0.76 new_lat.version $\leftarrow$ win.version;

0.77 CAS(&Lateral, read_lat, new_lat);

0.78

0.79

0.80

0.81method  _LateralNode.Update(self, win)_

0.82 if  _self.row $\leq$ win.Min() _ then

0.83 return self;

0.84

0.85 node’ $\leftarrow$ node.Clone();

0.86 if  _node.width $\leq$ win.push_width_ then

0.87 node’.row $\leftarrow$ win.Min();

0.88

0.89 else if  _node.width $>$ win.last_push_width and win.last_shift $=$ DOWN
_ then

0.90 last_min $\leftarrow$ win.max $-$ win.depth$/2$;

0.91 node’.row $\leftarrow$ min(node.row, last_min);

0.92

0.93 next $\leftarrow$ node’.next.Update(win);

0.94 if  _node’.row $\leq$ node.next.row_ then

return next;

$\triangleright$ Remove node

0.95

0.96 else

0.97 node’.next $\leftarrow$ next;

0.98 return node’;

0.99

0.100

0.101

Algorithm 3 Lateral and window code for the elastic LpW stack

The push and pop operations are very similar to the static 2D stack. The push
operations use the push_width, which is the desired global width (line 3), and
the pop operations now use the pop_width, which is the upper width bound on
the rows in the window based on the Lateral (line 3). Not shown in the
pseudocode, the nodes in the sub-stacks also store the row they are pushed at,
which is used at pops to update the descriptor for each sub-stack.

The window shift (line 3) updates these widths, as well as shifting the
Win${}^{\textit{}}_{\textit{max}}$ or Win${}^{\textit{}}_{\textit{min}}$ by
the new $\textit{Win}^{\textit{}}_{\textit{depth}}/2$ (lines 3 and 3). In
addition, it stores the last push_width and the direction of the shift (UP or
DOWN) in the window, which are used to keep the Lateral consisent for the next
window shift. It linearizes with a 16 byte CAS at line 3.

The core of this data structure is the Lateral, and how it is kept consistent
for every shift (line 3). This function maintains the stack invariant that for
any Lateral node $l$, all rows in the 2D stack between $l.row$ and
$l.\textit{next}.\textit{row}$ will have smaller or equal width as $l.0pt$. We
divide this synchronization into two phases, which together create a local top
candidate for the Lateral stack, and linearize with a CAS at line 3.

The first phase clones and tries to lower Lateral nodes above
Win${}^{\textit{}}_{\textit{min}}$ (line 3). By lowering a Lateral node $l$ to
row $r$, we set $l.\textit{row}\leftarrow min(l.\textit{row},r)$, and then if
$l.\textit{row}\leq l.\textit{next}.\textit{row}$, $l$ is removed from the
stack (by linking its parent $l^{\prime},l^{\prime}.\textit{next}\leftarrow
l.\textit{next}$). If a Lateral node
$l,l.\textit{row}>\textit{Win}^{\textit{}}_{\textit{min}}$ has
$l.0pt\leq\textit{Win}^{\textit{}}_{\textit{push\\_width}}$, then it is
lowered to Win${}^{\textit{}}_{\textit{min}}$ (line 3), as new nodes can have
been pushed outside $l.0pt$ within the window, invalidating its bound.
Otherwise, if $l.0pt>\textit{Win}^{\textit{}}_{\textit{last\\_push\\_width}}$
and the last shift was downwards, all sub-stacks must have been seen at the
previous Win${}^{\textit{}}_{\textit{min}}$ before it shifted down, so $l$ is
lowered to a conservative estimate of the previous
$\textit{Win}^{\textit{}}_{\textit{min}}$ (line 3). This estimate only
deviates from the actlal previous Win${}^{\textit{}}_{\textit{min}}$ when the
last Win${}^{\textit{min}}$ was smaller than
$\textit{Win}^{\textit{}}_{\textit{depth}}/2$, in which case it overestimates,
thus keeping a correct bound.

In the second phase (from line 3), a new Lateral node with width
Win${}^{\textit{}}_{\textit{last\\_push\\_width}}$ is pushed if the width has
changed.

  * •

If
$\textit{Win}^{\textit{}}_{\textit{push\\_width}}>\textit{Win}^{\textit{}}_{\textit{last\\_push\\_width}}$,
the width has increased, and a Lateral node is pushed at
Win${}^{\textit{}}_{\textit{min}}$ to signify that the width from there on is
smaller. This is not needed for correctness, but is helpful in limiting the
Win${}^{\textit{}}_{\textit{pop\\_width}}$ if the width shrinks in the future.

  * •

If
$\textit{Win}^{\textit{}}_{\textit{push\\_width}}<\textit{Win}^{\textit{}}_{\textit{last\\_push\\_width}}$,
the width has decreased and a new Lateral node needs to be pushed at the
highest row containing nodes between
Win${}^{\textit{}}_{\textit{push\\_width}}$ and
Win${}^{\textit{}}_{\textit{last\\_push\\_width}}$. This can not reliably be
calculated from the present window variables, so we simply iterate over the
sub-stacks (line 3).

In summary, the elastic LpW stack uses a similar idea as the elastic LpW
queue, but needs to do some extra work to maintain the Lateral invariant.
However, unless the workload is very pop-heavy, the Lateral nodes should
quickly stabilize and let the push_width and pop_width be equal.

###  3.4 Elastic Extension Outlines: 2D Counter and Deque

The 2D counter can easily be made elastic by adding a Lateral counter.
However, as the counter is not a list-based data structure, and the ”get”
operation is more akin to reading its size, it becomes slightly different. The
key is to let the Lateral track the difference between the the sum of all
counters within Win${}^{\textit{}}_{\textit{width}}$ and the total count. A
simple way to implement this is to add a small delay before changing
Win${}^{\textit{width}}$, as in the LpW queue, and iterate over the counters
between the next and current Win${}^{\textit{width}}$, updating them and the
Lateral to get a consistent offset.

To derive an elsatic 2D deque, we use a similar deque as [25], but with only
one window at each side of the deque, much like the 2D queue. However, as with
the 2D stack, these windows can shift both up and down. This can be made
elastic in a similar fashion to the LaW queue, where a Lateral deque is kept
with the sequence of all windows. If the windows shift with 0ptrows each time,
as in the queue, a similar approach to the k-stack from [11] can be used to
make sure a window is not removed while non-empty. If the window should shift
by $0pt/2$ as the stack, successive windows would overlap, requiring extra
care. A solution to this could be to split each window in two, letting the
threads operate on the two topmost windows, and still use the confirmation
technique from [11] for the top Win when shifting downwards.

##  4 Correctness

In this section, we prove the correctness and relaxation bounds for our
elastic designs. For simplicity, we only relax non-empty remove operations and
assume a double-collect [22] approach is used to get linearizable empty
returns, as is also done in [8]. However, it is possible to extend the
arguments to allow relaxed empty returns with the same rank error bound $k$.
Furthermore, if no elastic changes are used, our elastic designs have the same
error bounds as the static 2D structures: $0pt(0pt-1)$ for the queue [25] and
$2.50pt(0pt-1)$ for the stack (see Appendix 0.A).

Our designs are lock-free as (i) each sub-structure, the windows, and the
Lateral are updated in a lock-free manner (by linearizing with a CAS), (ii)
the Lateral is updated at most once every window, and (iii) that there cannot
be an infinite number of window shifts without progress on any of the sub-
structures, as was proved in [25].

###  4.1 Elastic LaW Queue

###### Theorem 4.1

The elastic LaW 2D queue is linearizeable with respect to a FIFO queue with
elastic $k$ out-of-order relaxed dequeues, where
$k=(\textit{Win}^{\textit{head}}_{\textit{width}}-1)\textit{Win}^{\textit{head}}_{\textit{depth}}$.

###### Proof

The key observation is that every Win${}^{\textit{tail}}$ must fill all
Win${}^{\textit{head}}_{\textit{depth}}$ rows of
Win${}^{\textit{head}}_{\textit{width}}$ items each before shifting to the
next Win. These items can be enqueued in any order, except that each sub-queue
is totally ordered. Enqueues in different windows are on the other hand
correctly ordered, due to the sequential semantics of the Lateral. The
Win${}^{\textit{head}}$ uses the same Win structs as the
Win${}^{\textit{tail}}$, by traversing the Lateral of past
Win${}^{\textit{tail}}$, not shifting past such a window until it has also
dequeued all its
$\textit{Win}^{\textit{}}_{\textit{width}}\times\textit{Win}^{\textit{}}_{\textit{depth}}$
items.

Thus, as the oldest items in the queue always are in Win${}^{\textit{head}}$,
and dequeues only ever dequeue from the Win${}^{\textit{head}}$, together with
the fact that the sub-queues are totally ordered, means that a dequeue can at
most skip the first
$(\textit{Win}^{\textit{head}}_{\textit{width}}-1)\textit{Win}^{\textit{head}}_{\textit{depth}}$
items.

Additionally, there is another measure of the relaxation error called the
lateness defined in [11], or delay in [28]. For a relaxed queue, the lateness
is the maximal number of consecutive dequeue operations that can be carried
out without dequeuing the head. Due to the monotonically increasing row counts
in the queue, this gets the same bound as the out-of-order bound $k$ proved in
Theorem 4.1, and follows by essentially the same argument. This also holds for
the static 2D queue.

###  4.2 LpW Elastic 2D Queue

This queues is not as trivial as the last one, as its 0ptcan change in both
Win${}^{\textit{head}}$ and Win${}^{\textit{tail}}$ instantly, meaning that
the Win${}^{\textit{head}}$ will not necessarily follow the same sequence of
row ranges as Win${}^{\textit{tail}}$. To simplify, we introduce an ordering
of the windows with respect to their max, such that
$\textit{Win}^{\textit{i}}<\textit{Win}^{\textit{j}}$ if
$\textit{Win}^{\textit{i}}_{\textit{max}}<\textit{Win}^{\textit{i}}_{\textit{max}}$.
We also denote the window during which item $x$ was enqueued or dequeued as
Win${}^{\textit{enq x}}$ or Win${}^{\textit{deq x}}$ respectively. Finally, we
denote the row of a node $x$ in a sub-queue or the Lateral queue as
$\textit{row}_{x}$.

###### Lemma 1

If a Lateral node $l$ is enqueued at time $t$, then
$\textit{Win}^{\textit{head}}_{\textit{max}}<\textit{row}_{l}$ at $t$.

###### Proof

We first note that
$\textit{row}_{l}\leftarrow\textit{Win}^{\textit{tail}}_{\textit{max}}+1$ when
it is enqueued (line 2). Furthermore, the enqueue of $l$ completes before the
window shifts, and it cannot be enqueued again after the window has shifted as
the comparison against the strictly increasing row count of the tail will fail
(line 2). As
$\textit{Win}^{\textit{head}}_{\textit{max}}\leq\textit{Win}^{\textit{tail}}_{\textit{max}}$
(line 2), and $\textit{Win}^{\textit{tail}}_{\textit{max}}<\textit{row}_{l}$
at $t$, it holds that
$\textit{Win}^{\textit{head}}_{\textit{max}}<\textit{row}_{l}$ at $t$.

###### Theorem 4.2

The elastic 2D LpW queue is linearizeable with respect to a FIFO queue with
elastic $k$ out-of-order relaxed dequeues, where for every dequeue of $x$,
$k=(\textit{Win}^{\textit{enq
x}}_{\textit{width}}-1)(\textit{Win}^{\textit{enq
x}}_{\textit{depth}}+\textit{Win}^{\textit{deq x}}_{\textit{depth}}-1)$.

###### Proof

Enqueues and non-empty dequeues linearize with a successful update on a MS
sub-queue. An empty dequeue linearizes when
$\textit{Win}^{\textit{head}}_{\textit{max}}=\textit{Win}^{\textit{tail}}_{\textit{max}}$
after a double-collect where it sees all sub-queues within
$\textit{Win}^{\textit{head}}_{\textit{width}}$ empty. Lemma 1 together with
$\textit{Win}^{\textit{head}}_{\textit{max}}=\textit{Win}^{\textit{tail}}_{\textit{max}}$
gives that all nodes must be within
$\textit{Win}^{\textit{head}}_{\textit{width}}$, meaning that empty returns
can linearize at a point where the queue was completely empty.

The core observation for proving the out-of-order bound is to observe that the
row counts for the sub-queues and the max of the windows strictly increase.
For a node $y$ to be enqueued before $x$, and not dequeued before $x$, it must
hold that $\textit{Win}^{\textit{enq y}}\leq\textit{Win}^{\textit{enq x}}$ and
$\textit{Win}^{\textit{deq y}}\geq\textit{Win}^{\textit{deq x}}$. As
$\textit{Win}^{\textit{enq x}}_{\textit{min}}\leq\textit{Win}^{\textit{deq
x}}_{\textit{max}}$, we can bound the possible row of $y$ by
$\textit{Win}^{\textit{deq
x}}_{\textit{min}}\leq\textit{row}_{y}\leq\textit{Win}^{\textit{enq
x}}_{\textit{max}}$. Using Lemma 1 together with the fact that
Win${}^{\textit{head}}$ only spans rows with one 0ptat a time (line 2), we get
that these valid rows for $y$ must have width $\textit{Win}^{\textit{enq
x}}_{\textit{width}}=\textit{Win}^{\textit{deq x}}_{\textit{width}}$. As both
Win${}^{\textit{enq x}}$ and Win${}^{\textit{deq x}}$ must share at least
$\textit{row}_{x}$, it holds that $\textit{Win}^{\textit{enq
x}}_{\textit{min}}\leq\textit{Win}^{\textit{deq x}}_{\textit{max}}$. This is
then used to limit the valid number of $\textit{row}_{y}$ by
$\textit{Win}^{\textit{enq x}}_{\textit{max}}-\textit{Win}^{\textit{deq
x}}_{\textit{min}}=\textit{Win}^{\textit{enq
x}}_{\textit{min}}+\textit{Win}^{\textit{enq
x}}_{\textit{depth}}-\textit{Win}^{\textit{deq
x}}_{\textit{max}}+\textit{Win}^{\textit{deq
x}}_{\textit{depth}}\leq\textit{Win}^{\textit{enq
x}}_{\textit{depth}}+\textit{Win}^{\textit{deq x}}_{\textit{depth}}-1$. As all
operations within each sub-queue are ordered, we reach the final bound of
$(\textit{Win}^{\textit{enq x}}_{\textit{width}}-1)(\textit{Win}^{\textit{enq
x}}_{\textit{depth}}+\textit{Win}^{\textit{deq x}}_{\textit{depth}}-1)$.

Similarly to the LpW queue, this argument can be flipped to prove that $k$
also bounds the lateness or delay of the queue.

###  4.3 Elastic LpW 2D Stack

To bound the out-of-order error for an item in the elastic LpW 2D stack. This
is done by first proving that the Lateral correctly bounds row widths in Lemma
2, bounding the size of sub-stacks in Lemma 3 and 4, and then deriving the
out-of-order bound in Theorem 4.3.

As in the queue analysis, we use $\textit{Win}^{\textit{push x}}$ or
$\textit{Win}^{\textit{pop x}}$, to denote the window when $x$ was pushed or
popped. We also introduce Win${}^{\textit{max x}}_{\textit{depth}}$ to denote
the maximum value of Win${}^{\textit{}}_{\textit{depth}}$ during the lifetime
of $x$, and equivalent notation for any window attribute. We denote
$\textit{Win}^{\textit{}}_{\textit{shift}}=\left\lfloor\textit{Win}^{\textit{}}_{\textit{depth}}/2\right\rfloor$,
the top row (size) of sub-stack $j$ as $N_{j}$, and the index an item $x$ is
pushed at as $\textit{index}_{x}$. Finally, we introduce a width bound (0ptr)
for each row $r$ as $l.0pt$ if there exists a Lateral node $l,l.next.row<r\leq
l.row$, or Win${}^{\textit{}}_{\textit{push\\_width}}$ if
$r>l.row\leavevmode\nobreak\ \forall\leavevmode\nobreak\ l$ (if this properly
bounds the row widths, the Lateral is consistent). Due to Lateral nodes being
removed from the stack if their row overlaps the next node’s row, this width
bound is uniquely defined.

###### Lemma 2

At the moment preceding the linearization of each window shift, it holds for
each row $r$ and every item $x$ where$\textit{row}_{x}=r$, that
$0pt{r}\geq\textit{index}_{x}$.

###### Proof

Informally, this lemma states that the Lateral stack properly bounds all rows
with widths greater than Win${}^{\textit{}}_{\textit{push\\_width}}$ after the
call to Stabilize at line 3. We prove this with induction over the sequence of
window shifts, and it is easy to see that it holds at the first window shift,
as all nodes will be pushed within Win${}^{\textit{}}_{\textit{put\\_width}}$.
Now, if the lemma held at the previous window shift, we check if it continues
to hold for the next shift where we shift from Win${}^{\textit{i}}$.

First, we inspect rows at and below Win${}^{\textit{i}}_{\textit{min}}$ and
note that during the lifetime of Win${}^{\textit{i}}$, all nodes are pushed
above Win${}^{\textit{i}}_{\textit{min}}$, and 0ptr will not be changed at
rows at or below Win${}^{\textit{i}}_{\textit{min}}$ (lines 3, 3, 3) from
lowering a Lateral node. Thus, if
$\textit{Win}^{\textit{i}}_{\textit{push\\_width}}=\textit{Win}^{\textit{i}}_{\textit{last\\_push\\_width}}$,
the lemma continues to hold for all rows lower or equal to
Win${}^{\textit{i}}_{\textit{min}}$. If the
$\textit{Win}^{\textit{i}}_{\textit{push\\_width}}\neq\textit{Win}^{\textit{i}}_{\textit{last\\_push\\_width}}$
a new Lateral node can be inserted with width
Win${}^{\textit{i}}_{\textit{last\\_push\\_width}}$. This node changes row
bounds for rows at or below Win${}^{\textit{i}}_{\textit{min}}$ if there was
no other Lateral node above Win${}^{\textit{i}}_{\textit{min}}$ at the shift
to Win${}^{\textit{i}}$, and in that case those rows would have before
Win${}^{\textit{i}}$ been bounded by
Win${}^{\textit{i}}_{\textit{last\\_push\\_width}}$, which is the same as the
width bound this node enforces. Therefore, the induction invariant continues
to hold for rows at or below Win${}^{\textit{i}}_{\textit{min}}$.

Now we inspect rows above Win${}^{\textit{i}}_{\textit{min}}$ to see if the
invariant also holds there. Firstly, no row will have a width bound smaller
than Win${}^{\textit{}}_{\textit{push\\_width}}$, as smaller widths will be
lowered or inserted to or below Win${}^{\textit{i}}_{\textit{min}}$ (lines 3,
3). Therefore, only items above Win${}^{\textit{i}}_{\textit{min}}$ outside
Win${}^{\textit{i}}_{\textit{push\\_width}}$ can break the invariant. In the
lowering phase, Lateral nodes
$l,l.0pt>\textit{Win}^{\textit{i}}_{\textit{last\\_push\\_width}}\land
l.0pt>\textit{Win}^{\textit{push\\_width}}$ are lowered iff the shift to
Win${}^{\textit{i}}$ was downwards, as then all sub-stacks outside
Win${}^{\textit{i}}_{\textit{last\\_push\\_width}}$ were seen at the bottom of
the last window. Thus, if
$\textit{Win}^{\textit{i}}_{\textit{push\\_width}}\geq\textit{Win}^{\textit{i}}_{\textit{last\\_push\\_width}}$
no nodes could have been pushed outside
Win${}^{\textit{i}}_{\textit{push\\_width}}$ since the shift to
Win${}^{\textit{i}}$, and as all widths bound held then, they will hold at the
shift from Win${}^{\textit{i}}$. Otherwise, if
$\textit{Win}^{\textit{i}}_{\textit{push\\_width}}<\textit{Win}^{\textit{i}}_{\textit{last\\_push\\_width}}$,
every row $r,r\leq l.\textit{row}$ for the topmost Lateral node $l$ must have
a valid bound, and the rows above $l.\textit{row}$ were before
Win${}^{\textit{i}}$ bounded by
Win${}^{\textit{i}}_{\textit{last\\_push\\_width}}$ which is smaller than the
new bound Win${}^{\textit{i}}_{\textit{push\\_width}}$, so the width bounds
must hold for all rows in this case as well.

###### Lemma 3

If $x$ lives on the stack during ${}^{\prime}x$, then for any item $y$ pushed
during ${}^{\prime}x$, $\textit{row}_{y}\geq\textit{Win}^{\textit{push
x}}_{\textit{min}}-\textit{Win}^{\textit{max x}}_{\textit{shift}}$.

###### Proof

This is proved by contradiction. Assume $x$ was pushed at time $t_{x}$ and
there exists an item
$y,\textit{row}_{y}\leq\textit{Win}^{\textit{x}}_{\textit{min}}-\textit{Win}^{\textit{max
x}}_{\textit{shift}}$, pushed at time $t_{y}<t_{x}$. Call the point in time
where a thread shifted the window to Win${}^{\textit{y}}$ as $t_{s}$.

  * •

If $t_{s}<t_{x}$, then $x$ must be pushed in the same, or a later window than
Win${}^{\textit{y}}$. But it cannot be later as $y$ is pushed during
Win${}^{\textit{y}}$, and $t_{y}>t_{x}$. Furthermore, as $t_{x}$ can’t be
during Win${}^{\textit{y}}$ either, as an item is pushed at or below
Win${}^{\textit{}}_{\textit{max}}$.

  * •

If instead $t_{s}>t_{x}$, we call the window before Win${}^{\textit{y}}$ as
Win${}^{\textit{z}}$. For a thread to shift from Win${}^{\textit{z}}$, it must
have seen $\forall j,N_{j}=\textit{Win}^{\textit{z}}_{\textit{min}}$ (as Lemma
2 shows iterating over Win${}^{\textit{}}_{\textit{pop\\_width}}$ is the same
as iterating over all $j$) at some point $t_{z}$ (set $t_{z}$ as the time it
started this iteration) during Win${}^{\textit{z}}$. As
$\textit{Win}^{\textit{z}}_{\textit{min}}<\textit{row}_{x}$, $t_{x}>t_{z}$,
which means that $t_{x}$ must have been during Win${}^{\textit{z}}$, as we
above showed $t_{x}<t_{s}$. This is impossible as during Win${}^{\textit{z}}$,
items are pushed at or below Win${}^{\textit{z}}_{\textit{max}}$.

###### Lemma 4

If $x$ lives on the stack during ${}^{\prime}x$, then for any item $y$ pushed,
but not popped, during ${}^{\prime}x$,
$\textit{row}_{y}\leq\textit{Win}^{\textit{pop
x}}_{\textit{max}}+\textit{Win}^{\textit{max x}}_{\textit{shift}}$.

###### Proof

This is similar to the last lemma and is also proved by contradiction,
assuming that $x$ was pushed at $t_{x}$, popped at time $t^{\prime}_{x}$ and
that there exists an item $y,\textit{row}_{y}>\textit{Win}^{\textit{pop
x}}_{\textit{max}}+\textit{Win}^{\textit{max x}}_{\textit{shift}}$ pushed at
$t_{y}$ and not popped at $t^{\prime}_{x}$, where
$t_{x}<t_{y}<t^{\prime}_{x}$. Call the point in time where a thread shifted to
Win${}^{\textit{pop x}}$ as $t_{s}$.

  * •

If $t_{s}<t_{y}$, then $y$ must have been pushed in the same window as $x$ was
popped. But items are only pushed at or below
Win${}^{\textit{}}_{\textit{max}}$, which contradicts the assumption, as $y$
is pushed too low.

  * •

If $t_{y}<t_{s}$, we call the window proceeding Win${}^{\textit{pop x}}$ as
Win${}^{\textit{z}}$. For a thread to shift from Win${}^{\textit{z}}$, it must
have seen $\forall j,N_{j}=\textit{Win}^{\textit{z}}_{\textit{min}}$ at some
point $t_{z}$ (set $t_{z}$ as the time it started the iteration, seeing the
first $N_{j}=\textit{Win}^{\textit{z}}_{\textit{min}}$) during
Win${}^{\textit{z}}$. Therefore, $t_{z}<t^{\prime}_{y}$, which is impossible
as $\textit{Win}^{\textit{z}}_{\textit{max}}<\textit{row}_{y}$ and
$t_{y}<t_{s}$.

###### Theorem 4.3

The elastic 2D stack is linearizeable with respect to a stack with $k$ out-of-
order relaxed non-empty pops, where $k$ is bounded for every item $x$ as
$k=(\textit{Win}^{\textit{max
x}}_{\textit{width}}-1)(3\textit{Win}^{\textit{max x}}_{\textit{depth}}-1)$.

###### Proof

Assume that $y$ is pushed after $x$ and not popped before $x$. Then Lemma 3
and 4 gives $\textit{Win}^{\textit{push
x}}_{\textit{min}}-\textit{Win}^{\textit{max
x}}_{\textit{shift}}\leq\textit{row}_{y}\leq\textit{Win}^{\textit{pop
x}}_{\textit{max}}+\textit{Win}^{\textit{max x}}_{\textit{shift}}$. As each
sub-stack is internally ordered and the maximum number of items pushed after
$x$ and not popped before $x$ becomes $(\textit{Win}^{\textit{max
x}}_{\textit{push\\_width}}-1)(\textit{Win}^{\textit{pop
x}}_{\textit{max}}-\textit{Win}^{\textit{push
x}}_{\textit{min}}+2\textit{Win}^{\textit{max
x}}_{\textit{shift}})\leq(\textit{Win}^{\textit{max
x}}_{\textit{push\\_width}}-1)(3\textit{Win}^{\textit{max
x}}_{\textit{depth}}-1)$.

##  5 Evaluation

We experimentally evaluate the scalability and elastic capabilities of our
elastically relaxed LaW queue, LpW queue, and LpW stack. All experiments run
on an AMD-based machine with a 128-core 2.25GHz AMD EPYC 9754 with two-way
hyperthreading, 256 MB L3 cache, and 755 GB of RAM. The machine runs openSUSE
Tumbleweed 20240303 which uses the 7.4.1 Linux kernel. All experiments are
written in C and are compiled with gcc 13.2.1 and its highest optimization
level. In all tests, threads are pinned in a round-robin fashion between
cores, starting to use hyperthreading after 128 threads.

Our elastic 2D implementations build on an optimized version of the earlier 2D
framework [25]. We use SSMEM from [4] for memory management, which includes an
epoch-based garbage collector for our dynamic memory.

###  5.1 Static Relaxation

To understand the performance of our data structures under static relaxation,
we compare their scalability against that of well-known relaxed and strict
designs. For the queues, we select the static 2D queue [25] and the k-segment
queue [16] as baselines for modern k-out-of-order designs. We selected the
wait-free (WF) queue from [30] as the state-of-the-art linearizable FIFO queue
for our study. Although we also evaluated the LCRQ from [20], it showed
slightly inferior performance in our tests. Additionally, we included the
Michael-Scott (MS) queue [18] as a baseline. For the stacks we similarly
selected the 2D stack [25] and the k-segment stack [11] for relaxed designs.
We then also compared with a lock-free elimination-backoff stack [10] and the
Treiber stack as a baseline [27]. All data structures were implemented in our
framework using SSMEM [4] for memory management, with the exception of the WF
queue, for which we used the authors’ implementation that employs hazard
pointers.

We use a benchmark where threads over $1$ second repetedly perform insert or
remove operations at random every iteration. Each data structure is pre-filled
with $2^{19}$ items to avoid empty returns, which significantly alter the
performance profile. Test results are aggregated over 10 runs, with standard
deviation included in the plots. The test bounds the rank error of the data
structures, and as the optimal choice of Win${}^{\textit{}}_{\textit{width}}$
and Win${}^{\textit{}}_{\textit{depth}}$ is not known [25], we simply set
$\textit{Win}^{\textit{}}_{\textit{width}}=2\times\textit{nbr\\_threads}$, and
use the maximum 0ptto stay within the bound, which is simple and gives
acceptable scalability.

Measuring rank errors without altering their distribution is an open problem,
and we adapt the method used, e.g. [25, 3, 24] to our algorithms. It
encapsulates the linearization points of all methods by global locks, imposing
a total order on all operations, and keeps a sequentially ordered data
structure on the side. After each removal operation that returns $x$, the
distance between $x$ and the top item gives the rank error. This strategy
greatly reduces throughput, as it serializes all operations, so all rank error
measurements are done in separate runs from throughput runs.

Figure 3 shows how the queues and stacks scale with both threads and
relaxation. The results show that the elastic designs scale essentially as
well as the static 2D framework and out-scale the other data structures. This
means that the overhead induced by Lateral is minimal in periods of static
relaxation. This is due to the extra work from the Lateral being mostly
confined to small checks during window shifts, and otherwise functions as the
static 2D structures.

Figure 3: Scalability of throughput and rank error during static relaxation.
When scaling with threads (top row), the error bound is fixed as $k=5\times
10^{3}$. When scaling with error bound, 256 threads are used.

###  5.2 Elastic Relaxation - Manual adjustments

Here, we demonstrate that our elastic designs can efficiently trade accuracy
for throughput by showing real-time relaxation and throughput metrics for a
benchmark with several elastic changes in relaxation. Figure 4 plots
throughput as well as average rank errors for a single run for our different
designs. Vertical lines represent user-initiated elastic relaxation
adjustments. Our data structures are pre-filled with $2^{15}$ items, as to
avoid empty returns while keeping the number of items relatively small. The
threads all save a timestamp every 1000 operations to measure the throughput
and the throughput values are then aggregated with a moving average window of
size $25$ ms. All 128 threads randomly alternate between inserting and
removing items.

Measuring the rank errors is done in a separate run from the throughput, as
the measurements impose a total ordering on all operations, massively slowing
down the throughput. To align the relaxation and throughput measurements, we
ran the relaxation test for $10^{3}$ times as long for the queue ($2\cdot
10^{3}$ for the stack) and subsequently compressed the relaxation measurements
to the same time frame. These factors were used because they were the average
slowdown of the throughput when measuring relaxation during the experiment.
The rank errors are also smoothed out with the same moving average window of
$25$ ms.

Figure 4: Performance during one run, where threads repeatedly insert or
remove items at random, and vertical lines indicate user-initiated elastic
changes. It runs for four seconds with 128 threads. The width (W) and depth
(D) are annotated for every relaxation period.

As show in Figure 4, the elastic relaxation works and can quickly change
throughput and rank errors. For the queues, the rank error measurements are
relatively stable, and so is the throughput, althought to a lesser extent. The
throughput is dependent on randomness and how the threads select sub-queues to
operate on, which leads to variance in the performance over time. The stack
has similar variance in throughput, but more erratic average rank errors. The
rank error bound for the stack does not only depend on the current window, but
also previous ones, which means it can sometimes change unexpectedly. The
stack also has a much more erratic performance profile, as the threads can
work completely thread-local on a sub-stack for a long time in the best case
with close to 0 rank error, but in the worst case can have to jump around a
lot.

Although requiring externally initiated changes in relaxation, the plots show
how swiftly the designs can trade accracy for throughput. It is evident that
the optimial choice of 0ptand 0ptdepends on the data structure, as well as the
workload, meaning these plots can be of use when creating applications where
you want to control the relaxation differently during different time periods.

###  5.3 Elastic Relaxation - Dynamic adjustments

Here we showcase the elastic capabilities of our designs by implementing a
simple controller that dynamically controls
Win${}^{\textit{}}_{\textit{width}}$ in a realistic use case with dynamic
workload. Consider a shared queue where tasks can be added and removed in FIFO
order. We let one third (42) of the 128 cores act as consumers of this queue,
constantly trying to dequeue tasks from it. The remaining (86) cores are
designated as producers, repeatedly adding tasks to the queue, though not
always active, as illustrated in the top graphs of Figure 5. This simulates a
task queue in a highly contended server, where the consumers are internal
workers working at a constant pace, and the load of the producers vary
depending on external factors. Our goal is to control the relaxation to cope
with the dynamic nature of this producer workload.

To cope with this dynamic nature, our relaxation controller strives to keep
the operational latency approximately constant for all producers. To minimize
overhead, this controller is thread-local and only tracks failed and
successful CAS linearizations, and is shown in Algorithm 4. It increments or
decrements a contention count by SUCC_INC or FAIL_DEC depending on if the CAS
linearization on a sub-queue succeeds or fails respectively (line 4). If
$|\textit{contention}|>\textit{CONT\\_TRESHOLD}$, the thread resets
contention, adds a local vote for increasing or decreasing the next
Win${}^{\textit{tail}}_{\textit{width}}$ by WIDTH_DIFF, and depending on its
votes tries to change width_shared (used at lines 1 and 2). When the window
shifts, the local vote count is reset. These values can be tuned, but are in
our experiments set as
$\textit{SUCC\\_INC}=1,\textit{FAIL\\_DEC}=75,\textit{CONT\\_TRESHOLD}=5000,\textit{WIDTH\\_DIFF}=5$.

0.1

0.2

0.3struct  _Controller_

0.4 uint contention;

0.5 uint version;

0.6 uint votes;

0.7

0.8

0.9method  _Controller.Update(self, cas_success)_

0.10 if  _self.version $\neq$ Win${}^{\textit{tail}}_{\textit{max}}$_ then

0.11 self.version $\leftarrow$ Win${}^{\textit{tail}}_{\textit{max}}$ ;

0.12 self.votes $\leftarrow$ 0;

0.13

0.14

0.15 self.contention $\leftarrow$ self.contention + if cas_success then
SUCC_INC else -FAIL_DEC;

0.16

0.17 if  _$|$ self.contention$|$ $\geq$ CONT_TRESHOLD_ then

0.18 self.votes $\leftarrow$ self.votes + sign(self.contention);

0.19 self.contention $\leftarrow$ 0;

0.20 width${}_{\textit{shared}}$ $\leftarrow$
Win${}^{\textit{tail}}_{\textit{width}}$ \- WIDTH_DIFF $*$ sign(self.votes);

0.21

0.22

Algorithm 4 Simple relaxation controller for the Elastic 2D queues

Figure 5 shows the average thread operational latency, as well as the error
bound
$(\textit{Win}^{\textit{head}}_{\textit{width}}-1)\times\textit{Win}^{\textit{head}}_{\textit{depth}}$
averaged over 50 runs for our elastic LaW queue. It also shows $\textit{tail
error}=(\textit{Win}^{\textit{tail}}_{\textit{width}}-1)\times\textit{Win}^{\textit{tail}}_{\textit{depth}}$
which can be interpreted as a rank error for enqueues, and shows that the
controller adapts quickly. However, it notes occasional delays between
Win${}^{\textit{tail}}_{\textit{width}}$ and
Win${}^{\textit{head}}_{\textit{width}}$, as the change has to propagate
through the queue. The figure shows a scenario without the dynamic controller,
one short test over $1$ second, and one long test over $1$ minute.

(a) Static Relaxation

(b) Dynamic Relaxation, 1 second

(c) Dynamic Relaxation, 1 minute

Figure 5: Producer-consumer system with a variable number of producers over
time for the elastic LaW queue. The Dynamic Relaxation plots use a controller
to adjust the relaxation, stabilizing the producer’s latency.

The test without the controller shows how the latency clearly scales with
contention for the producers, while the consumers are mostly unaffected.
However, using the controller, the producers’ latency is much more stable.
While latency spikes are evident with rapid increases in contention, the
controller effectively stabilizes them. While producers enjoy stable latency,
consumers must accommodate the significant variations in relaxation.
Furthermore, it is evident that the controller quickly adjusts
Win${}^{\textit{tail}}_{\textit{width}}$ based on the number of producers.
However, at some points, it takes a while for this change to reach
Win${}^{\textit{head}}$ and affect the rank error bound, as it must propagate
through the whole queue.

This experiment shows a practical use-case for the elastic queue, and that a
simple thread-local controller for the 0ptis enough to get good dynamic trade-
offs between relaxation and latency. Similar controllers could easily be
created to target different use-cases, such as those where we care about the
performance of both the producers and consumers. For example, using the
elastic LaW queue, a controller could control
Win${}^{\textit{head}}_{\textit{depth}}$ and
Win${}^{\textit{tail}}_{\textit{depth}}$ separately in combination with
Win${}^{\textit{}}_{\textit{width}}$, which would lead to more flexible
adaptation. To fully leverage such a controller, it would be helpful to design
a model for the queue performance, so that the choices of 0ptand 0ptcould be
made with more information.

##  6 Conclusions

We have presented the concept of elastic relaxation for concurrent data
structures, and extended the 2D relaxed framework from [25] to encompass
elasticity. The history of elastic changes is tracked by the Lateral
structure, which can also be used to extend other $k$ out-of-order data
structures. Our designs have established worst-case bounds, and demonstrate as
good performance during periods of constant relaxation as state-of-the-art
designs, while also being able to reconfigure their relaxation on the fly. Our
simple controller, based on thread-local contention, demonstrated that the
elasticity can be utilized to effectively trade relaxation for latency. We
believe elastic relaxation is essential for relaxed data structures to become
realistically viable and see this paper as a first step in that direction.

As further work, we find constructing a model over the data structure
performance interesting, which could aid in designing more sophisticated
relaxation controllers. Another direction is applying the idea of elasticity
to other data structures, such as relaxed priority queues.

## References

  * [1] Alistarh, D., Brown, T., Kopinsky, J., Li, J.Z., Nadiradze, G.: Distributionally Linearizable Data Structures. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures pp. 133–142 (2018). https://doi.org/10.1145/3210377.3210411
  * [2] Alistarh, D., Kopinsky, J., Li, J., Nadiradze, G.: The power of choice in priority scheduling. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. p. 283–292. PODC ’17, Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3087801.3087810
  * [3] Alistarh, D., Kopinsky, J., Li, J., Shavit, N.: The spraylist: A scalable relaxed priority queue. SIGPLAN Not. 50(8), 11–20 (jan 2015). https://doi.org/10.1145/2858788.2688523
  * [4] David, T., Guerraoui, R., Trigonakis, V.: Asynchronized concurrency: The secret to scaling concurrent search data structures. SIGARCH Comput. Archit. News 43(1), 631–644 (mar 2015). https://doi.org/10.1145/2786763.2694359
  * [5] Derrick, J., Dongol, B., Schellhorn, G., Tofan, B., Travkin, O., Wehrheim, H.: Quiescent consistency: Defining and verifying relaxed linearizability. In: Jones, C., Pihlajasaari, P., Sun, J. (eds.) FM 2014: Formal Methods. pp. 200–214. Springer International Publishing, Cham (2014)
  * [6] Ellen, F., Hendler, D., Shavit, N.: On the inherent sequentiality of concurrent objects. SIAM Journal on Computing 41(3), 519–536 (2012). https://doi.org/10.1137/08072646X
  * [7] Haas, A., Hütter, T., Kirsch, C.M., Lippautz, M., Preishuber, M., Sokolova, A.: Scal: A benchmarking suite for concurrent data structures. In: Bouajjani, A., Fauconnier, H. (eds.) Networked Systems. pp. 1–14. Springer International Publishing, Cham (2015)
  * [8] Haas, A., Lippautz, M., Henzinger, T.A., Payer, H., Sokolova, A., Kirsch, C.M., Sezgin, A.: Distributed queues in shared memory: Multicore performance and scalability through quantitative relaxation. In: Proceedings of the ACM International Conference on Computing Frontiers. CF ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2482767.2482789
  * [9] Hendler, D., Khattabi, A., Milani, A., Travers, C.: Upper and Lower Bounds for Deterministic Approximate Objects. 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS) 00, 438–448 (2021). https://doi.org/10.1109/icdcs51616.2021.00049
  * [10] Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. Journal of Parallel and Distributed Computing 70(1), 1–12 (2010). https://doi.org/10.1016/j.jpdc.2009.08.011
  * [11] Henzinger, T.A., Kirsch, C.M., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. SIGPLAN Not. 48(1), 317–328 (jan 2013). https://doi.org/10.1145/2480359.2429109
  * [12] Herlihy, M., Shavit, N., Luchangco, V., Spear, M.: The Art of Multiprocessor Programming. Elsevier Science (2020)
  * [13] Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12(3), 463–492 (1990). https://doi.org/10.1145/78969.78972
  * [14] Kappes, G., Anastasiadis, S.V.: A family of relaxed concurrent queues for low-latency operations and item transfers. ACM Trans. Parallel Comput. 9(4) (dec 2022). https://doi.org/10.1145/3565514
  * [15] Karp, R.M., Zhang, Y.: Randomized parallel algorithms for backtrack search and branch-and-bound computation. J. ACM 40(3), 765–789 (jul 1993). https://doi.org/10.1145/174130.174145
  * [16] Kirsch, C.M., Payer, H., Röck, H., Sokolova, A.: Performance, Scalability, and Semantics of Concurrent FIFO Queues. In: Algorithms and Architectures for Parallel Processing, vol. 7439, pp. 273–287. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33078-0_20
  * [17] Kraska, T.: Towards instance-optimized data systems, keynote. 2021 International Conference on Very Large Data Bases (2021)
  * [18] Michael, M.M., Scott, M.L.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing. pp. 267–275 (1996)
  * [19] Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12(10), 1094–1104 (2001). https://doi.org/10.1109/71.963420
  * [20] Morrison, A., Afek, Y.: Fast concurrent queues for x86 processors. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. p. 103–112. PPoPP ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2442516.2442527
  * [21] Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. p. 456–471. SOSP ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2517349.2522739
  * [22] Peterson, G.L., Burns, J.E.: Concurrent reading while writing II: The multi-writer case. In: 28th Annual Symposium on Foundations of Computer Science (Sfcs 1987). pp. 383–392. IEEE, Los Angeles, CA, USA (Oct 1987). https://doi.org/10.1109/SFCS.1987.15
  * [23] Postnikova, A., Koval, N., Nadiradze, G., Alistarh, D.: Multi-queues can be state-of-the-art priority schedulers. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. p. 353–367. PPoPP ’22, Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/10.1145/3503221.3508432
  * [24] Rihani, H., Sanders, P., Dementiev, R.: Multiqueues: Simple relaxed concurrent priority queues. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. p. 80–82. SPAA ’15, Association for Computing Machinery, New York, NY, USA (2015). https://doi.org/10.1145/2755573.2755616, https://doi.org/10.1145/2755573.2755616
  * [25] Rukundo, A., Atalar, A., Tsigas, P.: Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework. In: 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 146, pp. 31:1–31:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https://doi.org/10.4230/LIPIcs.DISC.2019.31
  * [26] Shavit, N.: Data structures in the multicore age. Commun. ACM 54(3), 76–84 (mar 2011). https://doi.org/10.1145/1897852.1897873
  * [27] Treiber, R.: Systems programming: Coping with parallelism. Tech. rep., International Business Machines Incorporated, Thomas J. Watson Research Center (1986)
  * [28] Williams, M., Sanders, P., Dementiev, R.: Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues. In: 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 204, pp. 81:1–81:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). https://doi.org/10.4230/LIPIcs.ESA.2021.81
  * [29] Wimmer, M., Gruber, J., Träff, J.L., Tsigas, P.: The lock-free k-lsm relaxed priority queue. In: Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. p. 277–278. PPoPP 2015, Association for Computing Machinery, New York, NY, USA (2015). https://doi.org/10.1145/2688500.2688547
  * [30] Yang, C., Mellor-Crummey, J.: A wait-free queue as fast as fetch-and-add. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2851141.2851168

##  Appendix 0.A New bound for static 2D stack

The relaxation bound for the static 2D stack from [25] (Theorem 5) has a small
mistake, and is too low. The error comes from the fact that the proof
mistakenly assumes that each item is popped while
Win${}^{\textit{}}_{\textit{max}}$ is the same as when it was pushed. If
$0pt=2\textit{shift}$, the difference between these two
Win${}^{\textit{}}_{\textit{max}}$ is shift. Here we present a new bound and
corresponding proof.

For brevity, we call the number of nodes on sub-stack $j$ as $N_{j}$, and the
window item $x$ was popped $\textit{Win}^{\textit{pop x}}$. We also note that
shift does not necessarily have to be $0pt/2$ which we assume in the rest of
the paper, as this is not enforced for the proofs in [25].

###### Lemma 5

It always holds that $\forall j:\textit{Win}^{\textit{min}}-\textit{shift}\leq
N_{j}\leq\textit{Win}^{\textit{}}_{\textit{max}}$ or $\forall
j:\textit{Win}^{\textit{min}}\leq
N_{j}\leq\textit{Win}^{\textit{}}_{\textit{max}}+\textit{shift}$.

###### Proof

This is equivalent to the already proven Lemma 4 in [25].

###### Theorem 0.A.1

The static 2D stack has a $k$ out-of-order relaxation bound of
$k=\left(20pt+2\textit{shift}+\left\lfloor\frac{0pt-1}{\textit{shift}}\right\rfloor\textit{shift}\right)(0pt-1)$.

###### Proof

This is proved by looking at how many items can be pushed during the lifetime
of $x$ (${}^{\prime}x$), without being popped during ${}^{\prime}x$. Lemma 5
bounds the size of all sub-stacks when $x$ is popped as
$N_{j}\leq\textit{Win}^{\textit{pop
x}}_{\textit{max}}+\textit{shift}=N_{\textit{upper}}$.

Additionally, Lemma 5 bounds the size of all sub-stacks during ${}^{\prime}x$
as $N_{j}\geq\textit{row}_{x}-\textit{shift}-0pt=N_{\textit{lower}}$.
Furthermore, the lemma limits $N_{\textit{lower}}$ to be at
$\textit{Win}^{\textit{}}_{\textit{min}}$, or shift below
$\textit{Win}^{\textit{}}_{\textit{min}}$ for some
Win${}^{\textit{}}_{\textit{min}}$ during ${}^{\prime}x$, meaning (i)
$\textit{Win}^{\textit{pop
x}}_{\textit{max}}-N_{\textit{lower}}=0pt+m\times\textit{shift}$ for some
integer $m$.

All items in the same sub-stack as $x$ are correctly ordered. Therefore, the
number of items pushed and not popped during ${}^{\prime}x$ must be at most
$(0pt-1)(N_{\textit{upper}}-N_{\textit{lower}})=(0pt-1)(\textit{Win}^{\textit{pop
x}}_{\textit{max}}-\textit{row}_{x}+2\textit{shift}+0pt)$. From (i) we have
that $\textit{Win}^{\textit{pop x}}_{\textit{max}}-\textit{row}_{x}$ is an
even multiple of shift. Additionally, as $x$ is popped during
$\textit{Win}^{\textit{pop x}}$, it holds that $\textit{Win}^{\textit{pop
x}}_{\textit{max}}-\textit{row}_{x}\leq 0pt-1$. Combining these two last
statements gives that $\textit{Win}^{\textit{pop
x}}_{\textit{max}}-\textit{row}_{x}\leq\left\lfloor\frac{depth-1}{shift}\right\rfloor\textit{shift}$,
which bounds the number of items pushed, but not popped, during ${}^{\prime}x$
as
$(0pt-1)(2\textit{shift}+0pt+\left\lfloor\frac{depth-1}{shift}\right\rfloor\textit{shift})$.