11 ms·

Use perfect hashing, instead of binary search, for keyword lookup

328 points by boshomi 8y ago

boshomi 8y ago
see also: Joerg Sonnenberger: Perfecting hashing in NetBSD (P3B, AsiaBSDCon 2013) [1] [1] https://www.youtube.com/watch?v=87pUZYERkNQ https://www.youtube.com/watch?v=87pUZYERkNQ (youtube)
- robustpastoral 8y ago
  Thanks
rurban 8y ago
perl, nice!
- ricardobeat 8y ago
  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.
- goosewaterfan 8y ago
  Always great to see some perl these days.
Tostino 8y ago
I love seeing all the work and optimizations that get done on Postgres. Very interesting.
koolba 8y ago
So is the idea here to generate a perfect hash table for the known set of SQL keywords in the parser rather than doing a binary search on the fly?
- anarazel 8y ago
  Correct.
canadev 8y ago
Can someone put this in lay terms for a casual postgresql user?
- p4lindromica 8y ago
  A perfect hash is one in which their are no collisions for a given data set, which guarantees O(1), or constant, lookup time. This patch introduces a perl script which computes a perfect hash function at build time given the current set of SQL keywords. The old keyword lookup method uses binary search. Binary search is a search algorithm that must compare at most O(log n) entries before finding a match. Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup.
  - anarazel 8y ago
    > Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup. Worthwhile to note that that speedup is for the raw parsing, without parse-analysis (i.e. looking up the tables referenced and such), planning (figuring out how to execute the query) and execution. So end-user impact will be much smaller than 20%. But for some cases, e.g. when many columns are referenced, it'll be measurable.
    - the_duke 8y ago
      Column names aren't keywords though, are they?. Using a perfect hash table is definitely cool, but it's hard to imagine a query with so many keywords that this would have a measurable impact on total query execution time.
      - anarazel 8y ago
        Due to the desire to have keywords that aren't fully reserved (we have keyword classes that are fully reserved, can appear as type names, can appear as column names, or can appear nearly everywhere) we/PG need to look up whether a specific string is a keyword or an identifier in a number of places in the scanner/parser. Addendum: And that indeed means that column references, unless quoted with "", used to go through the binary search and now go through the perfect hash. Edit: Typo
sjroot 8y ago
From the post: "The time savings is indeed significant: preliminary testing suggests that the total time for raw [SQL] parsing (flex + bison phases) drops by ~20%." Very impressive work!
- amelius 8y ago
  Impressive? They changed one textbook algorithm by another one. It turns out to be faster, but it might as well be slower for certain inputs (which might be common). Also, when they increase the number of keywords in the future, they might have to reconsider the implementation.
  - jimktrains2 8y ago
    I'm having trouble coming up with a scenario where perfect hashing Vs a binary search tree is slower. Also, yes, the very nature of perfect hashing means it will very potential need to be updated with additional keywords. However, that doesn't happen often and this is a small amount of work for what all would be entailed with a new keyword.
  - molyss 8y ago
    I think it's impressive, but maybe not for the same reasons as the OP : that means that keyword lookup accounted for at least 20% of total SQL parsing time. That's a surprise to me !
    - anarazel 8y ago
      Note it's the "raw" parsing time. If you include the semantic parse-analysis phase, i.e. looking up table names etc, it's a much smaller portion.
    - sjroot 8y ago
      This is basically what I was thinking -- that a relatively minor change to the parsing process could yield such significant results.
  - geophile 8y ago
