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

[Sergey Bronnikov via Tarantool-patches <tarantool-patches@dev.tarantool.org>]

[-- Attachment #1: Type: text/plain, Size: 4716 bytes --]

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?
>
>   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 @@
> +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?
>   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
> +  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?

>   
> -for depth=mindepth,maxdepth,2 do
> +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)))
> +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,
> +})
> +
> +bench:add({
> +  name = "all_in_once",
s/all_in_once/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()

[-- Attachment #2: Type: text/html, Size: 5781 bytes --]