Performance issues in trie

[franklucky001]

slower than std btreemap use in trie
index map
test tests::bench_trie_insert ... bench: 328,587,285 ns/iter (+/- 95,700,652)
test tests::bench_trie_search ... bench: 267,453,109 ns/iter (+/- 64,762,370)

std btreemap
test tests::bench_trie_insert ... bench: 169,694,058 ns/iter (+/- 21,693,177)
test tests::bench_trie_search ... bench: 133,411,341 ns/iter (+/- 5,039,801)

[cuviper]

What trie implementation is that?

[franklucky001]

@cuviper this is my code https://github.com/franklucky001/pytrie/blob/master/trie_rs/src/lib.rs
and this my bench code https://github.com/franklucky001/pytrie/blob/master/benches/src/main.rs, i just replace btreemap to indexmap in struct TrieNode,and test bench.

[cuviper]

Do you need the insertion-order or indexing properties of IndexMap? Otherwise, the standard HashMap will have more direct memory storage. They're both based on hashbrown's raw table underneath.

One thing jumps out at me in TrieNode::insert:

                node.children.entry(ch).or_insert(TrieNode::default());

That is always creating a default node, even if it's not needed. That includes a default children map, which for hash maps also has to initialize the hasher's random state. I would suggest or_default() instead, which will only create it for vacant entries. More generally, there's also or_insert_with(/* fn or closure */).

---

Your benchmark data has a lot of similar prefixes, which makes sense for testing a trie, but this also means that most of the nodes are going to have a small number of children. The standard library's BTreeMap has a capacity of 11 entries per node, so I think it's likely that most of your children maps are just a single btree node. It's entirely plausible that it could out-perform a hash map at this size, despite the O(log) versus O(1) algorithmic complexity.

[franklucky001]

@cuviper Thank you so much, i well modify the code as you suggest and retest some day :)