3 ms·

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 of

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

by nly 8y ago

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.