jnwatson 8y ago
Isn’t this just textbook perfect hashing? This is literally a primary use case for it.
- zzzcpan 8y ago
  Textbook here would be using goto-based DFA state machine (ragel can generate one).
  - PhilWright 8y ago
    If that would be faster, why not do that then?
    - wahern 8y ago
      Because they're using Flex & Bison, not Ragel. The latter is specialized for and excels at defining and applying finite state machines. But while the design of Ragel makes it relatively trivial to build ASTs during the parse, you still have to do it manually. Flex & Bison automate much more of the process of transforming an input stream to a tree. Dropping them and moving to Ragel would be a serious refactor. FWIW, Flex also builds DFAs. It's just that the design of Ragel is so elegant that Ragel DFA machines are more flexible, easier to compose (both in terms of combining abstract machines and in terms of language-level integration), and yet still incomparably faster. While a straight DFA match should in principle be at least as efficient as a perfect hash[1], this is really only realized with something like Ragel or Intel Hyperscan. As awesome as RE2 is, the performance isn't in the same league as those two; ditto for JIT'd PCREs and re2c--neither are comparable to Ragel or Hyperscan. [1] At least until the input set grows into the thousands or millions of items--at some point the size of the generated DFA grows faster than and overtakes the size of the generated perfect hash function.
      - goldenkey 8y ago
        Wouldn't a DFA be faster than perfect hashing here if only because non-keywords can collide with keyword hash values, so a strcmp is always going to be necessary regardless of the actual keyword differentiation? I tried looking at the code to see if they were excluding non-keywords at some other stage - because then this would seem redundant?
tachang 8y ago
Reading the discussion thread is fantastic. The postgres community culture definitely feels a lot different than some of the other open source projects I've seen.
amluto 8y ago
Binary search is a pretty bad algorithm. Sure, it runs in O(log n) time and it's more or less the best you can do to solve the general problem of finding something in a sorted list, but that does not mean it's a good way to create an immutable list of things that can be searched using comparisons. In particular, binary search has awful cache locality. Until you get very close to your target, you are essentially hitting a random cache line (and maybe even a random page for large lists) for every comparison. This is bad. A B-tree-like structure that is never modified is very easy to make, and it will be much faster. This came up with the ORC unwinder in Linux. We got something like a 4x speedup by changing from binary search to something a bit more clever to find unwind entries in the table.
- Terr_ 8y ago
  > In particular, binary search has awful cache locality. That makes me think of an idea which I'm certain can't be original, but I can't think of the jargon for what it's called. Suppose you have a fixed-length sorted array, and its binary-search can be visualized as a tree. Traverse that tree in level-order and pop it into a helper-array, arranged much like a heap: The midpoint is first and all left and right children are proceed from there at offsets that you can predict. So the original array [A,B,C,D,E,F,G] has a data-structure for searching of [(D,3), (B,1), (F,5), (A,0), (C,2), (E,4), (G,6)] While the high-indexed items will get spread out, the most common and sequential activity occurs all together near the lower indexes, minimizing large jumps. Since each entry has the original index stored, you can always switch back to the initial array when a different strategy (e.g. linear scan) becomes preferable.
  - RcouF1uZ4gsC 8y ago
    Here is a writeup of the idea and some numbers. http://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html http://bannalia.blogspot.com/2015/06/cache-friendly-binary-s...
  - macdice 8y ago
    Take a look at ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING. TL;DR there are schemes like this called "Eytzinger" and "van Emde Boas". https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf The topic of arranging keys like this within index pages (or maybe elsewhere) has come up on the pgsql-hackers mailing list before: https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A7-9642-7830DC1108F1%40yandex-team.ru https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A...
deleted 8y ago
[deleted]
chubot 8y ago
FYI PostGres appears to have over 400 keywords, shown here: https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/include/parser/kwlist.h;h=adeb834ce82422940cb89798ee18457c17c10853; https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f... The way I've seen most languages do it is something like this: switch (c[0]) { case 'c': if (strcmp(c, "case") == 0) return CASE; if (strcmp(c, "continue") == 0) return CONTINUE; ... case 'f': if (strcmp(c, "for") == 0) return FOR; if (strcmp(c, "friend") == 0) return FRIEND; ... } I suspect that's good enough if you have a typical keyword list of say 20-100. I just looked at Clang and it appears to build the list at runtime, using a regular hash table. I think this is because it has to handle C, C++, and Objective C, and they have different sets of keywords. It seems like they could change it to use something like perfect hashing, and if that's even a 1% win, it would be worth it for the extra build complexity, since C and C++ compilation take up so many CPU cycles in the world. See lib/Basic/IdentifierTable.cpp. Although another problem is that the list of keywords depends on whether you're compiling C89, C99, C++98, C++11, etc. But that is a finite list so it seems like it still can be done with code generation ahead of time like PostGres does. In Oil [1] I use re2c [1] recognize keywords, along with the rest of the complex lexing process, and it works well. It builds a DFA expressed in C code. The slower parts are elsewhere :) EDIT: In theory, the DFA seems better than perfect hashing because you can bail on the second character if you get "xzoo" and no keyword starts with "xz". I think with perfect hashing yo still have to look at every byte. The switch statement above also avoids looking at every byte in certain cases. [1] http://www.oilshell.org/ http://www.oilshell.org/ [2] http://re2c.org/ http://re2c.org/
- mark-r 8y ago
  There's a lot of overlap with those keywords, so perhaps the best bet is to create a single superset and use an attribute returned by the lookup to see if it's needed by the target language.
