Fast Dynamic Arrays
Philip Bille∗
phbi@dtu.dk

Anders Roy Christiansen†
miet@dtu.dk

Mikko Berggren Ettienne†
miet@dtu.dk

Inge Li Gørtz†
inge@dtu.dk

arXiv:1711.00275v1 [cs.DS] 1 Nov 2017

Abstract
We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of n elements supporting access in time O(1) and insertion and deletion in
time O(n ) for  > 0 while using o(n) extra space. We consider several different implementation optimizations in C++ and compare their performance to that of vector and multiset from
the standard library on sequences with up to 108 elements. Our fastest implementation uses
much less space than multiset while providing speedups of 40× for access operations compared
to multiset and speedups of 10.000× compared to vector for insertion and deletion operations
while being competitive with both data structures for all other operations.

1

Introduction

We present a highly optimized implementation of a data structure solving the dynamic array
problem, that is, maintain a sequence of elements subject to the following operations:
access(i): return the ith element in the sequence.
access(i, m): return the ith through (i + m − 1)th elements in the sequence.
insert(i, x): insert element x immediately after the ith element.
delete(i): remove the ith element from the sequence.
update(i, x): exchange the ith element with x.
This is a fundamental and well studied data structure problem [2, 4, 7, 8, 3, 1, 5, 6] solved
by textbook data structures like arrays and binary trees. Many dynamic trees provide all
the operations in O(lg n) time including 2-3-4 trees, AVL trees, splay trees, etc. and Dietz [2]
gives a data structure that matches the lower bound of Ω(lg n/ lg lg n) showed by Fredman
and Saks [4]. The lower bound only holds when identical complexities are required for all
operations. In this paper we focus on the variation where access must run in O(1) time.
Goodrich and Kloss present what they call tiered vectors [5] with a time complexity of O(1)
for access and update and O(n1/l ) for insert and delete for any constant integer l ≥ 2, using
ideas similar to Frederickson’s in [3]. The data structure uses only o(n) extra space beyond
that required to store the actual elements. At the core, the data structure is a tree with out
degree n1/l and constant height l − 1.
Goodrich and Kloss compare the performance of an implementation with l = 2 to that of
vector from the standard library of Java and show that the structure is competitive for access
operations while being significantly faster for insertions and deletions. Tiered vectors provide
a performance trade-off between standard arrays and balanced binary trees for the dynamic
array problem.

Our Contribution In this paper, we present what we believe is the first implementation of tiered vectors that supports more than 2 tiers. Our C++ implementation supports
access and update in times that are competitive with the vector data structure from C++’s
standard library while insert and delete run more than 10.000× faster. It performs access and
∗ Supported
† Supported

by the Danish Research Council (DFF – 4005-00267, DFF – 1323-00178)
by the Danish Research Council (DFF – 4005-00267)

1

PQRSTUVXY???ABCDEFGHIJKLMNO => ABCDEFGHIJKLMNOPQRSTUVX???
12

RSTUVXYPQ => PQRSTUVXY
7

0

R

3

1

S

T

X U V

Y

0

1

P Q

F

D

GHIJKLMNO => GHIJKLMNO
0

DEF???ABC => ???ABCDEF

E

A

B

0

1

C

I

2

G H

K

0

L

J

M N O

Figure 1: An illustration of a tiered vector with l = w = 3. The elements are letters, and the tiered
vector represents the sequence ABCDEFGHIJKLMNOPQRSTUVX. The elements in the leaves
are the elements that are actually stored. The number above each node is its offset. The strings
above an internal node v with children c1 , c2 , c3 is respectively A(c1 ) · A(c2 ) · A(c3 ) and A(v), i.e.
the elements v represents before and after the circular shift. ? specifies an empty element.

update more than 40× faster than the multiset data structure from the standard library while
insert and delete is only a few percent slower. Furthermore multiset uses more than 10× more
space than our implementation. All of this when working on large sequences of 108 32-bit
integers.
To obtain these results, we significantly decrease the number of memory probes per operation compared to the original tiered vector. Our best variant requires only half as many
memory probes as the original tiered vector for access and update operations which is critical for the practical performance. Our implementation is cache efficient which makes all
operations run fast in practice even on tiered vectors with several tiers.
We experimentally compare the different variants of tiered vectors. Besides the comparison to the two commonly used C++ data structures, vector and multiset, we compare the
different variants of tiered vectors to find the best one. We show that the number of tiers have
a significant impact on the performance which underlines the importance of tiered vectors
supporting more than 2 tiers.
Our implementations are parameterized and thus support any number of tiers ≥ 2. We use
techniques like template recursion to keep the code rather simple while enabling the compiler
to generate highly optimized code.
The source code can be found at https://github.com/mettienne/tiered-vector.

