Hi, Sergey!

thanks for the patch! LGTM

Sergey

This patch adjusts the aforementioned test to use the benchmark
framework introduced before. The default arguments are adjusted
according to the <PARAM_x86.txt> file. The arguments to the script still
can be provided in the command line run.

The test cases are split by the different types of trees:
1) stretched tree,
2) long-lived tree,
3) several trees with a depth of the power of 2,
4) iteration over all trees in the third test case.

The number of items is the number of `ItemCheck()` first-level calls
performed in the payload.
---
 perf/LuaJIT-benches/binary-trees.lua | 109 ++++++++++++++++++++++-----
 1 file changed, 91 insertions(+), 18 deletions(-)

diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
index bf040466..df288032 100644
--- a/perf/LuaJIT-benches/binary-trees.lua
+++ b/perf/LuaJIT-benches/binary-trees.lua
@@ -1,3 +1,10 @@
+-- The benchmark to check the performance of the GC and memory
+-- allocator. Allocate, walk, and deallocate many bottom-up binary
+-- trees.
+-- For the details, see:
+-- https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html
+
+local bench = require("bench").new(arg)
 
 local function BottomUpTree(item, depth)
   if depth > 0 then
@@ -10,6 +17,8 @@ local function BottomUpTree(item, depth)
   end
 end
 
+-- The checker function. For the tree created with the given
+-- `item` returns `item` - 1 (by induction).
 local function ItemCheck(tree)
   if tree[2] then
     return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
@@ -18,30 +27,94 @@ local function ItemCheck(tree)
   end
 end
 
-local N = tonumber(arg and arg[1]) or 0
+local N = tonumber(arg and arg[1]) or 16
 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 stretchdepth = maxdepth + 1
 
-local longlivedtree = BottomUpTree(0, maxdepth)
+-- Allocate a binary tree to "stretch" memory, check it exists,
+-- and "deallocate" it.
+bench:add({
+  name = "stretch_depth_" .. tostring(stretchdepth),
+  payload = function()
+    local stretchtree = BottomUpTree(0, stretchdepth)
+    local check = ItemCheck(stretchtree)
+    return check
+  end,
+  items = 1,
+  checker = function(check)
+    return check == -1
+  end,
+})
 
-for depth=mindepth,maxdepth,2 do
+-- Allocate a long-lived binary tree that will live on while
+-- other trees are allocated and "deallocated".
+-- This tree created once on the setup for the first test.
+local longlivedtree
+
+-- Allocate, walk, and "deallocate" many bottom-up binary trees.
+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))
+  local tree_bench
+  tree_bench = {
+    name = "tree_depth_" .. tostring(depth),
+    setup = function()
+      if not longlivedtree then
+        longlivedtree = BottomUpTree(0, maxdepth)
+      end
+      tree_bench.items = iterations * 2
+    end,
+    checker = function(check)
+      return check == -iterations * 2
+    end,
+    payload = function()
+      local check = 0
+      for i = 1, iterations do
+        check = check + ItemCheck(BottomUpTree(1, depth)) +
+                ItemCheck(BottomUpTree(-1, depth))
+      end
+      return check
+    end,
+  }
+
+  bench:add(tree_bench)
 end
 
-io.write(string.format("long lived tree of depth %d\t check: %d\n",
-  maxdepth, ItemCheck(longlivedtree)))
+-- Check that the long-lived binary tree still exists.
+bench:add({
+  name = "longlived_depth_" .. tostring(maxdepth),
+  payload = function()
+    local check = ItemCheck(longlivedtree)
+    return check
+  end,
+  items = 1,
+  checker = function(check)
+    return check == -1
+  end,
+})
+
+-- All in one benchmark for the various trees.
+bench:add({
+  name = "all_in_one",
+  payload = function()
+    for depth = mindepth, maxdepth, 2 do
+      local iterations = 2 ^ (maxdepth - depth + mindepth)
+      local tree_bench
+      local check = 0
+      for i = 1, iterations do
+        check = check + ItemCheck(BottomUpTree(1, depth)) +
+                ItemCheck(BottomUpTree(-1, depth))
+      end
+      assert(check == -iterations * 2)
+    end
+  end,
+  -- Geometric progression, starting at maxdepth trees with the
+  -- corresponding step.
+  items = (2 * maxdepth) * (4 ^ ((maxdepth - mindepth) / 2 + 1) - 1) / 3,
+  -- Correctness is checked in the payload function.
+  skip_check = true,
+})
+
+bench:run_and_report()