search

citahub / cita_trie

Rust implementation of the Modified Patricia Tree (aka Trie).
Apache License 2.0
71 stars 28 forks source link

avoid unnecessarily clone in insert function #18

Closed laizy closed 5 years ago

laizy commented 5 years ago

reduce clone from O(n^2) to O(n) where n is the trie depth.

before:  bench_trie_insert_worst_case ... bench: 202,780,700 ns/iter (+/- 47,220,500)
current: bench_trie_insert_worst_case ... bench:   1,902,175 ns/iter (+/- 161,597)
laizy commented 5 years ago

build failed caused by benchmark case can not allowed on the stable release channel, I will remove this.

yejiayu commented 5 years ago

Cool! But if possible, could you please use https://github.com/bheisler/criterion.rs to add benchmark case？

yejiayu commented 5 years ago

6