From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id 270D416744C3; Mon, 29 Dec 2025 17:04:50 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 270D416744C3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1767017090; bh=akwqvIFY39uebmkZZibbW/f4guhewwlwov2suh7vKBI=; h=Date:To:Cc:References:In-Reply-To:Subject:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=Hd+KGvNSjwqOCrGvAgY9+4BvaZgXH6bSq97P5hmMFmZ0SFsQC2OAglUxfyQFcOlmX gArRJvjzz3nw1iooOlN1FXrqYOLWSJ/CXr+3dGrCu4bIemyOAsTxJ/coz+IZ3c0uuB CXEFmawYfu2D2rMbL37pxTPpGKKQxAoDsVhngT1M= Received: from send218.i.mail.ru (send218.i.mail.ru [95.163.59.57]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 049D216744C1 for ; Mon, 29 Dec 2025 17:04:48 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 049D216744C1 Received: by exim-smtp-7b4fb89df9-4rqsk with esmtpa (envelope-from ) id 1vaDrb-00000000Kck-2zaq; Mon, 29 Dec 2025 17:04:48 +0300 Content-Type: multipart/alternative; boundary="------------Ca00S6ov4FBFZMupIKhdzIa8" Message-ID: <00a72dcc-ce51-4954-93af-538f03d2cbf4@tarantool.org> Date: Mon, 29 Dec 2025 17:04:47 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: Sergey Kaplun Cc: tarantool-patches@dev.tarantool.org References: <509bfe7fbf8b7bf14ed1fe6ddbef5e9615150b93.1766738771.git.skaplun@tarantool.org> In-Reply-To: <509bfe7fbf8b7bf14ed1fe6ddbef5e9615150b93.1766738771.git.skaplun@tarantool.org> X-Mailru-Src: smtp X-4EC0790: 10 X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD979975AF0D777FEBD390EF5E93CD1F77387498C0EC589AA68182A05F538085040385166B3CE4A8D423DE06ABAFEAF6705060DBEDBA37E726A0DDD1C039072FB1BE9F8F47979F3B776 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE792C68BF9CD4C0E9EEA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637AC83A81C8FD4AD23D82A6BABE6F325AC2E85FA5F3EDFCBAA7353EFBB55337566FFA32339A312E8EB222E6B8C2A350BF98170D25828FBE2DA7E789AD3FFCD2240389733CBF5DBD5E913377AFFFEAFD269176DF2183F8FC7C0A3E989B1926288338941B15DA834481FCF19DD082D7633A0EF3E4896CB9E6436389733CBF5DBD5E9D5E8D9A59859A8B65FF0BFC5AEE34BE6CC7F00164DA146DA6F5DAA56C3B73B237318B6A418E8EAB8D32BA5DBAC0009BE9E8FC8737B5C224958C1606C78F2434E76E601842F6C81A12EF20D2F80756B5FB606B96278B59C4276E601842F6C81A127C277FBC8AE2E8B6A4E49BB0F3BA1413AA81AA40904B5D99C9F4D5AE37F343AD1F44FA8B9022EA23BBE47FD9DD3FB595F5C1EE8F4F765FC72CEEB2601E22B093A03B725D353964B0B7D0EA88DDEDAC722CA9DD8327EE4930A3850AC1BE2E735BA6625F88748EAEFC4224003CC83647689D4C264860C145E X-C1DE0DAB: 0D63561A33F958A532A0B81961FA4D5F5002B1117B3ED696515BAF1B33010FFC47A99E6294EE8661823CB91A9FED034534781492E4B8EEAD17AEC49845D0B908 X-C8649E89: 1C3962B70DF3F0AD73CAD6646DEDE191716CD42B3DD1D34CAB70F9BE574AE9C625B6776AC983F447FC0B9F89525902EE6F57B2FD27647F25E66C117BDB76D659E884223F9506A05FDFD309DB0BACD3F86F3D52C2CC2897CE713A5D9E4564251BA1F21F718A81B4A4B8341EE9D5BE9A0ADAD403E885553316E412AD6A4166B68267539EE23E09F8908CD93680B12512CF4C41F94D744909CE2512F26BEC029E55448553D2254B8D95CD72808BE417F3B9E0E7457915DAA85F X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu53w8ahmwBjZKM/YPHZyZHvz5uv+WouB9+ObcCpyrx6l7KImUglyhkEat/+ysWwi0gdhEs0JGjl6ggRWTy1haxBpVdbIX1nthFXMZebaIdHP2ghjoIc/363UZI6Kf1ptIMVTZJppT4ZVHRBB5cmJx9kY0= X-Mailru-Sender: 811C44EDE0507D1FF7A5115BD94F8393F8DD85E2C142D26397B151A33FA7A9F8ABA7BDD432380C5415D9380DA0BDEA11645D15D82EE4B272BD6E4642A116CA93524AA66B5ACBE6721EF430B9A63E2A504198E0F3ECE9B5443453F38A29522196 X-Mras: Ok Subject: Re: [Tarantool-patches] [PATCH v2 luajit 05/41] perf: adjust binary-trees in LuaJIT-benches X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Sergey Bronnikov via Tarantool-patches Reply-To: Sergey Bronnikov Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" This is a multi-part message in MIME format. --------------Ca00S6ov4FBFZMupIKhdzIa8 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit 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 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() --------------Ca00S6ov4FBFZMupIKhdzIa8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit

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()
--------------Ca00S6ov4FBFZMupIKhdzIa8--