Re: [Tarantool-patches] [PATCH v2 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: 5283 bytes --]

Hi, Sergey!

thanks for the patch! LGTM

Sergey

On 12/26/25 12:17, 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.
> ---
>   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()

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