forked from martinvonz/jj
-
Notifications
You must be signed in to change notification settings - Fork 0
Benching Trie vs BTree
Ilya Grigoriev edited this page Jan 4, 2023
·
1 revision
🐟 # 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