Dynamic concurrent
van Emde Boas array
Konrad Kułakowski

arXiv:1509.06948v1 [cs.DS] 23 Sep 2015

AGH University of Science and Technology,
al. Mickiewicza 30, Kraków, Poland,
konrad.kulakowski@agh.edu.pl

Abstract. The growing popularity of
shared-memory multiprocessor machines
has caused significant changes in the design
of concurrent software. In this approach,
the concurrently running threads communicate and synchronize with each other
through data structures in shared memory.
Hence, the efficiency of these structures is
essential for the performance of concurrent
applications. The need to find new concurrent data structures prompted the author
some time ago to propose the cvEB array
modeled on the van Emde Boas Tree structure as a dynamic set alternative.
This paper describes an improved version
of that structure - the dcvEB array (Dynamic Concurrent van Emde Boas Array).
One of the improvements involves memory
usage optimization. This enhancement required the design of a tree which grows
and shrinks at both: the top (root) and
the bottom (leaves) level. Another enhancement concerns the successor (and predecessor) search strategy. The tests performed
seem to confirm the high performance of
the dcvEB array. They are especially visible when the range of keys is significantly
larger than the number of elements in the
collection.

1

Introduction

The rapid rise in the popularity of multi-core sharedmemory processor systems makes concurrent programs increasingly common and desirable. Following
the growing market for concurrent software, an increasing demand for the use of concurrent data structures can be observed. Such a situation makes the
search for new concurrent data structures particularly important. One of the attempts to find such a
structure is the work [15] in which the author proposed the early version of the concurrent van Emde
Boas (cvEB ) array. The structure presented here is
an example of concurrent dynamic set implementation providing, in addition to the standard methods

insert(), remove() and find(), also the method successor(), which allows users to determine the first greater
element from the specified one. It has very good theoretical and practical properties, as confirmed by tests
and analyses carried out. Unfortunately, one of the
shortcomings of that solution is the need to allocate
all the required memory at the very beginning, as in
the case of a regular array. Another limitation of that
structure is the implementation of successor(), which
in the case of massive interference with remove() operating in different threads might be delayed or failed
due to the search repetition. These deficiencies led
the author to propose a new dynamic concurrent van
Emde Boas (dcvEB ) array, which, on the one hand,
retains the good properties of its antecedent, and on
the other hand is deprived of its shortcomings. Hence,
the new structure presented in this article allocates
and deallocates memory dynamically, depending on
the amount of data stored in it. In addition, a new
strategy for the successor() and predecessor() methods has been adopted. The new structure, rather than
repeating the successor or predecessor search, continues searching until an appropriate element is found
or the absence of such an element is decided. The assumed strategy is more robust and less susceptible to
interference. It also seems to be more intuitive and
justifiable in the context of user expectation.
The article consists of several sections, where, except for introductory ones (Sec. 1 - 3), the dcvEB array (Subsection 4.2) and its implementation (Subsection 4.3) are discussed. Next, the mechanisms of concurrent expanding and shrinking are explained (Subsection 5.1). Other enhancements, such as dynamic
memory allocation and the new search strategy, are
explained (Subsections: 5.2 and 5.3). Then, the successor search running time and the structure correctness are discussed (Section 5). The experimental results are examined in Section 6. The comments and
discussion (Section 7) and a brief summary (Section
8) close the article.

2

Background

A dynamic set is one of the basic data structures in
computer science. Usually, it is assumed that a dynamic set supports the following operations: insert(),
delete(), search(), minimum(), maximum(), successor() and predecessor() [5, p. 230]. The first two of
them are included in the category of modifying operations, while others are queries, which do not modify
the structure. Due to increasing demands for data
format, different structures support dynamic set operations to varying degrees. In particular, good dynamic set operation performance is provided by bal-

anced search trees. For instance, all the dynamic set
operations can be handled by RB-Trees [1] in a sequential running time O(lg α), whilst van Emde Boas
trees [25] need barely O(lg lg α) time to complete any
of the mentioned operations [5]. Unfortunately, transition from the sequential to the concurrent objects
is not easy [24]. Hence, many concurrent dynamic set
implementations (e.g. [6,13]) do not support all the
dynamic set operations and instead focus on dictionary operations.
The early works on the concurrent balanced search
trees with dictionary operations began to emerge in
the 70s [23,2]. In the subsequent years, the topic was
studied in [7,16,19]. The studies, initially focusing
on lock strategy [2] and lock coupling [19,17], began to deal with the relaxed (delayed) re-balancing
[21,9] and the non-blocking synchronization schemes
[3,6,4,13].
Skip List, proposed by Pugh [22], is an alternative
to balanced search trees. It provides several linked
lists arranged in a hierarchy, so that the single list
corresponds to the set of nodes at the same depth
in a search tree. The structure avoids additional rebalancing due to the randomized fashion of the insertion algorithm. SkipList is suitable for both the
sequential and concurrent applications. Very efficient
SkipList implementation [10], based on Fraser [8], is
part of a standard Java API 5. The Java SkipList
implementation as one of the few (the second is a
SnapTree Map by Bronson [3]) supports all the dynamic set operations including successor() and predecessor().

3

van Emde Boas tree

The tree structure proposed by van Emde Boas [25]
is not a typical search tree. It supports all the
dynamic set operations, such as insert(), delete(),
search(), minimum(), maximum(), successor() and
predecessor() [5, p. 230] in O(ln ln α). This tremendous speed involves the requirement that the keys
must be unique integers in the range 0 to α − 1.
Thus, from a practical point of view, the van Emde
Boas (vEB) tree is something between an array and
a search tree. Assuming that the number of stored
elements is essentially smaller than α, the vEB tree
is better than the array as regards the speed of successor(), predecessor(), minimum() and maximum().
Of course, the efficiency of the array operations insert(), delete() and search() remains unchallenged regardless of the stored data size. In general, the vEB
tree operates faster than the other search trees. However, the strong constraint on the key values makes it

unusable if the stored objects cannot be represented
as unique integers.
The key to the efficiency of the vEB tree operations
is the uneven number of subtrees on different levels
of the vEB tree. Thus, the root node has α1/2 of subtrees, whereas each next level of the vEB tree shrinks
the number of children in the nodes by the square
root. Assuming that an operation over the vEB tree
performs O(1) work at each level of the hierarchy,
the running time of a method is O(h), where h is the
height of the vEB tree. Reducing the number of subtrees can not be carried out indefinitely. Thus, at the
last but one level of the tree, the nodes have at most
h−1
two single-element subtrees, i.e. α1/2
= 2. Hence,
h−1
we obtain ln α = 2
, and finally h = ln ln α + 1.
Thus, the asymptotic running time of an exemplary
operation is O(ln ln α + 1) = O(ln ln α).
To be able to traverse each level of a tree in O(1)
the vEB tree methods use the arrays of references to
the subtrees. For this reason the root node Troot needs
to store Troot .arr - α1/2 -element array of subtrees,
their children T , T.arr - α1/4 -element arrays of their
subtrees, and so on. With this construction, every
method can calculate in which subtree the given key
can be found. For example, in the case of the root
node, the key x is expected to be in x/α1/2 subtree
etc.
To achieve O(1) level traversing time, the more
complex methods like successor() and predecessor()
need further information about the subtrees. Thus,
with every node T the next three variables are assigned: T.max, T.min and T.summary, where T.max,
T.min denote correspondingly the maximal and the
minimal value of a key in the subtree rooted in T .
The summary is an auxiliary search structure. Intuitively speaking, the search() method traverses down
the vEB tree along a well-defined path from the root
to the given key. The successor() must deviate from
this path to the right (predecessor() to the left). The
decision whether to go down into the subtree according to the predetermined path or go to the right at the
same level is taken on the basis of the value T.max.
Thus, if T is a subtree in which, according to the
path calculation, the key x should be stored, then
the successor() goes down into T only if x < T.max,
i.e. when the maximal key in T is greater than x.
If x ≥ T.max the successor() method needs to move
horizontally to the right in search of the first nonempty subtree. Of course, such a horizontal search
might be time consuming. For instance, the linear
browsing Troot .arr may take up to O(α1/2 ). In order
to shorten the horizontal search, the same mechanism as in the case of the whole structure is used.
T.summary is an auxiliary tree that holds informa-

tion about the occupancy of the array T.arr in the
same manner as the main tree holds the keys. Thus,
traversing T.summary takes at most O(ln ln |T.arr|).
In the results, the overall asymptotic running time of
successor() and predecessor() is O(ln ln α).
A good and systematic introduction into the vEB
trees theory can be found in [5].

4
4.1

Construction of the dcvEB array
From the vEB Tree to the dcvEB array

