Analysis of Concurrent Lock-Free Hash Tries with Constant-Time Operations
Aleksandar Prokopec
cs.DS



Analysis of Tries with Constant-Time Operations]
Analysis of Concurrent Lock-Free Hash Tries with Constant-Time Operations
                                        
                                        
                                        

                                        
                                        


                                        
                                        















                                        
nnnn-nnnn-nnnn-nnnn             

  
  
  Oracle Labs            
  
  
  
  
  Switzerland

aleksandar.prokopec@gmail.com          




                                        

























                









                                        
                                        






Ctrie is a scalable concurrent non-blocking dictionary data structure,
with good cache locality,
and non-blocking linearizable iterators <cit.>.
However, operations on most existing
concurrent hash tries run in O(log n) time.

In this technical report,
we extend the standard concurrent hash-tries <cit.>
with an auxiliary data structure called a cache[
A complete description of the new data structure
is given in the corresponding PPoPP 2018 paper
<cit.>.
].
The cache is essentially an array that stores pointers
to a specific level of the hash trie.
We analyze the performance implications of adding a cache,
and prove that the running time of the basic operations becomes O(1).

























  






[
    Aleksandar Prokopec
    
=======================







§ INTRODUCTION


Since the first known proposal by Briandais
<cit.>,
tries have moved beyond their original string retrieval use-case.
The idea of guiding the search with individual string characters
was applied to hash tries,
which store arbitrary key types using their hash-code bits
<cit.>.
The growing interest in concurrent data structures
lead to the first non-blocking hash trie,
named Ctrie <cit.>,
whose key advantage was improved scalability <cit.>.
Subsequent research focused on additional non-blocking operations,
such as multi-key transactions <cit.>
and lazy snapshots <cit.>,
as well as on enhancing performance.
In the context of concurrent Prolog,
Areias described an insert-only variant with improved scalability
<cit.>.
Joisha proposed another insert-only variant
suitable for logging, Bloom filters and garbage collection
<cit.>,
and Steindorfer described techniques for
improving the memory footprint and cache locality
<cit.>.
However, most existing research on tries
does not improve their asymptotic running time.
Since anecdotal evidence suggests that lookup
is a predominantly used dictionary operation <cit.>,
it remains unclear if tries should replace concurrent hash tables.

In the past, it was frequently taken for granted
that concurrent hash trie operations run in O(log n) time
<cit.>.
This assumption is possibly based on the fact
that the depth of a perfectly balanced k-ary tree is Θ(log n).
However, a hash trie is not necessarily balanced and its depth can reach O(n) –
a trivial example involves a non-uniformly distributed hash function.
Furthermore, as shown before <cit.>,
hash trie operations are not constrained by the hash trie depth,
and can execute in O(loglog n) time.

In this work,
we propose a novel concurrent, lock-free hash trie design
that uses fewer allocations and fewer indirections
compared to the original Ctrie <cit.>.
We enhance the new hash trie variant
with an auxiliary data structure called a cache.
We call the resulting data structure a cache-trie.
By analyzing the key depth distribution,
we show that, given a universal hash function,
the expected key depth in a hash trie
(and by extension cache-trie) is O(log n).
We then prove that when a cache-trie is augmented with a cache,
its operations run in expected O(1) time.

Concretely, we bring forth the following contributions:



  * We present a novel lock-free concurrent hash trie design
that uses fewer object allocations

compared to the previous variants <cit.>
(Section sec:design-lookup and sec:design-insert).

  * We describe the cache-trie data structure,
which extends the concurrent hash trie with a quiescently consistent cache.
This allows insert, lookup and remove to run in expected O(1) time
(Section sec:design-cache).

  * We present a statistical analysis of the cache-trie operations
and prove the O(1) time bound
(Section sec:analysis-runtime).

  * We prove that all the operations are correct, linearizable and lock-free
(Section sec:analysis-correctness).

  * We evaluate the Scala implementation
of the proposed data structure
against similar concurrent data structures,
and show up to 5× performance improvements
with respect to previous hash trie variants
(Section sec:evaluation).


We then give a summary of related work in Section sec:related,
and conclude in Section sec:conclusion.
We start with an overview that informally explains how cache-tries work.




§ OVERVIEW


Before showing the concrete implementation,
we briefly consider one specific cache-trie execution scenario.
A cache-trie is identified with a  reference,
which points to an array of pointers, called an array node.
This array is initially empty,
but gets populated with pointers to single nodes as keys get inserted.
Consider the following cache-trie,
which contains a pointer to a single node whose key has a hash code
ending with 0001_2 = 1_10.
The position of this key is 1, as dictated by the 4 lowest bits.
Assume now that some thread T1 decides to insert
a key whose hash-code ends with 10000100.
Thread T1 executes a  at the empty location 0100_2 = 4_10,
and after that, another thread T2 can read it.



    < g r a p h i c s >


Assume now that the other thread T2 decides to insert another key
whose hash-code ends with 11110100.
The location 4 of the new key coincides with the previously inserted key,
so the cache-trie must be extended at the next level.
T2 decides not to waste an array of length 16 on just two keys,
so it creates a new array of length 4,
in which the previous key occupies the position 1000_2 % 100_2 = 00_2 = 0_10,
and the new key occupies the position 1111_2 % 100_2 = 11_2 = 3_10.
T2 then executes a  at the location 4 at the first level.
After the  completes, both keys are contained in the cache-trie:



    < g r a p h i c s >


Let T2 now insert another key
whose hash-code ends with 00110100.
Once more, T2 encounters a collision at level 0,
and then encounters another collision at the next level.
Instead of immediately adding an array node at a deeper level,
T2 decides to replace the narrow array node of length 4
with another array node of length 16.
However, T2 cannot immediately execute a 
at the position 4 at the root –
doing so would allow a race condition in which another thread T3
modifies the narrow node after it was removed from the root array.
Instead, T2 must first atomically freeze the narrow node
to prevent further updates
(details of freezing are shown later).
Only after the narrow node is frozen,
the pointer at the position 4 in the root can be swapped out.



    < g r a p h i c s >


Once the number of levels in the cache-trie grows sufficiently,
the majority of work consists of traversing the inner nodes.
The search gets progressively slower.

Cache.
This is where we introduce our key contribution.
We observe that pointers to nodes that are close to the leafs
would likely boost the key search.
We therefore extend the cache-trie with a singly-linked list of arrays.
Each array holds pointers to nodes in one level of the trie,
and the list is sorted from the deeper levels to the root.
We call this list of arrays a cache.
A fully populated cache of depth d
has an array at each level i, 1 ≤ i ≤ d,
that is effectively a concatenation of all the trie nodes at level i
(including any missing ones).
These arrays do not perfectly match the trie
because the cache is populated lazily and
because parts of the trie go deeper than d.
An example cache-trie is shown in the following figure:



    < g r a p h i c s >


The  pointer refers to the list of arrays
(list pointers are violet).
An array entry is either ,
or points to a node at the respective level
(each array has 16^i entries,
so we omit some entries and use the "…" notation).
A lookup or an insert operation starts
by inspecting the deepest level of the cache
and jumps to an inner node if a pointer exists,
or otherwise reverts to a slow search from the .

Challenges.
There are three obstacles with this design.


[label=(*),itemsep=0mm]

  * It is unclear how to keep the trie and the cache synchronized
using single-word  instructions.
In a non-blocking concurrent data structure,
efficiently updating multiple memory locations with a single 
is not straightforward.

  * It is not obvious if a cache level can be selected optimally.
A cache should target the level with the majority of keys (if such a level exists).
At the same time, the cache must not be larger than the trie,
since it is expensive to maintain.

  * Finally, even if we knew how to pick the cache level
based on the key depth distribution,
it is unclear how to retrieve the distribution correctly and optimally.


The next section shows how to overcome these obstacles.













§ DESIGN AND IMPLEMENTATION


In this section,
we present the implementation of the cache-trie data structure.
We start with the basic lookup and insert operations that do not use the cache,
and then explain how the cache improves them.
We then show how to manage the cache,
and discuss the remaining operations.




















Data types.
Figure <ref>
shows the basic cache-trie data types.
During any quiescent period,
a cache-trie consists only of  and  objects.
An  is a leaf node –
it holds a single key-value pair,
a copy of the corresponding hash code,
and a  field that is initialized to a special value .
An  is an inner node,
defined with the  keyword
as an alias for an array of  pointers.
Cache-trie is a 16-way trie,
so s can contain up to 16 pointers.
Each node occupies a specific level of the cache-trie,
where levels are multiples of 4 –
the root  is at level 0,
its pointees are at level 4, and so on.
At level ℓ, there can be up to 2^ℓ nodes.

Invariant.
A cache-trie that consists only of s and s
obeys the following invariant:
if the cache-trie contains an 
that stores a key whose hash-code bits are h,
then this  is reachable with a chain of  pointers
a_0 a_0[p_0]⟶
a_1 a_1[p_1]⟶…a_n[p_n]⟶
s_n+1
starting from the ,
such that p_0 p_1 … p_n is a prefix of h.

The rest of the node types,
summarized in Table <ref>,
exist only during an operation.
,  and  are special values
used to prevent modifications of other nodes,
as explained in Sections <ref> and <ref>.
The  is used to mark an  for expansion,
and is used for insertion.




 §.§ Lookup Operation


























The goal of the  operation is to find the value
associated with the specified key.
If the key is not a part of the cache-trie,
 must return the  value.

Summary.
To find a value associated with a key,
the  operation
relies on the invariant specified in the previous section.
The search works as follows –
upon reaching an  at level ℓ,
hash-code bits [ ℓ, ℓ+4 ⟩ are used as an index
to select the pointer to the next level.
This is repeated until reaching an empty entry or an .

If the lookup operation encounters a special node,
such as an , ,  or an ,
then that node contains sufficient information
to determine the state of the cache-trie when this node was created.
For example, an  contains the corresponding frozen ,
which is used to continue the search.
Thus, the lookup operation does not help a pending operation complete,
and is wait-free.






Implementation.
Figure <ref> shows the pseudocode
of the tail-recursive  subroutine,
which given a , its ,
the current  and the inner node ,
starts by extracting the relevant position bits of the hash-code.
The branching factor of each  is either 4 or 16,
so either 2 or 4 hash-code bits, starting from ,
are taken to compute the entry index  in line <ref>
(⊙ denotes the bitwise-and operation).
The index is used to atomically read the  value
from the  array in line <ref>.
If  is  or 
(i.e. a non-modifiable version of ) in line <ref>,
it means that the hash-code 
does not have a corresponding key in the cache-trie,
so  returns .
If  is an  (line <ref>),
 continues recursively from the next level.
If  is an  (line <ref>),
 checks if the  key is exactly equal to the desired key,
and returns either the corresponding value or .
The remaining cases deal with s and s,
and are covered in lines <ref> to <ref>.























 §.§ Insert Operation


Given a  and a , the  operation
adds a new key-value pair if the cache-trie did not previously contain the key.
Otherwise, the existing key-value pair is replaced.

Summary.
Inserting searches the trie analogous to .
The goal is to find an 
to which a new  can be added,
or an existing  to be replaced.
Once the  is found,
one of the following scenarios occurs.


[label=(*),itemsep=0mm]

  * 
If the corresponding  entry is empty,
the key-value pair is atomically added.
If the entry is occupied by a different key,
then there is a collision.

  * 
If there is a collision, and the  is wide,
i.e. it has 16 slots,
then  creates a new  at the next level.

  * 
Otherwise, if the  is narrow,
i.e. it has only 4 slots,
then  assumes that expanding the 
will resolve the collision.
To correctly expand the narrow ,
 must first prevent subsequent updates to the narrow 
by freezing it <cit.>.
After the narrow  gets frozen (Section <ref>),
its values are copied into the wide .

  * 
It is also possible that the colliding entry is occupied by the same key.
In this case, the existing key-value pair is atomically replaced.
For reasons that will become obvious
once we introduce the cache in Section <ref>,
 uses two  instructions to replace an  –
it first does a  on the  field to announce the new ,
and then another  on the corresponding .


A case that we skip for brevity
is when two different keys map to an identical hash-code.
We resolve such collisions with special list nodes,
similar to the ones used in Ctries <cit.>.





Implementation.
The  subroutine in Figure <ref>
atomically reads the  value from the .
If  is  (line <ref>),
then  handles the case <ref> –
it creates a new ,
and assigns it to the empty slot in line <ref>.


Next, if  is an  (line <ref>),
then  reads its  value (line <ref>)
to check if another transaction is in progress on that .
If  is equal to  (line <ref>),
then  first checks if the  has the currently inserted key.
If so, it proceeds according to the scenario <ref> –
it does a  on the  field in line <ref>
to announce the new ,
and then another  on the  in line <ref>
to commit.



If  is an  and does not contain the same key,
then  checks if the current 
is narrow (line <ref>),
according to the scenario <ref>.
If so,  must replace the current  
with an equivalent wide .
A new  is created to communicate the intention to other threads.
If the  that replaces  in its parent  succeeds
in line <ref>,
then  managed to announce its intention,
and can call the  subroutine, shown shortly.
The insertion then restarts from the same level,
but using the new wide 
that is stored in the  field of the .

Finally, if the current  is already wide (line <ref>),
then  follows the case <ref> –
it creates a new  with
both the   and the new one
(this is done in the  subroutine),
and attempts to replace  with the new 
using the  instructions
in lines <ref> and <ref>.

Coming back to the  field of the  ,
if  contains the  value,
then this indicates that a concurrent expansion froze that 
and further updates are not allowed.
In this case, the search needs to be restarted from the root
to find the  that caused the freeze,
so the  subroutine returns  to communicate this.
Finally, if  contains any other value,
such as an  or an  written by a concurrent insertion,
the current thread simply helps complete that transaction
with a  in line <ref>.

The remaining cases are as follows.
Either  is an ,
in which case  helps complete the concurrent expansion;
or  is an  or an ,
in which case  returns ,
and finds the corresponding  to complete the concurrent expansion.
The user-facing  subroutine checks if insertion returned 
and restarts the insertion from the root if necessary.




 §.§ Freezing and Expansion






After the node is frozen,
it is guaranteed that no operation will ever modify that node again.
A frozen node is effectively immutable,
and can be read and copied without race conditions.
This is important for expanding a narrow .

Summary.
Since all modifications to an  use its  field,
freezing consists of assigning the special value  to .
In the case of an ,
freezing must prevent subsequent modifications
at all the array entries.
The entries are therefore disabled one-by-one.
The  values are replaced with  values,
and child nodes are recursively frozen.

Note that, after freezing of an  starts, and before it ends,
other threads may encounter a frozen entry,
in which case they help complete the freezing,
or see a regular entry,
in which case they modify it.
In either case,
freezing eventually terminates in a lock-free manner.
The linearization point is the last successful modification by another thread.

Expansion implementation.
After insertion adds an  into the cache-trie
to announce the expansion to other threads,
expanding a narrow  into a wide one proceeds in three steps,
as shown in the  subroutine
in Figure <ref>.
First, the narrow  is frozen.

The  subroutine, used to prevent updates to the narrow ,
traverses the entries, and replaces each  with ,
each  with an  wrapper,
and puts the  value
into the  of each .
If  encounters nested s,
it completes those expansions before proceeding.
For s whose  fields are not ,
the pending changes are committed first.

Next, a wide  is allocated,
and the keys of the frozen narrow 
are sequentially transferred in the  subroutine.
The current thread then writes the wide 
to the 's  field in line <ref>.



Finally, the wide  is written into the parent
in line <ref>.




 §.§ Cache Data Structure


The lookup and insert operations
from Sections <ref> and <ref>
run in expected O(log n) time, as shown in Section <ref>.
To improve this,
we augment the cache-trie data structure with an additional data structure,
which we call a cache.
The cache contains references to nodes
close to where most of the keys reside.
Reading an entry from the cache allows skipping
O(log n) levels during the search.
As shown in Section <ref>,
this improves the expected operation running time to O(1).





Summary.
The cache is an array of pointers
to s and s at a specific level.
The core challenge in maintaining the cache
is simultaneously removing the pointer from the array
when the corresponding node is removed from the cache-trie.
Without ensuring this,
a thread could observe a key that had previously been removed.
Using the single word  operations,
it is difficult to efficiently update both the cache and the trie
at the same time
(notably, multi-word  constructions
exist <cit.>,
but they require intermediate object allocation,
more costly than a single ).

To ensure simultaneous eviction,
the cache relies on the following two properties.
First, if an 's  field contains the  value,
then there is a path from the root to that 
(in other words, the cache-trie contains the key).
Second, if an  contains at least a single entry that is not frozen,
then there is a path from the root to that .
Therefore, as soon as an  contains a non- value,
or an  contains a frozen entry,
then the respective node was likely removed,
or is about to be removed.

To conclude, a pointer is entered into the cache lazily,
and after the respective node is added to the trie.
The cache-trie is designed so that the cache eviction is automatic –
if a removed node is read from the cache,
then that node is certainly in a state in which it is known that it was removed.

Data types.
Figure <ref> shows the basic cache trie data types.
The  type alias is defined as an array of pointers.
The first entry is a special  object,
which contains the pointer  to another cache level.
The  chain forms a list of caches, one for each level,
such that the deepest level is at the head of the list.
The  array tracks statistics about cache misses,
as explained in Section <ref>.













Implementation.
A cache-trie lookup uses the subroutine ,
shown in Figure <ref>.
This subroutine reads the cache pointer in line <ref>.
If the cache pointer is ,
the normal  subroutine starts the search from the root.
Otherwise,  traverses the cache chain starting at the deepest level.
At each level,
the value at the appropriate entry is read
(line <ref>).
If the value is a live  (i.e.  is set to ),
then  checks if the keys match or not,
and returns accordingly.
If the value is an ,
then  first checks
if the relevant entry in that  is not frozen,
and then resumes the search.
Otherwise, this process repeats with the next deepest level of the cache.












 §.§ Cache Housekeeping


Summary.
A successful fast search does not update the cache –
since the key is already in the cache, no further actions are necessary
(this is especially important for fast lookups).
To maintain the cache, every slow operation does two things.
First, if it encounters a node at the level
that corresponds to the deepest cache level,
the operation inhabits the cache with that node.
Second, if the operation encounters a level
that is sufficiently far away from the cache,
then it records a cache miss.
If sufficiently many cache misses occur,
then an operation considers adjusting the cache level.

Implementation.
We modify the slow  operation in Figure <ref>.
When  encounters an  or an 
at the same level as the cache
in lines <ref>
and <ref>, respectively,
it calls the  subroutine,
which adds the node to the cache.
When  encounters an 
whose level is not ℓ_c or ℓ_c + 4
in line <ref>,
where ℓ_c is the level of the cache,
it calls the  subroutine
(Section <ref>).





The  subroutine in Figure <ref>
takes the  array,
the new cachee value ,
the hash-code  of the cachee node,
and the cachee level.
The cache-trie does not have a cache when created,
so  first checks if a cache is necessary.
If the cachee level is 12,  initializes the cache at level 8.
If the cache-trie already has a cache
and the cache is at the same level as the cachee,
then  performs a 
in line <ref>.

A  is not necessary,
since the cache need not be entirely consistent.







 §.§ Adjusting the Cache Level with Depth Sampling


Challenge.
The performance improvement from using the cache
is subject to placing it at the optimal level of the trie.
To determine the optimal level,
it is necessary to compute the distribution of keys across levels.
This raises two challenges:


[label=(*),itemsep=0mm]

  * On average, computing the distribution
can take only a small fraction of time
compared to the main operations.

  * It is hard to obtain a sequentially consistent view
of a concurrent data structure
(such as the depths of all its keys).


Summary.
To address the first challenge,
we note that it is not necessary to have an exact key depth distribution –
an approximate distribution is sufficient
to decide about the cache level with high confidence.
To address the second challenge,
we note that the key depth distribution changes are slow.
If we can estimate the distribution during a small enough time window,
then the concurrent operations will not significantly change the key depth.

To estimate the key depth distribution, we rely on periodic depth sampling.
When a fast operation, such as  from Section <ref>,
fails to obtain an  from the cache,
it falls back to a slow search and reports a cache miss.
The thread does not immediately start sampling,
but instead increases a counter.
When the cache miss counter reaches a certain threshold
(in our case, experimentally set to 2048),
it triggers a sampling pass.
The thread picks a random hash-code,
uses it to traverse one path in the cache-trie,
and records the number of s at different levels of that path.
The thread repeats this several times.
Based on this sample, the thread then interpolates the distribution.
Finally, the thread determines the most populated pair of consecutive levels,
and adjusts the cache level if necessary.
Importantly, in this approach,
the sampling overhead is paid less often when the cache is well positioned.
At the same time, sampling is triggered more frequently
if the cache is not well positioned.





Implementation.
Figure <ref> shows the  subroutine.
To decrease contention when counting the misses,
the subroutine uses the  array of the  object –
the counter position is computed from the thread ID.
When the counter reaches ,
a sampling pass gets triggered.
The high-level pseudocode of the sampling pass is shown
in the  subroutine in Figure <ref>.
Note that neither cache miss counting, nor depth sampling, are linearizable.
We found that the lack of consistency is tolerable – in the worst case,
a race condition during sampling could select an incorrect level,
but this is rare, and it gets corrected in the next sampling pass.




 §.§ Other Operations


In the previous sections, we examined the lookup and the insert operations.
For reasons of space, we did not closely examine the remove operation,
which erases a key-value pair from the cache-trie.
The  subroutine is similar to the  subroutine –
it probes the cache, and then searches the cache-trie until
finding an existing .
If the  key matches the specified key,
the  is removed by first setting its  to ,
and then setting the pointer in the parent  to .
A more challenging aspect of the  operation
is removing empty s –
if all the entries of the  are ,
then the  must be reclaimed.
For this reason,  first checks if the affected  is empty.
If it is,  freezes the  to prevent further updates,
and replaces it in its parent.
This is called compression,
and it is similar to expansion from Section <ref>.

Concurrent maps typically provide some additional operations.
For example, JDK also defines ,
which adds a key only if it was previously not in the map,
and , which modifies an existing key-value pair.
Since these operations work on a single ,
they are straightforward modifications
of the  subroutine.



















§ ANALYSIS




 §.§ Running Time


In this section, we show that the expected running time
of the lookup, insert and remove operations is O(1).
The proof relies on establishing the key depth distribution.
This leads to the expected key depth,
and the expected depth of the cache,
and consequently their expected distance.
For reasons of space,
we only list the main theorems in the main part of the paper,
and put the detailed proofs into the appendix.

We define the depth d of a node in the cache-trie as d = ℓ / 4,
where ℓ is the node level.
We say that a key occupies depth d if its  is at the depth d.


Given a universal hash function,
and a cache-trie that contains n + 1 keys,
the probability that an arbitrary key occupies
a position at depth d is:


    p(d, n) = (1 - 16^-d - 1)^n - (1 - 16^-d)^n





Consider a particular key with a hash-code h at the level ℓ.
Each of the hash-code bits of the other keys
is chosen independently at random.
By counting the events in which at least one other key has
the same ℓ-prefix of the hash-code h,
but not the same (ℓ + 4)-prefix, we get:


    p(ℓ, n) =
    ∑_k=1^n nk( 1/16^ℓ/4·15/16)^k
    ( 1 - 1/16^ℓ/4)^n - k


By simplifying this sum, the claim follows.


The function p(d, n) defines a family of depth probability distributions,
each for a specific choice of n.
Next, we show that for sufficiently large n,
most of the keys are expected to
occupy some pair of consecutive levels.


When the number of keys n tends to infinity,
there exists a consecutive pair of levels
for which the probability that a key occupies them
is in the interval ⟨ 0.8745, 0.9746 ⟩.



We define η(d, n) = p(d, n) + p(d, n + 1)
and μ(n) = max_d η(d, n).
We then consider what happens when n →∞.
For the upper bound,
we require ∂μ(n)/∂n = 0.
For the lower bound, we require η(d, n) = η(d + 1, n).


Note that the cache will target
exactly the pair of levels that contains the most keys.
We now know that the cache will cover a large percentage of keys.
We still need to prove that this level is
a constant number of levels away from an average key,
so we determine the expected key depth next.


In a cache-trie that contains n keys,
the expected key depth is E[d](n) = log_16 n + O(1).



From the definition of expectation.


Having the expected key depth,
we can establish the connection to the cache depth.


The expected distance between the cache depth
and the key depth is O(1).



We consider the probability that a key is at
d_1 = log_16 (n) - 2 and d_2 = log_16 n,
and conclude that the most populated pair of consecutive depths
must start between d_1 and d_2.
We know the expected key depth E[d](n)
is O(1) steps away from d_1 and d_2,
so the claim follows.














 §.§ Safety, Linearizability and Lock-Freedom


We first assume that the cache-trie does not use the cache,
and show that the operations are consistent with the semantics of an abstract set.
This helps us identify the  instructions
that are the linearization points,
and establish that the operations are linearizable.
We then show that the operations are lock-free.
Finally, we examine the fast variants of the operations,
which use the cache, and show that they are safe, linearizable and lock-free.
We include the complete proofs in the appendix.


Relation hasKey(n, k) holds if n is an  that contains k,
or if n is an  at level ℓ
whose entry i = hash(k) ℓ length(an)
contains m such that hasKey(m, k).
A cache-trie is consistent with an abstract set 𝔸
iff k ∈𝔸⇔ hasKey(, k).



If a thread reads a single node  at time t_0,
then hasKey(, ) holds at t_0.



If a thread searches for k and reads  from an array node at time t_0,
or if a thread reads a node  at t_0 such that ≠ k,
then hasKey(, k) does not hold at t_0.



 instructions in lines
<ref>,
<ref>,
and <ref> (Figure <ref>),
and in line <ref> (Figure <ref>),
change the abstract set that the cache-trie is consistent with.
The rest of the es do not change the corresponding abstract set.



At all times t, a cache-trie is consistent with some abstract set.
Cache-trie operations are always consistent with abstract set operations.



Cache-trie operations are linearizable.



There is a finite number of execution steps between any two cache-trie modifications,
and there can only be finitely many consecutive modifications
that do not change the corresponding abstract set.



Cache-trie operations are lock-free.



Both fast insert and fast lookup are consistent with the abstract set semantics.
Moreover, fast insert and fast lookup are linearizable and lock-free.





§ EVALUATION


In this section,
we compare the memory footprint and the running time of cache-tries
against the Ctrie implementation
from the Scala standard library <cit.>,
as well as the JDK 8  and .
We also compare against a cache-trie variant
that does not use the cache (abbreviated w/o cache).
 is a concurrent dictionary
with the fastest lookup implementation,
so we use it as a baseline.

We use standard performance evaluation methodologies for the JVM
<cit.>.
We run the benchmarks on a
3.9 GHz Intel i7-4930MX quad-core processor with hyperthreading,
and with frequency scaling turned off.
We use the 4.10.0-32 Linux kernel and Oracle JDK 8,
and we set the heap size to 6 Gb.



Memory footprint.
We start by comparing the memory footprints of various concurrent data structures
in Figure <ref>,
which shows the number of keys on the x-axis,
and the footprint on the y-axis.
Skip lists consume the least memory,
so the multipliers above the bars are normalized against them.
Since the cache duplicates a lot of pointers in the cache-trie,
we would expect a significant increase.
However, it turns out that the increase compared
to the cache-less variant is small, and typically below 10%.

In the corresponding technical report,
we show that most of the keys (>87%) occupy 
some two consecutive levels ℓ and ℓ + 1.
Cache targets level ℓ,
and contains only
≈ 10% of those keys in the best case,
or ≈ 79% of keys in the worst case.
On top of that, the relative overhead of a cache pointer is small.
The increase from those 10%-79% has to be divided by ≈ 5,
because the overhead of a cache pointer is only 1 word,
and the footprint of an SNode is 5 words
(object header, key and value pointers, hash code and the  field).

Cache-tries themselves have a footprint almost identical to Ctries,
and they both take around 50% more memory compared to hash tables.



Single-threaded running time.
Next, we show the single-threaded benchmark results in Figure <ref>.
The lookup benchmark receives a data structure
that already contains N keys (shown on the x-axis),
and then looks up each of the keys once.
The respective running time is shown on the y-axis.
We can see that cache-tries outperform Ctries,
which are up to 7.5× slower than concurrent hash tables.
Skip lists have the worst performance –
they are up to 36× slower
due to a large number of cache misses caused by pointer hops.
Cache-trie lookups themselves are 1.6-2.1× slower than CHM –
the source of the overhead is the extra pointer hop
that a cache-trie undergoes after reading the cache
(most keys are distributed across two consecutive levels,
by Theorem <ref>).

The insert benchmark starts with an empty data structure,
and sequentially inserts N different keys.
For the chosen N,
cache-tries are sometimes up to 20% faster than CHM,
and sometimes 10% slower.
The cache-less variant is within a margin of only 20% –
for these sizes, allocating and replacing the nodes takes longer
than traversing the trie.
Ctries are around 50% slower,
and skip lists are 6× slower than CHM.



Multi-threaded running time.
In Figure <ref>,
we repeat the insertion benchmark with multiple threads,
and for the number of keys 50k, 200k and 600k.
The threads insert the same set of keys,
in the same order, so we expect a high contention.
For N=50k, cache-tries outperform CHM by 10%
when there are 4 or less threads,
and perform equally for more than 4 threads.
At N=200k and N=600k, cache-tries are 10-30% slower.
The slowdown is due to a higher frequency of restarts on the slow path.



Figure <ref>
also shows multi-threaded insertion,
but this time threads operate on disjoint sets of keys.
Here, cache-tries consistently outperform CHM by 30-50% for 100k and 1M keys,
and are up to 20% faster for 10M keys.



Finally, Figure <ref>
shows the multi-threaded version of the lookup benchmark, for 1M keys.
For the same reasons as in Figure <ref>,
cache-tries lookups are up to 60% slower compared to CHM.
Both cache-tries and CHM are much faster than all other
examined data structures.




§ RELATED WORK


The trie data structure was proposed by Briandais
<cit.>
(and later named by Fredkin <cit.>)
as a way to efficiently store and retrieve strings.
The idea of guiding the trie search with hash-code strings,
and using the resulting data structure to implement the dictionary data type,
was mentioned in various forms by at least several authors
<cit.>.
One advantage of hash tries
(not to be confused with hash trees <cit.>)
is to implement immutable dictionaries,
used in functional languages such as Scala, Haskell or Clojure.
A non-blocking concurrent hash trie, called Ctrie,
was first proposed by Prokopec et al. <cit.>
and proven correct <cit.> –
in this design, the keys are stored in external nodes,
and fixed-size hash-code segments are stored
in internal nodes with a branching factor of 32.
In Ctries, synchronization between concurrent operations on different trie levels
is resolved by introducing special I-nodes,
which remain in the cache-trie even when the adjacent level is modified.
This improves concurrency,
but also doubles the number of pointer hops
and increases the average number of cache misses.
Cache-tries eliminate the need for I-nodes in two ways:
first, each inner node has only two possible sizes – 4 and 16.
Second, when an inner node needs to be removed from the trie,
its modifiable locations are set to special non-writable values –
this is similar to the freezing technique
used in SnapQueues <cit.>.

Subsequent research on lock-free tries took several directions.
One of the goals was to provide other non-blocking atomic operations,
such as the atomic two-keys replace operation,
first proposed in the context of Patricia trees <cit.>.
Ctries were extended
with atomic lazy O(1) time snapshots <cit.>,
which allowed implementing linearizable iterators.

On a separate front,
researchers aimed to improve performance
by specializing operations for specific use-cases.
Concurrent tries were found to be useful for tabling
in concurrent Prolog,
where tries store the results of redundant subcomputations.
Areias et al. describe several insert-only implementations
<cit.>,
and show that they are more efficient and scalable
compared to the general counterparts.
Separately, a variant of non-blocking tries
aimed at logging, Bloom filters, and implementing the GC store buffer,
was shown to have a better performance when delete operations are disallowed
<cit.>.
Steindorfer describes a data structure specialization technique
that automatically picks the optimal hash trie tradeoffs for a given program
<cit.>.

Other research on hash tries focused
on improving their performance in general.
In the context of PTries <cit.>,
the authors noted that restructuring the bit string used for the keys
can sometimes improve the running time by a constant factor.
Steindorfer, describes the CHAMP data structure
<cit.>,
which improves the memory footprint of standard immutable hash tries with compression,
and at the same time improves cache locality, but retains the same O(log n) bound.
Tries with O(loglog n) running time bounds were proposed as part of the
SkipTrie data structure <cit.>,
which can be viewed as a hash trie.
To the best of our knowledge,
O(loglog n) is the lowest previously known bound,
and our work is the first concurrent trie design
with a proven expected O(1) running time bound.
In this work, we showed the O(log n) expected hash trie key depth.
Aside from the previous analysis
of the b-trie depth <cit.>,
we are unaware of any prior work on depth bounds in concurrent hash tries.

Besides concurrent hash tries,
many other concurrent data structures were proposed in the past.
Most high-level languages expose a concurrent dictionary implementation –
Java's  (CHM) initially had a lock-based implementation,
which was replaced in JDK 8 with a closed-addressing concurrent hash table
<cit.>,
similar to Maged's original proposal <cit.>.
The JDK 8 CHM also has
a highly optimized, wait-free lookup operation.
Furthermore, the JDK 8 CHM uses a parallel resize operation,
triggered by insertion operations when they run out of space
(this is unlike its pre-JDK 8 counterpart,
which suffered scalability issues in insertions).
In terms of lookup,
the CHM is the most efficient and scalable
concurrent dictionary that we are aware of.
Despite the fact that CHM is a flat data structure
that does not support fast linearizable snapshots
(which makes a direct comparison with tree-like data structures unfair),
we decided to use it as a baseline in our benchmarks.

Click showed an alternative open-addresing implementation <cit.>,
but not as efficient as the JDK 8 hash table
(original Ctries were shown more scalable <cit.>).
Java also exposes ,
a concurrent lock-free skip list implementation
<cit.>.
One of the first concurrent binary search trees was described
by Kung <cit.>,
and a lock-based concurrent AVL-tree is described
by Bronson et al. <cit.>.
The first lock-free binary search tree variant
is described by Ellen et al. <cit.>.
Recently, a dictionary design optimized
for wait-free linearizable scan operations, similar to a B^+-tree,
was proposed by Basin et al. <cit.>.

A good overview of linearizability and lock-freedom,
as well as concurrent data structures,
and other concurrency-related topics is given by Herlihy and Shavit
<cit.>.




§ CONCLUSION


We described a novel concurrent hash trie design,
and extended it with an auxiliary data structure called a cache.
We showed that the resulting data structure
remains linearizable in the presence of the cache,
and that it is lock-free.
Furthermore, we proved that the expected running time of all operations
is bound by O(1),
and we empirically showed that cache-tries improve the performance
of many previously available data structures.
On typical dataset sizes,
lookups are improved up to 5×,
and inserts are improved up to 1.5× compared to Ctries <cit.>.
Due to a vastly lower number of pointer hops in a typical operation,
skip list lookups are outperformed by a factor of 15-22×,
and skip list insertions by a factor of 6×.
It seems likely that cache-tries
outperform most other tree-based concurrent data structures for the same reasons.
Moreover, unlike hash tables, cache-tries do not require resizing
a large underlying array, and this usually gives rise to better scalability.
In particular, cache-tries outperform concurrent hash maps
by a factor of 1.1-2.5× with uncontended parallel insertions,
but exhibit an overhead of up to 1.8× when insertions are contended.

Based on this, can cache-tries completely replace concurrent hash tables?
While the operations of both data structures
run in expected O(1) time,
we observed that our lookup is consistently 1.2-2.0× slower.
The reason for this is that a cache-trie typically needs
two pointer hops to find the key (as implied by Theorem <ref>),
whereas a hash table needs only one.
Also, since cache-tries have about 50% higher memory footprint
compared to concurrent hash tables,
their working set spills out of the cache more frequently,
which results in a higher cache miss rate.
While this overhead may be justified in applications
where lookups are not of paramount importance,
a further investigation is necessary to see
if the cache can achieve better locality,
e.g. by directly caching two levels of the cache at once.
Another deciding factor is the availability of
an efficient linearizable snapshot operation,
which is not available for concurrent hash tables –


it remains to show the exact snapshot implementation for cache-tries.
We plan to investigate these questions in future work.






















§ COMPLEXITY ANALYSIS


In this section,
we show that the expected execution time
of the cache-trie operations is O(1).
The proof consists of establishing the key depth distribution,
and bounding the expected key and cache depths.
From these bounds, we then conclude that the expected distance
from the cache to the key is constant.


Depth d of a key is the number of pointer indirections
required to reach an S-node by following pointers in the A-nodes minus 1,
starting from the root.
Level ℓ in a 16-way cache-trie
is the number of hash code bits used to find the corresponding S-node,
and is defined as ℓ = d · 4.



We say that a key with a specific hash code h
occupies level ℓ or a depth d = ℓ / 4 in a cache-trie
if it has a unique hash code ℓ-prefix in the cache-trie,
but it does not have a unique (ℓ - 4)-prefix.



Given a universal hash function,
and a cache-trie that contains n + 1 keys,
the probability that an arbitrary key occupies
a position at depth d is:


    p(d, n) = (1 - 16^-d - 1)^n - (1 - 16^-d)^n





Consider an arbitrary key x in the cache-trie.
There are n other keys in the cache-trie,
so the key x will occupy the level ℓ
if some non-empty subset of k other keys
has the same ℓ-prefix of the hash code,
but not the same (ℓ + 4)-prefix,
and the other n - k keys have a different ℓ-prefix.

Next, note that, for any given set of keys S,
the cache-trie has the same structure regardless of the order of insertion.
Thus, we can behave as if the key x was the first key inserted into the cache-trie.
The rest of the n keys are then inserted as n independent trials –
each trial is an independent choice of a hash code,
and can either cause a collision
(have the same ℓ-prefix and a different (ℓ + 4)-prefix compared to x),
or not cause a collision (have a different ℓ-prefix compared to x).
Two keys colliding at level ℓ have
ℓ / 4 identical consecutive hash code substrings of length 4,
followed by a different substring of length 4,
so the corresponding probability is 16^-ℓ/4· 15/16.
The probability of a non-collision is 1 - 16^-ℓ/4.
We are interested in those events in which there was at least one collision,
so we count all combinations of k colliding keys, where k ≥ 1.


    p(ℓ, n) =
    ∑_k=1^n nk( 1/16^ℓ/4·15/16)^k
    ( 1 - 1/16^ℓ/4)^n - k


From the identity:


    ∑_k=1^n nk P^k (1-P)^n-k Q^k =
    (1 - P + PQ)^n - (1 - P)^n


we get:


    p(ℓ, n) = (1 - 16^-ℓ/4-1)^n - (1 - 16^-ℓ/4)^n


By Definition <ref>, d = ℓ / 4, and the claim follows.


The probability function p(d, n) is a probability distribution over the depth d,
as shown by the following corollary.


Let a cache-trie contain a fixed number of keys n.
Then p(d, n) is a discrete probability distribution over the depths d.



From the definition of a discrete probability distribution –
the sum of probabilities across all depths is 1:


    ∑_d=0^∞ p(d, n) =   
    (1 - 1/16)^n - 0 +
    (1 - 1/16^2)^n - (1 - 1/16)^n +
    …
    
    =   lim_d →∞[
    (1 - 1/16)^n +
    (1 - 1/16^2)^n - (1 - 1/16)^n + 
       + … +
    (1 - 1/16^d+1)^n
    ]
    = lim_d →∞ (1 - 16^-d-1)^n = 1


Furthermore, p(d, n) is positive
for a non-negative d.


The following plot illustrates the probability p(d, n)
for different cache-trie sizes n, shown on the horizontal axis.
Four different probability curves are shown
for depths d = 0, d = 1, d = 2 and d = 3.
The probability curve for d = 0 is initially close to 1,
but then quickly drops to 0 before reaching 100 keys.
The probability curves for larger depths start at 0,
reach their maximum, and then descend back to 0.
Note that the horizontal axis is logarithmic –
the peeks are roughly exponentially distanced.



  [ 
    xmode=log,
    xlabel=n,
    ylabel=p(d, n),
    y label style=at=(axis description cs:-0.1,0.4),rotate=0,anchor=south,
    axis x line*=bottom,
    axis y line*=left,
    ymin=0.0,
    ymax=1.1,
    xmin=1.0,
    xmax=200000,
    grid=both,
    grid style=
      lightgray!40
    ,
  ]
  [dashed,no markers] gnuplot [domain=1:200000, samples=1000] 
  1.0
  ;

  [smooth,no markers] gnuplot [domain=1:200000, samples=1000] 
  (1.0 - 1.0/16)^x
  ;
  [above] at (1.6, 85) d = 0;

  [smooth,no markers] gnuplot [domain=1:200000, samples=1000] 
  (1.0 - 1.0/256)^x - (1.0 - 1.0/16)^x
  ;
  [above] at (3.8, 80) d = 1;

  [smooth,no markers] gnuplot [domain=1:200000, samples=1000] 
  (1.0 - 1.0/4096)^x - (1.0 - 1.0/256)^x
  ;
  [above] at (6.7, 80) d = 2;

  [smooth,no markers] gnuplot [domain=1:200000, samples=1000] 
  (1.0 - 1.0/65536)^x - (1.0 - 1.0/4096)^x
  ;
  [above] at (9.5, 80) d = 3;
  


The previous plot suggests that
for a given number of keys n contained in the cache-trie,
most keys likely occupy a few adjacent depths.
We will construct a function η(d, n) that captures this notion,
and then use it to construct another function μ(n) that
estimates the proportion of keys contained at the most inhabited
pair of depths.


The η function returns the probability that a key
occupies one of the consecutive depths d or d + 1,
and is defined as follows:


    η(d, n) = p(d, n) + p(d + 1, n)


The μ function returns the probability
that the key occupies the most inhabited pair of consecutive depths:


    μ(n) = max_d η(d, n)




Values of η(d, n) and μ(n) are shown below in the following plot.
It is now more apparent that, for any n,
a large percentage of keys occupies two consecutive depths[
Unfortunately, the arXiv server insists on rendering the Tex files on its own,
and does not accept a PDF.
At the same time, it is unaware of GNUPlot,
and does a poor job rendering some of the images.
For a better version of the images below, see the version of this document
at my homepage.
].



  [ 
    xmode=log,
    xlabel=n,
    ylabel=probability,
    y label style=at=(axis description cs:-0.1,0.5),rotate=0,anchor=south,
    axis x line*=bottom,
    axis y line*=left,
    ymin=0.0,
    ymax=1.1,
    xmin=1.0,
    xmax=225000,
    grid=both,
    grid style=
      lightgray!40
    ,
  ]
  [dashed,no markers] gnuplot [domain=1:225000, samples=1000] 
  1.0
  ;

  [style=line width=15pt,opacity=0.1,no markers] gnuplot [domain=1:225000, samples=1000] 
  0.9245
  ;

  [smooth,densely dashdotted,no markers] gnuplot [domain=1:10000, samples=1000] 
  (1.0 - 1.0/256)^x
  ;
  [above,rotate=-70] at (5.0, 20) η(d = 0);

  [smooth,densely dashdotted,no markers] gnuplot [domain=1:11500, samples=1000] 
  (1.0 - 1.0/4096)^x - (1.0 - 1.0/16)^x
  ;
  [above,rotate=-70] at (7.7, 20) η(d = 1);

  [smooth,densely dashdotted,no markers] gnuplot [domain=1:180000, samples=1000] 
  (1.0 - 1.0/65536)^x - (1.0 - 1.0/256)^x
  ;
  [above,rotate=-70] at (10.5, 20) η(d = 2);

  [smooth,no markers] gnuplot [domain=1:200000, samples=1000] 
  min(x, y) = (x < y) ? x : y
  max(x, y) = (x > y) ? x : y
  max(
    max(
      (x < 1000) ? (1.0 - 1.0/256)^x : 0,
      (x < 10000) ? (1.0 - 1.0/4096)^x - (1.0 - 1.0/16)^x : 0
    ),
    max(
      (x < 100000) ? (1.0 - 1.0/65536)^x - (1.0 - 1.0/256)^x : 0,
      max(
        (x < 150000) ? (1.0 - 1.0/1048576)^x - (1.0 - 1.0/4096)^x : 0,
        (1.0 - 1.0/16777216)^x - (1.0 - 1.0/65536)^x
      )
    )
  )
  ;
  [above] at (11.2, 80) μ;
  


We now substantiate the intuition
that the return values of μ are within a specific interval.


When the number of keys n tends to infinity,
values of μ are inside the interval ⟨ 0.8745, 0.9746 ⟩.



We first prove the upper bound of the interval.
The upper bound must be greater than or equal to
all the maxima of η(n, d).


    0
    =   ∂μ(n)/∂ n =
    ∂η(n, d)/∂ n =
    ∂/∂ n[(1 - 1/16^d+2)^n - (1 - 1/16^d)^n ]
    
    
    =    (1 - 1/16^d+2)^n ln(1 - 1/16^d+2) -
    (1 - 1/16^d)^n ln(1 - 1/16^d)


We get the following set of maxima, parametrized by d:


    n_max(d) =
    (
    lnln (1 - 16^-d)/ln(1 - 16^-d - 2))
    ·(
    ln1 - 16^-d - 2/1 - 16^-d)^-1


We can now compute the value of the maximum when n tends to infinity.
Note that, for a specific d, η(n, d) has a single maximum.
Furthermore, n_max(d) grows monotonically with d.
Consequently, when n tends to infinity, d also tends to infinity.
By puting n_max(d) back into the expression for η(n, d),
and substituting 16^-d = t, we get:













    μ_upper = lim_t → 0 (1 - t/256)^n_max(t) - (1 - t)^n_max(t)


This limit can be easily simplified
(we do not show the steps for brevity),
and we get the following upper bound:


    μ_upper = 2^-8/255 - 2^-2048/255≐ 0.9746


The upper bound is in itself not extremely useful,
since we know that μ≤ 1.
The lower bound is more important,
since it mandates the minimum proportion of keys that are close to the cache.
As seen in the earlier plot for μ(n),
the minimums occur when two η(n, d) curves meet
for two adjacent depths d.
The number of keys n for which this happens
is the solution to the following equation:


    η(n, d + 1) =   η(n, d) 
    
    (1 - 16^-d-3)^n - (1 - 16^-d-1)^n =    (1 - 16^-d-2)^n - (1 - 16^-d)^n


This equation does not have an algebraic solution.
Fortunately, we are only interested in how η behaves asymptotically
for large d.
Substituting x = n · 16^-d, we get:


    lim_d →∞η(n, d + 1) =   lim_d →∞η(n, d) 
    [ √(1/e)]^x -
    [ √(1/e)]^x =   [ √(1/e)]^x -
    [ 1/e]^x


This equation also does not have an algebraic solution,
but we got rid of d, so we can solve it numerically.
The solution x_0 ≐ 34.315 gives us the following lower bound:


    μ_lower = lim_d →∞η(x_0 · 16^d, d) ≐ 0.874553


The solution given above is approximate,
but it can be made arbitrarily precise,
and is greater than 0.8745.


Theorem <ref> implies that there always exists
a depth d such that a large percentage of the keys occupies
the depth d or d + 1.
If the cache data structure targets this depth,
then lookups and updates for those keys take O(1) time.
However, this does not yet prove the O(1) bound on the expected running time –
it is possible that some small percentage of keys
are a non-costant number of levels deeper than the cache.
In what follows, we prove that this is not the case –
all the remaining keys are expected to occupy depths
that are at most a constant number of levels away from the cache,
regardless of the total number of keys n.


The following sum:


    S_1(t) = ∑_j=1^t (1 - 16^-j)^16^t


converges and is less than 1/e - 1 when t tends to infinity.



To show this, we inspect the final term of the sum,
and conclude that it converges to 1/e for large t.
We then bound the sum with a geometric series.


    lim_t →∞ S_1(t) =   lim_t →∞∑_j=1^t (1 - 16^-j)^16^t
     =   lim_t →∞… + (1-16^-t+1)^16^t + (1-16^-t)^16^t
     =   lim_t →∞… + (1-16^-t+1)^16^t - 1· 16 + (1-16^-t)^16^t
     =   … + (1/e)^256 + (1/e)^16 + 1/e
     <   … + (1/e)^4 + (1/e)^3 + (1/e)^2 + 1/e
     =   1/e - 1





The following sum:


    S_2(t) = ∑_j=log_16n^∞[ 1 - (1 - 16^-j)^n ]


converges and is less than 1/e - 1 when n tends to infinity.



We rely on the limit when n tends to infinity to simplify the sum:


    lim_n →∞ S_2(t) =   lim_n →∞∑_k=1^∞[ 1 - (1 - 16^-k - log_16n)^n ]
    
     =   lim_n →∞∑_k=1^∞[ 1 - (1 - 16^-k· 16^-log_16n)^n · 16^k · 16^-k]
    
     =   ∑_k=1^∞ 1 - ( 1/e)^16^-k


We note that e^-k≥ 1 - e^-16^-k when k > 0:


    e^-k≥    1 - e^-16^-k
    
    e^log_16x≥    1 - e^-x         k = -log_16x 
    
    x^(ln 16)^-1≥    1 - e^-x
    
    x ≥    (1 - e^-x)^ln 16


The upper bound for S_2 follows:


    lim_n →∞ S_2(t) ≤∑_k=1^∞ e^-k = 1/e - 1





In a cache-trie that contains n keys,
the expected depth of a key is
bound by Θ(log n).
Moreover, the expected depth is exactly E[d](n) = log_16 n + O(1).



From the definition of the expected value
of a random variable,
for a specific choice of n:


    E[d](n) =   ∑_d=0^∞ d · p(d, n)
    
     =   ∑_d=0^∞ d ·[ (1 - 16^-d-1)^n - (1 - 16^-d)^n ]
    
     =      0 · p(0, n) +
    (1 - 16^-2)^n - (1 - 16^-1)^n
    
       +
    2 · (1 - 16^-3)^n - 2 · (1 - 16^-2)^n
    
       +
    3 · (1 - 16^-4)^n - 3 · (1 - 16^-3)^n + …
     =   lim_d →∞[
    d · (1 - 16^-d-1)^n + ∑_j=1^d (1 - 16^-j)^n
    ]
    
     =   lim_d →∞∑_j=1^d (1 - 16^-d-1)^n - (1 - 16^-j)^n
    
     =   ∑_j=1^∞ 1 - (1 - 16^-j)^n


We separate the last sum into two parts
at j = ⌈log_16n ⌉:


    E[d](n) =
    ∑_j=1^⌈log_16n ⌉[ 1 - (1 - 16^-j)^n ] +
    ∑_     j=⌈log_16n ⌉ +1^∞[ 1 - (1 - 16^-j)^n ]


Consider the first sum,
which consists of ⌈log_16n ⌉ terms.
We use Lemma <ref>
to compute the following lower bound for the expected depth,
noting that the second sum in (<ref>) is always positive
and cannot affect the lower bound:













    E[d](n) ≥∑_j=1^⌈log_16n ⌉ 1 - (1 - 16^-j)^n
    
    
    
    ≥log_16n - 1/e - 1


Coming back to (<ref>),
the first sum is upper bound by ⌈log_16 n ⌉.
The second sum is less than (e - 1)^-1 by Lemma <ref>,
resulting in the following upper bound:


    E[d](n) ≤⌈log_16n ⌉ + 1/e - 1


From (<ref>) and (<ref>),
E[d](n) = log_16n + O(1) follows.



For any cache-trie,
the expected distance between the cache depth
and the key depth is O(1).



To emphasize the fact that we analyze the depths for a fixed number of keys n,
we introduce a helper function η_n(d), defined as follows:


    η_n(d) = η(n, d)


We assume that the cache depth E[d_cache] is chosen
through an unbiased sampling process <cit.>.
By definition, this implies
that the expected sampled value E[d_sample]
of the most inhabited depth pair d
corresponds to the true value of the most inhabited pair.
The sampling strategy and the sample size
influence the variance of the sample,
but not its expected value.


    E[d_cache](n) = E[d_sample](n) = _d ∈ℕ_0η_n(d)


Therefore, the expected cache depth is equal
to the true value of the most inhabited depth.
It remains to show that
the expected key depth
E[d](n) is O(1) levels away from
_d η_n(d), i.e. the most inhabited depth pair.
We will show that the expected cache depth
is at most a small number of steps away from log_16 n.
To do this, we consider how the function η_n(d)
behaves around the value 

d = log_16(n) - 2 when n is large.






















    lim_n →∞η_n(log_16 (n) - 2) =   lim_n →∞[
    (1 - 1/n)^n - (1 - 256/n)^256^-1· n · 256]
    
     =   1/e - ( 1/e)^256≐1/e


Now, consider the expression for the first derivative of η_n:


    ∂η_n(d)/∂ d =    
    n · (1 - 16^-d-2)^n-1· 16^-d-2·ln 16
    
       -
    n · (1 - 16^-d)^n-1· 16^-d·ln 16


The first derivative of η_n(d) is positive at d = log_16 (n) - 2:


    lim_n →∞. ∂η_n(d)/∂ d|_log_16 (n) - 2 =
    [
    1/e - 256 ·( 1/e)^256] ·ln 16 > 0


Similarly, we inspect η_n(d) at d = log_16 n:


    lim_n →∞η_n(log_16 n) =   lim_n →∞[
    (1 - 1/256n)^256n · 256^-1 - (1 - 1/n)^n
    ]
    
     =   ( 1/e)^256^-1 - 1/e≐ 1 - 1/e


The first derivative is negative at d = log_16 n:


    lim_n →∞. ∂η_n(d)/∂ d|_log_16 n =
    [
    1/256·( 1/e)^256^-1  - 1/e] ·ln 16 < 0


We conclude that the value d
for which η_n(d) achieves its maximum value
must be within ⟨log_16(n) - 2,  log_16 n ⟩,
as illustrated by the following plot
(for the purposes of illustration, we picked n = 1000,
but the plot is similar for any choice of n).



  [ 
    xlabel=d,
    ylabel=η_n(d),
    y label style=at=(axis description cs:-0.07,0.4),rotate=0,anchor=south,
    axis x line*=bottom,
    axis y line*=left,
    ymin=0.0,
    ymax=1.1,
    xmin=0.0,
    xmax=4.0,
    grid=both,
    grid style=
      lightgray!40
    ,
    height=6.9cm,
    width=8.9cm,
    xtick=0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0,
  ]
  [dashed,no markers] gnuplot [domain=0:4, samples=1000] 
  1.0
  ;

  [dashed,mark=none] coordinates (2.49, 0) (2.49, 0.63);
  [dashed,mark=none] coordinates (0, 0.63) (2.49, 0.63);
  [dashed,mark=none] coordinates (0.49, 0) (0.49, 0.37);
  [dashed,mark=none] coordinates (0, 0.37) (0.49, 0.37);
  [above] at (280, 2) log_16 n;
  [above] at (100, 2) log_16(n) - 2;
  [above] at (25, 38) ≈ e^-1;
  [above] at (40, 65) ≈ 1 - e^-1;
  [stealth-stealth,mark=none] coordinates (1.20, 0.85) (2.20, 0.85);
  [dashed,mark=none] coordinates (2.20, 0.82) (2.20, 0.96);
  [dashed,mark=none] coordinates (1.20, 0.82) (1.20, 0.96);
  [above] at (325, 65) d ∈ℕ_0η_1000(d);
  [-latex,dashed,smooth,tension=1,mark=none] coordinates (2.55, 0.76) (2.10, 0.78) (1.75, 0.87);

  [style=line width=15pt,opacity=0.1,no markers] gnuplot [domain=0:4, samples=1000] 
  0.9245
  ;

  [smooth,no markers] gnuplot [domain=0:4, samples=1000] 
  (1.0 - 1.0/16^(x+2))^1000 - (1.0 - 1.0/16^(x))^1000
  ;
  [above] at (340, 20) η_1000(d);
  



By Theorem <ref>,
μ(n) = max_d η_n(d) must be within
the interval ⟨ 0.8745, 0.9746 ⟩,
which is above the values 1/e and 1 - 1/e.
The most inhabited depth pair
must therefore also be within the same interval
⟨log_16(n) - 2,  log_16 n ⟩.
Consequently:


    _d ∈ℕ_0η_n(d) = log_16(n) + O(1)


By Theorem <ref>,
the key depth E[d](n) is log_16(n) + O(1).
Therefore, E[d_cache](n) = E[d](n) + O(1).



Expected execution time of cache-trie lookup, insert and remove operations is O(1).



Direct consequence of the Theorem <ref>,
and the fact that the cache-trie operations use the cache to find keys.



The expected memory footprint of a
cache-augmented cache-trie is O(n).



Theorem <ref> implies that
the expected path from the root the key is O(log n).
Therefore, the expected memory footprint must be less
than some complete 16-way tree of depth O(log n), which is O(n).
Furthermore, by Theorem <ref>,
the cache-level is expected to be a constant number of levels away,
so its expected memory footprint is O(n) by the same argument.





§ CORRECTNESS PROOFS


We start by defining some preliminary notions,
and then showing that cache-trie operations are safe.
While proving safety, we develop sufficient foundation
to easily show linearizability as well.
After that, we show lock-freedom.
The proofs assume the absence of the cache extension.
We then prove that, by extending the cache-trie with the cache data structure,
none of the previously proven properties change.

We start with some basic definitions.


A single node ()
is a node that holds a single key and a transactional marker .
For a node sn that holds the key k,
the relation key(sn, k) holds.
An array node ()
is a node that contains a sequence of pointers to other nodes
or  entries.
A narrow array node contains 4 pointers or s.
A wide array node contains 16 pointers or s.
For an array node an,
length(an) is the number of pointers or s that it contains,
and array(an, i) is the the entry at the index i.
A frozen node () is a node that wraps an array node.
For a frozen node fn, unwrap(fn) is the node that it wraps.
A frozen single node () is a marker
that denotes that a single node should not be modified.
A frozen vacant node () is a marker
that denotes that an array node pointer is empty,
and should no longer be modified.
An expansion node () is a node that 
denotes that a narrow array node must be replaced with a wide one,
and it holds a narrow array node, and a corresponding wide array node.
For an expansion node en, unwrap(en) is the narrow array node
that it points to.
Every node n can be assigned to a level ℓ,
and this is denoted as n_ℓ.
Every node n can be additionally assigned to a sequence of bits p,
and this is denoted as n_ℓ,p.



For an array node an_ℓ at level ℓ and an index i,
the pointer child(an, i) is defined as follows:


    child(an, i) = 
    null     array(an, i) ∈{}
    
    cn     cn = array(an, i) ∈
    
    unwrap(fn)     fn = array(an, i) ∈
    
    unwrap(en)     en = array(an, i) ∈
    
    null     array(an, i) ∈


For convenience, we overload the child relation for keys k.
For an array node an_ℓ at level ℓ and a key k,
the pointer forKey(an_ℓ, k) is defined as:


    forKey(an_ℓ, k) = array(an_ℓ, (h ℓ)  length(an_ℓ))


where h = hash(k).

For an array node an and a key k, 
the pointer child(an, k) is defined as:


    child(an, k) = 
    null     forKey(an, k) ∈{}
    
    cn     cn = forKey(an, k) ∈
    
    unwrap(fn)     fn = forKey(an, k) ∈
    
    unwrap(en)     en = forKey(an, k) ∈
    
    null     forKey(an, k) ∈





A cache-trie is a pointer  to a wide array node.
A cache-trie state 𝕊 is the configuration of nodes
reachable from the root by following the pointers of the nodes.
A key k is contained in the state 𝕊
if and only if a single node sn with the key k
is reachable in the corresponding configuration.
We define the relation hasKey(an, k)
for a node n and the key k as follows:


    hasKey(an, k) ⇔
    sn = child(an, k) ∈∧ key(sn) = k 
    
    cn = child(an, k) ∈∧ hasKey(cn, k)





Let ϵ denote an empty sequence of bits,
and an_x,y denote an .
A cache-trie that respects the following invariants is called valid:


INV1
= an_0,ϵ∈∧
length() = 16


INV2
child(an_ℓ,p, i) ∈{ an_ℓ+4,p · i, }∪


INV3
child(an_ℓ,p, i) = sn ∈⇔
hash(key(sn)) = p · i · s



An abstract set 𝔸 is a mapping
𝔸 : K →{⊤, },
where K is the set of all keys,
and which is true for the keys that are present in the abstract set.
Abstract set operations are:



  * lookup(𝔸, k) = ⊤⇔ k ∈𝔸

  * insert(𝔸, k) =
𝔸' : k ∈𝔸' ∧∀ k', k' ∈𝔸⇒ k' ∈𝔸'

  * remove(𝔸, k) =
𝔸' : k' ∉𝔸' ∧∀ k' ≠ k, k' ∈𝔸⇒ k' ∈𝔸'




A cache-trie state 𝕊
is consistent with an abstract set 𝔸
if and only if ∀ k, k ∈𝔸⇔ hasKey(, k).
The cache-trie lookup on the state 𝕊
is consistent with an abstract set lookup
if and only if for all keys k
it returns the value lookup(𝔸, k),
where 𝔸 is consistent with 𝕊.
The cache-trie insert and remove on the state 𝕊
are consistent with an abstract set insert and remove, respectively,
if an only if for all keys k
they change the cache-trie to a new state 𝕊',
such that 𝕊 is consistent with an abstract set 𝔸,
and 𝕊' is consistent with an abstract set 𝔸',
and insert(𝔸, k) = 𝔸', and remove(𝔸, k) = 𝔸',
respectively.


Now that we have the basic definitions in place, we can state and prove
the safety property.


At all times t,
a cache-trie is valid and consistent with some abstract set 𝔸.
Cache-trie operations are always consistent with abstract set operations.


Before proving this theorem, we state and prove several lemmas.


A single node sn is frozen if its  field is set to .
The  is always frozen.
An array node an is frozen if all entries point to frozen nodes. 



A single node's  field is initially set to ,
and changes its value at most once.



By inspecting the source code, we see that every 
is created with  set to ,
and every  on  has  as the expected value.
The claim follows.



If an array node an is frozen at some time t_0,
then ∀ t > t_0 none of the entries of an change their value.
If a single node sn gets removed from its parent at some time t_0,
then its  field was not set to  at time t_0.



From the definition of a frozen array node,
at t_0 all of its entries must be either a , 
or an  with the  field set to .
Next, note that assignments to array node entries occur in  instructions.
By inspecting these  instructions in the pseudocode,
we can see that the expected value is never  or .
Finally, note that when the expected value is an  sn
(lines <ref>,
<ref>
and <ref> in Figure <ref>),
the new value for the respective  is equal to sn's  field.
Assume that such a  succeeds.
By Lemma <ref>,
 must be , since it can change at most once.
That is a contradiction, since none of those  instructions
has  as the expected value.
The argument applies inductively
if an points to nested s.

For the claim about the single node sn,
note that only the  instructions
in lines
<ref>,
<ref>,
and <ref> of Figure <ref>,
and the  in line <ref>
of Figure <ref>,
remove a single node from its parent.
All of those instructions first check, that  is not set to .
From Lemma <ref>,
 could not have changed back to  after the check,
so the claim follows.



Let a call to the  subroutine return at some time t_0.
Then, the array node passed to  is frozen at time t_0.



Assume that the claim holds inductively for every nested ,
and observe an entry at a particular index i.
By analyzing the different cases, we see that the index i gets changed
at the end of the loop iteration in 
only if the respective entry is frozen.
Hence, by the time that the loop in  completes,
the respective array node is frozen.



Let some  instruction make an array node an unreachable at time t_0.
Then, that an was frozen at time t_0.



The  instruction that makes an array node unreachable
is in line <ref>
of the  subroutine in Figure <ref>.
From Lemma <ref>, we know that the expected value
of the  instruction in line <ref>
is a frozen node.



If at some time t_0
a thread reads a node child from an array node an
in line <ref> of Figure <ref>
or in line <ref> of Figure <ref>,
then child is reachable at t_0.



Assume the opposite – that the node child is not reachable at t_0.
Then, by Lemma <ref>,
an was frozen at t_0.
But that is a contradiction, since at t_0
the thread read an array node, not an .



If a thread reads a single node sn at some time t_0 from an array node an,
in line <ref> of Figure <ref>
or in line <ref> of Figure <ref>.
then the relation hasKey(, key(sn))
holds at the time t_0.



From Lemma <ref>,
we know that the single node sn was reachable at time t_0.
The claim follows from the definition of the hasKey relation.



A path π(h) for some hash-code h
is a sequence of nodes from the root to a leaf,
such that:



  * The first node in the path is an_0,ϵ =.

  * ∀ an_ℓ,p∈π(h),
if h = p · i · s
and child(an, i) = cn,
then the next element of the path is cn.

  * ∀ an_ℓ,p∈π(h),
if h = p · i · s
and child(an, i) = null,
then an is the last element of the path.




Let the cache-trie be in a valid state 𝕊.
The path π(h) for some hash-code h = i_0 · i_1 ·…· i_n · s
is finite and has the form
an_0,ϵ an_4,i_0… an_4n,i_0 ·…· i_n x,
where x is either empty or sn ∈.



Directly from the definition and the invariants of the valid cache-trie state.



Let hash(k) = p · i · s for some key k.
Assume that at some time t_0
a thread is searching for a key k
and it reads  from an array node an_ℓ,p
in line <ref> of Figure <ref>
or in line <ref> of Figure <ref>.
Then hasKey(, k) does not hold at time t_0.



By the inductive hypothesis,
cache-trie was valid and consistent at the time t_0.
By Lemma <ref>,
an_ℓ,p is reachable at time t_0.
Now, consider the path
an_0,ϵ→ an_4,i_0→…→ an_ℓ,p
consisting of nodes that the thread traversed while searching for k,
where hash(k) = i_0 · i_1 ·…· i_n · s = p · s.
By Lemma <ref>,
none of those nodes could have been removed from the cache-trie
between the time they were read and the time t_0.
Therefore, by Lemma <ref>,
if the cache-trie state contains the key k,
then the path to the respective single node sn should have the prefix
an_0,ϵ→…→ an_ℓ,p.
To show this, assume by contradiction
that there is a key sn that does not have this path prefix.
This assumption violates the inductive hypothesis that the cache-trie
is valid and consistent.



Assume that at some time t_0
a thread is searching for a key k
and it reads single node  such that k ≠ key(sn).
Then, the relation hasKey(, k) does not hold at t_0.



Similar to Lemma <ref>.



Assume that the cache-trie is valid and consistent with some abstract set.



  * Assume that the  instruction
in line <ref> (Figure <ref>)
succeeds with the expected value  at some time t_1
after  was read from the entry  of the array node 
in line <ref> at time t_0 < t_1.
Then, ∀ t ∈⟨ t_0, t_1 ⟩,
the relation hasKey(, ) does not hold.

Otherwise, if the  instruction in line <ref>
does not succeed,
then there is a duration δ > 0,
such that during ⟨ t_0, t_0 + δ⟩
the relation hasKey(, ) does not hold,
but at t_0 + δ it holds.
At t_0 + δ
either the 
in line <ref> (Figure <ref>)
or the 
in line <ref> (Figure <ref>)
succeeds.

  * Assume that the  instruction
in line <ref> (Figure <ref>)
succeeds with the expected value  at some time t_1
after  was read from the entry  of the array node 
in line <ref> at time t_0 < t_1.
Then, ∀ t ∈⟨ t_0, t_1 ⟩,
the relation hasKey(, ) holds.

Otherwise, if the  instruction in line <ref>
does not succeed,
then there is a duration δ > 0,
such that during ⟨ t_0, t_0 + δ⟩
the relation hasKey(, ) holds,
and continues to hold after t_0 + δ,
but  is not reachable at t_0 + δ.
At t_0 + δ
either the 
in line <ref> (Figure <ref>)
or the 
in line <ref> (Figure <ref>)
succeeds.

  * Assume that the  instruction
in line <ref> (Figure <ref>)
succeeds with the expected value  at some time t_1
after  was read from the entry  of the array node 
in line <ref> at time t_0 < t_1.
Then, there exists some duration δ > 0
such that ∀ t ∈⟨ t_1 - δ, t_1 ⟩,
the relation hasKey(, ) does not hold.




We proceed casewise:



  * 
By Lemma <ref>,
we know that  was reachable at time t_0.
First assume that the  in line <ref> was successful.
Then, the  field of  must have been set to the same value
that  succeeded with.
By Lemma <ref>,
we know that this was the only value that was ever written to .
The conclusion is that  was at the position 
during the interval ⟨ t_0, t_1 ⟩.
Furthermore, by Lemma <ref>,
 is the only single node in the cache-trie
that could hold the key .
Since we check that  is not equal ,
the conclusion is that hasKey(, )
does not hold during ⟨ t_0, t_1 ⟩.

Now assume that the  in line <ref> was not successful.
This means that some other thread helped by committing the  value.
In other words,
there was at least one other  instruction that changed 
between the  in line <ref>
and the  in line <ref>.
By Lemma <ref>,
the first such  instruction must
have been in line <ref> (Figure <ref>)
or in line <ref> (Figure <ref>).

  * 
The reasoning is similar as in the previous case –
the  node must have been present during ⟨ t_0, t_1 ⟩.
This time, since we checked that  is equal to ,
hasKey(, ) holds during ⟨ t_0, t_1 ⟩.
Again, if the  was not successful,
then it means that some other thread helped in commiting the transaction
during ⟨ t_0, t_1 ⟩.

  * Since the  in line <ref> succeeded,
the entry  was  during ⟨ t_1 - δ, t_1 ⟩.
Note that the node  was reachable during ⟨ t_0, t_1 ⟩,
since it was not frozen
(Lemmas <ref> and <ref>).
Therefore, by Lemma <ref>,
the single node with a key  can only appear at ,
and the claim follows.




Assume that the cache-trie is valid and consistent
with some abstract set 𝔸.
Then,  instructions from Lemma <ref>
induce a change into a valid state that is consistent with the abstract set semantics.



Follows directly from Lemma <ref>
and the definition of consistency.



Let the cache-trie be valid and consistent with some abstract set 𝔸.
Assume that one of the  instructions in lines
<ref>,
<ref>,
and <ref>
of Figure <ref>,
or in lines
<ref>,
<ref>,
<ref>,
<ref>,
and <ref>
of Figure <ref>,
succeed.
Then, the cache-trie remains valid and consistent with 𝔸
after those instructions succeed.



From the definition of the hasKey relation,
it is straightforward to see that node of these  instructions
are state-changing.



Cache-trie invariants are always preserved.



From Lemmas <ref> and <ref>.



From Lemmas
<ref>,
<ref>,
<ref>,
<ref> and <ref>,
and Corollary <ref>.



The operations  and  are linearizable.



An operation is linearizable if,
from the perspective of all the threads in the system,
there is a single point in time during the execution of that operation
at which the cache-trie changes consistency.

We already identified the  instructions
that change the consistency in Lemma <ref>.
We also identified the  instructions
that do not change the consistency in Lemma <ref>.
It remains to show that during an execution of any operation,
there is at most one successful state-changing  instruction
that is consistent with the abstract set semantics of that operation.
We consider all successful state-changing  instructions in ,
and show that they either induce a state-change of a concurrent operation,
or they are the last successful state-changing  instructions
in the current operation.



  * It is easy to see that
following a successful 
in lines <ref>,
<ref>,
and <ref>
(Figure <ref>),
the respective  invocation
ends in a finite number of steps
without running any other  instruction.

  * Successful  instructions in lines
in line <ref> (Figure <ref>)
and <ref> (Figure <ref>)
induce a state-change in a concurrent  operation,
since they must occur after the successful  
in lines <ref> or <ref>,
and before the failed 
in lines <ref> or <ref>, respectively.


Finally, note that no code path in  ends the operation
without at least one such successful  operation.



The operations  and  are lock-free.



In each operation, there is a finite number of steps
between two  instructions,
a  instruction and the entry point or a return point.



The only  loop in the pseudocode is in the  subroutine,
which has a finite upper bound, and executes a  whenever
it decreases its counter.

Assume, therefore, that there exists an infinite number of execution steps
caused by recursion in .
The recursion never decreases the cache-trie level,
and retains the same level if and only if a  fails.
We know from Lemma <ref> that each path in the cache-trie is finite,
so the level cannot grow indefinitely.
Thus, there cannot be an infinite number of execution steps without a .



If any  instruction C_0 fails,
then there was a concurrent successful  instruction C_1
on the same memory location
that executed between the time t_r when the expected value for C_0 was read,
and the time t_0 > t_r when C_0 failed.



This can be easily proven by examining all the  instructions
and their expected values. 



From Lemmas <ref>
and <ref>,
it follows that there is a finite number of execution steps
between any two state changes.


A change in the cache-trie state does not imply a consistency change.
For example, when some operation expands a narrow node into a wide node,
the same set of keys remain in the cache-trie.
We therefore need to bound the number of subsequent state changes
that do not cause a consistency change –
we will show that, eventually, a state change must also change
the abstract set that the cache-trie is consistent with.


Given a cache-trie in some state 𝕊,
the transaction potential P(𝕊)
is the number of single nodes whose  field is set to .



Given a cache-trie in some state 𝕊,
the expansion potential E(𝕊)
is the number of narrow array nodes.



Non-consistency-changing  instructions
always either decrease the expansion potential or decrease the transaction potential.



Straightforward, by enumerating the es.



Consider the consistency-changing  instructions,
and all  instructions that cause a decrease
in P(𝕊) + E(𝕊).
There is a finite number of steps between two such instructions.



Assume that consistency-changing  instructions never occur.
By inspecting the remaining state-changing  instructions,
we see that each of them either expands a node (i.e. decreases E(𝕊))
or it announces a transaction (i.e. decreases P(𝕊)).
Therefore, after a finite number of steps,
P(𝕊) + E(𝕊) = 0.
This is a contradiction, since now a consistency-changing  must occur.



From Corollary <ref>
and Lemmas <ref> and <ref> –
since in any cache-trie state, there is a finite number of unfinished transactions
and narrow nodes, there is a finite number of steps between consistency changes.
By Theorem <ref>,
each consistency change corresponds to a completed operation.



A cache node is a node that holds
a pointer to a parent cache,
and an integer array for tracking cache misses.
A cache array is an array of length 2^ℓ + 1,
that contains a cache node at the index 0,
and the remaining entriese are either s or s.
We say that such a cache array is at level ℓ.
A cache is a pointer that is either  or points to a cache array.



A cache array at level ℓ contains pointers
to nodes that are either frozen or have  different than ,
or are reachable and at level ℓ of the cache-trie
(except at the index 0).



Consider the only write to the cache
in line <ref> of Figure <ref>.
The write is preceded by a check that the cache level corresponds
the cachee level.
Any  or  in the cache-trie
that is made unreachable must be frozen by Lemma <ref>,
and frozen nodes are never made reachable once they become unreachable.
Therefore, a reachable node remains at level ℓ of the cache.



Both fast insert and fast lookup are consistent with the abstract set semantics.
Moreover, fast insert and fast lookup are linearizable and lock-free.



We start by considering consistency.
From Lemma <ref>,
we know that a non-frozen node or a single node
whose  is different than 
is reachable in the cache-trie.

Assume that the fast lookup or fast insert calls the normal lookup or insert,
e.g. in line <ref>.
Since the respective array node is reachable,
safety and linearizability follow immediately by the same reasoning
as Theorems <ref> and <ref>.
Since the total number of execution steps is smaller
compared to an execution in which the search started at the root,
lock-freedom follows as well, by Theorem <ref>.

Assume that the fast lookup returns a value
in line <ref>,
or  in line <ref>
of Figure <ref>.
This is preceded by the read of the  field at some time t_0,
in line <ref>.
Since  is  at t_0, the corresponding node is reachable,
and by Lemma <ref>,
the relation hasKey must hold.
Therefore, fast lookup is safe.
The read of the  field is the linearization point,
so fast lookup is linearizable.
Since it takes a finite number of steps to reach that point,
fast lookup is also lock-free.

Finally, consider the case in which the node
read from the cache is frozen or has  different than .
In this case, a fast lookup or a fast insert both fall back to a normal,
so all three properties hold, by Theorems
<ref>, <ref> and <ref>.

















00


















#1     #1#1#1     #1     #1     #1     #1#1          #1#1           







[CochranCochran1977]
        cochran1977sampling
authorpersonW.G. Cochran.
  year1977.
booktitleSampling Techniques.
publisherWiley.
9780471162407
77000728


[ProkopecProkopec2018]
        prokopec18
authorpersonAleksandar Prokopec.
  year2018.
Cache-Tries: Concurrent Lock-Free Hash Tries with
  Constant Time Operations.
(year2018), 11.



[Prokopec, Bagwell, and OderskyProkopec
  et al2011]
        Prokopec2011
authorpersonAleksandar Prokopec, personPhil
  Bagwell, and personMartin Odersky.
  year2011.
booktitleLock-Free Resizeable Concurrent Tries.
publisherSpringer Berlin Heidelberg,
  addressBerlin, Heidelberg, pages156–170.
978-3-642-36036-7

<https://doi.org/10.1007/978-3-642-36036-7_11>


[Prokopec, Bronson, Bagwell, and
  OderskyProkopec et al2012]
        prokopec12ctries
authorpersonAleksandar Prokopec,
  personNathan Grasso Bronson, personPhil Bagwell,
  and personMartin Odersky. year2012.
Concurrent Tries with Efficient Non-blocking
  Snapshots.
(year2012), pages151–160.
978-1-4503-1160-1

<https://doi.org/10.1145/2145816.2145836>





