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!
"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!
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.
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.
1) Yes, a 20% improvement is impressive, especially in such a major component of such an important and long-lived piece of software.
2) What do you mean "certain inputs"? There is a fixed set of keywords. The set of inputs is known. It's a great application for perfect hashing. Or do you mean that some keys are going to be slower to search for than others? The best case of binary search is that you search for the key in the exact middle of the table, which requires to compare each character of the search key. (Searching for any other key will require cache misses, possibly, and additional scans of the key's characters.) By contrast, for perfect hashing, you scan the key once to compute the hash value and go directly to the correct slot. So the hash lookup for any key is pretty close to identical to the best case of the binary search.
3) When they add new keywords, they generate a different hash function. That's easy. The implementation does not have to be reconsidered.