Skip to content

Draft: [th/setting-info-binsearch] libnm: use binary search for nm_meta_setting_infos_by_gtype() for libnmc

Thomas Haller requested to merge th/setting-info-binsearch into main

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/tests/test-setting.c b/src/libnm-core-impl/tests/test-setting.c
    index 63064371187a..d79472e5ef68 100644
    --- a/src/libnm-core-impl/tests/test-setting.c
    +++ b/src/libnm-core-impl/tests/test-setting.c
    @@ -5075,6 +5075,29 @@ main(int argc, char **argv)
     {
         nmtst_init(&argc, &argv, TRUE);

    +    {
    +        gs_unref_object NMConnection *con = NULL;
    +        guint8                        ctr = 0;
    +        int                           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_INT(nm_connection_get_setting(con, NM_TYPE_SETTING_WIRED));
    +            ctr += GPOINTER_TO_INT(nm_connection_get_setting(con, NM_TYPE_SETTING_CONNECTION));
    +            ctr += GPOINTER_TO_INT(nm_connection_get_setting(con, NM_TYPE_SETTING_PROXY));
    +            ctr += GPOINTER_TO_INT(nm_connection_get_setting(con, NM_TYPE_SETTING_WIREGUARD));
    +            ctr += GPOINTER_TO_INT(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",

    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 87647438c6e6..c9ae50773245 100644
    --- a/src/libnm-core-impl/nm-meta-setting-base-impl.c
    +++ b/src/libnm-core-impl/nm-meta-setting-base-impl.c
    @@ -824,6 +824,11 @@ nm_meta_setting_infos_by_gtype(GType gtype)
     {
         const NMMetaSettingInfo *setting_info;

    +#if _NM_META_SETTING_BASE_IMPL_LIBNM
    +    return _infos_by_gtype_from_class(gtype);
    +#endif
    +    nm_assert_not_reached();
    +
     #if _NM_META_SETTING_BASE_IMPL_LIBNM
         setting_info = _infos_by_gtype_from_class(gtype);
     #else

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:

  • _infos_by_gtype_from_class:
          1,423.11 msec task-clock:u              #    0.993 CPUs utilized            ( +-  1.97% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
               310      page-faults:u             #  216.844 /sec                     ( +-  0.08% )
     5,078,272,385      cycles:u                  #    3.552 GHz                      ( +-  1.99% )
    12,046,740,527      instructions:u            #    2.32  insn per cycle           ( +-  0.00% )
     3,221,308,552      branches:u                #    2.253 G/sec                    ( +-  0.00% )
         9,747,799      branch-misses:u           #    0.30% of all branches          ( +- 13.26% )

            1.4335 +- 0.0279 seconds time elapsed  ( +-  1.95% )
  • _infos_by_gtype_binary_search:
          1,490.14 msec task-clock:u              #    0.981 CPUs utilized            ( +-  1.05% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
               311      page-faults:u             #  205.456 /sec                     ( +-  0.24% )
     5,286,277,050      cycles:u                  #    3.492 GHz                      ( +-  1.25% )
    14,616,732,947      instructions:u            #    2.69  insn per cycle           ( +-  0.00% )
     3,681,305,419      branches:u                #    2.432 G/sec                    ( +-  0.00% )
         3,032,597      branch-misses:u           #    0.08% of all branches          ( +- 19.27% )

            1.5189 +- 0.0162 seconds time elapsed  ( +-  1.07% )
  • _infos_by_gtype_search:
          3,530.73 msec task-clock:u              #    0.923 CPUs utilized            ( +-  2.05% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
               314      page-faults:u             #   82.203 /sec                     ( +-  0.30% )
    12,166,655,516      cycles:u                  #    3.185 GHz                      ( +-  2.67% )
    28,546,724,325      instructions:u            #    2.12  insn per cycle           ( +-  0.00% )
     9,671,306,320      branches:u                #    2.532 G/sec                    ( +-  0.00% )
        38,506,071      branch-misses:u           #    0.40% of all branches          ( +- 18.96% )

            3.8262 +- 0.0722 seconds time elapsed  ( +-  1.89% )

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

Still do it, because all the work to profile it was already done. Yes, it's slightly more complicated, but it's a self-contained piece that likely won't have to change anymore and which is widely hit by unit tests.

Merge request reports