2

Preliminaries

The first and ith element of a sequence A are denoted A[0] and A[i − 1] respectively and the
ith through j th elements are denoted A[i − 1, j − 1]. Let A1 · A2 denote the concatenation of
the sequences A1 and A2 . |A| denotes the number of elements in the sequence A. A circular
shift of a sequence A by x is the sequence A[|A| − x, |A| − 1] · A[0, |A| − x − 1]. Define the
remainder of division of a by b as a mod b = a − qb where q is the largest integer such that
q · b ≤ a. Define A[i, j] mod w to be the elements A[i mod w], A[(i + 1) mod w], . . . , A[j
mod w], i.e. A[4, 7] mod 5 = A[4], A[0], A[1], A[2]. Let bxc denote the largest integer smaller
than x.

3

Tiered Vectors

In this section we will describe how the tiered vector data structure from [5] works.

Data Structure An l-tiered vector can be seen as a tree T with root r, fixed height
l − 1 and out-degree w for any l ≥ 2. A node v ∈ T represents a sequence of elements
A(v) thus A(r) is the sequence represented by the tiered vector. The capacity cap(v) of a
node v is wheight(v)+1 . For a node v with children c1 , c2 , . . . , cw , A(v) is a circular shift of
the concatenation of the elements represented by its children, A(c1 ) · A(c2 ) · . . . · A(cw ). The
circular shift is determined by an integer off(v) ∈ [cap(v)] that is explicitly stored for all nodes.
2

Thus the sequence of elements A(v) of an internal node v can be reconstructed by recursively
reconstructing the sequence for each of its children, concatenating these and then circular
shifting the sequence by off(v). See Figure 1 for an illustration. A leaf v of T explicitly stores
the sequence A(v) in a circular array elems(v) with size w whereas internal nodes only store
their respective offset. Call a node v full if |A(v)| = cap(v) and empty if |A(v)| = 0. In order
to support fast access, for all nodes v the elements of A(v) are located in consecutive children
of v that are all full, except the children containing the first and last element of A(v) which
may be only partly full.

Access & Update To access an element A(r)[i] at a given index i; one traverses a
path from the root down to a leaf in the tree. In each node the offset of the node is added
to the index to compensate for the cyclic shift, and the traversing is continued in the child
corresponding to the newly calculated index. Finally when reaching a leaf, the desired element
is returned from the elements array of that leaf. The operation access(v, i) returns the element
A(v)[i] and is recursively computed as follows:
v is internal: Compute i0 = (i + off(v)) mod cap(v), let v 0 be the bi0 /wcth child of v and
return the element access(v 0 , i0 mod cap(v 0 )).
v is leaf: Compute i0 = (i + off(v)) mod w and return the element elems(v)[i0 ].
The time complexity is Θ(l) as we visit all nodes on a root-to-leaf path in T . To navigate
this path we must follow l − 1 child pointers, lookup l offsets, and access the element itself.
Therefore this requires l − 1 + l + 1 = 2l memory probes.
The update operation is entirely similar to access, except the element found is not returned
but substituted with the new element. The running time is therefore Θ(l) as well. For future
use, let update(v, i, e) be the operation that sets A(v)[i] = e and returns the element that was
substituted.

Range Access Accessing a range of elements, can obviously be done by using the
access-operation multiple times, but this results in redundant traversing of the tree, since
consecutive elements of a leaf often – but not always due to circular shifts – corresponds to
consecutive elements of A(r). Let access(v, i, m) report the elements A(v)[i . . . i + m − 1] in
order. The operation can recursively be defined as:
v is internal: Let il = (i + off(v)) mod cap(v), and let ir = (il + m) mod cap(v). The
children of v that contains the elements to be reported are in the range [bil ·w/cap(v)c, bir ·
w/cap(v)c] mod w, call these cl , cl+1 , . . . , cr . In order, call access(cl , il , min(m, cap(cl )−
il )), access(ci , 0, cap(ci )) for ci = cl+1 , . . . , cr−1 , and access(cr , er−1 , 0, ir mod cap(cr )).
v is leaf: Report the elements elems(v)[i, i + m − 1] mod w.
The running time of this strategy is O(lm), but saves a constant factor over the naive
solution.

