 |
lua-l archive |
|
|
||
|
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!
I did!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 box.
(Of course, these conclusions are only valid if everything's coded right)
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 and LuaJIT.
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 them.
Cheers, Geoff