5 ms·

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=adeb834c

by 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.
- chubot 8y ago
  Thanks, glad you like the blog! Nobody is really using Oil yet because I made it more of a programming language than an interactive shell, but that's changing right now :) There should be something interesting for people to use within a few months. I would like to see a comparison between DFA and perfect hashing sometime. I wanted to do it myself, but I couldn't justify it because there are other slow parts of the parser. I am surprised that postgres got such a large speedup, to be honest. I guess it has to do with the large number of keywords. BTW, this is related: https://github.com/oilshell/blog-code/tree/master/fgrep-problem-benchmarks https://github.com/oilshell/blog-code/tree/master/fgrep-prob... I match thousands of fixed strings "in parallel", and compare different regex engines, and compilation vs. interpretation. The biggest surprise is that interpreted regexes like grep and ripgrep are faster than compiled DFAs with re2c for 13 strings. When you search for thousands of strings in parallel, re2c takes over. This could be compared to perfect hashing, I think. This will be mentioned on my blog, but I'm not sure if I'll have time to do a detailed breakdown. The motivation for this was somewhat different. I was trying to understand if the Aho-Corasick algorithm to generate a DFA from fixed strings is "important", given that you can already generate a DFA from a regex. In other words, Aho-Corasick seems like more or less a special case of the typical regex -> DFA compilation.
caf 8y ago
When parsing C, typedef names essentially introduce new keywords so the table is constantly changing.
- kccqzy 8y ago
  typedef introduces new type names not keywords.
  - barrkel 8y ago
    Depending on whether an identifier is a type name or not affects the grammar. x * y; Is this a multiplication expression or a variable pointer to a value of type x? (x) * y Is this a typecast of *y to the x type, or is it x multiplied by y? This is what people mean when they say that typedefs introduce keywords in C. An easy way to solve it is to look up type names from the lexer and return a different token type (i.e. not identifier). This puts type names into a different category of lexeme to identifiers. https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack
    - summerlight 8y ago
      Why is this relevant to keyword lookup? Anyway you're not supposed to use reserved keywords as either a variable or type name except primitive types (which is obviously a type).
      - barrkel 8y ago
        Because it happens in the lexer, and depending on how you design your symbol table lookups, you may want to use the same hash function for all table lookups, instead of calculating different hashes for each table. Symbol table lookups can compare hash value first (store the full hash code per entry) to skip the expensive string comparison too. Perfect hashing isn't always what you want in any case. For many languages, especially symbolically flavoured ones like C, most strings found by the lexer aren't keywords. A hash table which is mostly empty and is statically verified not to contain keyword collisions is ideal. Keep the hash code calculation separate, and do it only once. Little point in repeatedly calculating it.
imaginenore 8y ago
I wonder why there's a need for any perfect hash for a case like this. If you only have a few hundred options, you can simply generate code that will look like: switch (c[0]) { case 'c': switch (c[1]) { case 'a': switch (c[2]) { case 'c': ... } ... } break; ... case 'f': ... } You can even make it optimal, require the fewest number of single-byte comparisons. Like if you know c[0]=='c' and c[3]=='i', then the only possible answer (of a Postgre keyword) is "chain".

by chubot 8y ago

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.

chubot 8y ago
Thanks, glad you like the blog! Nobody is really using Oil yet because I made it more of a programming language than an interactive shell, but that's changing right now :) There should be something interesting for people to use within a few months. I would like to see a comparison between DFA and perfect hashing sometime. I wanted to do it myself, but I couldn't justify it because there are other slow parts of the parser. I am surprised that postgres got such a large speedup, to be honest. I guess it has to do with the large number of keywords. BTW, this is related: https://github.com/oilshell/blog-code/tree/master/fgrep-problem-benchmarks https://github.com/oilshell/blog-code/tree/master/fgrep-prob... I match thousands of fixed strings "in parallel", and compare different regex engines, and compilation vs. interpretation. The biggest surprise is that interpreted regexes like grep and ripgrep are faster than compiled DFAs with re2c for 13 strings. When you search for thousands of strings in parallel, re2c takes over. This could be compared to perfect hashing, I think. This will be mentioned on my blog, but I'm not sure if I'll have time to do a detailed breakdown. The motivation for this was somewhat different. I was trying to understand if the Aho-Corasick algorithm to generate a DFA from fixed strings is "important", given that you can already generate a DFA from a regex. In other words, Aho-Corasick seems like more or less a special case of the typical regex -> DFA compilation.

caf 8y ago

When parsing C, typedef names essentially introduce new keywords so the table is constantly changing.

kccqzy 8y ago
typedef introduces new type names not keywords.
- barrkel 8y ago
  Depending on whether an identifier is a type name or not affects the grammar. x * y; Is this a multiplication expression or a variable pointer to a value of type x? (x) * y Is this a typecast of *y to the x type, or is it x multiplied by y? This is what people mean when they say that typedefs introduce keywords in C. An easy way to solve it is to look up type names from the lexer and return a different token type (i.e. not identifier). This puts type names into a different category of lexeme to identifiers. https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack
  - summerlight 8y ago
    Why is this relevant to keyword lookup? Anyway you're not supposed to use reserved keywords as either a variable or type name except primitive types (which is obviously a type).
    - barrkel 8y ago
      Because it happens in the lexer, and depending on how you design your symbol table lookups, you may want to use the same hash function for all table lookups, instead of calculating different hashes for each table. Symbol table lookups can compare hash value first (store the full hash code per entry) to skip the expensive string comparison too. Perfect hashing isn't always what you want in any case. For many languages, especially symbolically flavoured ones like C, most strings found by the lexer aren't keywords. A hash table which is mostly empty and is statically verified not to contain keyword collisions is ideal. Keep the hash code calculation separate, and do it only once. Little point in repeatedly calculating it.

imaginenore 8y ago

I wonder why there's a need for any perfect hash for a case like this. If you only have a few hundred options, you can simply generate code that will look like: switch (c[0]) { case 'c': switch (c[1]) { case 'a': switch (c[2]) { case 'c': ... } ... } break; ... case 'f': ... } You can even make it optimal, require the fewest number of single-byte comparisons. Like if you know c[0]=='c' and c[3]=='i', then the only possible answer (of a Postgre keyword) is "chain".