3 ms·
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 necessar
by 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?
- wahern 8y agoYeah, conceptually for smaller sets a DFA should easily meet or beat perfect hashing for the reason you describe. But because of pipelining, branch prediction, etc, it depends on the details of how the generated parser scans the input stream. A simple hash function is more likely to execute in a tight loop with minimal data dependencies because it's more natural to code it that way; it might be able to consume the stream faster even if performing more work simply because of how it slices the work. I'm not positive, but AFAICT Flex only generates table-driven machines, so at the very minimum the scanner is already handicapped. A tiny table that fits in cache might not be much of a handicap, but I'd be surprised if Flex does an especially good job of that. Any why would it--it's designed to work in tandem with Bison to solve more complex problems, plus it's hemmed in by having to support historical program structures and interfaces, such as liberal use of functions and function pointers for composition.
- rurban 8y agoNo, too branchy and bytewise only. This PH is word wise mostly, and the keywords are longer, ~4-5.
- goldenkey 8y agoStill, even the best strcmp is going to involve some byte checking unless the string is exactly divisible into large words. Wouldn't the efficiency between the two methods mainly depend on the relative odds of non-keywords occurring?