search

laysakura / trie-rs

Memory efficient trie (prefix tree) library based on LOUDS
https://crates.io/crates/trie-rs
Apache License 2.0
90 stars 10 forks source link

Slow predictive_search() compared to common_prefix_search() #10

Closed laysakura closed 4 months ago

laysakura commented 5 years ago

Many not use recursion.

Benchmarking [302b8e4] Trie::predictive_search() 100 times
Benchmarking [302b8e4] Trie::predictive_search() 100 times: Warming up for 1.0000 s
Benchmarking [302b8e4] Trie::predictive_search() 100 times: Collecting 10 samples in estimated 5.2899 s (275 iterations)
Benchmarking [302b8e4] Trie::predictive_search() 100 times: Analyzing
[302b8e4] Trie::predictive_search() 100 times
                        time:   [18.633 ms 18.806 ms 19.033 ms]
                        change: [-0.8818% +0.9228% +3.2224%] (p = 0.44 > 0.05)
                        No change in performance detected.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild

Benchmarking [302b8e4] Trie::common_prefix_search() 100 times
Benchmarking [302b8e4] Trie::common_prefix_search() 100 times: Warming up for 1.0000 s
Benchmarking [302b8e4] Trie::common_prefix_search() 100 times: Collecting 10 samples in estimated 5.1579 s (935 iterations)
Benchmarking [302b8e4] Trie::common_prefix_search() 100 times: Analyzing
[302b8e4] Trie::common_prefix_search() 100 times
                        time:   [5.3941 ms 5.4524 ms 5.5205 ms]
                        change: [-7.0522% -2.9814% +0.9275%] (p = 0.21 > 0.05)
                        No change in performance detected.
laysakura commented 5 years ago

recursion -> loop

http://d.hatena.ne.jp/sune2/20130129/1359429399

shanecelis commented 4 months ago

This has been fixed. Here's the latest benchmark on v0.3.0.

Benchmarking [ec35136] Trie::predictive_search() 100 times
Benchmarking [ec35136] Trie::predictive_search() 100 times: Warming up for 1.0000 s
Benchmarking [ec35136] Trie::predictive_search() 100 times: Collecting 10 samples in estimated 5.0899 s (880 iterations)
Benchmarking [ec35136] Trie::predictive_search() 100 times: Analyzing
[ec35136] Trie::predictive_search() 100 times
                        time:   [5.7049 ms 5.7427 ms 5.7790 ms]
                        change: [-1.8845% -0.7764% +0.2725%] (p = 0.20 > 0.05)
                        No change in performance detected.