JigaoLuo
commented
2 years ago Huge Page Layout
Cited from [COADS]
In fact, the order of the recursive subtrees is not important; what is important is that each recursive subtree is laid out in a single segment of memory, and that these segments are stored together without gaps.
The reason I picked 0.08M (80K) Keys is the ART in this setting fits into one 2 MiB Huge Page.
Baseline: Without Huge Page
0.08M (80K) Dense Keys
$ ./ART 80000 0 z 0
Number of huge pages: 1
Number of nodes: 316
node4_num:1| [0]: 1 |
node16_num:0
node48_num:0
node256_num:315 | [1]: 2 | | [2]: 313 |lookup,80000,48.623467
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
50.97, 134.96, 1.57, 0.00, 0.00, 0.00, 0.19, 20.56, 10000000, 2.65, 1.00, 2.48 1M Dense Keys
$ ./ART 1000000 0 z 0
Number of huge pages: 6
Number of nodes: 3924
node4_num:0
node16_num:1 | [Level 0]: 1 |
node48_num:0
node256_num:3923 | [Level 1]: 16 | | [Level 2]: 3907 | lookup,1000000,38.300823
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
64.72, 138.07, 2.81, 0.00, 0.00, 0.00, 0.00, 26.10, 10000000, 2.13, 1.00, 2.480.08M (80K) Sparse Keys
$ ./ART 80000 2 z 0
Number of huge pages: 1
Number of nodes: 39217
node4_num:19964| [2]: 19649 | | [3]: 315 |
node16_num:3302| [2]: 3302 |
node48_num:0
node256_num:129 | [0]: 1 | | [1]: 128 | lookup,80000,21.581766
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
114.68, 147.66, 3.45, 0.00, 0.00, 0.00, 0.93, 46.32, 10000000, 1.29, 1.00, 2.48 Baseline: Random Layout on Huge Pages
0.08M (80K) Dense Keys
lookup,80000,50.506096
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
49.08, 129.95, 1.57, 0.00, 0.00, 0.00, 0.18, 19.79, 10000000, 2.65, 1.00, 2.48 1M Dense Keys
lookup,1000000,40.450459
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
61.29, 133.07, 2.82, 0.00, 0.00, 0.00, 0.00, 24.72, 10000000, 2.17, 1.00, 2.48 0.08M (80K) Sparse Keys
lookup,80000,22.441458
cycles, instructions, L1-misses, LLC-misses, dTLB-load-misses, dTLB-store-misses, branch-misses, task-clock, scale, IPC, CPUs, GHz
110.37, 142.68, 3.45, 0.00, 0.00, 0.00, 0.91, 44.55, 10000000, 1.29, 1.00, 2.48 
The vEB Layout code strongly relies on a binary tree and computes recursively: https://github.com/patmorin/arraylayout/blob/master/src/veb_array.h
However, ART on Huge Pages
For
uint64_tkey:Completness of ART
ART is just hard to be complete. The ART itself is not compare-based and the empty byte slot remains if the corresponding element is not inserted into the index.
The vEB and other compare-based trees can be easily complete if the
Nis matched. Any missing number doesn't hurt the completeness of the index.Height of ART
The max height of
uint64_tkey is 8. There is no direct dependency between depth andN.The height (and complexity) of radix trees depends on the length of the keys but in general not on the number of elements in the tree. Two additional techniques, path compression and lazy expansion, allow ART to efficiently index long keys by collapsing nodes and thereby decreasing the tree height. Figure 17 [ART] shows that the height of ART is less than 10 in TPC-C. Figure 2 and Figure 3 [ART] are also height relevant. [START] reduces ART overall height to improve performance.
Examples
Dense
1M Dense Keys
10M Dense Keys
100M Dense Keys
Sparse
1M Sparse Keys
10M Sparse Keys
100M Sparse Keys
Empirical Knowledge
Dense
Almost all nodes are Node256. The depth of the tree is less than 4. (2^(4*8)=2^32=4294967296=4294M)
Sparse
In Level 0 & Level 1 are all Node256. In the bottom level are almost no Node256. The depth of the tree is more than 4.