4 ms·

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 initializat

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.

jibal 1y ago
See https://burtleburtle.net/bob/hash/perfect.html https://burtleburtle.net/bob/hash/perfect.html
- hinkley 1y ago
  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.
anitil 1y ago
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.
hinkley 1y ago
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.
zvr 1y ago
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.
- mgaunard 1y ago
  That means you need to deploy with a compiler etc., not ideal.
  - HackerThemAll 1y ago
    This situation doesn't have ideal solution. You either bundle compiler for the best speed at runtime, or you lose efficiency.
  - zvr 1y ago
    Yes, it was a controlled environment and it was known that there will be gperf and gcc available.

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.

jibal 1y ago

See https://burtleburtle.net/bob/hash/perfect.html https://burtleburtle.net/bob/hash/perfect.html

hinkley 1y ago
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.

anitil 1y ago

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.

hinkley 1y ago

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.

zvr 1y ago

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.

mgaunard 1y ago
That means you need to deploy with a compiler etc., not ideal.
- HackerThemAll 1y ago
  This situation doesn't have ideal solution. You either bundle compiler for the best speed at runtime, or you lose efficiency.
- zvr 1y ago
  Yes, it was a controlled environment and it was known that there will be gperf and gcc available.