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 8708B70361; Wed, 10 Feb 2021 02:48:50 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 8708B70361 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1612914530; bh=fgv3oQWIK6fR8i4GZHDDIFUeaBnJu8+LM8mSQcd8LCM=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=og3VL98nJ0f+ULoLabiv2XkiqggLzkAl+XI1Nc6rek1ZS1EG7KwL+uXF3PCAQPLvR UbJCOOz5oog2FH60DqwluitVDkKDqt90/rA8CsYDkLNMcAgO+ewW0sZWEyGhSmRzpn kaxP4X2l8uHDZsXR+1s3NkHmYfyds1oehL/Qygv8= Received: from smtpng3.m.smailru.net (smtpng3.m.smailru.net [94.100.177.149]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 48ED36AABD for ; Wed, 10 Feb 2021 02:46:25 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 48ED36AABD Received: by smtpng3.m.smailru.net with esmtpa (envelope-from ) id 1l9ci5-0002gH-82; Wed, 10 Feb 2021 02:46:21 +0300 To: tarantool-patches@dev.tarantool.org, olegrok@tarantool.org, yaroslav.dynnikov@tarantool.org Date: Wed, 10 Feb 2021 00:46:11 +0100 Message-Id: <69075e8e4536ad59560f36e564017b304f58b85c.1612914070.git.v.shpilevoy@tarantool.org> X-Mailer: git-send-email 2.24.3 (Apple Git-128) In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9C4647521586BE7E6324520D2A088600D8182A05F5380850402DF4EFA2CFEEEEAEC0993E73595BB5481A91BF3F6C1DD85BF755ECAD118015E7 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE742D9BD90C58D50E0EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F79006370D3D68FCEFFDD9EA8638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FCA6073DB25481D6C5FC8FD9CA096BDE8AB577EDE4492C79EE389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92A417C69337E82CC2CC7F00164DA146DA6F5DAA56C3B73B23C77107234E2CFBA567F23339F89546C55F5C1EE8F4F765FC9149C560DC76099D75ECD9A6C639B01BBD4B6F7A4D31EC0BC0CAF46E325F83A522CA9DD8327EE4930A3850AC1BE2E735B344165809136645C4224003CC836476C0CAF46E325F83A50BF2EBBBDD9D6B0FECB2555BB02FD5A93B503F486389A921A5CC5B56E945C8DA X-C1DE0DAB: C20DE7B7AB408E4181F030C43753B8186998911F362727C414F749A5E30D975CFE63F531D4BE5B715FB5DA81EFBF2367266C21AFB302975E9C2B6934AE262D3EE7EAB7254005DCED7532B743992DF240BDC6A1CF3F042BAD6DF99611D93F60EF31C0090ACECF247D699F904B3F4130E343918A1A30D5E7FCCB5012B2E24CD356 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34C2BE7381A0AD3DF1D33FB0DA33261997BD79077DB09FD68F46B3C8D8041D5DA1DC9334E5079E018C1D7E09C32AA3244C3F0A9EFEED436240B8367238B0BEE41497FE24653F78E668FACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmMmQ+JvDeDGuur/HOQ/59A== X-Mailru-Sender: 689FA8AB762F73936BC43F508A06382203E69AAE8CF8D26422BDC335E1DDB5CB3841015FED1DE5223CC9A89AB576DD93FB559BB5D741EB963CF37A108A312F5C27E8A8C3839CE0E267EA787935ED9F1B X-Mras: Ok Subject: [Tarantool-patches] [PATCH 5/9] util: introduce yielding table functions 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: Vladislav Shpilevoy via Tarantool-patches Reply-To: Vladislav Shpilevoy Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" The patch adds functions table_copy_yield and table_minus_yield. Yielding copy creates a duplicate of a table but yields every specified number of keys copied. Yielding minus removes matching key-value pairs specified in one table from another table. It yields every specified number of keys passed. The functions should help to process huge Lua tables (millions of elements and more). These are going to be used on the storage in the new GC algorithm. The algorithm will need to keep a route table on the storage, just like on the router, but with expiration time for the routes. Since bucket count can be millions, it means GC will potentially operate on a huge Lua table and could use some yields so as not to block TX thread for long. Needed for #147 --- test/unit/util.result | 113 ++++++++++++++++++++++++++++++++++++++++ test/unit/util.test.lua | 49 +++++++++++++++++ vshard/util.lua | 40 ++++++++++++++ 3 files changed, 202 insertions(+) diff --git a/test/unit/util.result b/test/unit/util.result index 096e36f..c4fd84d 100644 --- a/test/unit/util.result +++ b/test/unit/util.result @@ -71,3 +71,116 @@ test_run:grep_log('default', 'reloadable_function has been started', 1000) fib:cancel() --- ... +-- Yielding table minus. +minus_yield = util.table_minus_yield +--- +... +minus_yield({}, {}, 1) +--- +- [] +... +minus_yield({}, {k = 1}, 1) +--- +- [] +... +minus_yield({}, {k = 1}, 0) +--- +- [] +... +minus_yield({k = 1}, {k = 1}, 0) +--- +- [] +... +minus_yield({k1 = 1, k2 = 2}, {k1 = 1, k3 = 3}, 10) +--- +- k2: 2 +... +minus_yield({k1 = 1, k2 = 2}, {k1 = 1, k2 = 2}, 10) +--- +- [] +... +-- Mismatching values are not deleted. +minus_yield({k1 = 1}, {k1 = 2}, 10) +--- +- k1: 1 +... +minus_yield({k1 = 1, k2 = 2, k3 = 3}, {k1 = 1, k2 = 222}, 10) +--- +- k3: 3 + k2: 2 +... +do \ + t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ + f = fiber.create(function() \ + minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ + end) \ + yield_count = 0 \ + while f:status() ~= 'dead' do \ + yield_count = yield_count + 1 \ + fiber.yield() \ + end \ +end +--- +... +yield_count +--- +- 2 +... +t +--- +- k4: 4 + k1: 1 +... +-- Yielding table copy. +copy_yield = util.table_copy_yield +--- +... +copy_yield({}, 1) +--- +- [] +... +copy_yield({k = 1}, 1) +--- +- k: 1 +... +copy_yield({k1 = 1, k2 = 2}, 1) +--- +- k1: 1 + k2: 2 +... +do \ + t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ + res = nil \ + f = fiber.create(function() \ + res = copy_yield(t, 2) \ + end) \ + yield_count = 0 \ + while f:status() ~= 'dead' do \ + yield_count = yield_count + 1 \ + fiber.yield() \ + end \ +end +--- +... +yield_count +--- +- 2 +... +t +--- +- k3: 3 + k4: 4 + k1: 1 + k2: 2 +... +res +--- +- k3: 3 + k4: 4 + k1: 1 + k2: 2 +... +t ~= res +--- +- true +... diff --git a/test/unit/util.test.lua b/test/unit/util.test.lua index 5f39e06..4d6cbe9 100644 --- a/test/unit/util.test.lua +++ b/test/unit/util.test.lua @@ -27,3 +27,52 @@ fib = util.reloadable_fiber_create('Worker_name', fake_M, 'reloadable_function') while not test_run:grep_log('default', 'module is reloaded, restarting') do fiber.sleep(0.01) end test_run:grep_log('default', 'reloadable_function has been started', 1000) fib:cancel() + +-- Yielding table minus. +minus_yield = util.table_minus_yield +minus_yield({}, {}, 1) +minus_yield({}, {k = 1}, 1) +minus_yield({}, {k = 1}, 0) +minus_yield({k = 1}, {k = 1}, 0) +minus_yield({k1 = 1, k2 = 2}, {k1 = 1, k3 = 3}, 10) +minus_yield({k1 = 1, k2 = 2}, {k1 = 1, k2 = 2}, 10) +-- Mismatching values are not deleted. +minus_yield({k1 = 1}, {k1 = 2}, 10) +minus_yield({k1 = 1, k2 = 2, k3 = 3}, {k1 = 1, k2 = 222}, 10) + +do \ + t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ + f = fiber.create(function() \ + minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ + end) \ + yield_count = 0 \ + while f:status() ~= 'dead' do \ + yield_count = yield_count + 1 \ + fiber.yield() \ + end \ +end +yield_count +t + +-- Yielding table copy. +copy_yield = util.table_copy_yield +copy_yield({}, 1) +copy_yield({k = 1}, 1) +copy_yield({k1 = 1, k2 = 2}, 1) + +do \ + t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ + res = nil \ + f = fiber.create(function() \ + res = copy_yield(t, 2) \ + end) \ + yield_count = 0 \ + while f:status() ~= 'dead' do \ + yield_count = yield_count + 1 \ + fiber.yield() \ + end \ +end +yield_count +t +res +t ~= res diff --git a/vshard/util.lua b/vshard/util.lua index d3b4e67..2362607 100644 --- a/vshard/util.lua +++ b/vshard/util.lua @@ -153,6 +153,44 @@ local function version_is_at_least(major_need, middle_need, minor_need) return minor >= minor_need end +-- +-- Copy @a src table. Fiber yields every @a interval keys copied. +-- +local function table_copy_yield(src, interval) + local res = {} + -- Time-To-Yield. + local tty = interval + for k, v in pairs(src) do + res[k] = v + tty = tty - 1 + if tty <= 0 then + fiber.yield() + tty = interval + end + end + return res +end + +-- +-- Remove @a src keys from @a dst if their values match. Fiber yields every +-- @a interval iterations. +-- +local function table_minus_yield(dst, src, interval) + -- Time-To-Yield. + local tty = interval + for k, srcv in pairs(src) do + if dst[k] == srcv then + dst[k] = nil + end + tty = tty - 1 + if tty <= 0 then + fiber.yield() + tty = interval + end + end + return dst +end + return { tuple_extract_key = tuple_extract_key, reloadable_fiber_create = reloadable_fiber_create, @@ -160,4 +198,6 @@ return { async_task = async_task, internal = M, version_is_at_least = version_is_at_least, + table_copy_yield = table_copy_yield, + table_minus_yield = table_minus_yield, } -- 2.24.3 (Apple Git-128)