[Tarantool-patches] [PATCH] box: add binary search for _session settings space

[Vladislav Shpilevoy]

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;
> +}