Insert & Delete Inserting an element in the end (or beginning) of the array can
simply be achieved using the update-operation. Thus the interesting part is fast insertion at
an arbitrary position; this is where we utilize the offsets.
Consider a node v, the key challenge is to shift a big chunk of elements A(v)[i, i + m − 1]
one index right (or left) to A(v)[i + 1, i + m] to make room for a new element (without actually
moving each element in the range). Look at the range of children cl , cl+1 , . . . , cr that covers
the range of elements A(v)[i, i + m − 1] to be shifted. All elements in cl+1 , . . . , cr−1 must be
shifted. These children are guaranteed to be full, so make a circular shift by decrementing
each of their offsets by one. Afterwards take the element A(ci−1 )[0] and move it to A(ci )[0]
using the update operation for l < i ≤ r. In cl and cr only a subrange of the elements might
need shifting, which we do recursively. In the base case of this recursion, namely when v is a
leaf, shift the elements by actually moving the elements one-by-one in elems(v).
Formally we define the shift(v, e, i, m) operation that (logically) shifts all elements A(v)[i, i+
m − 1] one place right to A[i + 1, i + m], sets A[i] = e and returns the value that was previously
on position A[i + m] as:
v is internal: Let il = (i + off(v)) mod cap(v), and let ir = (il + m) mod cap(v). The
children of v that must be updated are in the range [bil · w/cap(v)c, bir · w/cap(v)c]
mod w call these cl , cl+1 , . . . , cr . Let el = shift(cl , e, il , min(m, cap(cl ) − il )). Let ei =

3

update(ci , size(c)−1, ei−1 ) and set off(ci ) = (off(ci )−1) mod cap(c) for ci = cl+1 , . . . , cr−1 .
Finally call shift(cr , er−1 , 0, ir mod cap(cr )).
v is leaf: Let eo = elems(v)[(i + m) mod w]. Move the elements elems(v)[i, (i + m − 1)
mod w] to elems(v)[i + 1, (i + m) mod w], and set elems(v)[i] = e. Return eo .
An insertion insert(i, e) can then be performed as shift(root, e, i, size(root) − i − 1). The
running time of an insertion is T (l) = 2T (l − 1) + w · l ⇒ T (l) = O(2l w).
A deletion of an element can basically be done as an inverted insertion, thus deletion
can be implemented using the shift-operation from before. A delete(i) can be performed as
shift(r, ⊥, 0, i) followed by an update of the root’s offset to (off(r) + 1) mod cap(r).

Space There are at most O(wl−1 ) nodes in the tree and each takes up constant space,
thus the total space of the tree is O(wl−1 ). All leaves are either empty or full except the
two leaves storing the first and last element of the sequence which might contain less than
w elements. Because the arrays of empty leaves are not allocated the space overhead of the
arrays is O(w). Thus beyond the space required to store the n elements themselves, tiered
vectors have a space overhead of O(wl−1 ).
To obtain the desired bounds w is maintained such that w = Θ(n ) where  = 1/l and n is
the number of elements in the tiered vector. This can be achieved by using global rebuilding
to gradually increase/decrease the value of w when elements are inserted/deleted without
asymptotically changing the running times. We will not provide the details here. We sum up
the original tiered vector data structure in the following theorem:
Theorem 1 ([5]) The original l-tiered vector solves the dynamic array problem for l ≥ 2
using Θ(n1−1/l ) extra space while supporting access and update in Θ(l) time and 2l memory
probes. The operations insert and delete take O(2l n1/l ) time.

4

Improved Tiered Vectors

In this paper, we consider several new variants of the tiered vector. This section considers the
theoretical properties of these approaches. In particular we are interested in the number of
memory accesses that are required for the different memory layouts, since this turns out to
have an effect on the experimental running time. In Section 5.1 we analyze the actual impact
in practice through experiments.

4.1

Implicit Tiered Vectors

