Naive trie implementation is slow and fails with large inputs, it uses std::collections::HashMap


#1

Hi!

I’ve started programming Rust in February, so I’m a noob.

I’m programming a navie trie implementation for storing words and then count how many of them have a given prefix.

The program works in the sense that is correct, it gives the correct results but:

  1. Is “slow” and my Hackerrank answer isn’t accepted. I think that it is because of the hashing algorithm for preventing HashDoS attacks. Someone told me that I can implement my own hash myself, but I don’t know how. Keys are simple chars.

  2. With large input like this it has a runtime error, maybe because it uses a lot of memory or I don’t know what.

The code is here

The things I want for you are:

  1. Some sort of tutorial for reading the docs and be capable to use libraries and implement traits.
  2. Help with my Trie problem.

Thanks in advance.


#2

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


#3

Many thanks for your help. I can’t use external crates in Hackerrank, and can’t even use your map/sum funcion because it says it’s unstable.

The clippy program is very nice and I will use it from now. I will edit my gist with rustfmt and I will try tomorrow (it’s dinner time in Spain xD) another solutions to this problem.

I will put tomorrow the backtrace error too, to see what’s happening here.

If anyone knows a tutorial on how to use libraries and implement their traits, like Hasher, I will be happy :grin:


#4

Note that sum has been stable for a while. Unfortunately they are using RUST Version 1.10. .fold(0, |s, x| s + x) should work as well as the .sum()


#5

I just had another look at this and was trying to optimise it. I didn’t really make much headway by changing your code so I used oprofile and you spend loads of time manipulating the hash table.

Rough breakdown:

  • 41.7% in “/src/libstd/collections/hash/table.rs”
  • 23.2% in “/src/libstd/collections/hash/map.rs”, of which
    • 23.5% is spent hashing (_$LT$std..collections..HashMap$LT$K$C$$u20$V$C$$u20$S$GT$$GT$::make_hash::h568057cf703f8d86)
    • 31.2% is spent fetching keys (_$LT$std..collections..HashMap$LT$K$C$$u20$V$C$$u20$S$GT$$GT$::get::h4fb99286e0254e31)

So looks like you’ll probably gain the most by minimising the number of get() calls you make. Otherwise I’d just swap to using a Vec and doing a linear/binary search, a quick O(n) (or O(log n)) algorithm would probably end up faster than a slow O(1) considering you’ve only got at most about 26 elements per trie node.


#6

If the hash is the problem than maybe std::collections::BTreeMap? I mean the real problem is an outdated rustc and no crates.io, but that is what drives innovation I guess.

If it is a fixed number of elements than use a vec<option> with the key being the index (test_char as usize - 'a' as usize)


#7

Wow, a BTreeMap makes a massive difference. On my machine it went from hovering around the 19.8s mark to 8.4s!


#8

Many thanks to all. Now with the fold and the BTreeMap it is “slow” on rust 1.10 but has no memory problems.

I will contact the hackerrank team ASAP and maybe the next rustacean will not come into this. If not, this thread will help him. Cheers.