Benching Trie vs BTree

🐟 # Btree
[09:44 AM] dragon ~/dev/jj  ((41522fe1…)|✔)
🐟 /usr/bin/time cargo bench  --bench trie
    Finished bench [optimized] target(s) in 0.08s
     Running benches/trie.rs (target/release/deps/trie-1bda1bec05eafe1c)
trie_20k_iterations     time:   [32.521 µs 32.658 µs 32.817 µs]
                        change: [+0.3833% +1.6295% +3.2871%] (p = 0.01 < 0.05)
                        Change within noise threshold.
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

trie_10k_insertions     time:   [4.9983 ms 5.0116 ms 5.0265 ms]
                        change: [-1.1369% +0.1537% +1.3049%] (p = 0.81 > 0.05)
                        No change in performance detected.
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

trie_20k_insertions     time:   [10.905 ms 10.940 ms 10.980 ms]
                        change: [-2.2062% -1.7759% -1.2906%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  1 (1.00%) high mild
  9 (9.00%) high severe

trie_50k_insertions     time:   [29.845 ms 30.042 ms 30.256 ms]
                        change: [-17.462% -14.496% -11.506%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

Benchmarking trie_200k_insertions: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 24.0s, or reduce sample count to 20.
trie_200k_insertions    time:   [225.82 ms 233.51 ms 241.05 ms]
                        change: [-6.9604% -3.4440% +0.0909%] (p = 0.06 > 0.05)
                        No change in performance detected.

trie_10k_prefixes       time:   [2.8657 ms 2.8803 ms 2.8953 ms]
                        change: [-1.2431% -0.4726% +0.2724%] (p = 0.22 > 0.05)
                        No change in performance detected.
Found 3 outliers among 100 measurements (3.00%)
  3 (3.00%) high mild

trie_20k_prefixes       time:   [5.9439 ms 5.9767 ms 6.0107 ms]
                        change: [-0.8050% -0.0330% +0.7491%] (p = 0.94 > 0.05)
                        No change in performance detected.
Found 2 outliers among 100 measurements (2.00%)
  2 (2.00%) high mild

77.09user 22.37system 1:28.78elapsed 112%CPU (0avgtext+0avgdata 59956maxresident)k
0inputs+0outputs (0major+39749minor)pagefaults 0swaps

Why is "maxresident" so low above and worse below?

[09:46 AM] dragon ~/dev/jj  ((41522fe1…)|✔)
🐟 jj up @-- # Best trie
Working copy now at: f826_991e260 (no description set)
Added 0 files, modified 1 files, removed 0 files
[09:46 AM] dragon ~/dev/jj  ((6e1ce95c…)|✔)
🐟 /usr/bin/time cargo bench  --bench trie
   Compiling jujutsu-lib v0.6.1 (/home/ilyagr/dev/jj/lib)
   Compiling jujutsu v0.6.1 (/home/ilyagr/dev/jj)
   Compiling testutils v0.6.1 (/home/ilyagr/dev/jj/lib/testutils)
    Finished bench [optimized] target(s) in 34.29s
     Running benches/trie.rs (target/release/deps/trie-1bda1bec05eafe1c)
trie_20k_iterations     time:   [515.70 µs 518.78 µs 523.28 µs]
                        change: [+1455.2% +1480.6% +1502.2%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 13 outliers among 100 measurements (13.00%)
  9 (9.00%) high mild
  4 (4.00%) high severe

trie_10k_insertions     time:   [5.2310 ms 5.2463 ms 5.2623 ms]
                        change: [+4.2439% +4.6833% +5.1150%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 13 outliers among 100 measurements (13.00%)
  2 (2.00%) low mild
  9 (9.00%) high mild
  2 (2.00%) high severe

trie_20k_insertions     time:   [10.998 ms 11.034 ms 11.074 ms]
                        change: [+0.3697% +0.8629% +1.3335%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 21 outliers among 100 measurements (21.00%)
  1 (1.00%) low severe
  11 (11.00%) low mild
  3 (3.00%) high mild
  6 (6.00%) high severe

trie_50k_insertions     time:   [34.602 ms 34.798 ms 35.018 ms]
                        change: [+14.764% +15.832% +16.939%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

Benchmarking trie_200k_insertions: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 24.3s, or reduce sample count to 20.
trie_200k_insertions    time:   [238.11 ms 241.66 ms 245.07 ms]
                        change: [-0.1130% +3.4884% +7.3099%] (p = 0.06 > 0.05)
                        No change in performance detected.
Found 16 outliers among 100 measurements (16.00%)
  4 (4.00%) low severe
  8 (8.00%) high mild
  4 (4.00%) high severe

trie_10k_prefixes       time:   [474.66 µs 476.46 µs 478.44 µs]
                        change: [-83.467% -83.360% -83.257%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
  5 (5.00%) high mild

Benchmarking trie_20k_prefixes: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 5.6s, enable flat sampling, or reduce sample count to 60.
trie_20k_prefixes       time:   [1.0979 ms 1.1026 ms 1.1076 ms]
                        change: [-81.666% -81.533% -81.391%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  8 (8.00%) high mild
  2 (2.00%) high severe

303.25user 27.99system 2:11.08elapsed 252%CPU (0avgtext+0avgdata 722172maxresident)k
0inputs+0outputs (157major+957495minor)pagefaults 0swaps
[09:49 AM] dragon ~/dev/jj  ((6e1ce95c…)|✔)

🐟 jj up btree
Working copy now at: 15d8_dc9cf67 (no description set)
Added 0 files, modified 1 files, removed 0 files
[09:54 AM] dragon ~/dev/jj  ((41522fe1…)|✔)
🐟 /usr/bin/time cargo bench  --bench trie
   Compiling jujutsu-lib v0.6.1 (/home/ilyagr/dev/jj/lib)
   Compiling jujutsu v0.6.1 (/home/ilyagr/dev/jj)
   Compiling testutils v0.6.1 (/home/ilyagr/dev/jj/lib/testutils)
    Finished bench [optimized] target(s) in 36.57s
     Running benches/trie.rs (target/release/deps/trie-1bda1bec05eafe1c)
trie_20k_iterations     time:   [34.666 µs 34.931 µs 35.255 µs]
                        change: [-93.042% -92.488% -91.859%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
  1 (1.00%) high mild
  6 (6.00%) high severe

trie_10k_insertions     time:   [5.1658 ms 5.1792 ms 5.1932 ms]
                        change: [-1.6801% -1.2780% -0.8815%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 33 outliers among 100 measurements (33.00%)
  20 (20.00%) low severe
  2 (2.00%) high mild
  11 (11.00%) high severe

trie_20k_insertions     time:   [11.212 ms 11.292 ms 11.395 ms]
                        change: [+1.5133% +2.3399% +3.2372%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 10 outliers among 100 measurements (10.00%)
  6 (6.00%) high mild
  4 (4.00%) high severe

trie_50k_insertions     time:   [30.812 ms 30.997 ms 31.205 ms]
                        change: [-11.741% -10.921% -10.133%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
  8 (8.00%) high mild
  4 (4.00%) high severe

Benchmarking trie_200k_insertions: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 24.1s, or reduce sample count to 20.
trie_200k_insertions    time:   [250.88 ms 253.81 ms 257.90 ms]
                        change: [+3.0186% +5.0277% +7.1786%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 6 outliers among 100 measurements (6.00%)
  2 (2.00%) high mild
  4 (4.00%) high severe

trie_10k_prefixes       time:   [2.8880 ms 2.9069 ms 2.9273 ms]
                        change: [+502.23% +506.53% +511.23%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

trie_20k_prefixes       time:   [5.9328 ms 5.9668 ms 6.0024 ms]
                        change: [+436.63% +440.61% +444.44%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 6 outliers among 100 measurements (6.00%)
  1 (1.00%) low mild
  5 (5.00%) high mild

273.88user 28.65system 2:11.91elapsed 229%CPU (0avgtext+0avgdata 691120maxresident)k
0inputs+0outputs (232major+949944minor)pagefaults 0swaps