As the degree of all nodes is always fixed at some constant value w (it may be changed for
all nodes when the tree is rebuilt due to a full root), it is possible to layout the offsets and
elements such that no pointers are necessary to navigate the tree. Simply number all nodes
from left-to-right level-by-level starting in the root with number 0. Using this numbering
scheme, we can store all offsets of the nodes in a single array and similarly all the elements of
the leaves in another array.
To access an element, we only have to lookup the offset for each node on the root-to-leaf
path which requires l − 1 memory probes plus the final element lookup, i.e. in total l which
is half as many as the original tiered vector. The downside with this representation is that it
must allocate the two arrays in their entirety at the point of initialization (or when rebuilding).
This results in a Θ(n) space overhead which is worse than the Θ(n1− ) space overhead from
the original tiered vector.
Theorem 2 The implicit l-tiered vector solves the dynamic array problem for l ≥ 2 using
O(n) extra space while supporting access and update in O(l) time requiring l memory probes.
The operations insert and delete take O(2l n1/l ) time.

4.2

Lazy Tiered Vectors

We now combine the original and the implicit representation, to get both few memory probes
and little space overhead. Instead of having a single array storing all the elements of the leaves,
we store for each leaf a pointer to a location with an array containing the leaf’s elements. The
array is lazily allocated in memory when elements are actually inserted into it.
The total size of the offset-array and the element pointers in the leaves is O(n1− ). At most
two leaves are only partially full, therefore the total space is now again reduced to O(n1− ).

4

To navigate a root-to-leaf path, we now need to look at l − 1 offsets, follow a pointer from a
leaf to its array and access the element in the array, giving a total of l + 1 memory accesses.
Theorem 3 The lazy l-tiered vector solves the dynamic array problem for l ≥ 2 using Θ(n1−1/l )
extra space while supporting access and update in Θ(l) time requiring l + 1 memory probes.
The operations insert and delete take O(2l n1/l ) time.

5

Implementation

We have implemented a generic version of the tiered vector data structure such that the number
of tiers and the size of each tier can be specified at compile time. To the best of our knowledge,
all prior implementations of the tiered vector are limited to the considerably simpler 2-tier
version. Also, most of the performance optimizations applied in the 2-tier implementations
do not easily generalize. We have implemented the following variants of tiered vectors:
• Original The data structure described in Theorem 1.
• Optimized Original As described in Theorem 1 but with the offset of a node v located
in the parent of v, adjacent in memory to the pointer to v. Leaves only consist of an
array of elements (since their parent store their offset) and the root’s offset is maintained
separately as there is no parent to store it in.
• Implicit This is the data structure described in Theorem 2 where the tree is represented
implicitly in an array storing the offsets and the elements of the leaves are located in a
single array.
• Packed Implicit This is the data structure described in Theorem 2 with the following
optimization; The offsets stored in the offset array are packed together and stored in as
little space as possible. The maximum offset of a node v in theP
tree is n(height(v)+1)
and the number of bits needed to store all the offsets is therefore li=0 n1−i log(ni ) =
P
log(n) li=0 in1−i ≈ n1− log(n) (for sufficiently large n). Thus the n1− offsets can
be stored in approximately n1− words giving a space reduction of a constant factor .
The smaller memory footprint could lead to better cache performance.
• Lazy This is the data structure described in Theorem 3 where the tree is represented
implicitly in an array storing the offsets and every leaf stores a pointer to an array storing
only the elements of that leaf.
• Packed Lazy This is the data structure described in Theorem 3 with the following optimization; The offset and the pointer stored in a leaf is packed together and stored at
the same memory location. On most modern 64-bit systems – including the one we are
testing on – a memory pointer is only allowed to address 48 bits. This means we have
room to pack a 16 bit offset in the same memory location as the elements pointer, which
results in one less memory probe during an access operation.
• Non-Templated The implementations described above all use C++ templating for recursive functions in order to let the compiler do significant code optimizations. This
implementation is template free and serves as a baseline to compare the performance
gains given by templating.
In Section 6 we compare the performance of these implementations.

5.1

C++ Templates

We use templates to support storing different types of data in our tiered vector similar to
what most other general purpose data structures in C++ do. This is a well-known technique
which we will not describe in detail.
However, we have also used template recursion which is basically like a normal recursion
except that the recursion parameter must be a compile-time constant. This allows the compiler
to unfold the recursion at compile-time eliminating all (recursive) function calls by inlining
code, and allows better local code optimizations. In our case, we exploit that the height of a
tiered vector is constant.
To show the rather simple code resulting from this approach (disregarding the template
stuff itself), we have included a snippet of the internals of our access operation:

