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 E1D9F15F7CC9; Fri, 24 Oct 2025 13:53:15 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org E1D9F15F7CC9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1761303196; bh=2NvOm8is/qTGMZa0upMXU0dBwUBqin6YcV9WoonhnhI=; 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=oP9wJJMbxQGb17v45ahDFqGAUJ3ZxDTx3stCLSIOjTuR46MfrACmPkWgltp/QJhYX bknPd0Xe2ifkMvgqSS9m5P6Ll12ylnitcoYH4dICpxjvPXhE+AqEWVyiVELY0X/Z/a 0jc1cG2l9EImEDzPncXnac/+qprRmtJFJ5mHAzIs= Received: from send152.i.mail.ru (send152.i.mail.ru [89.221.237.247]) (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 3DCDE15B1F74 for ; Fri, 24 Oct 2025 13:50:50 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 3DCDE15B1F74 Received: by exim-smtp-855f5997bb-88mr2 with esmtpa (envelope-from ) id 1vCFNg-000000006vv-3iqC; Fri, 24 Oct 2025 13:50:49 +0300 To: Sergey Bronnikov Date: Fri, 24 Oct 2025 13:50:09 +0300 Message-ID: <3e3085c7a9bcb7d1a185e683c8d774a57cb7816a.1761301736.git.skaplun@tarantool.org> X-Mailer: git-send-email 2.51.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Mailru-Src: smtp X-4EC0790: 10 X-7564579A: 78E4E2B564C1792B X-77F55803: 4F1203BC0FB41BD9DAB542EDD08389FE3A1DC7F2165CDF75DA90D95266D572EE182A05F538085040E83FE3FC77D730093DE06ABAFEAF67056EB9AA81297E162052E7C6720268728E0C8629FDE0E8EB2A X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE728F774C865CF4B07EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637AC83A81C8FD4AD23D82A6BABE6F325AC2E85FA5F3EDFCBAA7353EFBB55337566D857902A848E84F81F8C6E565307442D282EBDC4CF679BDED6FD36129120988A389733CBF5DBD5E913377AFFFEAFD269176DF2183F8FC7C000E2D00546020E658941B15DA834481FCF19DD082D7633A0EF3E4896CB9E6436389733CBF5DBD5E9D5E8D9A59859A8B6042F1592492B88C6CC7F00164DA146DA6F5DAA56C3B73B237318B6A418E8EAB86D1867E19FE14079C09775C1D3CA48CF17B107DEF921CE791DD303D21008E298D5E8D9A59859A8B6B372FE9A2E580EFC725E5C173C3A84C37CE9EF00282E02DF35872C767BF85DA2F004C90652538430E4A6367B16DE6309 X-C1DE0DAB: 0D63561A33F958A5C2A891719E01C2C35002B1117B3ED6960A7DB9D1BD45E67830C8F815570A3530823CB91A9FED034534781492E4B8EEAD528DE7AA5F2BD788C79554A2A72441328621D336A7BC284946AD531847A6065A535571D14F44ED41 X-C8649E89: 1C3962B70DF3F0ADE00A9FD3E00BEEDF3FED46C3ACD6F73ED3581295AF09D3DF87807E0823442EA2ED31085941D9CD0AF7F820E7B07EA4CFEB5FE60D745D562DFDEC95EFDAFB3FB800E6CA87CBCE4ACABE0B83DEA6FE9B6C1D17C9D1E19253446EB503EC62A3E87F7B8357D9B6ACCDC0E2422C6CC32E61FED0BF2E3861BE640C5F4332CA8FE04980913E6812662D5F2A5EAB5682573093F7837F15F2B5E4A70B33F2C28C22F508233FCF178C6DD14203 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu53w8ahmwBjZKM/YPHZyZHvz5uv+WouB9+ObcCpyrx6l7KImUglyhkEat/+ysWwi0gdhEs0JGjl6ggRWTy1haxBpVdbIX1nthFXMZebaIdHP2ghjoIc/363UZI6Kf1ptIMVRN2q9QiacRuycVuq9hiXjE= X-DA7885C5: 97BB41DF4EA1C4EFF255D290C0D534F949500735D494425EC9D7B1F0EEAAF21EA3EE6814987FF3A25B1A4C17EAA7BC4BEF2421ABFA55128DAF83EF9164C44C7E X-Mailru-Sender: 689FA8AB762F7393DDD5FD59B456EAD24E8B43384CD0683411988E4495A63B6E7061053887701AE9E49D44BB4BD9522A059A1ED8796F048DB274557F927329BE89D5A3BC2B10C37545BD1C3CC395C826B4A721A3011E896F X-Mras: Ok Subject: [Tarantool-patches] [PATCH v1 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. --- 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 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 + end, +}) -local longlivedtree = BottomUpTree(0, maxdepth) +-- This tree created once on the setup for the first test. +local longlivedtree -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", + 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.51.0