- nly 8y ago
  You don't necessarily have to look at every byte to compute the hash - gperf will generate hash functions that uses only a few characters at seemingly random offsets. You do however have to do a full strcmp() to rule out a hash collision (with words outside of your set) so DFA wins there. Imho though, the most significant difference between DFA and a PHF would be the DFA would likely generate code that introduces a lot of branches and control flow, which your CPU branch predictor might have a harder time with than a series of arithmetic ops and a single table lookup. By the way, thanks for oilshell. I don't use it, but your blog is a superb resource on parsing techniques.
woadwarrior01 8y ago
That remind me, some years ago, I’d created a pull request for redis to use perfect hashing with gperf to parse commands. IIRC, the author turned it down because he was wary of adding the build time dependency on gperf.
- rurban 8y ago
  That's awkward, because the gperf dependency is only needed every 2 years or so, when a new keyword is added. The genererated C code needs to be added to git, and only needs a regen if changed. I do that all the time via gperf or via some perl-generated perfect hash tables, eg for static keywords, Config tables, unicode tables, ... The memory win is always dramatic, like 20x better typically. I also use some standard gperf-fixup scripts for easier inclusion into my code.
nly 8y ago
Some guy called Ilan Schnell wrote a python code generator which uses the very same algorithm, and comes with language templates for Python, C and C++ (and is easy to expand to others), and a dot file generator so you can visualize the graph: http://ilan.schnell-web.net/prog/perfect-hash/ http://ilan.schnell-web.net/prog/perfect-hash/ He also has a superb illustrated explanation of the algorithm, a unique property of which is you get to choose the hash values: http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html I've been using it for years.
- onalark 8y ago
  Ilan Schnell is not "some guy". He's the original primary author of the Anaconda distribution. One of the main reasons that so many data scientists use Python.
  - fao_ 8y ago
    Well, he's just some guy, you know.
    - eesmith 8y ago
      Gag Halfrunt! How's the brain-care biz doing these days? (https://en.wikipedia.org/wiki/Zaphod_Beeblebrox https://en.wikipedia.org/wiki/Zaphod_Beeblebrox )
  - sameerds 8y ago
    whoosh
  - Spare_account 8y ago
    FWIW my understanding of the GP's phrasing was that Ilan Schnell is a significant person, it was implied.
- krackers 8y ago
  I think I'm missing something conceptually as to why perfect hashing is even needed in this case. Since postgres only has only about 450 or so keywords, shouldn't it suffice to just use a standard string hashing algorithm like: int Hash(string x) { unsigned int h = 31; for(int i = 0; i < x.length(); i++) { h = (h * 76991) ^ (x[i] * 77003); } return h; } Which I tested and seems to work fine with no collisions for the ~440 tokens postgres has. It's definitely not as theoretically fulfilling as a constructive way to generate perfect hashes, but unless they plan to add hundreds of new keywords in the future shouldn't standard hash functions work (after tweaking the constants to ensure that no collisions occur for their particular set of words)?
deleted 8y ago
[deleted]
innagadadavida 8y ago
The optimal algorithm is the CHD algorithm - the function can use as little as 1.6bits per key. http://cmph.sourceforge.net/papers/esa09.pdf http://cmph.sourceforge.net/papers/esa09.pdf There are implementations in Python: python chd perfect hashing and in go: https://github.com/alecthomas/mph https://github.com/alecthomas/mph In addition to the author's C code.
- alnsn 8y ago
  Space optimal isn’t necessarily the fastest. Note that PostgreSQL code uses 2-graph instead of a more compact 3-graph version. The latter is noticeably more compact: 1.25 vs 2.1 factor.