5

template <class T, class Layer>
struct helper {
static T& get(size_t node, size_t idx) {
idx = (idx + get_offset(node)) % Layer::capacity;
auto child = get_child(node, idx / Layer::child::capacity);
return helper<T, typename Layer::child>::get(child, idx);
}
}
template <class T, size_t W>
struct helper<T, Layer<W, LayerEnd> > {
static T& get(size_t node, size_t idx) {
idx = (idx + get_offset(node)) % L::capacity;
return get_elem(node, idx);
}
}
We also briefly show how to use the data structure. To specify the desired height of the
tree, and the width of the nodes on each tier, we also use templating:
Tiered<int, Layer<8, Layer<16, Layer<32>>>> tiered;
This will define a tiered vector containing integers with three tiers. The height of the
underlying tree is therefore 3 where the root has 8 children, each of which has 16 children each
of which contains 32 elements. We call this configuration 8-16-32.
In this implementation of tiered vectors we have decided to let the number of children on
each level be a fixed number as described above. This imposes a maximum on the number of
elements that can be inserted. However, in a production ready implementation, it would be
simple to make it grow-able by maintaining a single growth factor that should be multiplied on
the number of children on each level. This can be combined with the templated solution since
the growing is only on the number of children and not the height of the tree (per definition
of tiered vectors the height is constant). This will obviously increase the running time for
operations when growing/shrinking is required, but will only have minimal impact on all
other operations (they will be slightly slower because computations now must take the growth
factor into account).
In practice one could also, for many uses, simply pick the number of children on each
level sufficiently large to ensure the number of elements that will be inserted is less than
the maximum capacity. This would result in a memory overhead when the tiered vector is
almost empty, but by choosing the right variant of tiered vectors and the right parameters
this overhead would in many cases be insignificant.

6

Experiments

In this section we compare the tiered vector to some widely used C++ standard library
containers. We also compare different variants of the tiered vector. We consider how the
different representations of the data structure listed in Section 5, and also how the height of
tree and the capacity of the leaves affects the running time. The following describes the test
setup:

Environment All experiments have been performed on a Intel Core i7-4770 CPU @
3.40GHz with 32 GB RAM. The code has been compiled with GNU GCC version 5.4.0 with
flags “-O3”. The reported times are an average over 10 test runs.
Procedure In all tests 108 32-bit integers are inserted in the data structure as a preliminary step to simulate that it has already been used1 . For all the access and successor
operations 109 elements have been accessed and the time reported is the average time per
element. For range access, 10.000 consecutive elements are accessed. For insertion/deletion
1 In order to minimize the overall running time of the experiments, the elements were not added randomly, but
we show this does not give our data structure any benefits

6

106 elements have been (semi-)randomly2 added/deleted, though in the case of “vector” only
10.000 elements were inserted/deleted to make the experiments terminate in reasonable time.

6.1

Comparison to C++ STL Data Structures

