• Tom Lane's avatar
    Use perfect hashing, instead of binary search, for keyword lookup. · c64d0cd5
    Tom Lane authored
    We've been speculating for a long time that hash-based keyword lookup
    ought to be faster than binary search, but up to now we hadn't found
    a suitable tool for generating the hash function.  Joerg Sonnenberger
    provided the inspiration, and sample code, to show us that rolling our
    own generator wasn't a ridiculous idea.  Hence, do that.
    
    The method used here requires a lookup table of approximately 4 bytes
    per keyword, but that's less than what we saved in the predecessor commit
    afb0d071, so it's not a big problem.  The time savings is indeed
    significant: preliminary testing suggests that the total time for raw
    parsing (flex + bison phases) drops by ~20%.
    
    Patch by me, but it owes its existence to Joerg Sonnenberger;
    thanks also to John Naylor for review.
    
    Discussion: https://postgr.es/m/20190103163340.GA15803@britannica.bec.de
    c64d0cd5
ecpg_kwlist.h 2.34 KB