6 ms·

This looks scary: https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/tools/PerfectHash.pm;h=bd339e38a22db6975491652e3b638d50d12da301;hb=c64d0cd5ce

This looks scary: https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/tools/PerfectHash.pm;h=bd339e38a22db6975491652e3b638d50d12da301;hb=c64d0cd5ce24a344798534f1bc5827a9199b7a6e#l113 https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f... Isn't there a better option than manually generating C code from a Perl script?

Arnavion 8y ago
The hash function needs to be compiled into the final binary, so it needs to be C code. Thus something needs to generate that C code. There's already a bunch of other perl scripts in src/tools/ that generate / modify C code, so why use something else?
hinkley 8y ago
I think this is one of the classes of problems that Jonathan Blow identifies. Instead of having a Turing Complete macro system you have regular functions that evaluate at compile time. You’d generate your perfect hash in the same language you’re working in.
- nicoburns 8y ago
  D does this. Although it's not necessarily one or the other. C++ has the c preprocessor, templates, and constexpr. Rust has macros, but is looking at adding const function evaluation too.
  - steveklabnik 8y ago
    const fn has already landed, though a minimal version whose powers we are expanding upon almost every release.
jbn 8y ago
Another option would be using https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/
- anarazel 8y ago
  We looked at that, and the generated code/hash unfortunately isn't that good.
  - souprock 8y ago
    It can be made good. I used it for parsing /proc/PID/status keywords at a very high rate to support "top" and "ps". You'll have to change the generated code, which likely means that you use gperf during development instead of running it during every build. The first step was to put only the needed keywords in a file, without the colons. I ran gperf with options to choose 3 specific character offsets and to use the length in the calculation; this was best after I tried a few choices. I then cleaned up the code and optimized it. I rounded the table size up to a power of 2, padding it correctly, and changed the length check to a mask. I switched the code over to using gcc's computed goto extension. I provided the keyword lengths, letting me use memcmp instead of strcmp. I inlined everything.
    - rurban 8y ago
      I evaluated most of the available perfect hash generators a while ago, and gperf is not often the best. I've created much better ones. But I haven't added this NetBSD code yet and also not yet the new perl5 mph code, will do soon. https://github.com/rurban/Perfect-Hash https://github.com/rurban/Perfect-Hash
alnsn 8y ago
Not sure that scares you, code generation or a choice of scripting language? If you want to avoid a code generation, you can generate a .cdb (constant database) file with the cdbw(3) C API and read it using the cdbr(3) C API. cdbw(3) http://netbsd.gw.com/cgi-bin/man-cgi?cdbw+3+NetBSD-current http://netbsd.gw.com/cgi-bin/man-cgi?cdbw+3+NetBSD-current cdbr(3) http://netbsd.gw.com/cgi-bin/man-cgi?cdbr+3+NetBSD-current http://netbsd.gw.com/cgi-bin/man-cgi?cdbr+3+NetBSD-current Some examples of .cdb files on NetBSD: /usr/share/misc/terminfo.cdb /var/db/services.cdb If you don't like a particular choice of a scripting language, you can adapt my Lua script: https://gist.github.com/alnsn/68f599bc9358fcee122d6175392d779f https://gist.github.com/alnsn/68f599bc9358fcee122d6175392d77... Building and peeling a graph should be identical but the assign step is different. I use non-minimal not order preserving BDZ scheme while Joerg's code is based on the original CHM scheme. Given keys A, B, C and D, CHM always maps them to values 0, 1, 2 and 3. BDZ, on the other hand, can generate values in a range [0, 2.1 * 4) and it doesn't preserve an order. For instance, one possible mapping in the BDZ scheme is 7, 2, 5, 1. Alex
- rurban 8y ago
  Nope, cdb is worse than this generator. We've used cdb before. cdb is even worse than gperf.
  - alnsn 8y ago
    It’s down to a quality of implementation. I can give you some hints on improving it if you’re interested. A tiny JIT code generator inside cdb would definitely bring performance on par with a generated C code but it’s probably an overkill.
chocolateboy 8y ago
Yes, a better Perl script [1] :-) In C, re2c [2] provides something similar, and there are similar tools available in other languages. [1] https://metacpan.org/pod/Devel::Tokenizer::C https://metacpan.org/pod/Devel::Tokenizer::C [2] http://re2c.org/ http://re2c.org/
- rurban 8y ago
  Devel::Tokenizer::C generates horrible code, even worse than gperf. Much better is my Perfect::Hash module, this postgresql module or the new perl5 mph script. Haven't checked re2c but it looks like a naive lexer implementation generating a static DFA bytewise, not optimized for speed nor memory. Better generators should really operate on the wordlevel or wider (SSE), not bytes. These are ~8x faster, in some case up to 200x. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an...