In the following we have compared our best performing tiered vector (see the next sections) to
the vector and the multiset class from the C++ standard library. The vector data structure
directly supports the operations of a dynamic array. The multiset class is implemented as a
red-black tree and is therefore interesting to compare with our data structure. Unfortunately,
multiset does not directly support the operations of a dynamic array (in particular it has no
notion of positions of elements). To simulate an access operation we instead find the successor
of an element in the multiset. This requires a root-to-leaf traversal of the red-black tree, just
as an access operation in a dynamic array implemented as a red-black tree would. Insertion
is simulated as an insertion into the multiset, which again requires the same computations as
a dynamic array implemented as a red-black tree would.
Besides the random access, range access and insertion, we have also tested the operations
data dependent access, insertion in the end, deletion, and successor queries. In the data
dependent access tests, the next index to lookup depends on the values of the prior lookups.
This ensures that the CPU cannot successfully pipeline consecutive lookups, but must perform
them in sequence. We test insertion in the end, since this is a very common use case. Deletion
is performed by deleting elements at random positions. The successor queries returns the
successor of an element and is not actually part of the dynamic array problem, but is included
since it is a commonly used operation on a multiset in C++. It is simply implemented as a
binary search over the elements in both the vector and tiered vector tests where the elements
are now inserted in sorted order.
The results are summarized in Table 1 which shows that the vector performs slightly better
than the tiered vector on all access and successor tests. As expected from the Θ(n) running
time, it performs extremely poor on random insertion and deletion. For insertion in the end of
the sequence, vector is also slightly faster than the tiered vector. The interesting part is that
even though the tiered vector requires several extra memory lookups and computations, we
have managed to get the running time down to less than the double of the vector for access,
even less for data dependent access and only a few percent slowdown for range access. As
discussed earlier, this is most likely because the entire tree structure (without the elements)
fits within the CPU cache, and because the computations required has been minimized.
Comparing our tiered vector to multiset, we would expect access operations to be faster
since they run in O(1) time compared to O(log n). On the other hand, we would expect
insertion/deletion to be significantly slower since it runs in O(n1/l ) time compared to O(log n)
(where l = 4 in these tests). We see our expectations hold for the access operations where the
tiered vector is faster by more than an order of magnitude. In random insertions however,
the tiered vector is only 8% slower – even when operating on 100.000.000 elements. Both the
tiered vector and set requires O(log n) time for the successor operation. In our experiments
the tiered vector is 3 times faster for the successor operation.
Finally, we see that the memory usage of vector and tiered vector is almost identical. This
is expected since in both cases the space usage is dominated by the space taken by the actual
elements. The multiset uses more than 10 times as much space, so this is also a considerable
drawback of the red-black tree behind this structure.
To sum up, the tiered vectors performs better than multiset on all tests but insertion,
where it performs only slightly worse.

6.2

Tiered Vector Variants

In this test we compare the performance of the implementations listed in Section 5 to that or
the original data structure as described in 1.

Optimized Original By co-locating the child offset and child pointer, the two memory
lookups are at adjacent memory locations. Due to the cache lines in modern processors, the
second memory lookup will then often be answered directly by the fast L1-cache. As can be
seen on Figure 2, this small change in the memory layout results in a significant improvement
2 In order to not impact timing, a simple access pattern has been used instead of a normal pseudo-random
generator.

7

tiered vector
34.07 ns
99.09 ns
0.24 ns
1.79 µs
7.28 ns
0.55 µs
1.92 µs
408 MB

access
dd-access
range access
insert
insertion in end
successor
delete
memory

set
1432.05 ns
1436.67 ns
13.02 ns
1.65 µs
242.90 ns
1.53 µs
1.78 µs
4802 MB

set / tiered
42.03
14.50
53.53
0.92
33.38
2.75
0.93
11.77

vector
21.63 ns
79.37 ns
0.23 ns
21675.49 µs
2.93 ns
0.36 µs
21295.25 µs
405 MB

vector / tiered
0.63
0.80
0.93
12082.33
0.40
0.65
11070.04
0.99

it
ic

it
ic

im
pl

im
pl

ed

ed

pa
ck

or
iz
op
tim

(a) access

zy

it
ic

it
ic

im
pl

im
pl

ed
pa
ck

la
zy

zy
la

ig
in
al
or

ed
pa
ck

op
tim

iz

ed

or

0 s

ig
in
al

10 ns

la
zy

20 ns

la

30 ns

ed

40 ns

pa
ck

50 ns

ig
in
al

8 us
7 us
6 us
5 us
4 us
3 us
2 us
1 us
0 s

60 ns

or

70 ns

ig
in
al

Table 1: The table summarizes the performance of the implicit tiered vector compared to the performance of multiset and vector from the C++ standard library. dd-access refers to data dependent
access.

(b) insert

