Re: Lua is faster than Java?

[Mark Hamburg <mhamburg@...>]

Yes. Depending on comparison costs, sometimes linear search is a big win
over more complex data structures. It doesn't degrade particularly
gracefully, however.

Mark

on 7/25/05 4:15 PM, David Given at dg@cowlark.com wrote:

> On Monday 25 July 2005 23:07, Mike Pall wrote:
> [...]
>> I think it was Rici who suggested to me on IRC that a
>> sufficiently optimized and inlined hash method dispatch
>> comes pretty close to the performance of multi-level linear
>> dispatch. The above data supports that reasoning.
> 
> *nods*
> 
> Hash tables are disturbingly fast --- a well tuned hash table can be faster
> than an AVL tree, for example. (But the 'well tuned' bit is *really
> important*.)
> 
> One technique we use extensively at work is to have some complex data
> structure --- AVL tree, hash table, etc --- with a very small cache;
> typically only four slots or so. Doing a cache lookup can then be done
> inline; on the ARM you should be able to do it with a certain amount of
> cheating in four instructions. Depending on your access patterns this can
> have a surprisingly good effect.