Tarantool development patches archive
 help / color / mirror / Atom feed
From: imeevma@tarantool.org
To: tarantool-patches@freelists.org
Subject: [tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints
Date: Thu,  7 Jun 2018 19:34:21 +0300	[thread overview]
Message-ID: <cca41d61d75b984278f78ab66958f23d36e86e24.1528388742.git.imeevma@gmail.com> (raw)
In-Reply-To: <cover.1528388742.git.imeevma@gmail.com>

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
---
Branch: https://github.com/tarantool/tarantool/tree/imeevma/gh-3224-tuple-bigrefs
Issue: https://github.com/tarantool/tarantool/issues/3224

 src/box/tuple.c | 22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)

diff --git a/src/box/tuple.c b/src/box/tuple.c
index 7dafec5..4cbe80c 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -66,6 +66,14 @@ static struct bigref_list {
 	uint16_t size;
 	/** Capacity of the array. */
 	uint16_t capacity;
+	/**
+	 * On next bigref index retrieval start from this index.
+	 * It is either 0 and it is the same as its absence, or
+	 * it is > 0 and all the previous indexes are occupied.
+	 */
+	uint16_t hint_index_to_take;
+	/** Same hint but for bigref list compaction. */
+	uint16_t hint_index_to_free;
 } bigref_list;
 
 static const double ALLOC_FACTOR = 1.05;
@@ -300,11 +308,14 @@ bigref_list_destroy()
 static inline uint16_t
 bigref_list_new_index()
 {
+	/* Drop the 'free' hint. */
+	bigref_list.hint_index_to_free = bigref_list.capacity - 1;
 	if (bigref_list.size < bigref_list.capacity) {
-		uint16_t vacant_index = 0;
+		uint16_t vacant_index = bigref_list.hint_index_to_take;
 		while (bigref_list.refs[vacant_index] != 0)
 			++vacant_index;
 		++bigref_list.size;
+		bigref_list.hint_index_to_take = vacant_index + 1;
 		return vacant_index;
 	}
 	/* Extend the array. */
@@ -325,7 +336,9 @@ bigref_list_new_index()
 	memset(bigref_list.refs + bigref_list.capacity, 0, (capacity -
 	       bigref_list.capacity) * sizeof(*bigref_list.refs));
 	bigref_list.capacity = capacity;
-	return bigref_list.size++;
+	uint16_t vacant_index = bigref_list.size++;
+	bigref_list.hint_index_to_take = bigref_list.size;
+	return vacant_index;
 }
 
 void
@@ -354,13 +367,16 @@ bigref_list_delete_index(uint16_t index)
 		bigref_list_destroy();
 		return;
 	}
+	/* Drop the 'take' hint. */
+	bigref_list.hint_index_to_take = 0;
 	if (bigref_list.capacity == BIGREF_MIN_CAPACITY ||
 	    bigref_list.size > bigref_list.capacity / BIGREF_FACTOR)
 		return;
 
-	uint16_t top_index = bigref_list.capacity - 1;
+	uint16_t top_index = bigref_list.hint_index_to_free;
 	while (bigref_list.refs[top_index] == 0)
 		top_index--;
+	bigref_list.hint_index_to_free = top_index;
 
 	uint16_t needed_capacity = top_index + 1;
 	if (needed_capacity < BIGREF_MIN_CAPACITY)
-- 
2.7.4

  parent reply	other threads:[~2018-06-07 16:34 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <cover.1528388742.git.imeevma@gmail.com>
2018-06-07 16:28 ` [tarantool-patches] [PATCH v2 1/2] box: create bigrefs for tuples imeevma
2018-06-07 21:24   ` [tarantool-patches] " Vladislav Shpilevoy
2018-06-08 10:46     ` Imeev Mergen
2018-06-08 12:03       ` Vladislav Shpilevoy
2018-06-09 11:31         ` Vladimir Davydov
2018-06-07 16:34 ` imeevma [this message]
2018-06-09 11:49 [tarantool-patches] [PATCH v2 0/2] Create " imeevma
2018-06-09 11:49 ` [tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints imeevma
2018-06-09 12:39   ` Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=cca41d61d75b984278f78ab66958f23d36e86e24.1528388742.git.imeevma@gmail.com \
    --to=imeevma@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox