[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Possible enhancements for Lua 5.2
- From: Andre Leiradella <andre@...>
- Date: Wed, 29 Jun 2011 01:14:07 -0300
On 29/06/2011 00:18, TNHarris wrote:
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.
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...
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.
And sure, there will be collisions. And that's ok as long as you know it.