One of the reasons why vEB trees are not so popular in practice are space requirements [5]. The need
to allocate one continuous block of memory in the
root of a structure capable of holding α1/2 - element
array might be inconvenient. The problem can be
addressed in different ways [20,5]. One of them implemented in the dcvEB array proposes the use of
a fixed number of subtrees per node. It results in a
worse theoretical time complexity, however, in many
practical applications the achieved speed appears to
be quite sufficient. For the same reason, the summary
structure is simplified to a bit-vector aligned to the
length of a machine-word. The use of high-speed nonblocking bitwise operations on the summary vector
allows users to avoid the use of T.min and T.max.
The logic behind some methods of the dcvEB array is also changed. For example, in the vEB tree,
the delete() method performs one single pass from
the top to bottom. Due to synchronization issues in
the dcvEB array [15] the delete() method proceeds
bottom-up. Similarly, successor() and predecessor()
first reach the bottom of the tree, then start to traverse the tree moving up and down in search of the
appropriate element. The dcvEB array tries to use
the non-blocking synchronization mechanisms as often as possible. For example, the get() method uses
only the lock-free synchronization mechanisms, which
results in its very good performance in the tests (Sec.
6). The only exception is the mutual synchronization
of insert() and delete(). In this case, in order to ensure data consistency [15, p. 373] the readers-writer
lock [11] is used.
Despite the fact that the creation of the dcvEB
array was inspired by the vEB tree, the differences
between these two structures seem to be fundamental.
Therefore the dcvEB array should be treated, not as
a concurrent extension of the sequential vEB tree but,
as the new and original data structure.
4.2

Structure organization

The dcvEB and cvEB arrays can be seen as a tree
of arrays [15]. Each array’s cell holds the reference

to ArrayHolder (AH) - a tree node structure, which
wraps the lower-level array or stores a specific value
if AH is a leaf. The leaves are kept at the lower level
of the tree. Each array corresponds to an associated
summary - a bit vector, in which the i − th bit is
enabled only if the appropriate array’s cell holds the
lower level AH. Besides an array and the associated
bit vector, every AH also contains the readers-writers
lock object [11]. The leaf AH instead of an array reference holds an element and an integer index value
as its key. The value of the key determines the path
from the root to the leaf understood as a sequence of
positions on the various levels of the tree. The path
positions are calculated according to the following recurrent
formula:
ik = ik−1 − lpk−1 ∗ nh−k−1 , lpk =


h−k−1
ik /n
where n is the length of a bit vector, h is the height of the tree, lpk is the path position on the
k − th level, i0 is a key of the element.
 A position
 at
the root level lp0 is defined as lp0 = i0 /nh−1 . The
dcvEB array of the height h can hold elements within
the range [0, . . . , nh − 1]. If there is a need to store an
element with a key greater than nh −1 or by removing
the item there are no elements with the keys within
the range [nh−1 , . . . , nh − 1] the tree has to be vertically resized. The concurrent tree resizing algorithms
as integral parts of the insert() and remove() procedures are discussed later. If the dcvEB array does
not contain a particular element, and its key fits the
current key range, the insert procedure recreates the
missing AH along the path from the root to the leaf.
Similarly, the remove procedure deletes AHs if the
appropriated summaries are 0.
4.3

dcvEB array methods

The dcvEB array is designed to support all the dynamic set methods as specified in [5, p. 230]. Not all of
them are extensively discussed in the article, although
all of them are implemented1 . In particular, the basics
of the missing predecessor() method are very similar
to successor(), which is discussed below, whilst the
methods minimum() and maximum() have straightforward implementation using successor() and predecessor() 1 . It is assumed that the stored objects are
uniquely identified by integer keys. Thus, the key appears in most of the dcvEB array methods as an
input parameter, whilst the return value of all the
query methods is the pair consisting of the key and
the stored element. The presented implementation
uses locks as well as lock-free synchronization mechanisms. Hence, wherever an atomic, lock-free element
is used, an appropriate object or variable is declared
1

The minimum can be determined by the call successor(0), whilst maximum by the call predecessor( nh −1)

a tree implementing the dcvEB array structure except
the last leaf level, and root - a root’s AH (Listing: 2).
7
8
9
10

ArrayParam
int size
int height
ArrayHolder root

Listing 2: Array Parameters structure

Fig. 1. dcvEB array scheme

as atomic. The main purpose of this section is to allow the reader to understand the general idea behind
the presented algorithms and the data structures they
use. For this reason some issues connected with synchronization and concurrency are only indicated, and
will be discussed later.
The methods presented above use two additional
structures: ArrayHolder (Listing: 1), ArrayParam,
and one atomic common variable ap, which holds
the current ArrayParam value. The ArrayHolder contains five fields: array - atomic array of references to
the lower-level AHs, summary - an atomic bit vector
implemented as any integer type available on the current hardware platform, index - an atomic key value
of the stored object, data - an atomic reference to the
stored object, and lock - reader-writer lock object associated with the given AH.
1
2
3
4
5
6

ArrayHolder
AtomicRefArray array
AtomicInt summary
AtomicInt index
AtomicRef data
RWLock lock

Listing 1: Array Holder structure
The second structure ArrayParam (AP ) contains
the fields: size - the number of indices assignable at
the moment in the dcvEB array (i.e. the maximal
object stored in the dcvEB array cannot have a key
greater than size−1), height - the number of levels of

The current value of ArrayParam is stored in the
common atomic variable ap. Except for initialization,
the fields of AP are read-only, hence they do not need
to be synchronized.
The first presented method discussed in this section is insert() (Listing: 3). At the very beginning
it locks the common atomic variable ap (in order to
prevent altering the current ArrayParam reference by
remove()), then it makes the local copy of the current
array parameters (Line: 12). Next, it locks the root,
(Line: 13), and unlocks ap (Line: 13).
Then, it checks whether the key value fits the current array size and, if not, it tries to extend the array
(Listing: 3, Lines: 15 - 17). Array growing is implemented by adding successive levels above the current
root (Listing: 4). When the new top of the dcvEB
array tree is ready, the algorithm tries to set it as
the new root within the newly created ArrayParam
record (Listing: 4, Line: 17). Then, irrespectively of
the result of the CAS 2 invoke, it unlocks cAP’s root
(Listing: 3, Line: 18). If, due to concurrent interference with other threads, CAS fails and the common
array parameters are not changed, the root locking
guarded by the ap lock is repeated (Listing: 3, Lines:
20 - 21), and the loop condition is re-evaluated (Listing: 3, Line: 14). If CAS succeeds, then cAP is updated (Line: 22), and the loop is interrupted.
After the size of the array has been adapted to the
size of a key, the algorithm traverses the tree structure starting from the current root (Listing: 3, Line:
24) to the leaf. On every step of the loop while (Listing: 3, Lines: 25 - 38) a subsequent level of the tree is
visited. The loop starts from calculating the level position lp, then, if it is not the top level, cAH becomes
read locked, and the previous node pAH is unlocked
(Listing: 3, Line: 28). Next, pAH is set to cAH, and
cAH is atomically updated (Listing: 3, Lines: 29 31). This update is to set the n − lp bit in summary
corresponding to the lp cell of the cAH’s array field.
After setting the bit indicating that at lp position in
cAH’s array there is a subtree, iteration moves to the
lower level of the tree, i.e. the current value of cAH
2

CAS(a,b,c) - compare and swap atomic action operating under the scheme: if a = b then a ← c and return
true. Return false otherwise.

is replaced by the reference to its lp children (Listing:
3, Line: 32).
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

insert(key, data)
apLock.rLock(); cAP ← ap;
cAP.root.rLock(); apLock.rUnlock();
while (key >= cAP.size)
ArrayParam newAP ← grow(key);
newAP.rLock();
tmp ← CAS(ap,cAP,newAP);
cAP.root.rUnlock();
if not tmp then
apLock.rLock(); cAP ← ap;
cAP.root.rLock();apLock.rUnlock();
else cAP ← newAp; break;
end while;
cAH ← cAP.root; cl ← 0; pAH ← nil;
while (cl < cAP.height)
lp ← lvlPos(cl, key);
if cl 6= 0 then
cAH.rLock(); pAH.rUnlock();
pAH ← cAH; cAH.summary ←
0n . . . 0n−lp+1 1n−lp 0n−lp−1 . . . 01
ORbit cAH.summary;
cAH ← cAH.array[lp];
if (cAH = nil) then
cAH ← createAH();
CAS(pAH.array[lp],nil,cAH)
cAH ← pAH.array[lp];
cl ← cl+1;
end while
cAH.data ← data; cAH.index ← key;
pAH.rUnlock();

Listing 3: Insert method
Of course, it is possible that the subtree has not yet
been initialized (Listing: 3, Line: 33). In such a case
the new cAH is created, atomically assigned to the
parent AH’s array when possible (Listing: 3, Line:
35), then due to the possible interference with another insert thread (but not remove thread) the final
value of cAH is re-read from the parent cAH’s array (Listing: 3, Line: 36). At the end of the loop,
the variable determining the current level of iteration
is incremented (Listing: 3, Line: 37). The loop ends
when cAP is pointing at some leaf AH. Hence, at the
end of the method both leaf AH’s fields: data and index, are updated. In the last line of insert() the leaf’s
parent node lock is released (Listing: 3, Line: 40).

As a result of this operation, a new AP record is created (Listing: 4, Line: 42). Then, the grow() procedure calculates the appropriate new height and size
(Listing: 4, Lines: 43 - 44). The number of levels to
create is determined as the difference between the
previous height and the new height of the tree (Listing: 4, 46). Then, the procedure starts the loop while
(Listing: 4, Lines: 48 - 57), and within every turn of
the loop the new AH is generated. The first generated AH becomes a new root of the tree (Listing:
4, Line: 52), each further one becomes the leftmost
child of its predecessor (Listing: 4, Line: 54), and finally the last generated AH takes the previous root
AH as its leftmost child (Listing: 4, Line: 56). The
sequential running time of grow() is O(logn α). Since
the number of iterations of the loop while (Listing:
3, Lines: 14 - 23) depends on the interferences with
the concurrently operating delete threads, whilst the
number of iterations of while (Listing: 3, Lines: 25 40) is limited by the height h = logn α of the tree,
then the overall sequential running time of insert() is
O(logn α).
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

