4 ms·

"no tree can ever compare performance-wise to a well designed hash table" This is not always true...if you have to hash strings when executing queries, data st

"no tree can ever compare performance-wise to a well designed hash table" This is not always true...if you have to hash strings when executing queries, data structures like TRIEs or naive 256-ary trees may be faster (where the O(strlen) time it takes to hash the string is instead used to walk the tree).

nly 13y ago
It's true that both hashing a string of k bits and a lexicographically compare over k bits is O(k), but the chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache. Memoizing a hash code for a string is pretty cheap also, especially if you only dynamically allocate on the heap for long strings.
- optimiz3 13y ago
  "chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache" So a very common scenario for TRIEs/K-ary trees is for high-speed parsing - basically every byte read off the input transfers you to another state in the state machine. Cache is moot as the state machine/tree is almost always in cache. The key (ha!) is input doesn't need to be cached, nor is any precomputed data required on the input side to be performant.
  - nly 13y ago
    What would you be looking up in a radix tree while parsing? I don't think I've ever written one where prefix operations have been useful.
    - optimiz3 13y ago
      JSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member. Any scenario where you decode {k,v} pairs benefits from this.
      - nly 13y ago
        Why do you need prefixes for that? Sounds like the perfect usecase for a hash table or a precomputed perfect hash function.
        optimiz3 13y ago
        You pay for computing a hash function over directly walking to the next node. EDIT: Here you go. Some work I contributed a while ago when we were using Mongo. Replace hash table with a TRIE, deserialization performance goes up 40%. Because you don't need to decode a string, hash it, and then hit a hash table. https://github.com/mongodb/mongo-csharp-driver/commit/0b78790af8f510d588a2b7d5478f75290a649bf7 https://github.com/mongodb/mongo-csharp-driver/commit/0b7879...
        nly 13y ago
        Perfect hash functions are ridiculously cheap. Completely different beasts to those designed to operate as good hashers for all inputs.
        optimiz3 13y ago
        How so? Perfect hash functions only work when all possible inputs are known.
        sp332 13y ago
        Something odd about that commit message... You know that O(m) is equivalent to 5 * O(m) right? Any constant multiplier will have the same big-O value.
        optimiz3 13y ago
        While it is true that asymptotically 5 * O(m) equals O(m), in practice 5 * O(m) is still 5x slower. EDIT (reply threshold): "That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way." Now you're just being pedantic.
  - eloff 13y ago
    Yeah, that will work, if everything is hot in cache there won't be a big difference between a radix style tree and a hash table. Obviously python doesn't fit that description usually.
- danieldk 13y ago
  Or precompute the hash and store the hash when a string type is immutable. This is what Java does and it gives hash tables an advantage over graphs (trees, automata) in lookups. The advantages of trees lay elsewhere, such as persistence and ordering.
  - nly 13y ago
    If you want persistence (in the functional sense) and ordering I'd rather implement a skip list personally. You can use your existing hash code as a randomiser to determine level promotion. If you're going to keep it around you may as well make use of it. Skip Lists also have the nice property that you can stick a immutable linked list facade on them (since the base layer is fully linked)
  - eloff 13y ago
    Python also does this.

nly 13y ago

It's true that both hashing a string of k bits and a lexicographically compare over k bits is O(k), but the chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache. Memoizing a hash code for a string is pretty cheap also, especially if you only dynamically allocate on the heap for long strings.

optimiz3 13y ago
"chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache" So a very common scenario for TRIEs/K-ary trees is for high-speed parsing - basically every byte read off the input transfers you to another state in the state machine. Cache is moot as the state machine/tree is almost always in cache. The key (ha!) is input doesn't need to be cached, nor is any precomputed data required on the input side to be performant.
- nly 13y ago
  What would you be looking up in a radix tree while parsing? I don't think I've ever written one where prefix operations have been useful.
  - optimiz3 13y ago
    JSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member. Any scenario where you decode {k,v} pairs benefits from this.
    - nly 13y ago
      Why do you need prefixes for that? Sounds like the perfect usecase for a hash table or a precomputed perfect hash function.
      - optimiz3 13y ago
        You pay for computing a hash function over directly walking to the next node. EDIT: Here you go. Some work I contributed a while ago when we were using Mongo. Replace hash table with a TRIE, deserialization performance goes up 40%. Because you don't need to decode a string, hash it, and then hit a hash table. https://github.com/mongodb/mongo-csharp-driver/commit/0b78790af8f510d588a2b7d5478f75290a649bf7 https://github.com/mongodb/mongo-csharp-driver/commit/0b7879...
        nly 13y ago
        Perfect hash functions are ridiculously cheap. Completely different beasts to those designed to operate as good hashers for all inputs.
        optimiz3 13y ago
        How so? Perfect hash functions only work when all possible inputs are known.
        sp332 13y ago
        Something odd about that commit message... You know that O(m) is equivalent to 5 * O(m) right? Any constant multiplier will have the same big-O value.
        optimiz3 13y ago
        While it is true that asymptotically 5 * O(m) equals O(m), in practice 5 * O(m) is still 5x slower. EDIT (reply threshold): "That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way." Now you're just being pedantic.
- eloff 13y ago
  Yeah, that will work, if everything is hot in cache there won't be a big difference between a radix style tree and a hash table. Obviously python doesn't fit that description usually.
danieldk 13y ago
Or precompute the hash and store the hash when a string type is immutable. This is what Java does and it gives hash tables an advantage over graphs (trees, automata) in lookups. The advantages of trees lay elsewhere, such as persistence and ordering.
- nly 13y ago
  If you want persistence (in the functional sense) and ordering I'd rather implement a skip list personally. You can use your existing hash code as a randomiser to determine level promotion. If you're going to keep it around you may as well make use of it. Skip Lists also have the nice property that you can stick a immutable linked list facade on them (since the base layer is fully linked)
- eloff 13y ago
  Python also does this.