4 ms·

Since there is a lot of discussion about alternative solutions to the keyword lookup problem I was wondering, why Tries were not mentioned yet. Since the curre

by w23j 8y ago

Since there is a lot of discussion about alternative solutions to the keyword lookup problem I was wondering, why Tries were not mentioned yet. Since the current implementation has to do a string compare after the hash, wouldn't a Trie be at least as fast? Am I missing something? Are there other disadvantages?

krackers 8y ago
Someone else can probably comment better but hashing seems more efficient memory wise than holding the trie in memory, and hashing might probably also better cache-wise compared to jumping between the nodes of the trie.
Someone 8y ago
For the trie, you still would have to do multiple character comparisons (on level 1, on average about 13, I guess, given that I read there are 400 keywords, and 26 characters in the alphabet). Presumably, hashing the string is faster. I think that partly is because it introduces fewer cache misses than walking a trie. Both a this and a trie have to walk the input string, but code using a trie jumps around the trie, while this code only compare to the keyword, stored in contiguous bytes. Another reason might be that trie-based code is worse for branch prediction logic.
- w23j 8y ago
  Regarding your first point: One possible implementation of tries uses an array with length "size of alphabet" to store the children of a node. So at each node it's just an offset into an array, not multiple character comparisons. Of course your other points are valid. Thank you for your answer. So I gather the differences are rather subtle. I was wondering if I was missing something bigger.
  - Someone 8y ago
    Even assuming just a-z, that array will be mostly empty at lower levels, and most nodes are at lower levels. That’s not good for avoiding cache misses. There are tricks to counteract that (you don’t store pointers to lower levels, for example, but offsets, because at typical sizes of a trie you can store them in way fewer bits), and I haven’t timed any implementation for decades, but it would surprise me if such an approach would improve performance on lower levels. You could use it at top level (basically replacing the trie with separate tries for each starting letter) Also, the ‘search for a character in an array’ code can be sped up by using vector instructions nowadays (can’t find a link for the exact code, but http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html may give ideas). Whether want to do that because of power usage concerns is a completely different can of worms.

by w23j 8y ago

krackers 8y ago

Someone else can probably comment better but hashing seems more efficient memory wise than holding the trie in memory, and hashing might probably also better cache-wise compared to jumping between the nodes of the trie.

Someone 8y ago

For the trie, you still would have to do multiple character comparisons (on level 1, on average about 13, I guess, given that I read there are 400 keywords, and 26 characters in the alphabet). Presumably, hashing the string is faster. I think that partly is because it introduces fewer cache misses than walking a trie. Both a this and a trie have to walk the input string, but code using a trie jumps around the trie, while this code only compare to the keyword, stored in contiguous bytes. Another reason might be that trie-based code is worse for branch prediction logic.

w23j 8y ago
Regarding your first point: One possible implementation of tries uses an array with length "size of alphabet" to store the children of a node. So at each node it's just an offset into an array, not multiple character comparisons. Of course your other points are valid. Thank you for your answer. So I gather the differences are rather subtle. I was wondering if I was missing something bigger.
- Someone 8y ago
  Even assuming just a-z, that array will be mostly empty at lower levels, and most nodes are at lower levels. That’s not good for avoiding cache misses. There are tricks to counteract that (you don’t store pointers to lower levels, for example, but offsets, because at typical sizes of a trie you can store them in way fewer bits), and I haven’t timed any implementation for decades, but it would surprise me if such an approach would improve performance on lower levels. You could use it at top level (basically replacing the trie with separate tries for each starting letter) Also, the ‘search for a character in an array’ code can be sped up by using vector instructions nowadays (can’t find a link for the exact code, but http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html may give ideas). Whether want to do that because of power usage concerns is a completely different can of worms.