Re: [Tarantool-patches] [PATCH 2/4] box: add binary search for _session_settings space

[Nikita Pettik <korablev@tarantool.org>]

On 17 Feb 15:12, Chris Sosnin wrote:
> 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.

Is there any sufficient performance benefit except for code complication?:)
I really doubt that this part should be optimized for such rare in
terms of usage place. What is more, there's only dozen entries, so
binary search doesn't really make any sence. Idk why Kirill assigned 2.4.1
milestone, IMHO there are way far more important things to elaborate on.
 
> Closes #4712
> ---
>  src/box/session_settings.c                    | 97 +++++++++++++++++--
>  ...1-access-settings-from-any-frontend.result | 37 ++++---
>  ...access-settings-from-any-frontend.test.lua | 28 ++++--
>  3 files changed, 133 insertions(+), 29 deletions(-)
> 
> diff --git a/src/box/session_settings.c b/src/box/session_settings.c
> index 93d1c8e22..874fc304a 100644
> --- a/src/box/session_settings.c
> +++ b/src/box/session_settings.c
> @@ -81,6 +81,8 @@ struct session_settings_iterator {
>  	bool is_eq;
>  	/** True if the iterator should include equal keys. */
>  	bool is_including;
> +	/** True if the iterator is pointing to an existing setting */
> +	bool is_set;
>  };
>  
>  static void
> @@ -92,6 +94,72 @@ session_settings_iterator_free(struct iterator *ptr)
>  	free(it);
>  }
>  
> +static int
> +session_settings_set_forward(int *sid, const char *key, bool is_eq,
> +			     bool is_including)
> +{
> +	int low = 0, high = SESSION_SETTING_COUNT - 1;
> +	if (key == NULL)
> +		return 0;
> +	while (low <= high) {
> +		int index = (high + low) / 2;
> +		const char *name = session_setting_strs[index];
> +		int cmp = strcmp(name, key);
> +		if (cmp == 0) {
> +			if (is_including) {
> +				*sid = index;
> +				return 0;
> +			}
> +			*sid = ++index;
> +			return index < SESSION_SETTING_COUNT ? 0 : -1;
> +		}
> +		if (cmp < 0)
> +			low = index + 1;
> +		else
> +			high = index - 1;
> +	}
> +	if (is_eq) {
> +		*sid = SESSION_SETTING_COUNT;
> +		return -1;
> +	}
> +	assert(low > high);
> +	*sid = low;
> +	return low < SESSION_SETTING_COUNT ? 0 : -1;
> +}
> +
> +static int
> +session_settings_set_reverse(int *sid, const char *key, bool is_eq,
> +			     bool is_including)
> +{
> +	int low = 0, high = SESSION_SETTING_COUNT - 1;
> +	if (key == NULL)
> +		return 0;
> +	while (low <= high) {
> +		int index = (high + low) / 2;
> +		const char *name = session_setting_strs[index];
> +		int cmp = strcmp(name, key);
> +		if (cmp == 0) {
> +			if (is_including) {
> +				*sid = index;
> +				return 0;
> +			}
> +			*sid = --index;
> +			return index >= 0 ? 0 : -1;
> +		}
> +		if (cmp < 0)
> +			low = index + 1;
> +		else
> +			high = index - 1;
> +	}
> +	if (is_eq) {
> +		*sid = SESSION_SETTING_COUNT;
> +		return -1;
> +	}
> +	assert(low > high);
> +	*sid = high;
> +	return high >= 0 ? 0 : -1;
> +}
> +
>  static int
>  session_settings_next(int *sid, const char *key, bool is_eq, bool is_including)
>  {
> @@ -145,9 +213,15 @@ session_settings_iterator_next(struct iterator *iterator, struct tuple **result)
>  	int sid = it->setting_id;
>  	const char *key = it->key;
>  	bool is_including = it->is_including, is_eq = it->is_eq;
> -	bool is_found = false;
> -	if (session_settings_next(&sid, key, is_eq, is_including) == 0)
> -		is_found = true;
> +	bool is_found;
> +	if (!it->is_set) {
> +		it->is_set = true;
> +		is_found = session_settings_set_forward(&sid, key, is_eq,
> +							is_including) == 0;
> +	} else {
> +		is_found = session_settings_next(&sid, key, is_eq,
> +						 is_including) == 0;
> +	}
>  	it->setting_id = sid + 1;
>  	if (!is_found) {
>  		*result = NULL;
> @@ -167,9 +241,15 @@ session_settings_iterator_prev(struct iterator *iterator, struct tuple **result)
>  	int sid = it->setting_id;
>  	const char *key = it->key;
>  	bool is_including = it->is_including, is_eq = it->is_eq;
> -	bool is_found = false;
> -	if (session_settings_prev(&sid, key, is_eq, is_including) == 0)
> -		is_found = true;
> +	bool is_found;
> +	if (!it->is_set) {
> +		it->is_set = true;
> +		is_found = session_settings_set_reverse(&sid, key, is_eq,
> +							is_including) == 0;
> +	} else {
> +		is_found = session_settings_prev(&sid, key, is_eq,
> +						 is_including) == 0;
> +	}
>  	it->setting_id = sid - 1;
>  	if (!is_found) {
>  		*result = NULL;
> @@ -221,6 +301,7 @@ session_settings_index_create_iterator(struct index *base,
>  	it->is_eq = type == ITER_EQ || type == ITER_REQ;
>  	it->is_including = it->is_eq || type == ITER_GE || type == ITER_ALL ||
>  			   type == ITER_LE;
> +	it->is_set = false;
>  	it->format = index->format;
>  	if (!iterator_type_is_reverse(type)) {
>  		it->base.next = session_settings_iterator_next;
> @@ -244,7 +325,7 @@ session_settings_index_get(struct index *base, const char *key,
>  	key = mp_decode_str(&key, &len);
>  	key = tt_cstr(key, len);
>  	int sid = 0;
> -	if (session_settings_next(&sid, key, true, true) != 0) {
> +	if (session_settings_set_forward(&sid, key, true, true) != 0) {
>  		*result = NULL;
>  		return 0;
>  	}
> @@ -345,7 +426,7 @@ session_settings_space_execute_update(struct space *space, struct txn *txn,
>  	}
>  	key = mp_decode_str(&key, &key_len);
>  	key = tt_cstr(key, key_len);
> -	if (session_settings_next(&sid, key, true, true) != 0) {
> +	if (session_settings_set_forward(&sid, key, true, true) != 0) {
>  		*result = NULL;
>  		return 0;
>  	}
> diff --git a/test/box/gh-4511-access-settings-from-any-frontend.result b/test/box/gh-4511-access-settings-from-any-frontend.result
> index ed340d053..bae77192e 100644
> --- a/test/box/gh-4511-access-settings-from-any-frontend.result
> +++ b/test/box/gh-4511-access-settings-from-any-frontend.result
> @@ -82,6 +82,12 @@ function check_sorting(ss, ts, key)
>      for _, it in pairs(iterators_list) do
>          local view_space = ss:select({key}, {iterator = it})
>          local test_space = ts:select({key}, {iterator = it})
> +        if #view_space ~= #test_space then
> +            return {
> +                err = 'bad sorting', type = it, exp = test_space,
> +                got = view_space
> +            }
> +        end
>          for key, value in pairs(view_space) do
>              if test_space[key].name ~= value.name then
>                  return {
> @@ -111,32 +117,37 @@ check_sorting(s, t, 'sql_d')
>  check_sorting(s, t, 'sql_v')
>   | ---
>   | ...
> -check_sorting(s, t, 'sql_defer_foreign_keys')
> +check_sorting(s, t, 'z')
>   | ---
>   | ...
> -
> -t:drop()
> +check_sorting(s, t, 'sql_parser_debuf')
> + | ---
> + | ...
> +check_sorting(s, t, 'sql_parser_debuh')
>   | ---
>   | ...
>  
> --- Check get() method of session_settings space.
> -s:get({'sql_defer_foreign_keys'})
> +name = nil
>   | ---
> - | - ['sql_defer_foreign_keys', false]
>   | ...
> -s:get({'sql_recursive_triggers'})
> +err = nil
>   | ---
> - | - ['sql_recursive_triggers', true]
>   | ...
> -s:get({'sql_reverse_unordered_selects'})
> +for _, tuple in t:pairs() do                    \
> +    name = tuple.name                           \
> +    err = check_sorting(s, t, name)             \
> +    if err then                                 \
> +        break                                   \
> +    end                                         \
> +end
>   | ---
> - | - ['sql_reverse_unordered_selects', false]
>   | ...
> -s:get({'sql_default_engine'})
> +err and {err, name}
>   | ---
> - | - ['sql_default_engine', 'memtx']
> + | - null
>   | ...
> -s:get({'abcd'})
> +
> +t:drop()
>   | ---
>   | ...
>  
> diff --git a/test/box/gh-4511-access-settings-from-any-frontend.test.lua b/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> index 366874998..b243be15e 100644
> --- a/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> +++ b/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> @@ -36,6 +36,12 @@ function check_sorting(ss, ts, key)
>      for _, it in pairs(iterators_list) do
>          local view_space = ss:select({key}, {iterator = it})
>          local test_space = ts:select({key}, {iterator = it})
> +        if #view_space ~= #test_space then
> +            return {
> +                err = 'bad sorting', type = it, exp = test_space,
> +                got = view_space
> +            }
> +        end
>          for key, value in pairs(view_space) do
>              if test_space[key].name ~= value.name then
>                  return {
> @@ -52,17 +58,23 @@ check_sorting(s, t)
>  check_sorting(s, t, 'abcde')
>  check_sorting(s, t, 'sql_d')
>  check_sorting(s, t, 'sql_v')
> -check_sorting(s, t, 'sql_defer_foreign_keys')
> +check_sorting(s, t, 'z')
> +check_sorting(s, t, 'sql_parser_debuf')
> +check_sorting(s, t, 'sql_parser_debuh')
> +
> +name = nil
> +err = nil
> +for _, tuple in t:pairs() do                    \
> +    name = tuple.name                           \
> +    err = check_sorting(s, t, name)             \
> +    if err then                                 \
> +        break                                   \
> +    end                                         \
> +end
> +err and {err, name}
>  
>  t:drop()
>  
> --- Check get() method of session_settings space.
> -s:get({'sql_defer_foreign_keys'})
> -s:get({'sql_recursive_triggers'})
> -s:get({'sql_reverse_unordered_selects'})
> -s:get({'sql_default_engine'})
> -s:get({'abcd'})
> -
>  -- Check pairs() method of session_settings space.
>  t = {}
>  for key, value in s:pairs() do table.insert(t, {key, value}) end
> -- 
> 2.21.1 (Apple Git-122.3)
>