From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp14.mail.ru (smtp14.mail.ru [94.100.181.95]) (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 23CE94696C3 for ; Fri, 3 Apr 2020 17:00:19 +0300 (MSK) Date: Fri, 3 Apr 2020 14:00:17 +0000 From: Nikita Pettik Message-ID: <20200403140017.GE2993@tarantool.org> References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: Subject: Re: [Tarantool-patches] [PATCH 2/4] 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 Cc: tarantool-patches@dev.tarantool.org, v.shpilevoy@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) >