add lua-binarytrees benchmark

1 files changed, 50 insertions, 0 deletions

diff --git a/tests/lua/binarytrees.lua b/tests/lua/binarytrees.lua
new file mode 100644
index 00000000..2ae3dd69
--- /dev/null
+++ b/tests/lua/binarytrees.lua
@@ -0,0 +1,50 @@
+-- The Computer Language Benchmarks Game
+-- http://benchmarksgame.alioth.debian.org/
+-- contributed by Mike Pall
+
+local function BottomUpTree(item, depth)
+  if depth > 0 then
+    local i = item + item
+    depth = depth - 1
+    local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth)
+    return { item, left, right }
+  else
+    return { item }
+  end
+end
+
+local function ItemCheck(tree)
+  if tree[2] then
+    return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
+  else
+    return tree[1]
+  end
+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)))