michaelsproul / rust_radix_trie

Fast generic radix trie implemented in Rust
https://docs.rs/radix_trie/
MIT License
188 stars 33 forks source link

perf: minor optimizations #69

Closed pdogr closed 2 years ago

pdogr commented 2 years ago

This PR proposes a few optimizations based on comments in the code.

  1. Replace recursive compute_size with an iterative DFS.
  2. Modify replace_value to not check if the new_key is equal to the old_key at the node, as it is called only if either nv.len() == 0 or match_keys returns a KeyMatch::Full which implies that the compared keys match exactly.
  3. Replace rec_remove with an iterative version.
pdogr commented 2 years ago

Closed due to lack of benches. Will reopen this after adding a few benches.

michaelsproul commented 2 years ago

There are a few existing benches here: https://github.com/michaelsproul/rust_radix_trie/tree/master/benches

I think you could just run them on the old vs the new.

Of course, more sophisticated benches would be great too!

Thanks!

pdogr commented 2 years ago

Yes, I found these benches and the performance seems to be similar on them when comparing old vs new.

As the current benches only inserts string types, should we include other datatypes also in the benches?

michaelsproul commented 2 years ago

Could do! Yeah, some byte-array like strings could be interesting. Another thing is that the real bottlenecks may not be the ones identified by the TODOs

pdogr commented 2 years ago

Performance on removal did increase a bit but nothing significant.