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

[Chris Sosnin]

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;
 	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) {
+	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;
+}
+
 void
 close_all_xcpt(int fdc, ...)
 {
diff --git a/src/trivia/util.h b/src/trivia/util.h
index 8a3d22b38..5c1e3bd5d 100644
--- a/src/trivia/util.h
+++ b/src/trivia/util.h
@@ -98,6 +98,9 @@ strindex(const char **haystack, const char *needle, uint32_t hmax);
 uint32_t
 strnindex(const char **haystack, const char *needle, uint32_t len, uint32_t hmax);
 
+uint32_t
+str_bin_search(const char **haystack, const char *needle, uint32_t hmax);
+
 #define nelem(x)     (sizeof((x))/sizeof((x)[0]))
 #define field_sizeof(compound_type, field) sizeof(((compound_type *)NULL)->field)
 #ifndef lengthof
-- 
2.21.0 (Apple Git-122.2)