Hacker News Reader

Comment by rurban | Hacker News Reader

perl, nice!

This looks scary: 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?

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?

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.

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.

const fn has already landed, though a minimal version whose powers we are expanding upon almost every release.

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

We looked at that, and the generated code/hash unfortunately isn't that good.

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.

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

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 cdbr(3) 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/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

Nope, cdb is worse than this generator. We've used cdb before. cdb is even worse than gperf.

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.

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

[2] http://re2c.org/

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-an...

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.

Always great to see some perl these days.

Reply on news.ycombinator.com