# Chapter 13 experiment summary

- Measurement rows: 1740
- Out-of-place correctness: PASS
- In-place correctness: PASS
- Active single-node tree rows: 108
- All active single-node trees are valid connected trees.
- The synthetic DTree probe directly compiles src/graph/trees.cc.

## Stability repeat

The original N=3, Ring, 1 MiB group contained one 316.10 us first-cycle
outlier among nine 57.53-57.96 us samples. A separate two-process, 40-sample
repeat preserved the original data and produced:

| N | algo | bytes | samples | median us | P95 | CV | min | max | >2x median |
|---:|---|---:|---:|---:|---:|---:|---:|---:|---:|
| 3 | Ring | 1048576 | 40 | 60.885 | 61.391 | 0.52% | 60.410 | 62.190 | 0 |

## Winner segments

| N | winner | start B | end B | points | median margin | max margin |
|---:|---|---:|---:|---:|---:|---:|
| 2 | Ring | 4 | 8192 | 12 | 13.61% | 18.01% |
| 2 | Tie | 16384 | 32768 | 2 | 2.24% | 3.97% |
| 2 | Tree | 65536 | 1048576 | 5 | 6.15% | 7.35% |
| 2 | Tie | 2097152 | 1073741824 | 10 | 0.82% | 3.58% |
| 3 | Ring | 4 | 2048 | 10 | 11.80% | 15.87% |
| 3 | Tie | 4096 | 131072 | 6 | 0.82% | 4.73% |
| 3 | Ring | 262144 | 1073741824 | 13 | 51.12% | 125.94% |
| 4 | Ring | 4 | 8192 | 12 | 9.35% | 20.05% |
| 4 | Tie | 16384 | 16384 | 1 | 3.84% | 3.84% |
| 4 | Ring | 32768 | 1073741824 | 16 | 60.60% | 149.57% |

## Selected performance points

| N | algo | bytes | median us | P95 | CV | busbw |
|---:|---|---:|---:|---:|---:|---:|
| 2 | Ring | 4 | 18.500 | 19.108 | 1.64% | 0.00 |
| 2 | Ring | 4096 | 19.700 | 20.481 | 1.72% | 0.21 |
| 2 | Ring | 1048576 | 55.285 | 55.446 | 0.25% | 18.96 |
| 2 | Ring | 67108864 | 1570.665 | 1571.227 | 0.02% | 42.73 |
| 2 | Ring | 1073741824 | 24689.800 | 24692.250 | 0.00% | 43.49 |
| 2 | Tree | 4 | 21.755 | 22.021 | 0.59% | 0.00 |
| 2 | Tree | 4096 | 22.080 | 22.199 | 0.29% | 0.19 |
| 2 | Tree | 1048576 | 52.290 | 52.509 | 0.20% | 20.05 |
| 2 | Tree | 67108864 | 1574.125 | 1575.072 | 0.03% | 42.63 |
| 2 | Tree | 1073741824 | 24807.750 | 24813.990 | 0.02% | 43.28 |
| 3 | Ring | 4 | 24.925 | 25.131 | 0.48% | 0.00 |
| 3 | Ring | 4096 | 28.690 | 29.519 | 1.35% | 0.19 |
| 3 | Ring | 1048576 | 57.690 | 199.937 | 92.76% | 24.23 |
| 3 | Ring | 67108864 | 1076.765 | 1077.956 | 0.08% | 83.10 |
| 3 | Ring | 1073741824 | 16861.950 | 16871.925 | 0.03% | 84.91 |
| 3 | Tree | 4 | 28.880 | 29.026 | 0.36% | 0.00 |
| 3 | Tree | 4096 | 29.320 | 29.470 | 0.32% | 0.19 |
| 3 | Tree | 1048576 | 84.940 | 85.674 | 0.70% | 16.46 |
| 3 | Tree | 67108864 | 1662.215 | 1663.205 | 0.06% | 53.84 |
| 3 | Tree | 1073741824 | 25462.950 | 25513.100 | 0.12% | 56.22 |
| 4 | Ring | 4 | 30.375 | 30.791 | 0.71% | 0.00 |
| 4 | Ring | 4096 | 34.215 | 34.935 | 1.14% | 0.18 |
| 4 | Ring | 1048576 | 60.960 | 61.859 | 0.83% | 25.80 |
| 4 | Ring | 67108864 | 851.840 | 853.956 | 0.14% | 118.17 |
| 4 | Ring | 1073741824 | 13046.350 | 13054.240 | 0.08% | 123.45 |
| 4 | Tree | 4 | 36.465 | 36.851 | 0.63% | 0.00 |
| 4 | Tree | 4096 | 36.945 | 37.047 | 0.20% | 0.17 |
| 4 | Tree | 1048576 | 93.080 | 94.153 | 0.50% | 16.90 |
| 4 | Tree | 67108864 | 1477.910 | 1479.941 | 0.11% | 68.11 |
| 4 | Tree | 1073741824 | 20888.900 | 20902.120 | 0.05% | 77.10 |

