Re: Binarytrees benchmark results

[Tony Finch <dot@...>]

On Mon, 7 Dec 2009, Mike Pall wrote:
> Luís Eduardo Jason Santos wrote:
> > Does anyone knows why the binarytrees benchmark on [1] doesn't have the
> > usual 'killing machine' performance one could expect from Lua?
> > [1] http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytrees&lang=all
>
> All the other language implementations either use a bump allocator
> with a generational GC or a dedicated pool allocator.

I tried simulating a pool allocator using a Lua table, but it was much
slower.

I then wondered how much you are allowed to deviate from the spirit of the
benchmark. In particular this benchmark's trees aren't modified after
being built, so you can use a trick to represent the tree where the entire
thing is stored in one table, and the children of node t[i] are in t[i*2]
and t[i*2+1]. This turned out to be faster. I've attached the modified
code.

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.

local function BottomUpTree(item, depth)
  local tree = {}
  local function rec(node, item, depth)
    tree[node] = item
    if depth > 0 then
      node = node*2
      item = item*2
      depth = depth - 1
      rec(node, item-1, depth)
      rec(node+1, item, depth)
    end
  end
  rec(1, item, depth)
  return tree
end

local function ItemCheck(tree)
  local max = #tree
  local function rec(node)
    local child = node*2
    if child < max then
      return tree[node] + rec(child) - rec(child+1)
    else
      return tree[node]
    end
  end
  return rec(1)
end

local N = tonumber(arg and arg[1]) or 0
local mindepth = 4
local maxdepth = mindepth + 2
if maxdepth < N then maxdepth = N end

do
  local stretchdepth = maxdepth + 1
  local stretchtree = BottomUpTree(0, stretchdepth)
  io.write(string.format("stretch tree of depth %d\t check: %d\n",
    stretchdepth, ItemCheck(stretchtree)))
end

local longlivedtree = BottomUpTree(0, maxdepth)

for depth=mindepth,maxdepth,2 do
  local iterations = 2 ^ (maxdepth - depth + mindepth)
  local check = 0
  for i=1,iterations do
    check = check + ItemCheck(BottomUpTree(1, depth)) +
            ItemCheck(BottomUpTree(-1, depth))
  end
  io.write(string.format("%d\t trees of depth %d\t check: %d\n",
    iterations*2, depth, check))
end

io.write(string.format("long lived tree of depth %d\t check: %d\n",
  maxdepth, ItemCheck(longlivedtree)))