[tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints
imeevma at tarantool.org
imeevma at tarantool.org
Thu Jun 7 19:34:21 MSK 2018
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
More information about the Tarantool-patches
mailing list