grow(key)
nAP ← createAP()
nAP.height ← dlogd key e
nAP.size ← dcAP.hight
cAP ← ap;
topSize ← nAP.height - cAP.height
cl ← 0
while (cl < topSize)
cAH ← createAH()
cAH.summary ← 1n 0n−1 . . . 01
if cl = 0
nAP.root ← cAH
else
pAH.array[0] ← cAH
if cl = topSize - 1
cAH.array[0] ← cAP.root
pAH ← cAH
return nAP

Listing 4: Array growing

The next method get(), similarly to insert(), first
retrieves the current snapshot of the dcvEB array
parameters (Listing: 5, Line: 60), then traverses the
structure down from the root to the leaf following
the subsequent level positions. The main difference
between get() in the dcvEB array and get() from the
An important routine used within the insert()
previous version of the structure [15] is that currently
method is grow(). It is responsible for extending the
the enabled bit in a summary does not guarantee
dcvEB array, when it is too small to hold an elethe existence of the corresponding lower level array
ment with the given key. Enlarging the array relies
holder. Hence, the additional check whether the next
on adding additional levels above the existing root so
AH is not actually nil is necessary (Listing: 5, Lines:
that the total height h of the dcvEB array tree in67 - 68). As can be seen, the sequential running time
creases. Hence, the dcvEB array becomes capacious
enough to encompass the key i.e. it requires nh > key.

of get() is determined by the loop (Listing: 5, Lines:
61 - 70) and is O(logn α).
59
60
61
62
63
64
65
66
67
68
69
70
71

get(key)
cAP ← ap; cAH ← cAP.root; cl ← 0;
while (cl < cAP.height)
lp ← lvlPos(cl, key)
if (0n 0n−1 . . . 0n−lp+1 1n−lp 0n−lp−1 . . . 01
AN Dbit cAH.summary) = 0
return nil
cAH ← cAH.array[lp]
if cAH = nil
return nil
cl++
end while
return (cAH.data, cAH.index)

Listing 5: Get method
Changes resulting from the introduction of dynamic memory allocation also affected the delete()
method. Since insert() is able to expand the top of the
dcvEB array tree and to generate missing lower level
AHs, then delete() needs to be able to trim the top of
the tree and to remove redundant nodes. The delete()
method implementation can be logically divided into
three stages: preparing a path towards a leaf, deleting
the leaf with the deletion propagation and cleaning,
and the dcvEB array top trimming. Like almost all
presented dynamic set methods, delete() also starts
from fetching the snapshot of the current dcvEB array parameters (Listing: 6, Lines: 73 - 74). Then, after
the creation of the two empty tables ahol and pos for
holding the path between the root and the node for
disposal, the method makePath is invoked (Listing:
6, Line: 77). The purpose of this method is to fill
these tables with the subsequent AH s and their positions along the way from the root to the leaf node
being removed according to the formula for lpk . During the iteration, similarly to in get(), the presence
of the child must be checked twice. Firstly, by checking a summary bit vector (Listing: 7, Lines: 87 - 88),
the second time by checking whether the retrieved
subsequent AH is not nil (Listing: 7, Line: 91). It
is assumed that the arguments of makePath are inout, which means that the changes made inside the
method are visible outside.

72
73
74
75
76
77
78
79
80
81
82
83

delete(key)
cAP ← ap; cAH ← cAP.root;
pAH ← nil; cl ← 0;
ahol ← makeEmptyArray(cAP.height)
pos ← makeEmptyArray(cAP.height)
makePath(key,cAP,cAH,pAH,cl,ahol,pos)
if (!is_filed(ahol,cAP.height)) then
return;
delIntern(key,cAP,cAH,pAH,cl,ahol,pos);
while (cAP != ap and rep < maxRep)
deleteClean(key); rep ← rep + 1;
topTrim();

Listing 6: Delete method

84
85
86
87
88
89
90
91
92
93

makePath(key,cAP,cAH,pAH,cl,ahol,pos)
while (cl < cAP.height)
lp ← lvlPos(cl, key);
if (0n . . . 0n−lp+1 1n−lp 0n−lp−1 . . . 01 AN Dbit
cAH.summary) = 0 then break;
pos[cl] ← lp; ahol[cl] ← cAH;
pAH ← cAH; cAH ← cAH.array[lp];
if (cAH = nil) then break;
cl ← cl + 1;
end while

Listing 7: makePath - delete auxiliary method
The second and the major subroutine of delete()
is delIntern(). In terms of the synchronization structure, it is similar to the original delete() method presented in [15]. The need, however, for effective array holder removal caused the necessity to introduce
a few new elements into the code of the algorithm.
The delIntern() method is executed only if the array holder structure is correctly filled, which takes
place only if makePath() (Listing: 7) does not break
its while loop. Hence, at the very beginning of delIntern(), it is assumed that the variable pAH refers to
some AH from the last but one (cAP.height-1 ) level,
whilst cAH points at the element from the last level
containing pairs (index, data).

Thus, after locking appropriate array holders (Listing: 8, Line: 95), the stored data are overwritten by nil
(Listing: 8, Line: 96). Afterwords delIntern() begins
its arduous journey towards the root iterating within
It is noteworthy that makePath may not contain a the loop while (Listing: 8, Lines: 98 - 121). It starts
complete path between the root and the leaf designed from the last but one level (Listing: 8, Line: 100).
to be disposed. This happens when there is no such First, it sets an appropriate bit in cAH’s summary to
path i.e. because the desired element has just been re- 0 (Listing: 8, Line: 102). Therefore, the data was logmoved. In such a case the procedure stops, and leaves ically removed from the structure (data field is set to
the arrays ahol and pos partially filled. In the case of nil, index to −1, and AH is not by the parent’s sumdelete(), not entirely filled arrays indicate that there mary), although an appropriate array holder still exis no element to delete (Listing: 6, Line: 78). Hence ists. Such an array holder will be physically removed
the method can finalize its operation (Listing: 6, Line: only when the whole cAH’s summary is 0 (Listing: 8,
Line: 107). Otherwise, if cAH’s summary is not 0, the
79).

previously locked nodes are released and the method
exits (Listing: 8, Lines: 103 - 105).
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

delIntern(key,cAP,cAH,pAH,cl,ahol,pos)
pAH.wLock(); cAH.wLock();
cAH.data ← nil; cAH.index ← −1;
pAH ← cAH;
while (cl ≥ 0)
cAH ← ahol[cl]; lp ← pos[cl];
if (cl = cAP.height - 1)
cAH.summary ← 1n . . . 0n−lp . . . 11
AN Dbit cAH.summary;
if (cAH.summary 6= 0)
pAH.wUnlock(); cAH.wUnlock();
return;
else
cAH.array ← {nil0 , . . . , niln−1 };
else
cAH.wLock(); pAH.wLock();
isSummaryAltered ← false
if (pAH.summary = 0)
cAH.summary ← 1n . . . 0n−lp . . . 11
AN Dbit pAH.summary;
isSummaryAltered ← true
if (cAH.summary = 0)
cAH.array ← {nil0 , . . . , niln−1 }
cAH.wUnlock(); pAH.wUnlock();
if (not isSummaryAltered)
return;
cl ← cl - 1; pAH ← cAH;
end while

Listing 8: Delete internal - delete auxiliary
method
This, "my brother keeps me alive", lazy strategy
aims to reduce the amount of memory allocation performed during the course of the algorithm. If delIntern() processes the element on the level cAP.height
−2 or higher, then it first locks the current and previous AH’s node, and next alters the cAH summary by
removing the bit corresponding to the removed children (Listing: 8, Line: 113). As in the previous case, if
cAH summary is 0 then the child node is dereferenced
(Listing: 8, Lines: 115 - 116). Then, after unlocking
cAH and pAH (Listing: 8, Line: 117) and checking
whether it makes sense to propagate a delete action
towards the root (Listing: 8, Lines: 118 - 119) the else
block ends. At the end of the procedure the variables
cl (current level) and pAH (previous array holder)
are updated (Listing: 8, Line: 120).
The next subroutine of delete() is deleteClean(). It
is called from delete() just after delIntern() (Listing:
6, Lines: 81 - 82). The main reason for which it is
introduced is the danger of not removing all the required AH when the delete action interferes with the
insert action. The idea of deleteClean() implementation and further explanations are in Subsection 5.1.

122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

topTrim()
cAP ← ap;
while (cAP.root.summary = 1n 0n−1 . . . 01 )
if (cAP.height = 1) then break;
nAP ← createAP();
nAP.height ← cAP.height - 1;
nAP.size ← dnAP.hight ;
theLonelyChild ←
cAP.root.array[0];
if (theLonelyChild = nil) then
return nil;
nAP.root ← theLonelyChild;
apLock.wLock(); cAP.root.wLock();
if (cAP.root.summary = 1n 0n−1 . . . 01 )
then CAS(ap,cAP,nAP);
cAP.root.wUnlock();apLock.wUnlock();
cAP ← ap;