symisc_devel 8y ago
SQLite already implemented such mechanism[0] that determines whether or not a given identifier is really an SQL keyword. The result is a single static hashtable (C array of chars) with O(1) lookup result. This is the fastest known implementation for keyword lookup. [0]: https://sqlite.org/src/artifact/1f7f2ac1d9f262c0 https://sqlite.org/src/artifact/1f7f2ac1d9f262c0
- anarazel 8y ago
  I'm not clear as to why that'd be faster than what we/PG has done. On a quick skim that allows for conflicts in the hashtable, which our new implementation doesn't? Ours is also a C array (albeit of offsets into one blob of string srather than the strings directly, the higher data density achievable due to that was worth it).
Leszek 8y ago
We recently started using perfect hashing in V8's parser, also with measurable performance improvement (even over what we had previously, a first character jump table followed by linear search). It's always nice to apply that computer science education to a real world problem.
- miclill 8y ago
  Could you provide a link to the implementation, please?
  - Leszek 8y ago
    Just a wrapper around gperf: https://cs.chromium.org/chromium/src/v8/src/parsing/keywords-gen.h https://cs.chromium.org/chromium/src/v8/src/parsing/keywords... https://cs.chromium.org/chromium/src/v8/tools/gen-keywords-gen-h.p https://cs.chromium.org/chromium/src/v8/tools/gen-keywords-g...
w23j 8y ago
Since there is a lot of discussion about alternative solutions to the keyword lookup problem I was wondering, why Tries were not mentioned yet. Since the current implementation has to do a string compare after the hash, wouldn't a Trie be at least as fast? Am I missing something? Are there other disadvantages?
- krackers 8y ago
  Someone else can probably comment better but hashing seems more efficient memory wise than holding the trie in memory, and hashing might probably also better cache-wise compared to jumping between the nodes of the trie.
- Someone 8y ago
  For the trie, you still would have to do multiple character comparisons (on level 1, on average about 13, I guess, given that I read there are 400 keywords, and 26 characters in the alphabet). Presumably, hashing the string is faster. I think that partly is because it introduces fewer cache misses than walking a trie. Both a this and a trie have to walk the input string, but code using a trie jumps around the trie, while this code only compare to the keyword, stored in contiguous bytes. Another reason might be that trie-based code is worse for branch prediction logic.
  - w23j 8y ago
    Regarding your first point: One possible implementation of tries uses an array with length "size of alphabet" to store the children of a node. So at each node it's just an offset into an array, not multiple character comparisons. Of course your other points are valid. Thank you for your answer. So I gather the differences are rather subtle. I was wondering if I was missing something bigger.
    - Someone 8y ago
      Even assuming just a-z, that array will be mostly empty at lower levels, and most nodes are at lower levels. That’s not good for avoiding cache misses. There are tricks to counteract that (you don’t store pointers to lower levels, for example, but offsets, because at typical sizes of a trie you can store them in way fewer bits), and I haven’t timed any implementation for decades, but it would surprise me if such an approach would improve performance on lower levels. You could use it at top level (basically replacing the trie with separate tries for each starting letter) Also, the ‘search for a character in an array’ code can be sped up by using vector instructions nowadays (can’t find a link for the exact code, but http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html may give ideas). Whether want to do that because of power usage concerns is a completely different can of worms.
deleted 8y ago
[deleted]
senderista 8y ago
If your keyword list is small, you can just tweak a Pearson hash function (i.e. random permutation) until you get the desired result: http://burtleburtle.net/bob/hash/perfect.html http://burtleburtle.net/bob/hash/perfect.html
- rurban 8y ago
  Yes, you can, but this approach is better. Pearson would beat CHM on very small CPU's (8-16bit) and it is not guaranteed to find a good permutation. With CHM it's much easier. Most important thing is to store the keywords for the false positive verification in an continuous const char const* array.
