News for hackers. Stuff that matters.
Re:Use perfect hashing, instead of binary search, for keywor... by ricardobeat on Thursday January 10, 2019 @07:37PM (#18879993)
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?

Re:Use perfect hashing, instead of binary search, for keywor... by alnsn on Thursday January 10, 2019 @08:09PM (#18880160)
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

Re:Use perfect hashing, instead of binary search, for keywor... by rurban on Friday January 11, 2019 @04:24AM (#18882000)
Nope, cdb is worse than this generator. We've used cdb before. cdb is even worse than gperf.
Re:Use perfect hashing, instead of binary search, for keywor... by alnsn on Friday January 11, 2019 @05:48AM (#18882481)
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.

Re:Use perfect hashing, instead of binary search, for keywor... by Arnavion on Thursday January 10, 2019 @07:47PM (#18880036)
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?

Re:Use perfect hashing, instead of binary search, for keywor... by hinkley on Thursday January 10, 2019 @07:47PM (#18880037)
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.
Re:Use perfect hashing, instead of binary search, for keywor... by nicoburns on Thursday January 10, 2019 @09:36PM (#18880576)
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.
Re:Use perfect hashing, instead of binary search, for keywor... by steveklabnik on Thursday January 10, 2019 @10:35PM (#18880813)
const fn has already landed, though a minimal version whose powers we are expanding upon almost every release.
Re:Use perfect hashing, instead of binary search, for keywor... by jbn on Thursday January 10, 2019 @08:06PM (#18880141)
Another option would be using https://www.gnu.org/software/gperf/
Re:Use perfect hashing, instead of binary search, for keywor... by anarazel on Thursday January 10, 2019 @08:14PM (#18880185)
We looked at that, and the generated code/hash unfortunately isn't that good.
Re:Use perfect hashing, instead of binary search, for keywor... by souprock on Thursday January 10, 2019 @09:58PM (#18880657)
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.

Re:Use perfect hashing, instead of binary search, for keywor... by rurban on Friday January 11, 2019 @03:48AM (#18881881)
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

Re:Use perfect hashing, instead of binary search, for keywor... by nuclx on Thursday January 10, 2019 @08:22PM (#18880224)
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.
Re:Use perfect hashing, instead of binary search, for keywor... by chocolateboy on Thursday January 10, 2019 @08:17PM (#18880200)
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/

Re:Use perfect hashing, instead of binary search, for keywor... by rurban on Friday January 11, 2019 @03:52AM (#18881888)
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...