6 ms·

The article mentions replacing the python hash-backed dict with a crit-bit tree… Sounds like a good opportunity to try it out with pypy. If it has no drawbacks

• eloff 13y ago
  I can already tell you that no tree can ever compare performance-wise to a well designed hash table (like python's.) "costly string compares" are much cheaper than cache misses. And for class attributes and the like Python doesn't even do the string compares, just a quick pointer compare. cache miss = 100 cycles cache miss + tlb miss = 200 cycles memcmp compares many bytes per cycle, it's clear to see that the cache misses will dominate the runtime, and trees involve O(log(N)) cache misses. A hash table is typically two cache misses. For interned python strings it's only one.
  • optimiz3 13y ago
    "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...
                • 13y ago
      • 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.
  • deleted 13y ago
    [deleted]
• tveita 13y ago
  One issue with that is that dicts can hold any hashable object, not just strings. To get a comparable binary representation for arbitrary types, you need to use the hash method. So now you get the worst of both worlds - a hash call, and a tree lookup, and you need buckets for collisions. You can't special case strings either - non-string objects can be equal to strings.