A good day to trie-hard: saving compute 1% at a time

Re:A good day to trie-hard: saving compute 1% at a time by alohashirt99 on Wednesday September 11, 2024 @04:54PM (#41515259)

This was an interesting blog - a real world example of tuning Rust code with actual measurements.

I have no experience with Rust so this is a naive question- why not use an array of strings to store these headers?

[ Parent | on HN ]

Re:A good day to trie-hard: saving compute 1% at a time by steveklabnik on Wednesday September 11, 2024 @06:23PM (#41515830)

They did do that at first; the “static Vec” reference is to this. A Vec<T> is a growable array type.

Arrays have O(n) lookup in the worst case, and HashMaps have O(1), as the post mentions. Basically, you have to walk through the entire array of the header you’re looking for is at the end, whereas it’s always cheap with a HashMap. But the trie is even better!

Basically, none of this is Rust specific, it’s just algorithms stuff.

[ Parent | on HN ]