It might sound strange for me to call hashing an art. After all, it’s about the most fundamental data structure we’ve got, after arrays, linked lists, and binary trees. It’s been studied extensively for fifty years. What amount of “art” could possibly be left in such a topic?
I’ve learned to anticipate that there are dark and unstudied corners in even the most fundamental computer science topics. And hashing appears to be no exception. I’m investigating hashing at the moment because I need hash tables in a few places for my rapidly-developing Protocol Buffers implementation pbstream. So I wanted to take a quick survey of the state-of-the-art in hash tables, and implement a minimal hash table that suits my needs.
What are my needs? If someone defines a protobuf like so:
message Person {
required string name = 1;
required int32 id = 2;
optional string email = 3;
}
…I need to build two hash tables for looking up fields: one keyed by number (1, 2, 3) and one keyed by name (name, id, email).
You might say “why not just use an array for looking up fields by number?” Indeed that’s what I’ll do in most cases, but field numbers can be as large as 2**27 and needn’t be allocated densely. So gracefully degrading to a hash table is important (one practical reason why the field numbers might not be dense is if the client is using extensions). To get the best of both worlds I’ll follow Lua’s lead and have the field number table be a hybrid array/hashtable, where the size of the array part is such that it’s at least half full.
My usage pattern for these hashtables is that I’ll build them once (when I parse a .proto file), then do lookups in the critical path of parsing. So insert time is practically irrelevant, but lookup time is extremely important, because it’s in my critical path. I’ll gladly trade some memory for fast lookups.
So I figured I’d take a few hours to discover the state-of-the-art in hashtables, implement that, and be on my merry way. Unfortunately there doesn’t seem to be much agreement about what the state of the art even is!
Let’s start with even the simple and most basic question: how big should a hashtable be? The literature differs here: some of it claiming that hashtables should have sizes that are prime numbers and some saying they should be powers of two.
But once you’ve decided that, you’ve only just entered the jungle of collision-resolution strategies. There are a lot of them, and it’s not at all clear to me that the trade-offs are well understood. A list of ones I’ve come across, and my current understanding of what they mean:
- linear probing: if your hash function is h(k), then a collision in T[h(k)] means you should also try T[h(k)+i] for i=1 to some limit.
- quadratic probing: like linear probing, but also throw in a T[h(k) + i + j^2], to spread it out a little.
- double hashing: like linear probing, but you scale the jumps by another hash function: T[h(k) + g(k)*i].
- chaining: all entries that collide are in a linked list, so for lookups you search this list. chaining can be either internal (table entries have both values and links, links point to other locations in the table) or external (table is just pointers to the head of linked lists, inserts always allocate a new node).
- cuckoo hashing: Wikipedia makes this sound like hashing’s best-kept-secret. You use two hash functions: if you do an insertion and the spot you want is taken, you kick whatever was already there out and put it in its alternate spot.
- two-way chaining: use two hash functions (like cuckoo and double hashing), but you use the two hash values to find the two possible chains the value could be in.
Few papers seem to offer a comprehensive account of the trade-offs between these. Some authors claim that linear probing is best on modern CPUs because of excellent locality (cache-friendly), but this paper [PDF] takes exception to that claim, saying that the better overall performance of double-hashing negates the cache effects. And indeed, none of the real-world implementations I found use linear probing.
A quick survey of mainstream hashing implementations shows that they can’t agree on what’s best either.
- Lua uses internal chaining with powers-of-two table sizes and “Brent’s variation” (so-named because of a 1973 paper called Reducing the retrieval time of scatter storage techniques — so much for caching-conscious schemes).
- Ruby uses internal chaining with prime table sizes.
- Python uses a custom probing scheme. You have to read the comments in the source file itself — they do more to make hashing sound like black magic than I possible could.
- Perl appears to use external chaining, but its code is a bit hard to follow.
Even if you decide on a collision strategy, you still have to decide on a hash function, and there are surprises lurking for you there as well. Conventional wisdom about hashing is that you want a hash function that randomly distributes the inputs to the outputs. But Python and Lua both hash integers to themselves (so h(5) = 5)!
There are just a dizzying number of variations on hashing. Given my relatively simple use case (one-time construction, lookup speed trumps all) you’d think there would be a clear and obvious answer. But I don’t see one.
Given my deep respect for Lua’s implementation, I’m tempted to just start with that and worry about trying to optimize it later. I’m slightly disconcerted with its focus on getting good performance even when the table is quite full, because as I mentioned for my use case I’ll gladly trade modest amounts of RAM for faster lookup. At least it’s someplace to start.
But seriously, who knew that hash tables had so many variations, with no clear winner?
I’m curious, what made you decide to write a streaming protobuf implementation, versus sending a stream of protobufs embedded in another format?
Hey, uh, if lookup speed really trumps *all*, then I speculate that you should probably compile each set of keys into a machine-code subroutine expressing a balanced binary tree. The routine will contain N-1 compare-and-conditional-jump pairs for N keys, plus N key comparisons if it’s important to return an error when the key isn’t actually in the table. An immediate-compare-and-conditional-jump is 7 bytes on the x86, so about 9 of them fit into a 64-byte L1 cache line, and you execute 2 lg(N) + 4 or so instructions to look up one of N keys. (Possibly you’ll occasionally have an additional memory access to fetch another four bytes of the key, but I’m assuming not.) So if you have, say, 100 keys, you execute 16 or 18 instructions (and perform no memory accesses) to look one up and return the associated value.
A really straightforward way to implement this strategy (for integer keys) is to generate a C file with a switch statement in it, use GCC to compile it to a shared library, and then dlopen the shared library in order to call into it. (Alternatively you could use LLVM or GNU Lightning.)
The nearest hashing equivalent is “perfect hashing”, where you search for a hash function that hashes each key into a distinct bucket in a minimal-size hash table. gperf is a widely-available perfect-hash generator. I haven’t measured and so I don’t know which one of these is faster.
@Brian: there are many, many reasons that I hope to write up at some point. Basically I’m trying to implement protobufs in layers, where the lowest layer is blindingly fast and flexible. Say you have large protobufs (which a lot of people already do) and you want to just pull out the first value for field X. Existing protobuf libraries will make you parse the whole protobuf, copy it all into a separate data structure (malloc is expensive), just to get that one value! Mine will let you scan the protobuf for that value, and stop parsing when you find it.
@Kragen: I should have said “lookup speed trumps all within the constraint that I don’t know the table at compile time. One of the things I’m trying to deliver is a Python API that doesn’t require you to build a C extension for each different proto type you want to parse (ick!).
I’m considering adding a JIT using LLVM or similar sometime in the future — if I do that then I could do what you say.
It’s actually pretty easy to use GCC and dlopen as your JIT; see http://lists.canonical.org/pipermail/kragen-hacks/2003-February/000364.html for a Python example. It does build a C extension for each arithmetic expression, but that happens automatically and transparently, and it only takes about a second on the really old machine I was using then. With a little more work (making a version of Python.h that doesn’t depend on the system header files, and provides just the definitions you need for the generated extensions, you could probably get it down below 10ms on a modern machine.
But if you’re calling this hash lookup from Python anyway, it’s silly to worry about any of the micro-efficiencies you’re talking about. Just use Python’s dict; you might be able to do epsilon better, but that will be swallowed up by the bytecode dispatch overhead and function call and return (on the order of 30-300 instructions per bytecode).
BTW, you left out a slight variation of linear probing: you make each hash bucket big enough to contain more than one item. Of course this doesn’t save you from having to deal with the case for where the entire hash bucket fills up, when you either need to use one of the other strategies to figure out where the next item goes, or expand the hash table.
Oh hey, I just noticed you’re the guy that’s writing Gazelle. Cool! My friend Matthew O’Connor told me about you when he paired with you when applying to work at Pivotal, and I’m watching Gazelle on Github.
@Kragen: while shelling out to the system is always a possibility, I’m really trying to stay within portable C99, and not make assumptions about the environment. A good model for what I’m going for is zlib: I think zlib is ubiquitous in large part because it makes absolutely no assumptions about your system. It even lets you swap in your own implementations of malloc and free
For example, I want pbstream to be usable in embedded system. Here’s an example of a guy who’s in a situation I want to accommodate: GPB on non-Linux, non-Windows OS?.
I hear what you’re saying wrt. just using Python’s dict. Although accommodating languages like Python, Ruby, Lua, etc. is one of my goals, I also want this library to perform well standalone, in cases where there is no other hashtable implementation available. Also, of my two hashtable use cases, the int->void* lookup that happens in the critical path of parsing is the more important one to me by far, and this happens at a layer below where you’d interface something like Python or Ruby.
It makes me really happy that you’re independently interested in Gazelle! pbstream and Gazelle are actually soon to be intertwined: Gazelle needs a bytecode format and an AST serialization format (I mean to switch to protobufs from LLVM bitcode), and pbstream needs a way to parse .proto files. pbstream->Gazelle won’t be a hard dependency though — you’ll be able to load .proto definitions in binary form if you want.
I’m afraid I’m drawing a complete blank on your friend Matthew O’Connor though, and I’ve never been associated with Pivotal. Is there something I’m forgetting?
I recently came across perfect hashing (see http://burtleburtle.net/bob/hash/perfect.html). It’s not at all clear to me that this is necessarily a speed win versus the other hash table strategies you list, but it does avoid the issue of collisions entirely. I suspect the tradeoff is that finding a (possibly minimal) perfect hashing function for a given set of keys might be be tricky…
Oops! I confused you with the other person writing a novel parsing tool in a very-high-level language that I’m watching on Github, Nathan Sobo, whose parsing system is Treetop (in Ruby).
Thanks for this article. Once upon a time (back in 2002), I gave a short overview of some hashing techniques to the Hackers-IL mailing list. Seems like I missed some stuff you mentioned here, which wasn’t covered in my introductory Data Structures and Algorithms course.
I myself, always prefer to use some form of chaining instead of open addressing. That’s because with open-addressing, it’s harder to tell when an item was removed or does not exist at all, and as a result the hash becomes much more flimsy. Maybe there’s some magic way to achieve it, but I’m still ignorant of it.
Pingback: Books About Parsing » Josh the Outspoken