sheerun 8y ago
Wouldn't decision trees be useful for constructing most efficient perfect hash function?

328 points by boshomi 8y ago

see also: Joerg Sonnenberger: Perfecting hashing in NetBSD (P3B, AsiaBSDCon 2013) [1] [1] https://www.youtube.com/watch?v=87pUZYERkNQ https://www.youtube.com/watch?v=87pUZYERkNQ (youtube)

robustpastoral 8y ago
Thanks

rurban 8y ago

perl, nice!

ricardobeat 8y ago
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.
goosewaterfan 8y ago
Always great to see some perl these days.

Tostino 8y ago

I love seeing all the work and optimizations that get done on Postgres. Very interesting.

koolba 8y ago

So is the idea here to generate a perfect hash table for the known set of SQL keywords in the parser rather than doing a binary search on the fly?

anarazel 8y ago
Correct.

canadev 8y ago

Can someone put this in lay terms for a casual postgresql user?

p4lindromica 8y ago
A perfect hash is one in which their are no collisions for a given data set, which guarantees O(1), or constant, lookup time. This patch introduces a perl script which computes a perfect hash function at build time given the current set of SQL keywords. The old keyword lookup method uses binary search. Binary search is a search algorithm that must compare at most O(log n) entries before finding a match. Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup.
- anarazel 8y ago
  > Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup. Worthwhile to note that that speedup is for the raw parsing, without parse-analysis (i.e. looking up the tables referenced and such), planning (figuring out how to execute the query) and execution. So end-user impact will be much smaller than 20%. But for some cases, e.g. when many columns are referenced, it'll be measurable.
  - the_duke 8y ago
    Column names aren't keywords though, are they?. Using a perfect hash table is definitely cool, but it's hard to imagine a query with so many keywords that this would have a measurable impact on total query execution time.
    - anarazel 8y ago
      Due to the desire to have keywords that aren't fully reserved (we have keyword classes that are fully reserved, can appear as type names, can appear as column names, or can appear nearly everywhere) we/PG need to look up whether a specific string is a keyword or an identifier in a number of places in the scanner/parser. Addendum: And that indeed means that column references, unless quoted with "", used to go through the binary search and now go through the perfect hash. Edit: Typo

sjroot 8y ago

From the post: "The time savings is indeed significant: preliminary testing suggests that the total time for raw [SQL] parsing (flex + bison phases) drops by ~20%." Very impressive work!

amelius 8y ago
Impressive? They changed one textbook algorithm by another one. It turns out to be faster, but it might as well be slower for certain inputs (which might be common). Also, when they increase the number of keywords in the future, they might have to reconsider the implementation.
- jimktrains2 8y ago
  I'm having trouble coming up with a scenario where perfect hashing Vs a binary search tree is slower. Also, yes, the very nature of perfect hashing means it will very potential need to be updated with additional keywords. However, that doesn't happen often and this is a small amount of work for what all would be entailed with a new keyword.
- molyss 8y ago
  I think it's impressive, but maybe not for the same reasons as the OP : that means that keyword lookup accounted for at least 20% of total SQL parsing time. That's a surprise to me !
  - anarazel 8y ago
    Note it's the "raw" parsing time. If you include the semantic parse-analysis phase, i.e. looking up table names etc, it's a much smaller portion.
  - sjroot 8y ago
    This is basically what I was thinking -- that a relatively minor change to the parsing process could yield such significant results.
- geophile 8y ago

jnwatson 8y ago

Isn’t this just textbook perfect hashing? This is literally a primary use case for it.