Listing 9: TopTrim - delete auxiliary method
The purpose of topTrim() - the last auxiliary
method involved in delete() implementation is to cut
the top of the dcvEB array tree if it is reduced to
the list (Listing: 9). It is possible that, after the internalDelete() call, the root and a few nodes below
have only one, the leftmost, child. In such a case, the
sequence of such vertices starting from the root needs
to be safely removed. The topTrim() reduces the top
of the tree iteratively. It removes only one node (root)
in every course of the loop while (Listing: 9, Lines:
124 - 138). If the loop while condition is met, i.e. the
root has only one child at the leftmost cell in the
array, then the new AP candidate is prepared (Listing: 9, Lines: 126 - 128). Next the “lonely” child is
retrieved (Listing: 9, Line: 130). If it is not nil (it
might be nil due to another delete thread), it is promoted to a new root candidate of the whole dcvEB
array tree (Listing: 9, Line: 133). Finally, if the array properties are not changed during the course of
the topTrim routine (i.e. the assertion that the root
has only one leftmost child still holds) the newly prepared nAP becomes the main array parameters reference. The topTrim() method does not trim the trees
shallower than the ones composed of the root and
leaves (Listing: 9, Line: 125). The CAS call (Listing:
9, Line: 136) responsible for the ArrayParam altering
is guarded by two locks (Listing: 9, Line: 134). They
prevent a situation in which insert() adds the new
element into the subtree rooted in the node, which
is subject to removal by topTrim(). The sequential
running time of delete() depends on the complexity
of their subroutines. The first of them makePath()
(Listing: 7) comprises one loop while. Due to the loop
condition (Listing: 7, Line: 85) it is clear that the sequential running time of makePath() is limited by the
height of the tree i.e. O(logn α). The methods delIn-

tern(), deleteClean() and topTrim() also need at most
to visit all the nodes on a single path between the root
and a leaf. Therefore, their sequential running time is
O(logn α). Furthermore, if only one thread is up and
running, the loop while (Listing: 6, Line: 81) executes
only one. Thus the overall sequential running time of
delete() equals the maximum of the running time of
all their subcomponents, and is O(logn α).
The pseudo code of the last method successor()
was divided into two parts. The first (Listing: 10)
one is responsible for the attempt to reach the leaf
AH holding the data indexed by a key. If such a
leaf exists, it will be returned as its own successor.
The second part (Listing: 11) contains a loop which
consists of two other loops, where the first internal
loop is responsible for traversing the dcvEB array
tree up, whilst the second traverses the tree down.
Such a structure of the code in the second part corresponds to the successor()’s searching strategy. In
other words, first the method tries to go a little bit
higher to check where a successor leaf could be (the
first internal loop), then tries to go towards the leaf
in order to retrieve the stored data and key (the second internal loop). Of course, sometimes during the
gliding down the tree the successor candidate might
be removed. In such a case, the second loop must be
aborted and the method once again starts to follow
up the tree in order to find another potential successor candidate.
139
140
141
142
143
144
145
146
147
148
149
150
151

successor(key)
cAP ← ap; cAH ← cAP.root;
if (cAH.summary = 0) then return nil;
pAH ← nil; cl ← 0;
ahol ← makeEmptyArray(cAP.height);
pos ← makeEmptyArray(cAP.height);
makePath(key,cAP,cAH,pAH,cl,ahol,pos);
if (cl = cAP.height) then
cl ← cl - 1;
if (cAH 6= nil) then
data ← cAH.data; index ← cAH.index;
if (data 6= nil and index 6= -1)
then return pair;

Listing 10: Successor method (part 1)
At the very beginning, the successor() sets its own
local copy of the array parameters (Listing: 10, Line:
140), then it prepares a pair of holders, cAH and
pAH, used to traverse the structure. Then the cl variable indicating the visited level and two other variables, ahol and pos, referring to arrays holding AH s
and their level positions along the path from the root
to the visited node, are defined (Listing: 10, Lines: 140
- 144). All the newly introduced variables, including
cAH, pAH, cl, ahol and pos are initiated within the
makePath() auxiliary method. If makePath() reaches

the leaf level, ( the condition cl = cAP.height is true,
see Fig. 1) this means that the element indexed by the
key exists. Hence, if only the successor() procedure
manages to fetch the stored data, then the appropriate (data, key) pair is returned by the method (Listing: 10, Lines: 146 - 151). Of course, makePath() may
not reach the leaf level (the condition cl = cAP.height
does not hold) or even if the leaf is reached, its removal might start before the leaf data are extracted
(one of the following three conditions is true: cAH
= nil, data = nil, index = -1 ). In such a case, the
method control goes to the while loop (Listing: 11)
and the algorithm starts to explore other successor
candidates.
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

mark: while(true)
while (cl ≥ 0)
cAH ← ahol[cl];lp ← pos[cl];
tmpSum = 0n . . . 0n−lp 1n−lp+1 . . . 11
AN Dbit cAH.summary;
if (tmpSum = 0) then cl ← cl - 1;
else break;
end while
if (cl = -1) then return nil;
while(true)
if (tmpSum = 0) then
cl ← cl - 1; goto mark;
bp ← mostLeftBitPos(tmpSum);
lp ← lvlPos(pb); pos[cl] ← lp;
ahol[cl]←cAH;cAH←cAH.array[lp];
if (cAH = nil)
cl ← cl - 1; goto mark;
tmpSum ← cAH.summary; cl ← cl + 1;
if (cAP.height = cl) then break;
end while
data ← cAH.data; index ← cAH.index;
if (data 6= nil and index 6= -1) then
return (data, index);
else
cl ← cl - 1; goto mark;
end while;

Listing 11: Successor method (part 2)
The second part of the successor() method (Listing: 11) is responsible for traversing the structure up
and down looking for the next successor candidate.
The first inner loop (Listing: 11, Lines: 153 - 159)
is responsible for traversing the structure up until
the node with the non-empty subtree further to the
right is found or the root level is achieved, i.e. cl =
0. At the very beginning, it initiates cAH and lp using the values stored in pos and ahol (Listing: 11,
Line: 154). Then, it prepares the tmpSum vector so
that the value tmpSum is non-zero, only if there are
some bits enabled to the right of the lp position (Listing: 11, Lines: 155 - 156). In other words, the tmpSum is non zero only if there exists some successor

candidate in some of the current level’s subtree. In
such a case, the first loop is interrupted (Listing: 11,
Line: 158) and the control goes to the if condition
(Listing: 11, Line: 160), otherwise the level variable
cl is decremented and the first inner loop starts to
examine the current node’s parent (Listing: 11, Line:
157). If the condition cl = -1 is true, then there are
no successors in the dcvEB array and the procedure
returns nil (Listing: 11, Line: 160). The second inner loop (Listing: 11, Lines: 161 - 171) starts from
checking the bit vector tmpSum. The 0 = tmpSum
indicates that the successor candidate is removed after it has been checked (Listing: 11, Line: 162), hence
the loop is interrupted (Listing: 11, Line: 163), and
the control goes back to the beginning of the outer
loop while (Listing: 11, Line: 152). If the successor is
still there, the leftmost bit of tmpSum corresponding
to the position of the first non-empty subtree is calculated (Listing: 11, Line: 164). Then, the position
in the bit vector bp to the level position lp is transformed (Listing: 11, Line: 165), and the variables pos,
ahol and cAH are appropriately updated (Listing: 11,
Lines: 165 - 166). In particular , the value of cAH is
set to the subtree reference. Hence, if the only element in the subtree was a successor candidate, and
unfortunately it was removed during the course of
the second inner loop, then the value of cAH is nil
(Line: 167). In such a case, the algorithm must go
up the tree and look for another successor candidate
i.e. go to the beginning of the outer loop while (Listing: 11, Line: 168). Otherwise, the tmpSum is set to
cAH ’s bit vector (Line: 169) and the current level cl
is incremented. The second inner loop ends when the
current level reaches the leaf level (Listing: 11, Line:
170). At the leaf level, the algorithm tries to fetch
the key and data and, if it succeeds, the successor element is returned. If not, the control goes back to the
beginning of the outer loop while, and the algorithm
begins the journey up the tree.
In the sequential case the successor() method first
traverses the dcvEB array down (Listing: 10, Line:
145), next a bit up (Listing: 11, Lines: 153 - 159), and
then down again (Listing: 11, Lines: 161 - 177). Thus,
during their execution, the successor() method visits
the nodes of the dcvEB array at most 3log˙n α times.
Thus, their sequential running time is O(3 · logn α) =
O(logn α).

5
5.1

Concurrency and dynamism
Expanding and trimming

It is widely accepted that the trees in computer science are usually drawn with the root at the top, and

