From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id C2C5C25CEC for ; Thu, 7 Jun 2018 12:34:25 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Wz1P_o3r51K0 for ; Thu, 7 Jun 2018 12:34:25 -0400 (EDT) Received: from smtp35.i.mail.ru (smtp35.i.mail.ru [94.100.177.95]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 82AFC25C0E for ; Thu, 7 Jun 2018 12:34:25 -0400 (EDT) Received: from [185.6.245.156] (port=40562 helo=mimeev-ThinkPad-T460p.mail.msk) by smtp35.i.mail.ru with esmtpa (envelope-from ) id 1fQxrj-0001y1-UD for tarantool-patches@freelists.org; Thu, 07 Jun 2018 19:34:24 +0300 From: imeevma@tarantool.org Subject: [tarantool-patches] [PATCH v2 2/2] tuple: introduce bigref hints Date: Thu, 7 Jun 2018 19:34:21 +0300 Message-Id: In-Reply-To: References: Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-subscribe: List-owner: List-post: List-archive: To: tarantool-patches@freelists.org 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