Perfect hashing for string switch

[BCS]

Hello Matti,

> On 2010-01-27 15:17, bearophile wrote:
> 
>> BCS:
>> 
>>> Have you compared it to a decisition tree or lex style state
>>> mechine?
>>> 
>> I have now implemented that too, it was not an immediate thing to do
>> (I have removed the versions 2 to 5 to reduce code size on codepad):
>> 
>> http://codepad.org/zOmPeE13
>> 
>> The results are good:
>> Timings, ldc, seconds:
>> test1: 4.48 // normal string switch
>> test2: 2.98 // perfect hash
>> test3: 2.09
>> test4: 2.07
>> test5: 5.44 // AA. Tango AA opIn_r is bug-slow
>> test6: 1.18 // new result
>> I hope this is enough.
>> I have created that large finite state machine in D with a Python
>> program :-)
> Your test6 is invalid: it reads beyond the bounds of the given array.
> For example with input "th", it will check whether the third character
> is 'i'; but the length of the array is only 2, so it shouldn't be
> doing that.
> 

A simple fix to that is to make he first transition of the state machine 
based on the length of the key.

that is, 'if' at the top becomes:

            switch(word.length) {
            case 13: goto S...:
            case 12: goto S...:
            case 11: goto S...:
            case 10: goto S...:
            case 9: goto S...:
            case 8: goto S...:
            case 7: goto S...:
            case 6: goto S...:
            case 5: goto S...:
            case 4: goto S...:
            case 3: goto S...:
            case 2: goto S...:

            default: goto UNREC;
            }

--

<IXOYE><