Re: Possible enhancements for Lua 5.2

[Andre Leiradella <andre@...>]

On 29/06/2011 00:18, TNHarris wrote:
> On 06/26/2011 05:29 PM, Andre Leiradella wrote:
> > But then I'd have to convert my switch to a series of ifs since the
> > pointers to the literals are computed during runtime.
> >
> > I know switches are not great with sparse constant spaces such as when
> > using hashes (i.e. only a few tenths of used values from 2^32 possible
> > values) but I like the compiler doing the binary search for me (gcc
> > does) instead of having to figure it out myself. I'm also experimenting
> > hashing the hash (just shifts and xors, nothing fancy or costly) to make
> > the space dense enough so the switch will (hopefully) become a goto
> > table + one if for each case to see if it's really a match. Better than
> > the hard-coded binary tree...
> >
> > Cheers,
> >
> > Andre
>
> I don't think Lua's table hash for strings is suitable for this. There 
> will be collisions. You should probably use a perfect hash generator 
> like gperf instead.
I've tried that already. gperf is great and solves some problems. It's 
fast (it only compares strings as a final check, it doesn't perform 
logical/arithmetic ops on every character of the string) and can return 
any info attached to the lookup result (like integers in sequence to 
turn switches into computed gotos) but it has a show stopper for me: it 
takes too much memory space.

And sure, there will be collisions. And that's ok as long as you know it.

Cheers,

Andre