libnm: use binary search for nm_meta_setting_infos_by_gtype() for libnmc

The file "nm-meta-setting-base-impl.c" is shared by "libnm-core-impl" and
"libnmc-setting". For "libnm-core-impl" it uses a efficient lookup from the
gtype. For "libnmc-setting", that class information is not available, so
it did a linear search. Instead, do a binary search.

Tested:

    diff --git a/src/libnm-core-impl/nm-meta-setting-base-impl.c b/src/libnm-core-impl/nm-meta-setting-base-impl.c
    index 3434c858391f..62c366d2ca42 100644
    --- a/src/libnm-core-impl/nm-meta-setting-base-impl.c
    +++ b/src/libnm-core-impl/nm-meta-setting-base-impl.c
    @@ -821,6 +821,11 @@ nm_meta_setting_infos_by_gtype(GType gtype)
     {
         const NMMetaSettingInfo *setting_info;

    +#if _NM_META_SETTING_BASE_IMPL_LIBNM
    +    return _infos_by_gtype_binary_search(gtype);
    +#endif
    +    nm_assert_not_reached();
    +
     #if _NM_META_SETTING_BASE_IMPL_LIBNM
         setting_info = _infos_by_gtype_from_class(gtype);
     #else
    diff --git a/src/libnm-core-impl/tests/test-setting.c b/src/libnm-core-impl/tests/test-setting.c
    index 85d549eb766c..65fcafd076c9 100644
    --- a/src/libnm-core-impl/tests/test-setting.c
    +++ b/src/libnm-core-impl/tests/test-setting.c
    @@ -5134,6 +5134,29 @@ main(int argc, char **argv)
     {
         nmtst_init(&argc, &argv, TRUE);

    +    {
    +        gs_unref_object NMConnection *con = NULL;
    +        guint8                        ctr = 0;
    +        guint                         i;
    +
    +        con = nmtst_create_minimal_connection("test", NULL, NM_SETTING_WIRED_SETTING_NAME, NULL);
    +
    +        nm_connection_add_setting(con, nm_setting_wired_new());
    +
    +        nmtst_connection_normalize(con);
    +        nmtst_assert_connection_verifies_without_normalization(con);
    +
    +        for (i = 0; i < 10000000; i++) {
    +            ctr += GPOINTER_TO_UINT(nm_connection_get_setting(con, NM_TYPE_SETTING_WIRED));
    +            ctr += GPOINTER_TO_UINT(nm_connection_get_setting(con, NM_TYPE_SETTING_CONNECTION));
    +            ctr += GPOINTER_TO_UINT(nm_connection_get_setting(con, NM_TYPE_SETTING_PROXY));
    +            ctr += GPOINTER_TO_UINT(nm_connection_get_setting(con, NM_TYPE_SETTING_WIREGUARD));
    +            ctr += GPOINTER_TO_UINT(nm_connection_get_setting(con, NM_TYPE_SETTING_IP4_CONFIG));
    +        }
    +
    +        return !!ctr;
    +    }
    +
         g_test_add_func("/libnm/test_connection_uuid", test_connection_uuid);

         g_test_add_func("/libnm/settings/test_nm_meta_setting_types_by_priority",

Results of `make src/libnm-core-impl/tests/test-setting && libtool --mode=execute perf stat -r 5 -B src/libnm-core-impl/tests/test-setting`:

 1) previous linear search: 3,182.81 msec
 2) bsearch not inlined:    1,611.19 msec
 3) bsearch open-coded:     1,214.45 msec
 4) bsearch inlined:        1,167.70 msec
 5) lookup from class:      1,147.64 msec

 1) previous implementation
 2) using nm_array_find_bsearch()
 3) manually implementing binary search
 4) using nm_array_find_bsearch_inline()
 5) only available to libnm-core as it uses internal meta data

Note that for "libnm-core-impl" the implementation was already fast (5), and
it didn't change. It only changed to binary search for "libnmc-setting",
which arguably is a less strong use-case.

