[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] LuaJIT-2.0.0-beta1
- From: Geoff Leyland <geoff_leyland@...>
- Date: Thu, 5 Nov 2009 14:30:29 +1300
On 3/11/2009, at 11:57 PM, Mike Pall wrote:
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!
Running a test to find the best leaf size on my spare hardware is very
slow (not enough memory), but it seems that the best size for a leaf
in the kdtree (for the NY map, this hardware, LJ2 etc) is about 400
items (not the 100 I had). I'll run it on something more likely to
get a result while I'm out.
Still, 400 is a lot less than the 800,000-odd items in the map, so
modern architecture is all good, but those logs tend to win in the
end. I tried querying with a leaf size larger than the items in the
map (ie a linear search), but I got bored of waiting even on the fast
(Of course, these conclusions are only valid if everything's coded
Anyway, this is no longer particularly relevant to LuaJIT, other than
I'm curious to see if the optimal leaf size is different between Lua
I'm trying to get the rima unit tests running on LJ2 and will
hopefully get there soon. The Lulu patch fixed one segfault, and the
other problems so far have been me being lax with tables with nils in