From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints References: <9c250cefbee4375f722235eaf234b734bf98b83d.1527867534.git.imeevma@gmail.com> From: Vladislav Shpilevoy Message-ID: <3a358c6b-ad7c-1e18-65aa-e5540c44d30c@tarantool.org> Date: Mon, 4 Jun 2018 23:57:27 +0300 MIME-Version: 1.0 In-Reply-To: <9c250cefbee4375f722235eaf234b734bf98b83d.1527867534.git.imeevma@gmail.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org, Vladimir Davydov List-ID: commit 3237caac5f436dab34dddabb53cd9b6c4ed8fa0b Author: Vladislav Shpilevoy 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)