zzzcpan 8y ago
Textbook here would be using goto-based DFA state machine (ragel can generate one).
- PhilWright 8y ago
  If that would be faster, why not do that then?
  - wahern 8y ago
    Because they're using Flex & Bison, not Ragel. The latter is specialized for and excels at defining and applying finite state machines. But while the design of Ragel makes it relatively trivial to build ASTs during the parse, you still have to do it manually. Flex & Bison automate much more of the process of transforming an input stream to a tree. Dropping them and moving to Ragel would be a serious refactor. FWIW, Flex also builds DFAs. It's just that the design of Ragel is so elegant that Ragel DFA machines are more flexible, easier to compose (both in terms of combining abstract machines and in terms of language-level integration), and yet still incomparably faster. While a straight DFA match should in principle be at least as efficient as a perfect hash[1], this is really only realized with something like Ragel or Intel Hyperscan. As awesome as RE2 is, the performance isn't in the same league as those two; ditto for JIT'd PCREs and re2c--neither are comparable to Ragel or Hyperscan. [1] At least until the input set grows into the thousands or millions of items--at some point the size of the generated DFA grows faster than and overtakes the size of the generated perfect hash function.
    - goldenkey 8y ago
      Wouldn't a DFA be faster than perfect hashing here if only because non-keywords can collide with keyword hash values, so a strcmp is always going to be necessary regardless of the actual keyword differentiation? I tried looking at the code to see if they were excluding non-keywords at some other stage - because then this would seem redundant?

tachang 8y ago

Reading the discussion thread is fantastic. The postgres community culture definitely feels a lot different than some of the other open source projects I've seen.

amluto 8y ago

Binary search is a pretty bad algorithm. Sure, it runs in O(log n) time and it's more or less the best you can do to solve the general problem of finding something in a sorted list, but that does not mean it's a good way to create an immutable list of things that can be searched using comparisons. In particular, binary search has awful cache locality. Until you get very close to your target, you are essentially hitting a random cache line (and maybe even a random page for large lists) for every comparison. This is bad. A B-tree-like structure that is never modified is very easy to make, and it will be much faster. This came up with the ORC unwinder in Linux. We got something like a 4x speedup by changing from binary search to something a bit more clever to find unwind entries in the table.

Terr_ 8y ago
> In particular, binary search has awful cache locality. That makes me think of an idea which I'm certain can't be original, but I can't think of the jargon for what it's called. Suppose you have a fixed-length sorted array, and its binary-search can be visualized as a tree. Traverse that tree in level-order and pop it into a helper-array, arranged much like a heap: The midpoint is first and all left and right children are proceed from there at offsets that you can predict. So the original array [A,B,C,D,E,F,G] has a data-structure for searching of [(D,3), (B,1), (F,5), (A,0), (C,2), (E,4), (G,6)] While the high-indexed items will get spread out, the most common and sequential activity occurs all together near the lower indexes, minimizing large jumps. Since each entry has the original index stored, you can always switch back to the initial array when a different strategy (e.g. linear scan) becomes preferable.
- RcouF1uZ4gsC 8y ago
  Here is a writeup of the idea and some numbers. http://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html http://bannalia.blogspot.com/2015/06/cache-friendly-binary-s...
- macdice 8y ago
  Take a look at ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING. TL;DR there are schemes like this called "Eytzinger" and "van Emde Boas". https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf The topic of arranging keys like this within index pages (or maybe elsewhere) has come up on the pgsql-hackers mailing list before: https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A7-9642-7830DC1108F1%40yandex-team.ru https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A...

deleted 8y ago

[deleted]

chubot 8y ago

FYI PostGres appears to have over 400 keywords, shown here: https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/include/parser/kwlist.h;h=adeb834ce82422940cb89798ee18457c17c10853; https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f... The way I've seen most languages do it is something like this: switch (c[0]) { case 'c': if (strcmp(c, "case") == 0) return CASE; if (strcmp(c, "continue") == 0) return CONTINUE; ... case 'f': if (strcmp(c, "for") == 0) return FOR; if (strcmp(c, "friend") == 0) return FRIEND; ... } I suspect that's good enough if you have a typical keyword list of say 20-100. I just looked at Clang and it appears to build the list at runtime, using a regular hash table. I think this is because it has to handle C, C++, and Objective C, and they have different sets of keywords. It seems like they could change it to use something like perfect hashing, and if that's even a 1% win, it would be worth it for the extra build complexity, since C and C++ compilation take up so many CPU cycles in the world. See lib/Basic/IdentifierTable.cpp. Although another problem is that the list of keywords depends on whether you're compiling C89, C99, C++98, C++11, etc. But that is a finite list so it seems like it still can be done with code generation ahead of time like PostGres does. In Oil [1] I use re2c [1] recognize keywords, along with the rest of the complex lexing process, and it works well. It builds a DFA expressed in C code. The slower parts are elsewhere :) EDIT: In theory, the DFA seems better than perfect hashing because you can bail on the second character if you get "xzoo" and no keyword starts with "xz". I think with perfect hashing yo still have to look at every byte. The switch statement above also avoids looking at every byte in certain cases. [1] http://www.oilshell.org/ http://www.oilshell.org/ [2] http://re2c.org/ http://re2c.org/