grow downwards instead of upwards. Donald Knuth
in [14] writes: "There is an overwhelming tendency
to make hand-drawn charts grow downwards instead
of upward (...) even the word ’subtree’ (as opposed
to ’supertree’) tends to connote a downward relationship". In this context, the solution adopted in the
dcvEB array might be a little unintuitive3 . The tree
of arrays, which in fact is the dcvEB array, on the one
hand preserves the rule of the-root-at-the-top, on the
other hand, it grows in both directions: downwards
and upwards. The dcvEB array’s tree grows downwards if the key of the inserted element is smaller
than its current maximal capacity, and upwards if
the key of the inserted element exceeds the current
capacity and the tree needs to be expanded. Adding
a new root above the current one makes the old tree
the leftmost subtree of the new root. Hence, the new
root summary, just after tree expansion, has the leftmost bit enabled. Inserting the new element, which
was the cause of expansion, enables another bit in
the root summary. The tree expansion increases the
size of the dcvEB array (understood as the range of
the allowable keys) exponentially. Hence, adding k
levels above the current root increases the size of a
dcvEB array Cnew = Cold · nk times, where n is a
summary size, Cold - the old capacity and Cnew - the
new capacity. The dcvEB array tree expansion does
not reorganize the old tree. Hence, all the existing elements remain in place. Because the structure of the
subtree does not change the threads, which started to
use the subtree before expansion, we do not have to
worry about the changed size of the tree. The variable
size of the tree does not affect the method of determining the position of an element with the given key
in a tree. Following the changed size of a dcvEB array (the height of the tree), the algorithm also adapts
(h)
to the new size of the array. Hence, lpk - the level
position computed for the tree of height h and the
(h+r)
fixed key i0 < nh − 1 equals lpk+r - the level position computed after the dcvEB array tree expansion
of r levels, where the level position lp at the newly
added levels is 0 i.e. lp0 = . . . = lpr−1 = 0. Since the
expansion does not change the structure of the existing tree, there is no reason to make any additional
blocking synchronization mechanisms due to the expansion itself. The threads that start working before
expansion also finish their work within the old structure using the synchronization scheme as is presented
in [15]. The new threads that start working after the
3

Of course, in Mathematics, a “tree” is just an acyclic
and connected graph. Thus, it can expand in all directions. From this perspective, adding a new root over
the old one is not unusual.

expansion use the new structure, however, within the
subtree resulting from the previous tree, they synchronize with the “old” threads using the locks available within the subtree. Hence, the main role of synchronization in the case of the tree expansion is to
provide the new threads with the latest consistent
information about the dcvEB array tree. For this reason, the vital dcvEB array information, such as root
reference, height, and the associated size, are kept
in the atomic global variable ap (ArrayParam structure). That is why every interface method starts from
fetching the current array parameters (Listings: 3, 5,
6, 10 Lines: 12, 60, 73, 140). The dcvEB array expansion is implemented as part of the insert() implementation (Listing: 3). The auxiliary method grow() first
prepares the new top of the dcvEB array tree, then
the insert() method tries to atomically replace the
current ArrayParam set with the new one prepared
by grow(). The insert() method managed to set the
new top of the tree. The gray triangle represents the
tree before expansion.
Most methods do not interfere with insert() as regards extending the tree. This group includes queries
such as get(), successor(), predecessor(), min() and
max(). If the expansion occurs after they fetch their
own AP copy, the result they return will just not
take into account the new elements, for which the
key is greater than the size of the structure before
expansion. Hence, the synchronization with respect
to these methods can be limited to the nonblocking
operations on atomic variables. Unfortunately, in the
case of delete() a dcvEB array tree expansion would
be easily disrupted by the trimming procedure.
It is possible that, if there were no additional
synchronization mechanism a global read-write lock
apLock, (Listings: 3, 9). In the absence of this mechanism it is possible that between fetching the new array parameters (Listing: 3, Line: 12) and read-locking
the root (Listing: 3, Line: 13) the top of the array
would be trimmed. In such a case, insert() would use
the root AH that was in fact removed from the tree,
thus an insertion would be ineffective. Hence, the aim
of the lock combinations (apLock read lock and AH
read lock) used in both insert() and topTrim() is to
prevent removal of the node when it is examined due
to the insertion procedure. Both locks support readerwriter semantics. Hence, many different inserts but
only one delete can be handled at the same time.
Calling delete() during the expansion of the tree
might also cause another problem that may lead (if
not handled) in the long time perspective to performance deterioration. Namely, delete() first goes towards the leaf, then removes it, and next it tries to
propagate the delete information to the higher lev-

els of the tree. If the tree is extended after delete()
fetches the current AP snapshot (Listing: 6, Line:
73), then the highest reachable node for delete is the
root of the tree before expansion. Hence, delIntern()
is not able to propagate delete information up to the
new root and ends earlier within a subtree. In such
a case, delete() may leave the path starting from the
new root (and ending in the old root), which is composed of nodes containing false information indicating
that their subtrees are non-empty. This issue can be
solved in a few different ways. One of them could be
to relax the delete operation and use query methods
like get() or successor() to clean up the tree. Another, proposed in this article, is to repeat deleteClean() (Listing: 6, Line: 82) - the procedure, which
discovers an undeleted path’s residues and removes
them when needed. The method deleteClean() is very
similar in implementation to delete() itself. However,
other than delete(), it does not remove the element,
but instead it tries to confirm that there is no element
with the given key in the tree. If there is no such element, but there are some AHs in the tree leading
to them and only to them, then such nodes are removed and appropriate bits are disabled. The implementation of the functionality of deleteClean() boils
down to small changes in the code of the makePath()
and delIntern() methods. Hence, taking into account
that the Java code of the presented solution is publicly available, the pseudocode of deleteClean() is not
thoroughly analyzed in the paper. An optimal number of deleteClean() calls is discussed later, when the
progress condition is considered.
As the dcvEB array grows upwards, it is trimmed
from the top. The trimming routine is located at the
end of the delete() method. It checks whether the current root has only one child at position 0, and if so,
it attempts to remove the root. Hence, the root can
be trimmed if the maximal element stored within the
structure is smaller than size/n, where size means
the current size of the structure (the largest key that
can be inserted into the dcvEB array without triggering its extension), and n is the length of the summary
bit vector. Trimming is implemented as the inverse
of expansion. The only difference is that the insert()
method tries to insert all the required nodes at once,
whilst delete() trims elements one by one. The root
element after trimming is removed from the tree, and
its only child is promoted to the new root element.
The trimming mechanism is completely neutral for
get(). This is partly a merit of Java, where, of course,
nodes can be detached from the tree, but they are
not destroyed, just as in C++ or C. Hence, as only
get() obtains its own reference to the AP structure
(Listing: 5, Line: 60), and thus, the reference to the

root, then regardless of whether any visited node is
detached from the tree, get() may always continue
traversing the structure. Similarly, the other query
methods are not affected by the trimming. For instance, successor(), when it obtains the root snapshot, creates the path snapshot from the root to the
lowest existing node on the path leading to the element with the given key (Listing: 10, Line: 145).
The path is kept in the two auxiliary arrays ahol and
pos. Thus, if some of the vertices stored in ahol are
removed from the tree, they are not removed from
ahol, thus the successor() algorithm still has access
to them. Hence, if there is a need to traverse the
tree upwards, successor() is always able to do that.
On the other hand, if some of the visited nodes have
been actually removed from the tree, this also implies
that there are no further successor candidates available, and successor() may finish its task earlier. For
the same reason, trimming does not affect delete() either. Since, during the passage down, delete() creates
its own ahol array, it has no problems with propagation of the deletion status up. Of course, if some of
the nodes referenced in ahol are removed (trimmed)
from the tree, delete() might stop status propagation
immediately after encountering such a node. This observation, as well as an analogous situation in the case
of the successor search, can also be a subject for further optimization.
Two or more different topTrim() calls are synchronized with each other by using apLock writer lock. On
the other hand, for the purpose of mutual topTrim()
synchronization, a nonblocking mechanism seems to
be sufficient. Hence, the apLock usage in this place
is caused only by the necessity of protecting insert()
against trimming. The writer locks used here (Listing: 9 Line: 134) provide topTrim() exclusive access
to the top of the structure, which could be potentially dangerous for the concurrent performance of
the structure. However, in practice, the need to trim
the top of the dcvEB array tree is not frequent, thus
with the performance issue in mind, it is better first
to check whether the trimming is needed (Listing: 9,
Lines: 124 - 125), and if so, lock the top of the structure, and before trimming, check once again (Listing: 9, Line: 135) whether the trimming is actually
needed.

nodes. In the presented solution, it is assumed (due
to the desire to avoid separate handling of the uninitialized root case) that there is always at least one
node within the tree. This means that the root node
exists, even if there are no other elements in the tree.
The insert() method creates the new element when it
turns out that there is no AH at the specified position
(Listing: 3, Line: 34). Adding a child AH into the parent array may interfere with another insert activity.
Hence, to avoid overwriting one AH by another AH,
the parent’s array update is implemented as a CAS
instruction (Listing: 3, 35). Then, if the first thread
wins and successfully updates the parent AH’s array, the second thread just retrieves the winning AH
(Listing: 3, Line: 36) and continues the insertion procedure with them. It is worth noting that the whole
operation is protected in the same way as the summary bit-vector update, i.e. by the AH’s reader lock
(Listing: 3, Line: 28). Thus, there is no risk that the
newly updated AH would be removed by delete() (after execution Line: 35), and insert() could fetch a nil
value (Listing: 3, Line: 36). A more detailed analysis
of the synchronization scheme used here can be found
in [15].