Figure 2: Figures (a) and (b) show the performance of the original ( ), optimized original (
lazy ( ) packed lazy ( ), implicit ( ) and packed implicit ( ) layouts.

in performance for both access and insertion. In the latter case, the running time is more
than halved.

Lazy and Packed Lazy Figure 2 shows how the fewer memory probes required by
the lazy implementation in comparison to the original and optimized original results in better
performance. Packing the offset and pointer in the leaves results in even better performance
for both access and insertion even though it requires a few extra instructions to do the actual
packing and unpacking.
Implicit From Figure 2, we see the implicit data structure is the fastest. This is as
expected because it requires fewer memory accesses than the other structures except for the
packed lazy which instead has a slight computational overhead due to the packing and unpacking.
As shown in Theorem 2 the implicit data structure has a bigger memory overhead than
the lazy data structure. Therefore the packed lazy representation might be beneficial in some
settings.
Packed Implicit Packing the offsets array could lead to better cache performance due
to the smaller memory footprint and therefore yield better overall performance. As can be
seen on Figure 2, the smaller memory footprint did not improve the performance in practice.
The simple reason for this, is that the strategy we used for packing the offsets required extra
computation. This clearly dominated the possible gain from the hypothesized better cache
performance. We tried a few strategies to minimize the extra computations needed at the
expense of slightly worse memory usage, but none of these led to better results than when not
packing the offsets at all.

6.3

Width Experiments

This experiment was performed to determine the best capacity ratio between the leaf nodes
and the internal nodes. The six different width configurations we have tested are: 32-3232-4096, 32-32-64-2048, 32-64-64-1024, 64-64-64-512, 64-64-128-256, and 64-128-128-128. All
configurations have a constant height 4 and a capacity of approximately 130 mio.

8

),

5 us

40 ns

200 ps

4 us

30 ns

150 ps

3 us

20 ns

100 ps

2 us

10 ns

50 ps

1 us

0 s

0 s

0 s

(a) access

40
96
40
96
20
48
20
48
10
24
10
24
51
2
51
2
25
6
25
6
12
8
12
8

6 us

250 ps

40
96
40
96
20
48
20
48
10
24
10
24
51
2
51
2
25
6
25
6
12
8
12
8

300 ps

50 ns

(b) range access

(c) insert

Figure 3: Figures (a), (b) and (c) show the performance of the implicit (
original tiered vector ( ) for different tree widths.

5 us

0 s

0 s

0 s

15 us

(a) access(i)

(b) access(i, m)

6

6

5

5

4

3

3

2

2

6

6

5

5

4

4

3

3

2

10 us

2

6

50 ps
6

10 ns
5

100 ps

5

20 ns

4

150 ps

4

200 ps

30 ns

3

20 us

40 ns

3

25 us

250 ps

2

300 ps

50 ns

2

60 ns

) and the optimized

4

40
96
40
96
20
48
20
48
10
24
10
24
51
2
51
2
25
6
25
6
12
8
12
8

60 ns

(c) insert

Figure 4: Figures (a),(b) and (c) show the performance of the implicit (
original tiered vector ( ) for different tree heights.

) and the optimized

We expect the performance of access operations to remain unchanged, since the amount
of work required only depends on the height of the tree, and not the widths. We expect range
access to perform better when the leaf size is increased, since more elements will be located
in consecutive memory locations. For insertion there is not a clearly expected behavior as
the time used to physically move elements in a leaf will increase with leaf size, but then less
operations on the internal nodes of the tree has to be performed.
On Figure 3 we see access times are actually decreasing slightly when leaves get bigger.
This was not expected, but is most likely due to small changes in the memory layout that
results in slightly better cache performance. The same is the case for range access, but this
was expected. For insertion, we see there is a tipping point. For our particular instance, the
best performance is achieved when the leaves have size 512.

6.4

Height Experiments

In these tests we have studied how different heights affect the performance of access and
insertion operations. We have tested the configurations 8196-16384, 512-512-512, 64-64-64512, 16-16-32-32-512, 8-8-16-16-16-512. All resulting in the same capacity, but with heights
in the range 2-6.
We expect the access operations to perform better for lower trees, since the number of
operations that must be performed is linear in the height. On the other hand we expect
insertion to perform significantly better with higher trees, since its running time is O(n1/l )
where l is the height plus one.
On Figure 4 we see the results follow our expectations. However, the access operations
only perform slightly worse on higher trees. This is most likely because all internal nodes fit
within the L3-cache. Therefore the running time is dominated by the lookup of the element
itself. (It is highly unlikely that the element requested by an access to a random position
would be among the small fraction of elements that fit in the L3-cache).
Regarding insertion, we see significant improvements up until a height of 4. After that,
increasing the height does not change the running time noticeably. This is most likely due to
the hidden constant in O(n1/l ) increasing rapidly with the height.

6.5

Configuration Experiments

In these experiments, we test a few hypotheses about how different changes impact the running
time. The results are shown on Figure 5, the leftmost result (base) is the implicit 64-64-64-512

9

