Perfect hashing for string switch

[Matti Niemenmaa]

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.

-- 
E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi