Introduction
The previous posts discussed some details of my initial adaptive radix tree implementation:
In this post, let’s review the performance against a couple of comparison-based tree data-structures.
Benchmarks
Benchmarks run against the Java SDK’s TreeMap (OpenJDK 14 / 2020-03-17) and fastutil’s Long2ObjectRBTreeMap (8.4.1). I spent very little time on optimising the adaptive radix tree implementation, so it is good to see that it does perform as well as these reference collections. Following the adaptive radix tree design was enough to create a collection that performs well.
Benchmark data can be found at the end of this post.
Points to note:
- As the collection grows in size (i.e. has 16 million keys) the adaptive radix tree does not have the same problems with having a large tree depth, which seems to be problem with the other implementations.
- The same can be said with sparsely populated collections, the performance is better than the other implementations. Perhaps the ArtNode4’s architecture sensitive layout really makes a big difference. It’ll be interesting to review the node type distribution, i.e. the proportion of ArtNode4s v ArtNode16s v ArtNode48s v ArtNode 256s at a later date.
- At the 256k key size, the performance between the collections narrows. Again, it would be interesting to investigate this further.
- The remove performance is consistent across all three implementations.
The benchmarks are:
- get: starts with populating the initial tree collection with a specified number of keys, and then retrieve the specified keys from the tree.
- getCeiling/getFloor: starts with populating the initial tree collection with a specified number of keys, and getCeiling()/getFloor() is called given another population of keys.
- put: starts with an empty collection and then add the specified number of keys to the collection.
- update: starts with a populated collection, and for each key in the collection call put().
- remove: starting with a populated collection, attempt to remove all keys in that collection. Time runs out before the test completes, so the collection never empties.
To Do
- Better separation of duties between the adaptive radix tree and its nodes.
- Better ceiling / floor navigation, if the ceiling or floor entry is not a sibling, then the search starts again from the root with a modified key.
- Extend key type support beyond long types.
- Review the Art node header memory usage.
Appendix
| Benchmark | ART | TreeMap | Long2ObjectRBTreeMap |
|---|---|---|---|
| get-65k | 13,254,126.61 | 6,175,546.45 | 7,344,950.27 |
| get-256k | 4,538,262.30 | 3,136,407.85 | 4,816,847.19 |
| get-16m | 2,721,010.10 | 861,569.75 | 1,172,132.98 |
| getCeiling-65k | 7,468,700.59 | 5,505,394.23 | 3,293,177.30 |
| getCeiling-256k | 3,822,805.23 | 2,763,641.60 | 2,429,067.58 |
| getCeiling-1.6m | 2,758,720.53 | 1,421,706.88 | 1,400,326.46 |
| getFloor-65k | 7,708,700.40 | 5,614,605.97 | 4,576,324.94 |
| getFloor-256k | 3,859,795.54 | 2,858,385.96 | 3,186,495.45 |
| getFloor-16m | 2,709,427.97 | 1,464,912.62 | 1,636,459.64 |
| put-65k | 11,155,414.01 | 6,062,899.65 | 4,800,909.72 |
| put-256k | 4,642,355.26 | 3,171,117.91 | 3,229,927.63 |
| put-16m | 2,786,946.39 | 711,878.07 | 1,591,446.80 |
| update-65k | 11,374,192.82 | 6,145,684.77 | 5,051,957.22 |
| update-256k | 4,571,227.36 | 3,171,689.43 | 3,746,812.01 |
| update-16m | 2,793,331.62 | 873,041.93 | 974,548.49 |
| remove | 1,667,228.49 | 1,681,988.95 | 1,698,690.84 |