mark-r 8y ago
There's a lot of overlap with those keywords, so perhaps the best bet is to create a single superset and use an attribute returned by the lookup to see if it's needed by the target language.
nly 8y ago
You don't necessarily have to look at every byte to compute the hash - gperf will generate hash functions that uses only a few characters at seemingly random offsets. You do however have to do a full strcmp() to rule out a hash collision (with words outside of your set) so DFA wins there. Imho though, the most significant difference between DFA and a PHF would be the DFA would likely generate code that introduces a lot of branches and control flow, which your CPU branch predictor might have a harder time with than a series of arithmetic ops and a single table lookup. By the way, thanks for oilshell. I don't use it, but your blog is a superb resource on parsing techniques.

woadwarrior01 8y ago

That remind me, some years ago, I’d created a pull request for redis to use perfect hashing with gperf to parse commands. IIRC, the author turned it down because he was wary of adding the build time dependency on gperf.

rurban 8y ago
That's awkward, because the gperf dependency is only needed every 2 years or so, when a new keyword is added. The genererated C code needs to be added to git, and only needs a regen if changed. I do that all the time via gperf or via some perl-generated perfect hash tables, eg for static keywords, Config tables, unicode tables, ... The memory win is always dramatic, like 20x better typically. I also use some standard gperf-fixup scripts for easier inclusion into my code.

nly 8y ago

Some guy called Ilan Schnell wrote a python code generator which uses the very same algorithm, and comes with language templates for Python, C and C++ (and is easy to expand to others), and a dot file generator so you can visualize the graph: http://ilan.schnell-web.net/prog/perfect-hash/ http://ilan.schnell-web.net/prog/perfect-hash/ He also has a superb illustrated explanation of the algorithm, a unique property of which is you get to choose the hash values: http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html I've been using it for years.

onalark 8y ago
Ilan Schnell is not "some guy". He's the original primary author of the Anaconda distribution. One of the main reasons that so many data scientists use Python.
- fao_ 8y ago
  Well, he's just some guy, you know.
  - eesmith 8y ago
    Gag Halfrunt! How's the brain-care biz doing these days? (https://en.wikipedia.org/wiki/Zaphod_Beeblebrox https://en.wikipedia.org/wiki/Zaphod_Beeblebrox )
- sameerds 8y ago
  whoosh
- Spare_account 8y ago
  FWIW my understanding of the GP's phrasing was that Ilan Schnell is a significant person, it was implied.
krackers 8y ago
I think I'm missing something conceptually as to why perfect hashing is even needed in this case. Since postgres only has only about 450 or so keywords, shouldn't it suffice to just use a standard string hashing algorithm like: int Hash(string x) { unsigned int h = 31; for(int i = 0; i < x.length(); i++) { h = (h * 76991) ^ (x[i] * 77003); } return h; } Which I tested and seems to work fine with no collisions for the ~440 tokens postgres has. It's definitely not as theoretically fulfilling as a constructive way to generate perfect hashes, but unless they plan to add hundreds of new keywords in the future shouldn't standard hash functions work (after tweaking the constants to ensure that no collisions occur for their particular set of words)?

deleted 8y ago

[deleted]

innagadadavida 8y ago

The optimal algorithm is the CHD algorithm - the function can use as little as 1.6bits per key. http://cmph.sourceforge.net/papers/esa09.pdf http://cmph.sourceforge.net/papers/esa09.pdf There are implementations in Python: python chd perfect hashing and in go: https://github.com/alecthomas/mph https://github.com/alecthomas/mph In addition to the author's C code.