nuclx 8y ago
It's a reasonable choice for the use-case at hand. I used a similar approach to generate C code using python with jinja2. Ironically, I generated a binary hash based lookup, because the hash values ought to stay constant even when new keys are added in future versions.

Arnavion 8y ago

The hash function needs to be compiled into the final binary, so it needs to be C code. Thus something needs to generate that C code. There's already a bunch of other perl scripts in src/tools/ that generate / modify C code, so why use something else?

hinkley 8y ago

I think this is one of the classes of problems that Jonathan Blow identifies. Instead of having a Turing Complete macro system you have regular functions that evaluate at compile time. You’d generate your perfect hash in the same language you’re working in.

nicoburns 8y ago
D does this. Although it's not necessarily one or the other. C++ has the c preprocessor, templates, and constexpr. Rust has macros, but is looking at adding const function evaluation too.
- steveklabnik 8y ago
  const fn has already landed, though a minimal version whose powers we are expanding upon almost every release.

jbn 8y ago

Another option would be using https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/

anarazel 8y ago
We looked at that, and the generated code/hash unfortunately isn't that good.
- souprock 8y ago
  It can be made good. I used it for parsing /proc/PID/status keywords at a very high rate to support "top" and "ps". You'll have to change the generated code, which likely means that you use gperf during development instead of running it during every build. The first step was to put only the needed keywords in a file, without the colons. I ran gperf with options to choose 3 specific character offsets and to use the length in the calculation; this was best after I tried a few choices. I then cleaned up the code and optimized it. I rounded the table size up to a power of 2, padding it correctly, and changed the length check to a mask. I switched the code over to using gcc's computed goto extension. I provided the keyword lengths, letting me use memcmp instead of strcmp. I inlined everything.
  - rurban 8y ago
    I evaluated most of the available perfect hash generators a while ago, and gperf is not often the best. I've created much better ones. But I haven't added this NetBSD code yet and also not yet the new perl5 mph code, will do soon. https://github.com/rurban/Perfect-Hash https://github.com/rurban/Perfect-Hash

alnsn 8y ago

Not sure that scares you, code generation or a choice of scripting language? If you want to avoid a code generation, you can generate a .cdb (constant database) file with the cdbw(3) C API and read it using the cdbr(3) C API. cdbw(3) http://netbsd.gw.com/cgi-bin/man-cgi?cdbw+3+NetBSD-current http://netbsd.gw.com/cgi-bin/man-cgi?cdbw+3+NetBSD-current cdbr(3) http://netbsd.gw.com/cgi-bin/man-cgi?cdbr+3+NetBSD-current http://netbsd.gw.com/cgi-bin/man-cgi?cdbr+3+NetBSD-current Some examples of .cdb files on NetBSD: /usr/share/misc/terminfo.cdb /var/db/services.cdb If you don't like a particular choice of a scripting language, you can adapt my Lua script: https://gist.github.com/alnsn/68f599bc9358fcee122d6175392d779f https://gist.github.com/alnsn/68f599bc9358fcee122d6175392d77... Building and peeling a graph should be identical but the assign step is different. I use non-minimal not order preserving BDZ scheme while Joerg's code is based on the original CHM scheme. Given keys A, B, C and D, CHM always maps them to values 0, 1, 2 and 3. BDZ, on the other hand, can generate values in a range [0, 2.1 * 4) and it doesn't preserve an order. For instance, one possible mapping in the BDZ scheme is 7, 2, 5, 1. Alex

rurban 8y ago
Nope, cdb is worse than this generator. We've used cdb before. cdb is even worse than gperf.
- alnsn 8y ago
  It’s down to a quality of implementation. I can give you some hints on improving it if you’re interested. A tiny JIT code generator inside cdb would definitely bring performance on par with a generated C code but it’s probably an overkill.

chocolateboy 8y ago

Yes, a better Perl script [1] :-) In C, re2c [2] provides something similar, and there are similar tools available in other languages. [1] https://metacpan.org/pod/Devel::Tokenizer::C https://metacpan.org/pod/Devel::Tokenizer::C [2] http://re2c.org/ http://re2c.org/

rurban 8y ago
Devel::Tokenizer::C generates horrible code, even worse than gperf. Much better is my Perfect::Hash module, this postgresql module or the new perl5 mph script. Haven't checked re2c but it looks like a naive lexer implementation generating a static DFA bytewise, not optimized for speed nor memory. Better generators should really operate on the wordlevel or wider (SSE), not bytes. These are ~8x faster, in some case up to 200x. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an...

nuclx 8y ago

It's a reasonable choice for the use-case at hand. I used a similar approach to generate C code using python with jinja2. Ironically, I generated a binary hash based lookup, because the hash values ought to stay constant even when new keys are added in future versions.