## Active tree shapes

| N | ch | root | depth | max arity | chain | order |
|---:|---:|---:|---:|---:|---:|---|
| 2 | 0 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1-0 |
| 2 | 2 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 3 | 1 | 1 | 1 | 1 | 1-0 |
| 2 | 4 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 5 | 1 | 1 | 1 | 1 | 1-0 |
| 2 | 6 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 7 | 1 | 1 | 1 | 1 | 1-0 |
| 2 | 8 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 9 | 1 | 1 | 1 | 1 | 1-0 |
| 2 | 10 | 0 | 1 | 1 | 1 | 0-1 |
| 2 | 11 | 1 | 1 | 1 | 1 | 1-0 |
| 3 | 0 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 1 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 2 | 0 | 2 | 1 | 1 | 0-2-1 |
| 3 | 3 | 0 | 2 | 1 | 1 | 0-2-1 |
| 3 | 4 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 5 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 6 | 0 | 2 | 1 | 1 | 0-2-1 |
| 3 | 7 | 0 | 2 | 1 | 1 | 0-2-1 |
| 3 | 8 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 9 | 0 | 2 | 1 | 1 | 0-1-2 |
| 3 | 10 | 0 | 2 | 1 | 1 | 0-2-1 |
| 3 | 11 | 0 | 2 | 1 | 1 | 0-2-1 |
| 4 | 0 | 0 | 3 | 1 | 1 | 0-1-2-3 |
| 4 | 1 | 0 | 3 | 1 | 1 | 0-1-2-3 |
| 4 | 2 | 0 | 3 | 1 | 1 | 0-2-1-3 |
| 4 | 3 | 0 | 3 | 1 | 1 | 0-2-1-3 |
| 4 | 4 | 1 | 3 | 1 | 1 | 1-0-3-2 |
| 4 | 5 | 1 | 3 | 1 | 1 | 1-0-3-2 |
| 4 | 6 | 0 | 3 | 1 | 1 | 0-1-2-3 |
| 4 | 7 | 0 | 3 | 1 | 1 | 0-1-2-3 |
| 4 | 8 | 0 | 3 | 1 | 1 | 0-2-1-3 |
| 4 | 9 | 0 | 3 | 1 | 1 | 0-2-1-3 |
| 4 | 10 | 1 | 3 | 1 | 1 | 1-0-3-2 |
| 4 | 11 | 1 | 3 | 1 | 1 | 1-0-3-2 |

## Source DTree construction

| nodes | mode | roots | depths | internal overlap |
|---:|---|---|---|---|
| 1 | trivial | 0/0 | 0/0 | - |
| 2 | mirror | 0/1 | 1/1 | - |
| 3 | shift | 0/1 | 2/2 | 0 |
| 4 | mirror | 0/3 | 2/2 | - |
| 5 | shift | 0/1 | 3/3 | 0 |
| 6 | mirror | 0/5 | 3/3 | - |
| 7 | shift | 0/1 | 3/3 | 0 |
| 8 | mirror | 0/7 | 3/3 | - |
| 9 | shift | 0/1 | 4/4 | 0 |
| 10 | mirror | 0/9 | 4/4 | - |
| 11 | shift | 0/1 | 4/4 | 0 |
| 12 | mirror | 0/11 | 4/4 | - |
| 13 | shift | 0/1 | 4/4 | 0 |
| 14 | mirror | 0/13 | 4/4 | - |
| 15 | shift | 0/1 | 4/4 | 0 |
| 16 | mirror | 0/15 | 4/4 | - |