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 726E26C7D2; Thu, 11 Feb 2021 01:34:29 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 726E26C7D2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1612996469; bh=UOb158EXGv5wrLvQVt4Nhk/5kTxS3vb1hNcDdGWDm+8=; 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=R+t+fZVq270g3nJWdhQztIoffWxnZq9QppXFXACT/Z4Xjx1bhmMicO7ULOCLP+Kqt jhaGJRLaB96HJ6O+gGT82fKJLLACmM89hrmRuWxRUJNIN7pxaLu0uRmLpEQ6Jm8m2z GoEGnBHqUMYENrbt+MlLrSrt4eM6t3H3YWwhuSi4= Received: from smtpng2.m.smailru.net (smtpng2.m.smailru.net [94.100.179.3]) (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 88A926C7D2 for ; Thu, 11 Feb 2021 01:34:27 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 88A926C7D2 Received: by smtpng2.m.smailru.net with esmtpa (envelope-from ) id 1l9y3z-00022Q-7d; Thu, 11 Feb 2021 01:34:23 +0300 To: Oleg Babin , tarantool-patches@dev.tarantool.org, yaroslav.dynnikov@tarantool.org References: <69075e8e4536ad59560f36e564017b304f58b85c.1612914070.git.v.shpilevoy@tarantool.org> Message-ID: <481db25d-5324-0494-e8b9-da9ff1ec39ac@tarantool.org> Date: Wed, 10 Feb 2021 23:34:22 +0100 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.7.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-7564579A: B8F34718100C35BD X-77F55803: 4F1203BC0FB41BD953AC099BC0052A9CD238BCF93DF23716D1711D0DDC4F5AC2182A05F538085040A722CBE800D94473DF71A551A84A144C2E6163D7C13EB1851D42C98DB7C93CFA X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE721B3E54BB37EA0B4EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637D99F96657F58F1038638F802B75D45FF5571747095F342E8C7A0BC55FA0FE5FC5ED48DDBF877A970BB590863C7175B7226491581ABC6F88E389733CBF5DBD5E913377AFFFEAFD269A417C69337E82CC2CC7F00164DA146DAFE8445B8C89999729449624AB7ADAF37F6B57BC7E64490611E7FA7ABCAF51C92A417C69337E82CC2CC7F00164DA146DA6F5DAA56C3B73B23C77107234E2CFBA567F23339F89546C55F5C1EE8F4F765FC041BD12FB6B4799375ECD9A6C639B01BBD4B6F7A4D31EC0BC0CAF46E325F83A522CA9DD8327EE4930A3850AC1BE2E735CC4B623DB76FBBCBC4224003CC836476C0CAF46E325F83A50BF2EBBBDD9D6B0FECB2555BB02FD5A93B503F486389A921A5CC5B56E945C8DA X-C1DE0DAB: 0D63561A33F958A59578F3427FF57C39B3F1D4B7403AEFA243A5EA70A3090612D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75F04B387B5D7535DE410CA545F18667F91A7EA1CDA0B5A7A0 X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D342E8FEDBD32DECB6DCF739CFC3E059C8498B862E13B1157BC780E012C02FF783B6FA5B6DC097623071D7E09C32AA3244C920AF396CFEEBD50B829FC49407FE4A2D9ADFF0C0BDB8D1FFACE5A9C96DEB163 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojmMmQ+JvDeDHLcMtDEb26+g== X-Mailru-Sender: 689FA8AB762F73936BC43F508A06382201BB8DF164A8032F51C12C585037CBFB3841015FED1DE5223CC9A89AB576DD93FB559BB5D741EB963CF37A108A312F5C27E8A8C3839CE0E267EA787935ED9F1B 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: Vladislav Shpilevoy via Tarantool-patches Reply-To: Vladislav Shpilevoy Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" 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, }