Re: [ANN] LuaJIT-2.0.0-beta1

[Mike Pall <mikelu-0911@...>]

Geoff Leyland wrote:
> Like the heap, I managed to screw some of test results up (just in case 
> there's any doubt, I've been waiting for LJ2 with as much anticipation as 
> the rest of the list and am convinced it will make the world a better 
> place.
> My test cases are just a little problematic.

A trace compiler and a modern CPU have something in common: they
don't like branchy code. And CPUs don't like pointer chasing.
That's why standard textbook tree data structures are rarely
the best choice anymore.

The big-O notation assumes constant overhead per access or per
instruction. But that's far from the truth with a modern CPU. An
O(n) linear search can outperform an O(log n) tree search for a
much larger 'n' than you might imagine. Try it!

A case in point are the algorithms and data structures used by
compilers: traditional compilers make heavy use of trees and
pointers, which is one reason why they are usually dead slow.

LuaJIT uses growable arrays with direct indexing for almost
everything. It also employs growable hash tables, semi-perfect
hashes, skip lists, stacks, round-robin queues and bloom filters.
But not a single search tree ...

> Hopefully that's 
> not too much bad coding on my part, and of some help for improving LJ2).

Your code serves as nice worst-case test cases. Very useful,
indeed. Thank you!

BTW: The upcoming beta2 will compile table.insert/table.remove.

> Reading and querying are much better.  Querying is particularly nice: a 
> tree query returns a coroutine iterator, so tracking a mouse moving  
> across a map and highlighting the road it's over allocates an awful lot 
> of coroutines, so lighter coroutines are a real bonus!

Umm yes, that should help. But currently LJ2 doesn't trace across
coroutine boundaries. That's planned for the future.

But for now kdtree-test has this (sad) profile:

  41% Interpreter
  29% Compiled
  19% GC
  11% C functions

--Mike