[self-interest] embedding based prototype languages

Steve Dekorte steve at dekorte.com
Thu Nov 7 06:24:57 UTC 2002


On Wednesday, November 6, 2002, at 07:30 PM, James McCartney wrote:
>> A perfect hash would take care of that(I use them in Io)
> I'm not really sure that the perfect hash as you have implemented them
> really buys you anything. You use a prime sized table and the %
> operator

Actually, I don't use a prime size table. The table grows by one until 
the hash is perfect, so it can be any size above the minimum.

> instead of using a power of two sized table and masking.

Memory usage may be a problem there. The important bit about getting a 
small perfect hash is having a lot of sizes to try out (because the 
chance of any given small size working is small). There aren't many 
powers of 2 before you get big numbers.

> Mod % is a pretty slow operation.

That's true.

> In the time it takes to do the % operation
> you could probably have chained along once. With a 0.5 load factor and
> separate chaining, the average chain length is 1.27 . So I'd think that
> your perfect hash is not really winning on performance, but is losing
> big on space.

I've found it doesn't take much space as long as the number of slots is 
low(which is typical when using differential inheritance).

But I'd certainly like to move to another technique if it's better. 
I'll run a memory&speed comparison if you send me a piece of your 
sample code(just the hash code) and post the results.

Cheers,
Steve
OSX freeware and shareware: http://www.dekorte.com/downloads.html




More information about the Self-interest mailing list