I'm not exactly sure why your naive trie is performing slower than you'd expect, but it may be because of how you're doing certain things.
For example, your recursive children count uses a mutable return value. I suspect you've done that to try and gain performance, but it doesn't actually gain anything due to a &usize taking up exactly the same amount of space as a usize. Additionally, you're actually hindering yourself because you're forcing everything to be done sequentially. A better implementation might look like this:
fn max_children_count_in_node_recursive(&self) -> usize {
let children = self.children.len();
let childrens_children = self.children.iter()
.map(|(_, child)| child.max_children_count_in_node_recursive())
.sum();
children + childrens_children
}
This then opens you up to being able to swap out the self.children.iter() with par_iter() from rayon and gain parallelism essentially for free.
One reason your true implementation might be slow is simply because a full blown hashmap is probably overkill considering you're expecting at most 26 keys. I imagine saving as a sorted list and doing binary search instead would probably be faster than going through the overhead of hashing.
You could implement your own hashing algorithm, but chances are your performance issues are because of something to do with your algorithm, not the hashing algorithm itself (which I imagine is already quite good).
Also, I noticed you mentioned:
we have to write return because the "fail" in the borrow checker
Usually the borrow checker yells at you because you're doing something wrong. In that case there's probably a better way to do what you're trying to do.
I know this doesn't have much to do with your performance issue, but I feel like each of your methods are doing quite a lot and are quite complex. You may want to pull bits out into helper functions, that way it's easier for you to read, you're less likely to make mistakes, and you don't lose any performance because the optimiser will inline everything.
What runtime error were you getting? If your program panicked then can you print the error message?
This is more of a stylistic thing, but do you have your editor set up to run rustfmt on save? Another really useful tool for checkling you code is to use clippy, it often helps to point out logical errors or ways you could do things more idiomatically.
I'm sorry I couldn't be of more help, I'm on my phone and that makes inspecting code and writing markdown a bit of a pain. The easiest thing to help your performance issue will probably be looking into rayon and checking your algorithms to see if you aren't doing something inefficiently.
EDIT: formatting code snippets is hard