Figure 5: Figures (a) and (b) show the performance of the base (
sizes ( ), non-templated ( ) layouts.

pl
at
ed

s
ze

ed

si

at

nno

n-

al

ig

te

ne

m

d

ro
t

ba
se

in
at
pl
m
te

(b) range access

no

ig
no

n-

al

18 us
16 us
14 us
12 us
10 us
8 us
6 us
4 us
2 us
0 s

no

ne

te
nno

(a) access

g

s
id
th
w

m

w
d
ne
ig
al
no

n-

d

pl
at
ed

s
id
th

ed
at
ro
t

0 s

ba
se

50 ns

ed

100 ns

at

150 ns

450 ps
400 ps
350 ps
300 ps
250 ps
200 ps
150 ps
100 ps
50 ps
0 s

ro
t

200 ns

ba
se

250 ns

(c) insert(i,x)

), rotated (

), non-aligned

configuration of the tiered vector to which we compare our hypotheses.
Rotated : As already mentioned, the insertions performed as a preliminary step to the tests
are not done at random positions. This means that all offsets are zero when our real operations
start. The purpose of this test is the ensure that there are no significant performance gains
in starting from such a configuration which could otherwise lead to misleading results. To
this end, we have randomized all offsets (in a way such that the data structure is still valid,
but the order of elements change) after doing the preliminary insertions but before timing the
operations. As can be seen on Figure 5, the difference between this and the normal procedure
is insignificant, thus we find our approach gives a fair picture.
Non-Aligned Sizes: In all our previous tests, we have ensured all nodes had an out-degree
that was a power of 2. This was chosen in order to let the compiler simplify some calculations,
i.e. replacing multiplication/division instructions by shift/and instructions. As Figure 5 shows,
using sizes that are not powers of 2 results in significantly worse performance. Besides showing
that powers of 2 should always be used, this also indicates that not only the number of
memory accesses during an operation is critical for our performance, but also the amount of
computation we make.
Non-Templated The non-templated results in Figure 2 the show that the change to templated recursion has had a major impact on the running time. It should be noted that some
improvements have not been implemented in the non-templated version, but it gives a good
indication that this has been quite useful.

7

Conclusion

This paper presents the first implementation of a generic tiered vector supporting any constant
number of tiers. We have shown a number of modified versions of the tiered vector, and
employed several optimizations to the implementation. These implementations have been
compared to vector and multiset from the C++ standard library. The benchmarks show
that our implementation stays on par with vector for access and on update operations while
providing a considerable speedup of more than 40× compared to multiset. At the same time
the asymptotic difference between the logarithmic complexity of multiset and the polynomial
complexity of tiered vector for insertion and deletion operations only has little effect in practice.
For these operations, our fastest version of the tiered vector suffers less than 10% slowdown.
Arguably, our tiered array provides a better trade-off than the balanced binary tree data
structures used in the standard library for most applications that involves big instances of the
dynamic array problem.

References
[1] Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick.
Resizable arrays in optimal time and space. In Proceedings of the 6th International Workshop on Algorithms and Data Structures, WADS ’99, pages 37–48, London, UK, UK, 1999.
Springer-Verlag.
[2] Paul F. Dietz. Optimal algorithms for list indexing and subset rank. In Proceedings of
the Workshop on Algorithms and Data Structures, WADS ’89, pages 39–46, London, UK,
UK, 1989. Springer-Verlag.

10

[3] Greg N. Frederickson. Implicit data structures for the dictionary problem. J. ACM,
30(1):80–94, January 1983.
[4] M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In
Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC
’89, pages 345–354, New York, NY, USA, 1989. ACM.
[5] Michael T. Goodrich and John G. Kloss. Tiered Vectors: Efficient Dynamic Arrays for
Rank-Based Sequences, pages 205–216. Springer Berlin Heidelberg, Berlin, Heidelberg,
1999.
[6] Jyrki Katajainen. Worst-Case-Efficient Dynamic Arrays in Practice, pages 167–183.
Springer International Publishing, Cham, 2016.
[7] Jyrki Katajainen and Bjarke Buur Mortensen. Experiences with the Design and Implementation of Space-Efficient Deques, pages 39–50. Springer Berlin Heidelberg, Berlin,
Heidelberg, 2001.
[8] Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct Dynamic Data Structures, pages 426–437. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.

11

