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 81A6D16C65B7; Fri, 26 Dec 2025 12:20:51 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 81A6D16C65B7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1766740851; bh=IGYeaYGIQCdgJGxmXSiLdlck3U3mIjryxryfQJD0uJ0=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=f1IISr10jSLg0vJs8XLCQCRdt9q7H480KcyZNHVSZCj5Dly66rOl4SgoCOTgqdpnC Caeht34Sm5sPFqWjpUhOCA0SH5q9ZfQUvfgfjfPJDjc4dXr40V8t04f9LFpQjjykIq 2SC9JRAnJpdsgEHoWcCcm8cjIWbTvYsAR4pl86oM= Received: from send58.i.mail.ru (send58.i.mail.ru [89.221.237.153]) (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 B760516AE268 for ; Fri, 26 Dec 2025 12:18:24 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org B760516AE268 Received: by exim-smtp-7b4fb89df9-lft7n with esmtpa (envelope-from ) id 1vZ3xn-000000008Cp-3OWb; Fri, 26 Dec 2025 12:18:24 +0300 To: Sergey Bronnikov Date: Fri, 26 Dec 2025 12:17:36 +0300 Message-ID: <509bfe7fbf8b7bf14ed1fe6ddbef5e9615150b93.1766738771.git.skaplun@tarantool.org> X-Mailer: git-send-email 2.52.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Mailru-Src: smtp X-4EC0790: 10 X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD979975AF0D777FEBD651A111AECFA267DF4E9497E9DD4D3AA182A05F5380850403B30D129F610B3913DE06ABAFEAF670538DFA920D44CABF1B4FA2C6BBBE99EF9B949C4EC051D72BC X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7FEAC828D2BF6EC3CEA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637AC83A81C8FD4AD23D82A6BABE6F325AC2E85FA5F3EDFCBAA7353EFBB55337566657B88B02DF8C86932AB2B297BD91C738EDCD39A7D089D1AA053949A71A04BED389733CBF5DBD5E913377AFFFEAFD269176DF2183F8FC7C0F60A601881DBAB3C8941B15DA834481FCF19DD082D7633A0EF3E4896CB9E6436389733CBF5DBD5E9D5E8D9A59859A8B6B0E9FD5D4288160ECC7F00164DA146DA6F5DAA56C3B73B237318B6A418E8EAB86D1867E19FE14079C09775C1D3CA48CF3D321E7403792E342EB15956EA79C166A417C69337E82CC275ECD9A6C639B01B78DA827A17800CE79E9721B410A3B6ED731C566533BA786AA5CC5B56E945C8DA X-C1DE0DAB: 0D63561A33F958A55E6BECD833BFC6C45002B1117B3ED6966D7936D2954CEEFB361FAC1196A180DE823CB91A9FED034534781492E4B8EEAD6A17C1D737525568C79554A2A72441328621D336A7BC284946AD531847A6065A535571D14F44ED41 X-C8649E89: 1C3962B70DF3F0AD73CAD6646DEDE191716CD42B3DD1D34CAB70F9BE574AE9C625B6776AC983F447FC0B9F89525902EE6F57B2FD27647F25E66C117BDB76D6595D61AE6C05FA8092946DE06DE8B472E998D83346C03C08E8A13DBF9FD2A574BA12E4E54EE67F252FB8341EE9D5BE9A0A718C95A638069B3505D8439B09F6DFF06C48C964CF62C6D46536EB022892E5344C41F94D744909CECFA6C6B0C050A61A8CAF69B82BA93681CD72808BE417F3B9E0E7457915DAA85F X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu53w8ahmwBjZKM/YPHZyZHvz5uv+WouB9+ObcCpyrx6l7KImUglyhkEat/+ysWwi0gdhEs0JGjl6ggRWTy1haxBpVdbIX1nthFXMZebaIdHP2ghjoIc/363UZI6Kf1ptIMVdtTL5f5BIXbWcEVs+vuaaI= X-Mailru-Sender: 689FA8AB762F7393DDD5FD59B456EAD2F4DC31CD1CDC528A8700636FE984EBB81AA35090E60707E0E49D44BB4BD9522A059A1ED8796F048DB274557F927329BE89D5A3BC2B10C37545BD1C3CC395C826B4A721A3011E896F X-Mras: Ok Subject: [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 Kaplun via Tarantool-patches Reply-To: Sergey Kaplun Cc: tarantool-patches@dev.tarantool.org Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" 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() -- 2.52.0