From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: Re: [tarantool-patches] Re: [PATCH v2 2/1] tuple: introduce bigref hints References: <9c250cefbee4375f722235eaf234b734bf98b83d.1527867534.git.imeevma@gmail.com> <3a358c6b-ad7c-1e18-65aa-e5540c44d30c@tarantool.org> <20180608032823.GD6866@chai> From: Vladislav Shpilevoy Message-ID: <90b9229b-ea58-e583-40d5-1969783bd265@tarantool.org> Date: Fri, 8 Jun 2018 13:36:40 +0300 MIME-Version: 1.0 In-Reply-To: <20180608032823.GD6866@chai> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org, Konstantin Osipov Cc: Vladimir Davydov List-ID: On 08/06/2018 06:28, Konstantin Osipov wrote: > * Vladislav Shpilevoy [18/06/05 00:01]: >> tuple: introduce bigref hints >> Typical usage of bigrefs: allocate many bigrefs in Lua in a row, >> reach memory threshold and delete many bigrefs in a row. >> Hits allow to make multiple refs deletions or creations be >> faster. For example, before the patch complexity of N refs with >> C capacity in a row: O(C) * N. >> After the patch: O(C) + N. >> Same about unrefs. >> Follow up #3224 > > Why not chain up all free links into a free list, similarly to > what we do in the slab allocator? > > True list of uint16 has to big overhead on next/prev pointer. If we use array instead of list, then we face with the same problem as original bigref array has. Removal from the array produces gaps. I have decided that the pair of simple hints is enough since the typical bigref usage follows the scenario: create many bigrefs in Lua in a row, that triggers lua GC, that frees many bigrefs in a row. My hints graceful deal with it.