Since operations related to the memory allocation
and deallocation involve operating system function
call, they are usually time-consuming. Therefore, for
the purpose of this algorithm a kind of lazy approach
has been adopted. Therefore, the AHs are not removed from the tree immediately after they become
empty (leaves are considered empty when the fields’
data and index are set to nil, whilst other nodes are
empty if their summary bit-vector equals 0). Instead,
if some non-leaf node becomes empty, it actually removes all its children AH s from the memory. Therefore, the operation of deleting elements can be considered as composed of two phases: the first one logical removing - when data and index are set to nil
or appropriate position in the parent’s summary bitvector is zeroed, and the second one - physical removing - when the AH’s reference is physically removed
from the parent’s array and the AH record is actually removed from the memory. Since the AH record
5.2 Dynamic adding and removing elements is physically removed (Listing: 8, Lines: 107 - 116)
only when it has no siblings, the physical removing is
In addition to extending and trimming the root, the likely to occur less frequently than the logical removdcvEB array tree also adds and removes elements be- ing. Both logical and physical removing use the same
low the root. This is similar to the behaviour known synchronization scheme as presented in [15]. Thus,
from the classical trees, where inserting or removing the modified elements are always exclusively held by
data causes the creation or deletion of appropriate the thread performing deletion.

5.3

Successor search strategy

The working scheme of the successor() method is
composed of three phases. During the first one (Listing: 7), the algorithm goes as far as possible towards
the element indexed by the given key. If the element
exists, it returns them. If not, the control goes to the
second phase (Listing: 11, Lines: 153 - 159) in which
the algorithm retracts until the next nonempty subtree is found. Then, during the third phase (Listing:
11, Lines: 161 - 171) the algorithm goes down towards
the element which is minimal within the detected
nonempty subtree. If the third phase fails (the desired
element can be removed in the meantime), then the
control goes to the second phase and the algorithm
starts to go upwards. The second and third phases
are repeated as many times as needed. The main difference in comparison with [15] is that, in the case
of the necessity to repeat the second and the third
phase, the second phase starts exactly from the same
point where the third phase has been stopped. Thus,
with each search failure the successor() method tries
to look further for the next possible successor candidate. Therefore, the number of repetitions of phase
two and three is naturally limited by the size of the
dcvEB array.
Thanks to the adopted strategy, the successor element will always be found if it remains in a dcvEB
array long enough. Thus, let key be the index of element x whose successor we are looking for, and let
succ be the index of y - some successor of x, such that
key < succ. In such a case, if during processing the
second part of the successor() method (Listing: 11) y
is not removed from the dcvEB array, then the maximal possible key of the next successor of x is succ.
In other words, when the search algorithm detects
the subtree (phase 2) containing y as the minimal
element, then the algorithm seamlessly (i.e. without
failures) reaches y. The current algorithm always returns the successor if it is available during the whole
course of the successor() method. In the previous implementation [15] there was a small chance that the
successor would not be found and successor() would
return nil. On the other hand, the previous implementation limits the number of failures that can be
safely handled by the successor(), whilst currently,
the allowable number of failures is limited only by the
current size of the structure. This raises the question
of the actual concurrent running time of the current
successor() implementation. As will be shown in the
next section (Sec. 5.4), the concurrent running time
estimation is worse than in the sequential case. Fortunately, the tests carried out indicate rather high overall efficiency of the structure rather than its suscep-

tibility to the interferences and thereby performance
deterioration.

5.4

Successor search concurrent running
time

The sequential running time of all the methods presented in the article is the same as in [15], and equals
O(logn α), where n is the size of the summary bit
vector, whilst α is the current size of the dcvEB
array. The detailed arguments presented previously,
with only minor amendments, also fit the dcvEB array. The concurrent running time estimation is much
more complex, because, besides the code structure,
different kinds of concurrent interactions, such as
blocking synchronization, need to be taken into account. Fortunately, some of the dcvEB array methods
discussed in this article use only non-blocking synchronization mechanisms. These methods are: get()
and successor(). Since the get() method only checks
the presence of one, well-defined element in the array, if the check fails (no matter when the element
has been removed), it returns nil. Hence, its concurrent running time estimation is not affected by the
interferences with other concurrently executed methods. Thus, the concurrent running time of get() does
not change and is O(logn α).
In contrast, in the case of successor(), despite the
non-blocking synchronization, every deletion of a successor candidate may increase the overall concurrent
running time of the method. In the worst case scenario, the value of the successor() method is called for
input argument 0, and the next greater element has
the key 1. Then, if the element indexed by 1 is deleted
just after successor() reaches the end of the loop
(Listing: 11, Line: 159), then the deletion has been
discovered (Listing: 11, Line: 173) and the next iteration will be initiated (Listing: 11, Line: 176). This
may lead to alteration of the subsequent removal and
search attempts. The worst case scenario described
above may occur α − 1 times, forcing the successor()
method to check every single position in the dcvEB
array. Hence, in the worst case, the concurrent running time of successor() is O(α). A natural question
arises whether this slightly disappointing result can
be improved. The easiest solution (but without any
guarantee that the successor will be found even if
it exists in the tree) is to limit the possible number
of iterations of phases 2 and 3 (the loop while Listing: 11, Lines: 152 - 177) by some empirically chosen
constant. In such a case, the user must accept that
(probably) very rarely the successor() method would

fail and never return the correct value4 . Despite the
moderately good theoretical concurrent running time
estimation, the current solution performs very well in
practice. Conducted tests for the random data (Section 6) seem to suggest that the successor() average
running time is closer to O(logn α) than O(α).
There are also some theoretical arguments that
may indicate in favour of O(logn α). For simplicity,
let us assume that the dcvEB array is full (without nil values) and every deleted element is reinserted into the table in a short time after removal. Hence, without making a big mistake, it can
be assumed that the successor of sk is sk+1 for
k = 1, . . . , m. Thus, the collision may happen, if at
roughly the same time, successor() processes sk and
delete() removes sk+1 . Assuming that both: successor() and delete() process m randomly selected indices: (s1 , . . . , sm ) and (d1 , . . . , dm ) at the same and
equal time intervals, the likelihood5 of the simultaneous execution of delete(dr ) and successor(sk )
where dr = sk + 1 is 1/α. Hence, the execution of
m consecutive successor() and delete() calls may result in m/α collisions. Since every collision entails
additional tree traversal by successor(), the total expected concurrent running time of m successor() calls
is T (α, m) = mO(logn α) + (m/α)O(logn α). Thus,
the amortized concurrent running time of a single
successor() call is T (α, m)/m = (1 + 1/α)O(logn α).
In most cases α is large, for that it is safe to assume that T (α, m)/m ≈ O(logn α). Similarly, the
amortized concurrent running time of a single successor call for h delete threads running in parallel
is T (α, m)/m = (1 + h/α)O(logn α). Thus, as long
as h is significantly smaller than α it still holds that
T (α, m)/m ≈ O(logn α). At the expense of increasing
the complexity, the above reasoning can be adapted
to the successor() algorithm as presented in the article.
5.5

Correctness

As with other concurrent data structures, the dcvEB
array should be considered while bearing in mind
the concurrent objects specificity[18,11]. In particu4

5

In fact, this approach provides a “limited warranty” to
find a successor, i.e. if the iteration number is limited
by e.g. 1000 and the successor() method is called with
α on its input, then (even in the worst case scenario)
there is a guarantee that if the successor exists during
the successor() call, then it will be found if only β −α ≤
1000, where β is the key of successor.
It is enough to assume that at the certain moment of
time dr is fixed, whilst the index sk is selected as one
out of 1, . . . , N .

lar, correctness is discussed in terms of data consistency (quiescent and sequential), linearizability [12],
and the progress condition. Although these problems
were already discussed in [15], some issues need to
be revisited due to the changes made to the original idea. One of them is linearizability. The proposed
enhancements are of two types: the first group concerns growing and shrinking the dcvEB array tree,
whilst the second concerns allocation and deallocation memory for AHs. Bearing in mind the principle [11] according to which every linearizable method
call should appear to take effect instantaneously at
some moment between its invocation and response,
it is clear that the first group of enhancements do
not affect linearizability property. In the case of insert() and delete(), natural linearization points are
unlock calls just after setting the values into the leaf
AH (Listing: 3, Line: 40), and (Listing: 8, Lines: 104 117). Since the code responsible for the array growth
(inserting) or trimming (deleting) is not directly involved in setting or unsetting the new values in AHs,
then the linearizability property is not affected by the
first group of enhancements. The second group of enhancements do not change the logic of inserting and
deleting elements either. This is because they relate
to the memory management rather than deleting the
elements (elements cease to be available to the user
at the same time as previously, i.e. the element is considered to be deleted when its value in the leaf AH
is overwritten by nil (Listing: 8, Line: 96)). In other
words, despite the fact the memory is not immediately freed after the delete() call (due to the lazy
approach to the memory deallocation), the delete()
method logically takes effect immediately.
Similarly, all the query methods, including get()
and successor(), are also linearizable i.e. they take
effect before the query value is returned. Therefore,
the dcvEB array is linearizable, hence, it is also quiescently and sequentially consistent [11].
Another important criterion of concurrent object
correctness is the progress condition. As has been
shown in [15], to preserve the progress condition the
fair locking strategy needs to be used. Since the general synchronization scheme remains unchanged, a
potential risk to the progress condition may come
from the introduced enhancements. Especially dangerous are those loops in which fulfillment of the stop
condition is not obvious. The first such loop is responsible for the dcvEB array growing (Listing: 14, Lines:
14 - 23). The loop executes until the size of the array
cAP.size is greater than the requested key. To prove
that the iteration of the loop will end, note first that
in every turn of the loop cAP.size can only grow.
That is because cAP.root is reader-locked (Listing:

3, Line: 13), hence the method delete() is not able
to trim the dcvEB array in the meantime. Secondly,
let us note that in every turn of the loop cAP.height
increases by at least one. Although within the current loop insert() tries to increase the array as far
as necessary, it is possible that it loses the race with
another thread, which increases the array height only
by one.
Another important loop with an unobvious endcondition is connected with the cleaning after deletion
(Listing: 6. Lines: 81 - 82). Although the number of
possible iterations is limited by the maxRep constant,
the question arises as to how many iterations are sufficient, i.e. how large the maxRep constant should be.
To answer this question, let us recall that the loop is
introduced to prevent incomplete deletion, which may
happen if, during the element removal, the tree is expanded up by the insert() method. In such a case,
since delete() knows only the root before expansion,
then it is able to propagate the delete information
only up to this old root. Hence, if some nodes placed
above the old root also need to be removed, the solution proposes a re-run of the deleteClean() method.
It starts from the new root and checks whether for
all the nodes on the path from the (new) root and
the requested element, information contained in AH’s
fields summary and AH’s array are mutually consistent. Hence, the question about the optimal value of
maxRep (Listing: 6, Line: 81) is the question about
how many times in a row there may be a situation
that the dcvEB array tree will be expanding up when
the delIntern() or deleteClean() operations are ongoing. The answer depends on the domain of the array’s
key. For instance, if the array key is Java’s Integer 6 ,
then assuming the length of the bit-vector as 64, the
height of the dcvEB array tree that could hold an object with the key
 equal to themaximal representable
