From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <vdavydov.dev@gmail.com>
Date: Sat, 9 Jun 2018 15:39:34 +0300
From: Vladimir Davydov <vdavydov.dev@gmail.com>
Subject: Re: [tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints
Message-ID: <20180609123934.dsuw5vvet5uu2qcd@esperanza>
References: <cover.1528544705.git.imeevma@gmail.com>
 <a379eb1b59f1883d890c605e2b8a1c762e943f93.1528544705.git.imeevma@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <a379eb1b59f1883d890c605e2b8a1c762e943f93.1528544705.git.imeevma@gmail.com>
To: imeevma@tarantool.org
Cc: tarantool-patches@freelists.org
List-ID: <tarantool-patches.dev.tarantool.org>

On Sat, Jun 09, 2018 at 02:49:09PM +0300, imeevma@tarantool.org wrote:
> 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.

It's a decent optimization, but why can't we simply use a free list
like structure, i.e. store the index of the next free entry in each
unoccupied array element?