2 files changed, 154 insertions, 8 deletions

diff --git a/src/libnm-core-impl/nm-meta-setting-base-impl.c b/src/libnm-core-impl/nm-meta-setting-base-impl.c
index 31e1012b1d..5e627cfc7d 100644
--- a/src/libnm-core-impl/nm-meta-setting-base-impl.c
+++ b/src/libnm-core-impl/nm-meta-setting-base-impl.c
@@ -3,6 +3,8 @@
  * Copyright (C) 2017 - 2018 Red Hat, Inc.
  */
 
+#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+
 #include "libnm-glib-aux/nm-default-glib-i18n-lib.h"
 
 #include "nm-meta-setting-base.h"
@@ -745,6 +747,75 @@ _infos_by_gtype_search(GType gtype)
     return NULL;
 }
 
+typedef struct {
+    GType                    gtype;
+    const NMMetaSettingInfo *setting_info;
+} LookupData;
+
+_nm_always_inline static inline int
+_lookup_data_cmp(gconstpointer ptr_a, gconstpointer ptr_b, gpointer user_data)
+{
+    const GType *const a = ptr_a;
+    const GType *const b = ptr_b;
+
+    nm_assert(a);
+    nm_assert(b);
+    nm_assert(a != b);
+
+    NM_CMP_DIRECT(*a, *b);
+    return 0;
+}
+
+static const NMMetaSettingInfo *
+_infos_by_gtype_binary_search(GType gtype)
+{
+    static LookupData        static_array[_NM_META_SETTING_TYPE_NUM];
+    static const LookupData *static_ptr = NULL;
+    const LookupData        *ptr;
+    gssize                   idx;
+
+again:
+    ptr = g_atomic_pointer_get(&static_ptr);
+    if (G_UNLIKELY(!ptr)) {
+        static gsize g_lock = 0;
+        int          i;
+
+        if (!g_once_init_enter(&g_lock))
+            goto again;
+
+        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+            const NMMetaSettingInfo *m = &nm_meta_setting_infos[i];
+
+            static_array[i] = (LookupData){
+                .gtype        = m->get_setting_gtype(),
+                .setting_info = m,
+            };
+        }
+
+        g_qsort_with_data(static_array,
+                          _NM_META_SETTING_TYPE_NUM,
+                          sizeof(static_array[0]),
+                          _lookup_data_cmp,
+                          NULL);
+
+        ptr = static_array;
+        g_atomic_pointer_set(&static_ptr, ptr);
+
+        g_once_init_leave(&g_lock, 1);
+    }
+
+    idx = nm_array_find_bsearch_inline(ptr,
+                                       _NM_META_SETTING_TYPE_NUM,
+                                       sizeof(ptr[0]),
+                                       &gtype,
+                                       _lookup_data_cmp,
+                                       NULL);
+    if (idx < 0)
+        return NULL;
+
+    return ptr[idx].setting_info;
+}
+
 const NMMetaSettingInfo *
 nm_meta_setting_infos_by_gtype(GType gtype)
 {
@@ -752,13 +823,15 @@ nm_meta_setting_infos_by_gtype(GType gtype)
 
 #if _NM_META_SETTING_BASE_IMPL_LIBNM
     setting_info = _infos_by_gtype_from_class(gtype);
-
-    if (NM_MORE_ASSERTS > 20)
-        nm_assert(setting_info == _infos_by_gtype_search(gtype));
 #else
-    setting_info = _infos_by_gtype_search(gtype);
+    setting_info = _infos_by_gtype_binary_search(gtype);
 #endif
 
+    if (NM_MORE_ASSERTS > 20) {
+        nm_assert(setting_info == _infos_by_gtype_search(gtype));
+        nm_assert(setting_info == _infos_by_gtype_binary_search(gtype));
+    }
+
     return setting_info;
 }
 
