Adaptive Radix Tree Implementation Part 2

Introduction

This post continues on from part 1, going into the ArtNode16 ordered and unordered implementations.

ArtNode16: Ordered v Unordered

While implementing the adaptive nodes, both unordered ArtNode16 and ordered ArtNode16 were considered. Therefore, both were built and tested.

The linear (unordered) ArtNode16 is structured much like an expanded ArtNode4 where look ups are simply a linear scan through the arrays. While the binary search (ordered) ArtNode16 will maintain an ordered array and all looks ups make use of a binary search. Below are the benchmarks for this and some discussion.

Node Comparison

Ordered v Unordered

Benchmark data can be found at the end of this post.

The unordered ArtNode16 implementation performs better on get(), put() and remove(). While the ordered ArtNode16 implementation performs better on getCeiling(), getFloor(), getFirst() and getLast(). It is interesting to see that the get() is faster in the unordered implementation, meaning a linear scan is quicker, taking advantage of modern hardware architecture.

Adaptive Radix Tree (ART) Comparison

Both implementations have their distinct advantages, let’s now test this as part of the adaptive radix tree implementation.

ART with Ordered v Unordered

The unordered implementation performed better in almost all cases. A few things worth noting:

The performance difference is not significant. It is likely the number of nodes of size 5 to 16 is actually a small proportion, therefore not having a large impact on the ART performance. ArtNode4 types are the initial node-type and the leaf node-type, while the end state for a node is ArtNode256 (as the tree becomes more populated). Therefore these two types - ArtNode4 and ArtNode256 - should represent a large proportion of the nodes.
The getFloor() and getCeilng() performance is actually better with the unordered implementation because these methods require quite a few get() calls internally for navigating the tree. get() performance is far better with the unordered implementation.

Summary

The final tree uses the unordered ArtNode16 implementation.

Interface

This is how the interface looks:

public interface ILongARTree<V> {
    V get(long key);
 
    V getCeiling(long key);

    V getFloor(long key);

    boolean contains(long key);

    void put(long key, V leaf);

    V remove(long key);
}

In the next post, the benchmarks for the adaptive radix tree implementation will be presented along-side a couple of comparison-based tree data structures for comparison.

Appendix

Ordered Benchmarks

Benchmark	Ops / sec	Error
get()	45,233,935.63	+/- 273,254.93
getCeiling()	23,735,459.38	+/- 71,920.51
getFirst()	76,753,394.25	+/- 285,424.53
getFloor()	24,167,499.89	+/- 57,742.18
getLast()	76,116,595.24	+/- 270,560.62
putNode()	10,052,060.76	+/- 69,658.14
putValue()	10,691,590.12	+/- 53,436.74
remove()	10,098,550.34	+/- 291,034.06

Unordered Benchmarks

Benchmark	Ops / sec	Error
get()	79,20,470.22	+/- 233,546.04
getCeiling()	12,888,789.68	+/- 37,783.92
getFirst()	29,750,517.94	+/- 120,634.39
getFloor()	12,964,313.61	+/- 31,808.17
getLast()	29,660,908.11	+/- 190,980.38
putNode()	53,820,749.06	+/- 246,225.65
putValue()	106,459,905.50	+/- 308,317.27
remove()	16,162,420.97	+/- 332,097.94

ART with Ordered ArtNode16 v UnorderedArtNode16

Benchmark	ART with Ordered ArtNode16	ART with Unordered ArtNode16	% diff (Ordered v Unordered)
get()	4,553,266.73	4,538,262.30	-0.33%
getCeiling()	11,683,900.38	12,278,661.15	4.84%
getFloor()	12,698,914.17	13,222,819.46	3.96%
put()	4,589,908.61	4,642,355.26	1.13%
update()	4,507,434.78	4,571,227.36	1.40%
remove()	1,643,435.00	1,667,228.49	1.43%

tingh dev blog