[tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints

[Vladislav Shpilevoy]

commit 3237caac5f436dab34dddabb53cd9b6c4ed8fa0b
Author: Vladislav Shpilevoy <v.shpilevoy at tarantool.org>
Date:   Mon Jun 4 23:27:54 2018 +0300

     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

diff --git a/src/box/tuple.c b/src/box/tuple.c
index 5fc1c1283..a030b6eb8 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,10 +308,13 @@ 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.hint_index_to_take = vacant_index + 1;
  		return vacant_index;
  	}
  	/* Extend the array. */
@@ -324,7 +335,9 @@ bigref_list_new_index()
  	memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
  	       bigref_list.capacity);
  	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
@@ -353,13 +366,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)