diff --git a/src/libnmc-setting/nm-meta-setting-base-impl.c b/src/libnmc-setting/nm-meta-setting-base-impl.c
index 31e1012b1d..5e627cfc7d 100644
--- a/src/libnmc-setting/nm-meta-setting-base-impl.c
+++ b/src/libnmc-setting/nm-meta-setting-base-impl.c
@@ -3,6 +3,8 @@
  * Copyright (C) 2017 - 2018 Red Hat, Inc.
  */
 
+#define NM_WANT_NM_ARRAY_FIND_BSEARCH_INLINE
+
 #include "libnm-glib-aux/nm-default-glib-i18n-lib.h"
 
 #include "nm-meta-setting-base.h"
@@ -745,6 +747,75 @@ _infos_by_gtype_search(GType gtype)
     return NULL;
 }
 
+typedef struct {
+    GType                    gtype;
+    const NMMetaSettingInfo *setting_info;
+} LookupData;
+
+_nm_always_inline static inline int
+_lookup_data_cmp(gconstpointer ptr_a, gconstpointer ptr_b, gpointer user_data)
+{
+    const GType *const a = ptr_a;
+    const GType *const b = ptr_b;
+
+    nm_assert(a);
+    nm_assert(b);
+    nm_assert(a != b);
+
+    NM_CMP_DIRECT(*a, *b);
+    return 0;
+}
+
+static const NMMetaSettingInfo *
+_infos_by_gtype_binary_search(GType gtype)
+{
+    static LookupData        static_array[_NM_META_SETTING_TYPE_NUM];
+    static const LookupData *static_ptr = NULL;
+    const LookupData        *ptr;
+    gssize                   idx;
+
+again:
+    ptr = g_atomic_pointer_get(&static_ptr);
+    if (G_UNLIKELY(!ptr)) {
+        static gsize g_lock = 0;
+        int          i;
+
+        if (!g_once_init_enter(&g_lock))
+            goto again;
+
+        for (i = 0; i < _NM_META_SETTING_TYPE_NUM; i++) {
+            const NMMetaSettingInfo *m = &nm_meta_setting_infos[i];
+
+            static_array[i] = (LookupData){
+                .gtype        = m->get_setting_gtype(),
+                .setting_info = m,
+            };
+        }
+
+        g_qsort_with_data(static_array,
+                          _NM_META_SETTING_TYPE_NUM,
+                          sizeof(static_array[0]),
+                          _lookup_data_cmp,
+                          NULL);
+
+        ptr = static_array;
+        g_atomic_pointer_set(&static_ptr, ptr);
+
+        g_once_init_leave(&g_lock, 1);
+    }
+
+    idx = nm_array_find_bsearch_inline(ptr,
+                                       _NM_META_SETTING_TYPE_NUM,
+                                       sizeof(ptr[0]),
+                                       &gtype,
+                                       _lookup_data_cmp,
+                                       NULL);
+    if (idx < 0)
+        return NULL;
+
+    return ptr[idx].setting_info;
+}
+
 const NMMetaSettingInfo *
 nm_meta_setting_infos_by_gtype(GType gtype)
 {
@@ -752,13 +823,15 @@ nm_meta_setting_infos_by_gtype(GType gtype)
 
 #if _NM_META_SETTING_BASE_IMPL_LIBNM
     setting_info = _infos_by_gtype_from_class(gtype);
-
-    if (NM_MORE_ASSERTS > 20)
-        nm_assert(setting_info == _infos_by_gtype_search(gtype));
 #else
-    setting_info = _infos_by_gtype_search(gtype);
+    setting_info = _infos_by_gtype_binary_search(gtype);
 #endif
 
+    if (NM_MORE_ASSERTS > 20) {
+        nm_assert(setting_info == _infos_by_gtype_search(gtype));
+        nm_assert(setting_info == _infos_by_gtype_binary_search(gtype));
+    }
+
     return setting_info;
 }