3 ms·

Crit-bit trees are great but they're not silver-bullet: like every tree structure, even in the lucky case a search can cause O(log n) cache misses, while a good

by ot 15y ago

Crit-bit trees are great but they're not silver-bullet: like every tree structure, even in the lucky case a search can cause O(log n) cache misses, while a good hash table needs just one or two. Also, as pointed out in another comment, it is not necessarily balanced (like red-black trees) and there are some real-world datasets where crit-bit (or Patricia) trees behave poorly, for example URLs. I myself have seen Patricia trees with height greater than 100, for sets of URLs where log n ~ 30. According to VTune, most time in searches was spent in cache misses.

fmap 15y ago
That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore, without ordering the implementation is trivial. At the same time you will not need rehashing once the table "fills up" and since you use don't discard bits from the hash function the expected number of collisions after inserting n elements with a 32 bit hash is n / 2^32 - or 0 for reasonable values of n. Additionally you can use clustering (e.g. build a crit-nibble tree, with 16 pointers per node - one 64 byte cache line) to reduce the number of cache misses. This can backfire spectacularly unless the data is essentially random, so the hashing step remains important. It may not be a silver bullet, but there are some interesting trade-offs.
- ot 15y ago
  That is true but you lose some of the most important properties of crit-bit trees, ordered operations. If the data structure is unordered, I don't see any reason why it should be better than a normal hash table.
  - fmap 15y ago
    The data structure is not better than a normal hash table. It is a different trade-off. For instance, you don't have to do a rehashing step, which is important for real time applications. Memory usage is also very deterministic at 2*(n-1) words in an n element table (with 2 words per node). If none of this matters to you and you merely want a map with fast lookups then a simple hash table is probably a better choice.
- jbapple 15y ago
  The string b-tree also does trie-like search without sacrificing balance: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5939 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.59...

by ot 15y ago

fmap 15y ago

That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore, without ordering the implementation is trivial. At the same time you will not need rehashing once the table "fills up" and since you use don't discard bits from the hash function the expected number of collisions after inserting n elements with a 32 bit hash is n / 2^32 - or 0 for reasonable values of n. Additionally you can use clustering (e.g. build a crit-nibble tree, with 16 pointers per node - one 64 byte cache line) to reduce the number of cache misses. This can backfire spectacularly unless the data is essentially random, so the hashing step remains important. It may not be a silver bullet, but there are some interesting trade-offs.

ot 15y ago
That is true but you lose some of the most important properties of crit-bit trees, ordered operations. If the data structure is unordered, I don't see any reason why it should be better than a normal hash table.
- fmap 15y ago
  The data structure is not better than a normal hash table. It is a different trade-off. For instance, you don't have to do a rehashing step, which is important for real time applications. Memory usage is also very deterministic at 2*(n-1) words in an n element table (with 2 words per node). If none of this matters to you and you merely want a map with fast lookups then a simple hash table is probably a better choice.
jbapple 15y ago
The string b-tree also does trie-like search without sacrificing balance: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5939 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.59...