<!DOCTYPE html>
<html data-lt-installed="true">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body style="padding-bottom: 1px;">
<p>Hi, Sergey!</p>
<p>thanks for the patch! LGTM</p>
<p>Sergey</p>
<div class="moz-cite-prefix">On 12/26/25 12:17, Sergey Kaplun wrote:<br>
</div>
<blockquote type="cite"
cite="mid:509bfe7fbf8b7bf14ed1fe6ddbef5e9615150b93.1766738771.git.skaplun@tarantool.org">
<pre wrap="" class="moz-quote-pre">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:
+-- <a class="moz-txt-link-freetext" href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html">https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html</a>
+
+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<a class="moz-txt-link-rfc2396E" href="it.+bench:add({+name=">" it.
+bench:add({
+ name = "</a>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,
+ }
+
+ <a class="moz-txt-link-freetext" href="bench:add(tree_bench)">bench:add(tree_bench)</a>
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()
</pre>
</blockquote>
</body>
<lt-container></lt-container>
</html>