From 611f2c3a60af1895575e0a0d2802952ff35f3c6c Mon Sep 17 00:00:00 2001 From: Thomas Haller Date: Tue, 6 Sep 2022 11:29:20 +0200 Subject: 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. --- src/libnm-core-impl/nm-meta-setting-base-impl.c | 81 +++++++++++++++++++++++-- src/libnmc-setting/nm-meta-setting-base-impl.c | 81 +++++++++++++++++++++++-- 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]), + >ype, + _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]), + >ype, + _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; } -- cgit v1.2.3