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

[Nikita Pettik <korablev@tarantool.org>]

On 30 Mar 12:13, 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.
> 
> Closes #4712
> ---

Still I see no need for this patch. It is unclear which improvements
it introduces except for code complication.
 
> diff --git a/src/box/session_settings.c b/src/box/session_settings.c
> index 2ecf71f2d..5e4a50427 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)
>