search

derekparker / trie

Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.
MIT License
761 stars 115 forks source link

Significant improvement in all benchmarks #22

Closed jsign closed 5 years ago

jsign commented 5 years ago

The collect method was doing too much allocations, and we could take advantage of the calculated depth per node.

Here are the before/after benchmarks:

benchmark                   old ns/op     new ns/op     delta
BenchmarkTieKeys-8          5116          4569          -10.69%
BenchmarkPrefixSearch-8     399301        286591        -28.23%
BenchmarkFuzzySearch-8      5985155       5120769       -14.44%

benchmark                   old allocs     new allocs     delta
BenchmarkTieKeys-8          56             29             -48.21%
BenchmarkPrefixSearch-8     5548           1494           -73.07%
BenchmarkFuzzySearch-8      47089          15004          -68.14%

benchmark                   old bytes     new bytes     delta
BenchmarkTieKeys-8          840           756           -10.00%
BenchmarkPrefixSearch-8     71613         52985         -26.01%
BenchmarkFuzzySearch-8      794541        623999        -21.46%