[Tarantool-patches] [PATCH v1 luajit 05/41] perf: adjust binary-trees in LuaJIT-benches

[Sergey Kaplun]

Hi, Sergey!

Thanks for the review!
Please consider my answers below.

On 13.11.25, Sergey Bronnikov wrote:
> Hi, Sergey!
> 
> thanks for the patch!
> 
> On 10/24/25 13:50, Sergey Kaplun wrote:
> > 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.
> > ---
> >
> > I'm not sure that we should distinguish different subtests here.
> > OTOH, how to calculate the amount of items correctly for the whole test
> > instead?

Discussed offline to leave different subtests for now.

> >
> >   perf/LuaJIT-benches/binary-trees.lua | 94 ++++++++++++++++++++++------
> >   1 file changed, 76 insertions(+), 18 deletions(-)
> >
> > diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
> > index bf040466..9d4dc7b4 100644
> > --- a/perf/LuaJIT-benches/binary-trees.lua
> > +++ b/perf/LuaJIT-benches/binary-trees.lua
> > @@ -1,3 +1,4 @@


Also, added the comment with the benchmark description as we discussed
offline.

===================================================================
diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
index ae02a1ab..df288032 100644
--- a/perf/LuaJIT-benches/binary-trees.lua
+++ b/perf/LuaJIT-benches/binary-trees.lua
@@ -1,3 +1,9 @@
+-- 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)
@@ -28,6 +34,8 @@ if maxdepth < N then maxdepth = N end
 
 local stretchdepth = maxdepth + 1
 
+-- Allocate a binary tree to "stretch" memory, check it exists,
+-- and "deallocate" it.
 bench:add({
   name = "stretch_depth_" .. tostring(stretchdepth),
   payload = function()
@@ -41,9 +49,12 @@ bench:add({
   end,
 })
 
+-- 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 tree_bench
@@ -71,6 +82,7 @@ for depth = mindepth, maxdepth, 2 do
   bench:add(tree_bench)
 end
 
+-- Check that the long-lived binary tree still exists.
 bench:add({
   name = "longlived_depth_" .. tostring(maxdepth),
   payload = function()
@@ -83,6 +95,7 @@ bench:add({
   end,
 })
 
+-- All in one benchmark for the various trees.
 bench:add({
   name = "all_in_one",
   payload = function()
===================================================================

> > +local bench = require("bench").new(arg)
> >   
> >   local function BottomUpTree(item, depth)
> >     if depth > 0 then
> > @@ -18,30 +19,87 @@ local function ItemCheck(tree)
> >     end
> >   end
> >   
> > -local N = tonumber(arg and arg[1]) or 0
> > +local N = tonumber(arg and arg[1]) or 16
> Why 16?

It is the default for x86 arch. I've taken the values from PARAMS_x86,
since this is the most important architecture for the Tarantool, see the
commit message.

> >   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
> > +
> > +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
> it deserves a comment

Added the corresponding comment to the `ItemCheck()`.
===================================================================
diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
index 9d4dc7b4..75c60332 100644
--- a/perf/LuaJIT-benches/binary-trees.lua
+++ b/perf/LuaJIT-benches/binary-trees.lua
@@ -11,6 +11,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])
===================================================================

> > +  end,
> > +})
> >   
> > -local longlivedtree = BottomUpTree(0, maxdepth)
> > +-- This tree created once on the setup for the first test.
> > +local longlivedtree
> 
> I don't like that we should save a benchmark state in global variables.
> 
> What if we allow setting a user-defined object that will have a state
> 
> and this state will be passed to checker/payload functions?

This changes the semantics of the benchmark.
It is improtant that the state is created in the first benchmark and
used later as an upvalue, for the example.

> 
> >   

<snipped>

> > +bench:add({
> > +  name = "all_in_once",
> s/all_in_once/all_in_one/?

Renamed:

===================================================================
diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
index 75c60332..ae02a1ab 100644
--- a/perf/LuaJIT-benches/binary-trees.lua
+++ b/perf/LuaJIT-benches/binary-trees.lua
@@ -84,7 +84,7 @@ bench:add({
 })
 
 bench:add({
-  name = "all_in_once",
+  name = "all_in_one",
   payload = function()
     for depth = mindepth, maxdepth, 2 do
       local iterations = 2 ^ (maxdepth - depth + mindepth)
===================================================================

> > +  payload = function()

<snipped>

-- 
Best regards,
Sergey Kaplun