summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas Haller <thaller@redhat.com>2020-02-13 11:17:22 +0100
committerThomas Haller <thaller@redhat.com>2020-02-13 14:49:45 +0100
commit17d9b852c80ceefa37478eea03e844d0d057c4de (patch)
treeb4a3ce48e5a6fd23f6e33ecedca9cf0579337701
parent760551e3fc11b367431c80e36d9ca892c10481f2 (diff)
shared: explicitly implement binary search in NM_UTILS_STRING_TABLE_LOOKUP_DEFINE*()
When looking at nm_utils_array_find_binary_search(), we see that binary search really isn't complicated. In nm_utils_array_find_binary_search() it looks complicated, because that is our general purpose function which accepts arbitrary lists, uses an opaque compare function, accepts a user data argument, and returns the insertion position. This is unnecessary for the narrow purpose in NM_UTILS_STRING_TABLE_LOOKUP_DEFINE*(). When we inline the binary search, it can be simplified, and the remaining parts is simple enough to prefer this duplication of binary search over using our general purpose function. Also, this gives the compiler more chance for optimization. For example, we can use "unsigned" as index type instead of gssize, because we know (at compile time), that this type will always be large enough for our LIST. Also, we can directly call strcmp(). The result is that the macro's implementation is also fast in the best case (where the needle is found with only one strcmp()) and in the cases where there is a small number of items to search. It thus alleviates concerns that using the macro might be slower than an optimized implementation. The binary size of the defined function increases slightly (from 112 bytes to 192 bytes, on x86_64, GCC, -O2). But according to my tests it is slightly and measurably faster.
-rw-r--r--shared/nm-glib-aux/nm-shared-utils.h33
1 files changed, 22 insertions, 11 deletions
diff --git a/shared/nm-glib-aux/nm-shared-utils.h b/shared/nm-glib-aux/nm-shared-utils.h
index 3d211f39f..c1984e1a1 100644
--- a/shared/nm-glib-aux/nm-shared-utils.h
+++ b/shared/nm-glib-aux/nm-shared-utils.h
@@ -1565,8 +1565,6 @@ fcn_name (const char *name) \
static gboolean checked = FALSE; \
int i; \
\
- G_STATIC_ASSERT (G_N_ELEMENTS (LIST) > 1); \
- \
if (!checked) { \
checked = TRUE; \
\
@@ -1579,16 +1577,29 @@ fcn_name (const char *name) \
} \
\
if (G_LIKELY (name)) { \
- gssize idx; \
+ G_STATIC_ASSERT (G_N_ELEMENTS (LIST) > 1); \
+ G_STATIC_ASSERT (G_N_ELEMENTS (LIST) < G_MAXUINT / 2u - 10u); \
+ unsigned imin = 0; \
+ unsigned imax = (G_N_ELEMENTS (LIST) - 1); \
+ unsigned imid = (G_N_ELEMENTS (LIST) - 1) / 2; \
\
- idx = nm_utils_array_find_binary_search (LIST, \
- sizeof (LIST[0]), \
- G_N_ELEMENTS (LIST), \
- &name, \
- nm_strcmp_p_with_data, \
- NULL); \
- if (G_LIKELY (idx >= 0)) \
- return LIST[idx].value; \
+ for (;;) { \
+ const int cmp = strcmp (LIST[imid].name, name); \
+ \
+ if (G_UNLIKELY (cmp == 0)) \
+ return LIST[imid].value; \
+ \
+ if (cmp < 0) \
+ imin = imid + 1u; \
+ else \
+ imax = imid - 1u; \
+ \
+ if (G_UNLIKELY (imin > imax)) \
+ break; \
+ \
+ /* integer overflow cannot happen, because LIST is shorter than G_MAXUINT/2. */ \
+ imid = (imin + imax) / 2u;\
+ } \
} \
\
{ unknown_val_cmd; } \