I never really finished the project, thus only the rough qualitative benchmarks you get at the bottom (measured mostly by profiling and size(1)); I saw that it wasn't enough of a win in the larger context where I needed it, thus it made sense to stop early instead of making exhaustive benchmarks.
The blog post was mainly for curious readers, I'm surprised it hit HN at all. :-)
Well, again, different problem constraints, different solutions. Seemingly that tool can handle larger sets than gperf (although it claims gperf stops at a couple hundred, which is an exaggeration; try it with the first 1000 lines of /usr/dict/words and it's nearly instant, and with the first 10k it needs 35 seconds or so), but it also says the runtime is even slower. My goal was to have faster runtime, not handle more keys. YMMV.
There’s an explanation of how to implement a perfect hash generator in “Hacker’s Delight” that you can read to take a known set of keys and produce a consistent perfect hash at runtime.
It’s a very worthwhile thing to keep in your back pocket if you’re going to deal with hashes whose keys are 100% knowable at runtime but not before.
I believe there are some high concurrency hash tables out there where the data structure contains two tables, and so each get results in a constant number of fetches, but the count is almost always greater than one. But if it avoids concurrency issues that ends up being acceptable.
I remember Cliff Click presenting one that was lockless and if I'm recalling correctly, where capacity growth operations could happen in parallel with reads. And possibly writes.
Uhh, there is nothing at all "academic" about pthash, (or phast, or ptrhash), apart from the fact that they also described their ideas in papers. All of those tools work on massive sets of data, support massively parallel construction, and support external memory construction. They are all well-engineered libraries and not "academic" in any derogatory sense.
They are academic, as they are not practical. Most of the algos produce random graphs, ie random indices. The given index has nothing to do with the keys.
They give the hash sizes without the needed ordering tables, they don't even produce those seperate tables. Because academic competition. So in reality you'd need O(2n) more time and O(n) space. Without random key access it gets slow. Then there are no checks for false-positives. You'd need fast random access to the keys then. Then they could not compile to static sourcecode.
All this is pure fantasy for real products. gperf, nbperf are practical. They store the keys, and give a proper search function. They produce C code. pthash, ptrhash, cmph not. It's complicated because the keys can be in a file, a stream, a database, with just linear access or random access. I'm adding options to either store the ordering table, or emit an ordered keys file. And I compile to C or C++ code. And I allow several hash algos, not just random seeds. Jenkins hash is mostly good, but there are better, depending on the keys.
Your statement conveys a lack of knowledge of the main purpose of minimal perfect hash functions, as compared to generic/general hash tables (which are a more general, but therefore, in some cases, less efficient data structure). The main point of the MPHF is not to be order preserving, or to provide a prescribed function from the keys to [1...n]. Rather, it is to provide a collision free mapping between the set of keys and [1..n].
The fact that minimal perfect hashes do not reject alien keys is not an "academic" limitation, it is implicit in the definition of the problem being solved. In fact, the relevant space bounds cannot be satisfied if you either (1) must reject elements not in the key set at the time of construction or (2) require a prescribed order be assigned to the specific keys.
However, even given your misapprehensions about the purpose of minimal perfect hash functions, your statement about how they are not useful in practice is also simply false. You are describing uses for classical hash tables that store their key set explicitly and in their entirety. These serve an entirely different purpose in application to minimal perfect hash functions.
Minimal perfect hash functions are particularly useful when you know the key set ahead of time and are certain that only valid keys will be queried. In this case, the values can be stored in a flat array (in the order prescribed by the MPHF) and the cost of the hash itself is only ~2 bits/key. So the total storage is the minimal storage for the values + a small overhead to allow constant-time access to the value for a given key. If you need to reject alien keys, then you can of course store those as well. In that case, the MPHF costs the storage cost for the key set + value set + ~2 bits/key; still smaller than most existing dynamic hash tables.
In many cases, you don't need an ordering table. If you are allowed to permute the keys and all you require is O(1) access to the corresponding index for a key, then the additional ordering table is unnecessary overhead. On the other hand, if you need, for some reason, to remap the keys to be in a specific order, then this is easy simply by iterating over the keys and observing what indices they yield.
Simply because a particular MPHF construction doesn't suit the problem you have in mind doesn't mean it's not useful or that it's "academic". MPHFs have plenty of uses, some without the need for a key routing or key-reordeing table. Other times, one needs the keys in a particular order and even then MPHFs are very useful because if the key set is static, the MPHF + the rerouting table is often still smaller than alternative dynamic hash table approaches while being similarly fast for query. They can be built in an parallel, external memory, and cache efficient manner.
The argument that MPHFs are "academic" and not useful because they don't adhere to constraints to which they are not intended to adhere is like arguing that a hammer is not useful because you cannot use it to tighten philips head screws.
What exactly would be “practical” about exporting an ordering table when your application doesn’t need it? That’s the whole point of minimal perfect hashing — to provide a compact, collision-free mapping from a known key set to [1..n], without extra structures unless they’re required.
If you do need to preserve key order, that’s a different problem entirely — and one that’s already well-studied. You’d use an order-preserving MPHF (OMPHF), not a standard MPHF. There’s a large body of literature on this (e.g. “Order Preserving Minimal Perfect Hashing” – VTechWorks,
).
You seem to conflate the two problems — building an efficient MPHF versus building an OMPHF. Both are useful, but for different goals. Dismissing something as “academic” because it solves a different problem efficiently isn’t a fair critique — it’s misunderstanding what it’s optimizing for. It’s like saying “Bloom filters aren’t practical because they don’t store the original data.”
What's most annoying with gperf and similar tools is that they aren't really suited to applications where the set of keys is known at runtime during initialization.
If I'm understanding this correctly, you're essentially hashing twice. You get a perfect hash on the second hash call, and don't worry about one on the first.
There are other hash tables that use double hashing but they don't guarantee a lack of collisions. They just make them highly improbable.
I've written code that, during initialization, after all keys have been collected, essentially called gperf to create the lookup function, compiled it, and then dynamically loaded it, so that the (long-running) program would be able to use it.
Maybe this is one of those situations where compile time code execution wins out. Instead of needing one solution for runtime and one for a priori knowledge, you just run the runtime code during the build process and Bob's your uncle.
I wrote a python library that would build a perfect hash at run-time, it was basically the stupidest way you could do it - it would shell out to gperf to build the library, compile it to a shared library, then link the entry points in (I think with ctypes? I can't remember).
It was just for fun, but in the end even ignoring the startup costs of all of that, the default performance of python's dictionary was better.
Make sure to read the post linked right at the beginning as well: http://0x80.pl/notesen/2023-04-30-lookup-in-strings.html as well as the magic bitboards linked, too https://www.chessprogramming.org/Magic_Bitboards
Though honestly this post really needed some numbers and benchmarks.
I never really finished the project, thus only the rough qualitative benchmarks you get at the bottom (measured mostly by profiling and size(1)); I saw that it wasn't enough of a win in the larger context where I needed it, thus it made sense to stop early instead of making exhaustive benchmarks.
The blog post was mainly for curious readers, I'm surprised it hit HN at all. :-)
gperf is very limited in the number of keys it can handle as opposed to, say, https://burtleburtle.net/bob/hash/perfect.html
Well, again, different problem constraints, different solutions. Seemingly that tool can handle larger sets than gperf (although it claims gperf stops at a couple hundred, which is an exaggeration; try it with the first 1000 lines of /usr/dict/words and it's nearly instant, and with the first 10k it needs 35 seconds or so), but it also says the runtime is even slower. My goal was to have faster runtime, not handle more keys. YMMV.
Not an exaggeration, just written when machines were a lot slower. Anyway, more work in this space is always welcome, so thanks.
There’s an explanation of how to implement a perfect hash generator in “Hacker’s Delight” that you can read to take a known set of keys and produce a consistent perfect hash at runtime.
It’s a very worthwhile thing to keep in your back pocket if you’re going to deal with hashes whose keys are 100% knowable at runtime but not before.
One thing not mentioned: very often "give up and allow a not-quite-perfect hash" is a reasonable solution.
I believe there are some high concurrency hash tables out there where the data structure contains two tables, and so each get results in a constant number of fetches, but the count is almost always greater than one. But if it avoids concurrency issues that ends up being acceptable.
I remember Cliff Click presenting one that was lockless and if I'm recalling correctly, where capacity growth operations could happen in parallel with reads. And possibly writes.
I am working on modern perfect hashing also. First for integer keys, and then also for millions of keys. Should be practical, not academic.
https://github.com/rurban/gperf/tree/autotools or some other branch. Forgot which.
https://github.com/rurban/cmph/tree/compressed_o (lotsa improvements)
https://github.com/rurban/pthash (compile to static C++)
I've also extended nbperf for those features
Uhh, there is nothing at all "academic" about pthash, (or phast, or ptrhash), apart from the fact that they also described their ideas in papers. All of those tools work on massive sets of data, support massively parallel construction, and support external memory construction. They are all well-engineered libraries and not "academic" in any derogatory sense.
They are academic, as they are not practical. Most of the algos produce random graphs, ie random indices. The given index has nothing to do with the keys.
They give the hash sizes without the needed ordering tables, they don't even produce those seperate tables. Because academic competition. So in reality you'd need O(2n) more time and O(n) space. Without random key access it gets slow. Then there are no checks for false-positives. You'd need fast random access to the keys then. Then they could not compile to static sourcecode.
All this is pure fantasy for real products. gperf, nbperf are practical. They store the keys, and give a proper search function. They produce C code. pthash, ptrhash, cmph not. It's complicated because the keys can be in a file, a stream, a database, with just linear access or random access. I'm adding options to either store the ordering table, or emit an ordered keys file. And I compile to C or C++ code. And I allow several hash algos, not just random seeds. Jenkins hash is mostly good, but there are better, depending on the keys.
Your statement conveys a lack of knowledge of the main purpose of minimal perfect hash functions, as compared to generic/general hash tables (which are a more general, but therefore, in some cases, less efficient data structure). The main point of the MPHF is not to be order preserving, or to provide a prescribed function from the keys to [1...n]. Rather, it is to provide a collision free mapping between the set of keys and [1..n].
The fact that minimal perfect hashes do not reject alien keys is not an "academic" limitation, it is implicit in the definition of the problem being solved. In fact, the relevant space bounds cannot be satisfied if you either (1) must reject elements not in the key set at the time of construction or (2) require a prescribed order be assigned to the specific keys.
However, even given your misapprehensions about the purpose of minimal perfect hash functions, your statement about how they are not useful in practice is also simply false. You are describing uses for classical hash tables that store their key set explicitly and in their entirety. These serve an entirely different purpose in application to minimal perfect hash functions.
Minimal perfect hash functions are particularly useful when you know the key set ahead of time and are certain that only valid keys will be queried. In this case, the values can be stored in a flat array (in the order prescribed by the MPHF) and the cost of the hash itself is only ~2 bits/key. So the total storage is the minimal storage for the values + a small overhead to allow constant-time access to the value for a given key. If you need to reject alien keys, then you can of course store those as well. In that case, the MPHF costs the storage cost for the key set + value set + ~2 bits/key; still smaller than most existing dynamic hash tables.
In many cases, you don't need an ordering table. If you are allowed to permute the keys and all you require is O(1) access to the corresponding index for a key, then the additional ordering table is unnecessary overhead. On the other hand, if you need, for some reason, to remap the keys to be in a specific order, then this is easy simply by iterating over the keys and observing what indices they yield.
Many times, people wish to use MPHFs for non-static purposes (i.e. where the key set is not known at compile time). Consider e.g. in network mapping (https://dl.acm.org/doi/abs/10.1109/tnet.2018.2820067), or in taxonomic classification (https://academic.oup.com/bioinformatics/article/34/1/171/393...) or in k-mer indexing (https://academic.oup.com/bioinformatics/article/34/13/i169/5... or https://academic.oup.com/bioinformatics/article/38/Supplemen...). Moreover, MPHFs form the basis for near-optimal static filters, by storing fingerprints of the keys in the indexed spots (https://www.sciencedirect.com/science/article/pii/S0166218X1...).
Simply because a particular MPHF construction doesn't suit the problem you have in mind doesn't mean it's not useful or that it's "academic". MPHFs have plenty of uses, some without the need for a key routing or key-reordeing table. Other times, one needs the keys in a particular order and even then MPHFs are very useful because if the key set is static, the MPHF + the rerouting table is often still smaller than alternative dynamic hash table approaches while being similarly fast for query. They can be built in an parallel, external memory, and cache efficient manner.
The argument that MPHFs are "academic" and not useful because they don't adhere to constraints to which they are not intended to adhere is like arguing that a hammer is not useful because you cannot use it to tighten philips head screws.
See, your academic defense lacks any practicalism. I know how academics define it, that's why you barely cannot them use as is.
With some algos you can export the ordering tables trivially, but nobody does. Because someone else's problem.
What exactly would be “practical” about exporting an ordering table when your application doesn’t need it? That’s the whole point of minimal perfect hashing — to provide a compact, collision-free mapping from a known key set to [1..n], without extra structures unless they’re required.
If you do need to preserve key order, that’s a different problem entirely — and one that’s already well-studied. You’d use an order-preserving MPHF (OMPHF), not a standard MPHF. There’s a large body of literature on this (e.g. “Order Preserving Minimal Perfect Hashing” – VTechWorks, ).
You seem to conflate the two problems — building an efficient MPHF versus building an OMPHF. Both are useful, but for different goals. Dismissing something as “academic” because it solves a different problem efficiently isn’t a fair critique — it’s misunderstanding what it’s optimizing for. It’s like saying “Bloom filters aren’t practical because they don’t store the original data.”
What's most annoying with gperf and similar tools is that they aren't really suited to applications where the set of keys is known at runtime during initialization.
See https://burtleburtle.net/bob/hash/perfect.html
If I'm understanding this correctly, you're essentially hashing twice. You get a perfect hash on the second hash call, and don't worry about one on the first.
There are other hash tables that use double hashing but they don't guarantee a lack of collisions. They just make them highly improbable.
I've written code that, during initialization, after all keys have been collected, essentially called gperf to create the lookup function, compiled it, and then dynamically loaded it, so that the (long-running) program would be able to use it.
That means you need to deploy with a compiler etc., not ideal.
This situation doesn't have ideal solution. You either bundle compiler for the best speed at runtime, or you lose efficiency.
Maybe this is one of those situations where compile time code execution wins out. Instead of needing one solution for runtime and one for a priori knowledge, you just run the runtime code during the build process and Bob's your uncle.
I wrote a python library that would build a perfect hash at run-time, it was basically the stupidest way you could do it - it would shell out to gperf to build the library, compile it to a shared library, then link the entry points in (I think with ctypes? I can't remember).
It was just for fun, but in the end even ignoring the startup costs of all of that, the default performance of python's dictionary was better.
Obligatory mention: https://github.com/pytries/marisa-trie (marisa trie - a succinct DS) which gives nearly perfect information theoretic lower bound compression
particularly marisa_trie.RecordTrie: https://marisa-trie.readthedocs.io/en/latest/tutorial.html#m...