integer is 6 = log64 (231 −
 1) . For Java’s
 Long, the
sufficient height is 11 = log64 (263 − 1) . Hence, for
an array indexed by Java’s Integer, it is enough to set
maxRep to 6, or to 11 if an array is indexed by Java’s
Long. Of course, the exact value of maxRep depends
on the specific data types and hardware platform and
needs to be re-calculated for every specific implementation.
There is also one “hidden” loop, mentioned in [15],
which is not explicitly shown in pseudo-code, although it is important for practical implementation.
This loop is connected with atomic update of the
summary bit-vector within the insert() method (Listing: 3, Line: 31). Since, in most of the program6

ming languages including Java, bit operations are not
atomic, this update has to be implemented according
to the scheme: atomic read, modify, atomic compare
and set (Listing: 12).
178
179
180
181
182
183
184
185
186

while(true)
s ← cAH.summary;
if 0n 0n−1 . . . 0n−lp+1 1n−lp 0n−lp−1 . . . 01
AN Dbit s > 0
break;
if CAS(cAH.summary, s, s ORbit
0n 0n−1 . . . 0n−lp+1 1n−lp 0n−lp−1 . . . 01 )
break;
end

Listing 12: Atomic bit-vector update scheme
In order to prove that the bit-vector update scheme
presented above meets the progress condition, it is
necessary to note that cAH is reader-locked within
the insert() method. Thus, the only concurrent modifications coming from other threads that may occur
within the code (Listing: 12, Lines: 179 - 184) may
enable another bit in cAH.summary (but not disable
them). Since cAH.summary is modified (Listing: 12,
Line: 184) only if the requested bit is not enabled
(Listing: 12, Line: 182) then the CAS instruction may
fail in the worst case n times in a row, where n is
the size of the bit vector. So, at most after n iterations cAH.summary contains only enabled bits, thus
the result of the if condition (Listing: 12, Lines: 180
- 181) is always true. As a result, at most after n
iterations the loop is stopped. Hence, the progress
condition is preserved.

6

Experimental results

The experimental implementation of the test application together with the dcvEB array was written in
Java 7 and has been tested on an isolated test station Intel R CoreTM i7-3930K (6 cores, 12 threads,
3.8 GHz) processor with 8 GB of operating memory.
As in the case of the cvEB array, the results achieved
by its successor, the dcvEB array, are very promising. In many cases, the new structure turns out to be
faster than the compared alternatives. Of course, the
presented results are indicative and do not pretend
to be a ranking or review.
Since one of the advantages of the dcvEB array is to
support all the dynamic set’s methods mentioned in
[5, p. 230], one of the major challenges was to find an
appropriate concurrent dynamic set implementation,
which in addition to the standard get(), delete() and
insert() also provides successor() and predecessor().
The maximal integer and the long value in Java are An experimental implementation of the dcvEB array
has been written in Java. Since sometimes even small
M AX_IN T = 231 − 1, M AX_LON G = 263 − 1.

implementation details may affect the overall application performance, it was equally important to find
such dynamic set solutions written in Java that have
been identified by the authors as reference solutions.
Besides the dcvEB array, SnapTree Map [3], ConcurrentSkipListMap [11], non-blocking k-ary search
tree [4] and the synchronized java.util.TreeMap were
selected for the tests. The structure proposed by
Bronson et al. was selected for testing because of
the publicly available Java implementation provided
by the authors7 , and the presence of support for
successor() and predecessor() (via Java’s ConcurrentNavigableMap interface). The second structure,
ConcurrentSkipListMap, as it is implemented in recent Java distributions was a natural candidate for
comparison. In [10] Herlihy et al. wrote about ConcurrentSkipListMap that “(...) written by Doug Lea
based on work by Fraser and Harris [8] and released
as part of the JavaTM SE 6 platform, is the most
effective concurrent SkipList implementation that we
are aware of ”. The structure also implements successor() and predecessor(). Moreover, its inclusion into
the standard Java 6 platform indicates its optimality.
The non-blocking k-ary search tree (LockFree9ST
class8 ) [4] is a new efficient tree structure modeled on
[6] with the publicly available Java implementation.
It does not support the successor() and predecessor()
operations. Thus, for the test purposes, the successor operation has been implemented as the iterative
get() method calls for subsequent indices. The iteration ends when get() returns a non-null element or the
iteration reaches the largest possible index that can
be stored in the tree. In general, such an approach
is not effective, especially when the indices are distributed sparsely. Fortunately, during the tests the
indices are distributed fairly densely, thus, one may
expect that the performance deterioration resulting
from using this “naive” successor search strategy is
not too high.
In contrast to the ConcurrentSkipListMap structure, TreeMap is not even a concurrent object implementation. It is a globally synchronized sequential
structure, which is included into the tests in order to
show the difference between concurrent and sequential approaches.
In testing, there are four groups of threads: getters(), inserters(), removers(), and successors() 9 .
Each getter thread repeatedly calls the method get(),
inserter thread - insert() etc. Every thread has to perform the same z number of calls. The input parameter
7
8
9

key is randomly chosen from K ⊆ [0, . . . , x−1], where
x is a test run parameter. The number of threads in
groups is denoted by the letters g, i, r and s. For instance, g = 3, s = 5 means that in the given test
run three getters and five successor searchers are involved. Since the number of operations per thread
is fixed, the method performance is measured as an
execution time according to the principle, the lower
the value, the better the result. The execution time
is measured per thread, thus the time of the whole
test run is the arithmetic mean of the execution time
of each thread involved. In other words, the thread
execution time is the time needed by the thread to
make z calls of the given method.
As before, the first test (Fig. 2) measures how the
overall thread execution time grows, when the number of threads in each group is the same and increases. In the first test run there are four threads
g = i = r = s = 1, in the second one eight threads
g = i = r = s = 2 and, finally, in the last one 100
threads g = i = r = s = 25. Every thread performs
z = 500000 method calls. The results are averaged,
so that the bad test result of one method can be compensated by the good result of another method.
32499

25600

29563

6400
3587
1994	
  
1104

1600
400
100
4
tree map

12

20

28

skiplist map

36

44

52

dcvEB array

60

68

76

snap tree

84

92 100

k-ary search tree

Fig. 2. The dcvEB array overall performance test results
(g = i = r = s = 1, 2 . . . , 25, z = 500000 and m =
500000)

The best result has been achieved by the dcvEB array. Its averaged thread execution time gets 1104 ms.
and is approximately 1.8 times better than the second
result belonging to LockFree9ST. Both TreeMap and
SnapTree are far behind the two previous structures.
Such a structure of results demonstrates that the improvements made to the original cvEB array do not
affect its overall performance, and, on the contrary,
they seem to be even better than in [15].
In addition to the general performance comparison
of the structures, it is interesting to compare the performance of the particular methods. As in [15], the
https://github.com/nbronson/snaptree
results were averaged, so that the particular numwww.cs.utoronto.ca/∼tabrown/ksts/
Due to the symmetrical similarity with successor(), the ber in milliseconds denotes the average time required
predecessor() method has not been subject to testing. by a getter, an inserter, a deleter and a successor

searcher thread to execute half a million calls of the
given method.

10240

182769

180557

5120

4271

2560

28094	
  

43827	
  

46320	
  

169263

22268

20480

1280
512
281	
  
196

tree map

inserter
skiplist map

dcvEB array

getter
snap tree

deleter

successor
searcher

tree map

k-ary search tree

Fig. 3. The dcvEB array method performance test results
(g = i = r = s = 1, 2 . . . , 25, z = 500000 and m =
500000).

skiplist map

dcvEB array

snap tree

751000

676000

601000

526000

451000

376000

301000

226000

76000

151000

41000

26000

900

11000

600

80

10

160
300

1187	
  

1935

320

418

1162	
  

2030
444

937	
  

188
343

925	
  

1898

640
1468
1524

262144
131072
65536
32768
16384
8192
4096
2048
1024
512
256
128
64
32
16

45874	
  

miliseconds

miliseconds

k-ary search tree

