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 0075770361; Wed, 10 Feb 2021 11:59:42 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 0075770361 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1612947583; bh=5eNOtzP/nXj2YSUbcDuDDOp+Fhp99PBYxkUbbrpekAA=; h=To:References:Date:In-Reply-To:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=CbIBnw22GuPS/YnD1exgfJPQudXOn67wjWZTqUtFkJbt7jz0GyAI6kNFEpHzn5BO4 /Vthy6/TzCDlHSDVygLtblCQe3sy386+UJbeQIXwp/deDcZa+GK0fsuefE8b+PnxQC GB5qMeDrFekxyhr1ei7PD8tdDr0T0rYriTur44CU= Received: from smtp38.i.mail.ru (smtp38.i.mail.ru [94.100.177.98]) (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 9A1F76AABE for ; Wed, 10 Feb 2021 11:59:13 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 9A1F76AABE Received: by smtp38.i.mail.ru with esmtpa (envelope-from ) id 1l9lL3-0003ox-Ik; Wed, 10 Feb 2021 11:59:10 +0300 To: Vladislav Shpilevoy , tarantool-patches@dev.tarantool.org, yaroslav.dynnikov@tarantool.org References: <69075e8e4536ad59560f36e564017b304f58b85c.1612914070.git.v.shpilevoy@tarantool.org> Message-ID: Date: Wed, 10 Feb 2021 11:59:08 +0300 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0) Gecko/20100101 Thunderbird/78.7.0 MIME-Version: 1.0 In-Reply-To: <69075e8e4536ad59560f36e564017b304f58b85c.1612914070.git.v.shpilevoy@tarantool.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-Language: en-GB X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9CD238BCF93DF23716D1711D0DDC4F5AC2182A05F538085040E8C7BB9E2E702E270A0D58A3B86E8500FE456FF63ACAC676F4C5C44E6496A928 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7B9FBA884A7C9B8BAEA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637976142D429C486548638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FC8767A9B625D33EB45E869D88DCAC9767F1A3A3F51189E594389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92A417C69337E82CC2CC7F00164DA146DA6F5DAA56C3B73B237318B6A418E8EAB8D32BA5DBAC0009BE9E8FC8737B5C2249668B94F0A65C3A0C3AA81AA40904B5D9CF19DD082D7633A078D18283394535A93AA81AA40904B5D98AA50765F790063720016CB649FC17EDD81D268191BDAD3D698AB9A7B718F8C442539A7722CA490C13377AFFFEAFD26923F8577A6DFFEA7C3DDF88F19B2F251A93EC92FD9297F6715571747095F342E857739F23D657EF2BD5E8D9A59859A8B6221D5A8161B58CB575ECD9A6C639B01B4E70A05D1297E1BBC6867C52282FAC85D9B7C4F32B44FF57285124B2A10EEC6C00306258E7E6ABB4E4A6367B16DE6309 X-C1DE0DAB: 0D63561A33F958A543B35A46CFF68A0F11D5DF307CA48F06A94BCAF09D985AB0D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75F04B387B5D7535DE410CA545F18667F91A7EA1CDA0B5A7A0 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34D9DC20663B80603F5378845AD9293B92AFA7449BBE243E60A2E41BF42E0E26174AE3F20BB1D587BC1D7E09C32AA3244CAAD21FDC7A5DA7971112C6BF32A2987F259227199D06760AFACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmMmQ+JvDeDGRzSBmxq1GKg== X-Mailru-Sender: E02534FE7B43636DC6DBEBE964139794B3431C176F1D321E9E290F5E0AA81254AFCE93479A255C8023E75C7104EB1B885DEE61814008E47C7013064206BFB89F93956FB04BA385BE9437F6177E88F7363CDA0F3B3F5B9367 X-Mras: Ok Subject: Re: [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: Oleg Babin via Tarantool-patches Reply-To: Oleg Babin Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" Thanks for your patch 1 comment below. On 10/02/2021 02:46, Vladislav Shpilevoy wrote: > 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 > +--- Why can't you use "csw" of fiber.self() instead? Also it's it reliable enough to simply count yields? Could scheduler skip this fiber at some loop iteration? In other words, won't this test be flaky? > +... > +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, > }