alnsn 8y ago
Space optimal isn’t necessarily the fastest. Note that PostgreSQL code uses 2-graph instead of a more compact 3-graph version. The latter is noticeably more compact: 1.25 vs 2.1 factor.

symisc_devel 8y ago

SQLite already implemented such mechanism[0] that determines whether or not a given identifier is really an SQL keyword. The result is a single static hashtable (C array of chars) with O(1) lookup result. This is the fastest known implementation for keyword lookup. [0]: https://sqlite.org/src/artifact/1f7f2ac1d9f262c0 https://sqlite.org/src/artifact/1f7f2ac1d9f262c0

anarazel 8y ago
I'm not clear as to why that'd be faster than what we/PG has done. On a quick skim that allows for conflicts in the hashtable, which our new implementation doesn't? Ours is also a C array (albeit of offsets into one blob of string srather than the strings directly, the higher data density achievable due to that was worth it).

Leszek 8y ago

We recently started using perfect hashing in V8's parser, also with measurable performance improvement (even over what we had previously, a first character jump table followed by linear search). It's always nice to apply that computer science education to a real world problem.

miclill 8y ago
Could you provide a link to the implementation, please?
- Leszek 8y ago
  Just a wrapper around gperf: https://cs.chromium.org/chromium/src/v8/src/parsing/keywords-gen.h https://cs.chromium.org/chromium/src/v8/src/parsing/keywords... https://cs.chromium.org/chromium/src/v8/tools/gen-keywords-gen-h.p https://cs.chromium.org/chromium/src/v8/tools/gen-keywords-g...

w23j 8y ago

Since there is a lot of discussion about alternative solutions to the keyword lookup problem I was wondering, why Tries were not mentioned yet. Since the current implementation has to do a string compare after the hash, wouldn't a Trie be at least as fast? Am I missing something? Are there other disadvantages?

krackers 8y ago
Someone else can probably comment better but hashing seems more efficient memory wise than holding the trie in memory, and hashing might probably also better cache-wise compared to jumping between the nodes of the trie.
Someone 8y ago
For the trie, you still would have to do multiple character comparisons (on level 1, on average about 13, I guess, given that I read there are 400 keywords, and 26 characters in the alphabet). Presumably, hashing the string is faster. I think that partly is because it introduces fewer cache misses than walking a trie. Both a this and a trie have to walk the input string, but code using a trie jumps around the trie, while this code only compare to the keyword, stored in contiguous bytes. Another reason might be that trie-based code is worse for branch prediction logic.
- w23j 8y ago
  Regarding your first point: One possible implementation of tries uses an array with length "size of alphabet" to store the children of a node. So at each node it's just an offset into an array, not multiple character comparisons. Of course your other points are valid. Thank you for your answer. So I gather the differences are rather subtle. I was wondering if I was missing something bigger.
  - Someone 8y ago
    Even assuming just a-z, that array will be mostly empty at lower levels, and most nodes are at lower levels. That’s not good for avoiding cache misses. There are tricks to counteract that (you don’t store pointers to lower levels, for example, but offsets, because at typical sizes of a trie you can store them in way fewer bits), and I haven’t timed any implementation for decades, but it would surprise me if such an approach would improve performance on lower levels. You could use it at top level (basically replacing the trie with separate tries for each starting letter) Also, the ‘search for a character in an array’ code can be sped up by using vector instructions nowadays (can’t find a link for the exact code, but http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html may give ideas). Whether want to do that because of power usage concerns is a completely different can of worms.

deleted 8y ago

[deleted]

senderista 8y ago

If your keyword list is small, you can just tweak a Pearson hash function (i.e. random permutation) until you get the desired result: http://burtleburtle.net/bob/hash/perfect.html http://burtleburtle.net/bob/hash/perfect.html

rurban 8y ago
Yes, you can, but this approach is better. Pearson would beat CHM on very small CPU's (8-16bit) and it is not guaranteed to find a good permutation. With CHM it's much easier. Most important thing is to store the keywords for the false positive verification in an continuous const char const* array.

sheerun 8y ago

Wouldn't decision trees be useful for constructing most efficient perfect hash function?