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 D85626AABC; Thu, 11 Feb 2021 09:51:07 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org D85626AABC DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1613026267; bh=kZxduHWmGc7pf60ioxa7zITYAVJqfvQc5qlI7NXuoP4=; 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=c9polKU7H+1bL57qDHcacCrwr28dms2FOdYRKWsE6ipkZ+Ruk0K8A7zmNuWUD09GJ E6cr6ObYeIAPlJdsBWPF3lXQYFjqtnG76Z5QcO1PgyTkOk+q5ixZprMnOWxyQa5FGr 45Q32nCUnvJG8tnM8snECZBtVRSHHjBq/PdrP8KU= Received: from smtp39.i.mail.ru (smtp39.i.mail.ru [94.100.177.99]) (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 E9E826AABC for ; Thu, 11 Feb 2021 09:50:37 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org E9E826AABC Received: by smtp39.i.mail.ru with esmtpa (envelope-from ) id 1lA5o9-0005s1-Rg; Thu, 11 Feb 2021 09:50:34 +0300 To: Vladislav Shpilevoy , tarantool-patches@dev.tarantool.org, yaroslav.dynnikov@tarantool.org References: <69075e8e4536ad59560f36e564017b304f58b85c.1612914070.git.v.shpilevoy@tarantool.org> <481db25d-5324-0494-e8b9-da9ff1ec39ac@tarantool.org> Message-ID: <22c4aff1-1305-bf7f-e43b-1fe4d3fa5c51@tarantool.org> Date: Thu, 11 Feb 2021 09:50:33 +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: <481db25d-5324-0494-e8b9-da9ff1ec39ac@tarantool.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-GB X-7564579A: 78E4E2B564C1792B X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9C6D5758EA387698D8F2F71171D5C2C2E5182A05F538085040A2FB1999495CC9BD6247FC7C1B522B0711A890A368E476876998F216EF39BDE1 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE721B3E54BB37EA0B4EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637652CD06254D2F21C8638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FC7BF04B2A11D85FC6FD2D1FBC96E440512BAFCB16F9BF41E5389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92A417C69337E82CC2CC7F00164DA146DA6F5DAA56C3B73B237318B6A418E8EAB8D32BA5DBAC0009BE9E8FC8737B5C2249241DEFC3979DFA5476E601842F6C81A12EF20D2F80756B5F7E9C4E3C761E06A776E601842F6C81A127C277FBC8AE2E8BBD12FCBAD2CEA44E3AA81AA40904B5D9DBF02ECDB25306B2B25CBF701D1BE8734AD6D5ED66289B5278DA827A17800CE70AD1028CF10412FC93EC92FD9297F6715571747095F342E857739F23D657EF2BD5E8D9A59859A8B698B1B85E56A716AC089D37D7C0E48F6C5571747095F342E857739F23D657EF2B6825BDBE14D8E7028C9DFF55498CEFB0BD9CCCA9EDD067B1EDA766A37F9254B7 X-B7AD71C0: AC4F5C86D027EB782CDD5689AFBDA7A2BBE337FB72E92315FF39D8DB89857825EFA8BF88FCBFD63CE0852D54D1EC5181CC40ECEDB3F569EB653005A1B9AEE1ED X-C1DE0DAB: 0D63561A33F958A5FD03E2A7D446D87A031E10B8E4F3355E75D776DF0231DD53D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75448CF9D3A7B2C848410CA545F18667F91A7EA1CDA0B5A7A0 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34197948450CB5442AD4F36516F3AE53A11A7860D0EDB0F7F113ECE4CED606FC021771497D3CEBB5231D7E09C32AA3244C171FEDD7CC3F4E37B4309D9DFD2D168E7C0C08F7987826B9FACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmjFTaBTEi1agVjoOzedEKA== X-Mailru-Sender: 583F1D7ACE8F49BD9317CE1922F30C7E9A20125C00004011C54BF956258C08D9B6E5BCF5C76F7C6B23E75C7104EB1B885DEE61814008E47C7013064206BFB89F93956FB04BA385BE9437F6177E88F7363CDA0F3B3F5B9367 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 fixes! LGTM. On 11/02/2021 01:34, Vladislav Shpilevoy wrote: > Thanks for the review! > >>> 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) >>> +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? > Yup, will work too. See the diff below. > > ==================== > diff --git a/test/unit/util.result b/test/unit/util.result > index c4fd84d..42a361a 100644 > --- a/test/unit/util.result > +++ b/test/unit/util.result > @@ -111,14 +111,14 @@ minus_yield({k1 = 1, k2 = 2, k3 = 3}, {k1 = 1, k2 = 222}, 10) > ... > do \ > t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ > + yield_count = 0 \ > f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > end) \ > - yield_count = 0 \ > - while f:status() ~= 'dead' do \ > - yield_count = yield_count + 1 \ > - fiber.yield() \ > - end \ > + test_run:wait_cond(function() return f:status() == 'dead' end) \ > end > --- > ... > @@ -151,14 +151,14 @@ copy_yield({k1 = 1, k2 = 2}, 1) > do \ > t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ > res = nil \ > + yield_count = 0 \ > f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > res = copy_yield(t, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > end) \ > - yield_count = 0 \ > - while f:status() ~= 'dead' do \ > - yield_count = yield_count + 1 \ > - fiber.yield() \ > - end \ > + test_run:wait_cond(function() return f:status() == 'dead' end) \ > end > --- > ... > diff --git a/test/unit/util.test.lua b/test/unit/util.test.lua > index 4d6cbe9..9550a95 100644 > --- a/test/unit/util.test.lua > +++ b/test/unit/util.test.lua > @@ -42,14 +42,14 @@ minus_yield({k1 = 1, k2 = 2, k3 = 3}, {k1 = 1, k2 = 222}, 10) > > do \ > t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ > + yield_count = 0 \ > f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > end) \ > - yield_count = 0 \ > - while f:status() ~= 'dead' do \ > - yield_count = yield_count + 1 \ > - fiber.yield() \ > - end \ > + test_run:wait_cond(function() return f:status() == 'dead' end) \ > end > yield_count > t > @@ -63,14 +63,14 @@ copy_yield({k1 = 1, k2 = 2}, 1) > do \ > t = {k1 = 1, k2 = 2, k3 = 3, k4 = 4} \ > res = nil \ > + yield_count = 0 \ > f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > res = copy_yield(t, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > end) \ > - yield_count = 0 \ > - while f:status() ~= 'dead' do \ > - yield_count = yield_count + 1 \ > - fiber.yield() \ > - end \ > + test_run:wait_cond(function() return f:status() == 'dead' end) \ > end > yield_count > t > ==================== > >> Could scheduler skip this fiber at some loop iteration? In other words, won't this test be flaky? > Nope. Unless the fiber is sleeping on some condition or for a timeout, a plain > sleep(0) also known as fiber.yield() won't skip this fiber on the next > iteration of the loop. But does not matter if csw is used to count the yields. > > Full new patch below. > > ==================== > util: introduce yielding table functions > > 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 > > diff --git a/test/unit/util.result b/test/unit/util.result > index 096e36f..42a361a 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} \ > + yield_count = 0 \ > + f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > + minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > + end) \ > + test_run:wait_cond(function() return f:status() == 'dead' 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 \ > + yield_count = 0 \ > + f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > + res = copy_yield(t, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > + end) \ > + test_run:wait_cond(function() return f:status() == 'dead' 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..9550a95 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} \ > + yield_count = 0 \ > + f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > + minus_yield(t, {k2 = 2, k3 = 3, k5 = 5, k4 = 444}, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > + end) \ > + test_run:wait_cond(function() return f:status() == 'dead' 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 \ > + yield_count = 0 \ > + f = fiber.create(function() \ > + local csw1 = fiber.info()[fiber.id()].csw \ > + res = copy_yield(t, 2) \ > + local csw2 = fiber.info()[fiber.id()].csw \ > + yield_count = csw2 - csw1 \ > + end) \ > + test_run:wait_cond(function() return f:status() == 'dead' 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, > } >