Fig. 4. The dcvEB array performance test with a variable
key set (g = i = r = s = 2, z = 500000 and m =
10, 100, . . . , 776000).

achieved by LockFree9ST. It is almost two times better than ConcurrentSkipListMap, although it is worse
than the dcvEB array. As in the previous test, the results achieved by the other two structures are worse
than the results of the two ranking leaders.
The results achieved, although encouraging, have
to be interpreted carefully. In particular, it is difficult to prejudge the performance of the dcvEB array
relative to LockFree9ST, ConcurrentSkipListMap and
SnapTree. The last two of these structures have a very
powerful interface providing users with much more
functionality than the dcvEB array. Moreover, ConcurrentSkipListMap and LockFree9ST are not optimized to integer keys, hence, in return, they can handle any object as the key. LockFree9ST does not support natively the successor() and predecessor() operations. Hence, its actual results can be better than
those observed during the tests. Finally, SnapTree
adopts an optimistic locking strategy, which in some
cases can cause performance degradation. Despite the
better results achieved by the dcvEB array than by
the cvEB array [15] and the similar testing procedure, the performance of both structures cannot be
directly compared. The presented tests were carried
out on another (faster) machine than the previous
tests, the code of the testing procedure has been improved, and another (new) version of Java has been
used. It should also be noted that the dcvEB array
used in the experiment is “flatter” than the cvEB
array used in [15], since every non-leaf node in the
dcvEB array has 64 children, whilst in the cvEB array used in [15] it was less than half of that.

The obtained results (Fig. 3) show that the performance of each method varies. The very fast get()
method and quite fast delete() and successor() are
contrasted with the average insert(). The relationships between the results are similar to those of [15],
except insert(), which seems to be slower than before. The need for memory allocation, as expected, results in performance degradation. Fortunately, however, despite the decrease in performance, the insert()
method still has a comparable speed to the reference
ConcurrentSkipListMap. Noteworthy is the very good
result of insert() achieved by LockFree9ST. Other
than for the successor() method, the dcvEB array
turns out to be the fastest.
The dcvEB array concurrent processing efficiency
comes from the local nature of the synchronization
mechanisms (lock objects are spread over all the AH).
However, it can be assumed that this “locality” may
not be beneficial when the requested indices are close
to each other. Hence, it is natural to test how the
structure can handle situations when the key set is
small. For the test purposes it was adopted that
K = [0, . . . m], where m increases starting from 10
and ending at 776000.
As before, for the narrow key ranges ConcurrentSkipListMap runs similarly fast to the dcvEB array. The result of LockFree9ST does not differ significantly from those two structures. For the larger values
of m the dominance of the dcvEB array becomes apparent. The slow increase in execution time is caused
mainly by the insert() and successor() methods. With 7 Comments and discussion
the increasing key range, insert() needs to allocate
more and more memory and the distances scanned The presented dcvEB array is the result of improveby successor() get bigger. A very good result is also ments introduced into its previous version [15]. In

contrast to the cvEB array, the presented structure is
able to grow when more data need to be stored in it,
and to shrink when the data are removed. Hence, the
amount of occupied memory (RAM) is in relation to
the amount of stored data. Of course, this relationship is not as simple as in the case of an ordinary
binary search tree or a heap tree [5]. In those structures, the amount of memory occupied depends more
or less linearly on the amount of stored data. In the
case of the dcvEB array, it also depends on the data
layout. More precisely, if the smallest key is 0 and
the largest key is nh − 1 (where n is the length of the
AHs’ summary bit vector), then the dcvEB array can
h
−1
non-leaf AHs,
have up to 1 + n + . . . + nh−1 = nn−1
h
and up to n − 1 leaf AHs. Whilst the number of leaf
AHs depends only on the amount of data actually
stored in the dcvEB array, the number of non-leaf
AHs also depends on data distribution and the value
of the maximal key. If the stored keys are scattered
throughout the array, so that at all 64 positions (assuming that n = 64) at least one element can be
found, then the memory consumption by the dcvEB
array is relatively high. In fact, in the worst case scenario even 64 times more items could be stored in
the dcvEB array without increasing the number of
non-leaf AHs. Reversely, if the data is indexed by the
keys arranged one after the other, memory utilization
is optimal and any increase in the amount of stored
data by at least 64 keys, triggers the creation of at
least one non-leaf AH.
Scattered keys, although undesirable due to the use
of extra RAM, may by beneficial to the methods using
blocking synchronization, such as delete() or insert().
The keys’ dispersion increases the chance that the
threads operating on the dcvEB array less frequently
block each other, which results in an increase in the
speed of the structure.

8

Summary

In this paper, the author proposes the dcvEB array
- the new concurrent implementation of the dynamic
set structure based on the synchronization scheme
proposed in [15]. The preliminary tests conducted
using a prototype Java-based implementation of the
structure seem to confirm that it maintains the high
performance of the concurrent operations. The introduced extensions are of great practical importance.
Thanks to them, the structure is able to dynamically
adapt its size to the amount of stored data and increase or decrease the range of indices stored. There
are also some smaller improvements, such as a new
successor search strategy.

The variable amount of memory used, and no limit
on the size of the key in combination with the high
performance of concurrent applications, can make
this structure useful for a wide range of professionals involved in concurrent or parallel programming.

Acknowledgment
The author would like to thank Prof. Jacek Kitowski
and Piotr Matyasik, Ph.D. (AGH) for providing the
test environments, and Paweł Salata, for helping the
author in launching multiple variants of tests.

References
1. R. Bayer, “Symmetric binary B-Trees: Data structure and maintenance algorithms,” Acta Informatica,
1972.
2. R. Bayer and M. Schkolnick, “Concurrency of Operations on B-Trees,” Acta Informatica, 1977.
3. N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun, “A practical concurrent binary search tree,” in
Proceedings of 15th ACM SIGPLAN, 2010.
4. T. Brown and J. Helga, “Non-blocking K-ary Search
Trees,” in Proceedings of the 15th International Conference on Principles of Distributed Systems, 2011.
5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and
C. Stein, Introduction to Algorithms, 3rd ed. MIT
Press, 2009.
6. F. Ellen, P. Fatourou, E. Ruppert, and F. van
Breugel, “Non-blocking binary search trees,” in Proceeding of the 29th ACM SIGACT-SIGOPS symposium, 2010.
7. C. S. Ellis, “Concurrent Search and Insertion in 2-3
Trees,” Acta Informatica, vol. 14, no. 1, pp. 63–86,
1980.
8. K. Fraser, “Practical lock-freedom,” University of
Cambridge, Tech. Rep. UCAM-CL-TR-579, 2004.
9. S. Hanke, T. Ottmann, and E. Soisalon-Soininen,
“Relaxed balanced red-black trees,” Algorithms and
Complexity, 1997.
10. M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit,
“A simple optimistic skiplist algorithm,” in
SIROCCO’07: Proceedings of the 14th international conference on Structural information and
communication complexity.
Springer-Verlag, Jun.
2007.
11. M. Herlihy and N. Shavit, "The Art of Multiprocessor
Programming". Elsevier, 2008.
12. P. M. Herlihy and J. M. Wing, “Linearizability: a
correctness condition for concurrent objects,” ACM
Transactions on Programming Languages and Systems, vol. 12, 1990.
13. S. V. Howley and J. Jones, “A non-blocking internal
binary search tree,” in Proceedings of the 24th ACM
symposium on Parallelism in algorithms and architectures, 2012.

14. D. E. Knuth, The Art of Computer Programming,
Volume I: Fundamental Algorithms, 2nd Edition.
Addison-Wesley, 1973.
15. K. Kułakowski, “A concurrent van Emde Boas
array as a fast and simple concurrent dynamic set
alternative,” Concurrency and Computation: Practice
and Experience, vol. 26, no. 2, pp. 360–379, 2014.
[Online]. Available: http://dx.doi.org/10.1002/cpe.
2995
16. H. T. Kung and P. L. Lehman, “Concurrent manipulation of binary search trees,” Trans. on Dat. Systems,
1980.
17. V. Lanin and D. Shasha, “A symmetric concurrent
b-tree algorithm,” in Proceedings of 1986 ACM Fall
joint computer conference, 1986.
18. D. Lea, Concurrent Programming in Java. Second
Edition: Design Principles and Patterns, 2nd ed.
Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1999.
19. P. L. Lehman and S. Bing Yao, “Efficient locking
for concurrent operations on B-trees,” Trans. on Dat.
Systems, 1981.
20. K. Mehlhorn and S. Näher, “Bounded ordered dictionaries in o(loglogn) time and o(n) space,” Inf. Process. Lett., vol. 35, no. 4, pp. 183–189, Aug. 1990.
21. O. Nurmi, E. Soisalon-Soininen, and D. Wood, “Relaxed AVL Trees, Main-Memory Databases, and Concurrency,” HKUST, Tech. Rep., 1996.
22. W. Pugh, “Concurrent maintenance of skip lists,” College Park, MD, USA, Tech. Rep., 1990.
23. B. Samadi, “B-trees in a system with multiple users,”
Information Processing Letters, pp. 107–112, 1976.
24. N. Shavit, “Data structures in the multicore age,”
Communication of the ACM, 2011.
25. P. van Emde Boas, “Preserving order in a forest in less
than logarithmic time and linear space,” Inf. Process.
Lett., vol. 6, no. 3, pp. 80–82, 1977.

