From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp39.i.mail.ru (smtp39.i.mail.ru [94.100.177.99]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 7D7D646970E for ; Wed, 15 Jan 2020 23:24:18 +0300 (MSK) References: <20200110074609.68016-1-k.sosnin@tarantool.org> From: Vladislav Shpilevoy Message-ID: <8c5c71e4-b637-a39b-1de4-2172dea88d66@tarantool.org> Date: Wed, 15 Jan 2020 21:24:16 +0100 MIME-Version: 1.0 In-Reply-To: <20200110074609.68016-1-k.sosnin@tarantool.org> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: Re: [Tarantool-patches] [PATCH] box: add binary search for _session settings space List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Chris Sosnin , tarantool-patches@dev.tarantool.org Hi! Thanks for the patch! On 10/01/2020 08:46, Chris Sosnin wrote: > box: add binary search for _session settings space There is no '_session' space. Please, add '_' between '_session' and 'settings'. > As it is mentioned in implementation, it is important > that _session_settings options are sorted by name, so > there is no need in linear lookup and we can replace it > with binary search. > > Closes #4712 > --- > branch: https://github.com/tarantool/tarantool/tree/ksosnin/gh-4712-search-settings > issue: https://github.com/tarantool/tarantool/issues/4712 > > src/box/session_settings.c | 10 ++++++---- > src/lib/core/util.c | 22 ++++++++++++++++++++++ > src/trivia/util.h | 3 +++ > 3 files changed, 31 insertions(+), 4 deletions(-) > > diff --git a/src/box/session_settings.c b/src/box/session_settings.c > index a969d3d10..ec87641be 100644 > --- a/src/box/session_settings.c > +++ b/src/box/session_settings.c > @@ -265,9 +265,10 @@ session_settings_index_get(struct index *base, const char *key, > struct session_setting_module *module = &session_setting_modules[0]; > struct session_setting_module *end = module + session_setting_type_MAX; > int sid = 0; > + int count = module->setting_count; 1. 'Module' is different on each iteration, because I do '++module' each time. Here you took count only for the first module, but use it for all of them. The same below. > for (; module < end; ++module, sid = 0) { > - if (session_settings_next_in_module(module, &sid, key, true, > - true) == 0) > + if ((sid = str_bin_search(module->settings, key, > + count)) != count) > goto found; > } > *result = NULL; > @@ -372,9 +373,10 @@ session_settings_space_execute_update(struct space *space, struct txn *txn, > key = tt_cstr(key, key_len); > struct session_setting_module *module = &session_setting_modules[0]; > struct session_setting_module *end = module + session_setting_type_MAX; > + int count = module->setting_count; > for (; module < end; ++module, sid = 0) { > - if (session_settings_next_in_module(module, &sid, key, true, > - true) == 0) > + if ((sid = str_bin_search(module->settings, key, > + count)) != count) > goto found; > } > *result = NULL; > diff --git a/src/lib/core/util.c b/src/lib/core/util.c > index ffa1d2b51..6553d6626 100644 > --- a/src/lib/core/util.c > +++ b/src/lib/core/util.c > @@ -84,6 +84,28 @@ strnindex(const char **haystack, const char *needle, uint32_t len, uint32_t hmax > return hmax; > } > > +/** > + * Same as strindex(), but assuming the array is sorted and it's > + * size is known. > + */ > +uint32_t > +str_bin_search(const char **haystack, const char *needle, uint32_t hmax) { 2. We don't really need this function anywhere except session_settings.c. Besides, even in that file it is needed only in session_settings_next_in_module(). So you can just patch the latter function. > + int cmp; > + uint32_t index, start = 0; > + uint32_t end = hmax; > + while (start < end) { > + index = (start + end) / 2; > + cmp = strcmp(haystack[index], needle); > + if (cmp < 0) > + start = index + 1; > + else > + end = index; > + } > + if (start < hmax && strcmp(haystack[start], needle) == 0) > + return start; > + return hmax; > +}