dhcp: binary search in nm_dhcp_option_find()

Let's use binary search.

Test patch:

    diff --git a/src/core/dhcp/tests/test-dhcp-utils.c b/src/core/dhcp/tests/test-dhcp-utils.c
    index 9b54e2cd0228..007993341672 100644
    --- a/src/core/dhcp/tests/test-dhcp-utils.c
    +++ b/src/core/dhcp/tests/test-dhcp-utils.c
    @@ -788,6 +788,24 @@ NMTST_DEFINE();
     int
     main(int argc, char **argv)
     {
    +    int i;
    +    guint idx;
    +    guint c;
    +
    +    idx = 0;
    +    c = 0;
    +    for (i = 0; i < 1000000; i++) {
    +        const guint option = _nm_dhcp_option_dhcp4_options[idx % G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)].option_num;
    +
    +        idx += 2010055757;
    +
    +        if (nm_dhcp_option_find(AF_INET, option)->name)
    +            c++;
    +    }
    +    g_print(">%u\n", c);
    +
    +    return 0;
    +
         nmtst_init_assert_logging(&argc, &argv, "WARN", "DEFAULT");

         g_test_add_func("/dhcp/generic-options", test_generic_options);

Build:

  CFLAGS='-O2' ./autogen.sh --with-more-asserts=0
  make -j 10 src/core/dhcp/tests/test-dhcp-utils && \
    src/core/dhcp/tests/test-dhcp-utils && \
    perf stat -r 200 -B src/core/dhcp/tests/test-dhcp-utils

Before:

 Performance counter stats for 'src/core/dhcp/tests/test-dhcp-utils' (200 runs):

             82.83 msec task-clock:u              #    0.994 CPUs utilized            ( +-  0.21% )
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
               579      page-faults:u             #    0.007 M/sec                    ( +-  0.03% )
       264,676,245      cycles:u                  #    3.195 GHz                      ( +-  0.06% )
       544,792,266      instructions:u            #    2.06  insn per cycle           ( +-  0.00% )
       151,624,848      branches:u                # 1830.472 M/sec                    ( +-  0.00% )
         1,083,780      branch-misses:u           #    0.71% of all branches          ( +-  0.01% )

          0.083328 +- 0.000178 seconds time elapsed  ( +-  0.21% )

After:

 Performance counter stats for 'src/core/dhcp/tests/test-dhcp-utils' (200 runs):

             39.21 msec task-clock:u              #    0.987 CPUs utilized            ( +-  0.57% )
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
               579      page-faults:u             #    0.015 M/sec                    ( +-  0.03% )
       115,396,123      cycles:u                  #    2.943 GHz                      ( +-  0.23% )
       137,664,630      instructions:u            #    1.19  insn per cycle           ( +-  0.00% )
        25,866,025      branches:u                #  659.597 M/sec                    ( +-  0.00% )
         1,919,616      branch-misses:u           #    7.42% of all branches          ( +-  0.12% )

          0.039717 +- 0.000227 seconds time elapsed  ( +-  0.57% )

1 files changed, 162 insertions, 10 deletions

diff --git a/src/core/dhcp/nm-dhcp-options.c b/src/core/dhcp/nm-dhcp-options.c
index a8b27ddb8d..3537cd147e 100644
--- a/src/core/dhcp/nm-dhcp-options.c
+++ b/src/core/dhcp/nm-dhcp-options.c
@@ -7,6 +7,8 @@
 
 #include "nm-dhcp-options.h"
 
+#include "nm-glib-aux/nm-str-buf.h"
+
 /*****************************************************************************/
 
 #define REQ(_num, _name, _include)                                                         \
@@ -169,6 +171,23 @@ const NMDhcpOption _nm_dhcp_option_dhcp4_options[] = {
     REQ(NM_DHCP_OPTION_DHCP4_NM_NEXT_SERVER, "next_server", FALSE),
 };
 
+static const NMDhcpOption *const _sorted_options_4[G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)] = {
+#define A(idx) (&_nm_dhcp_option_dhcp4_options[(idx)])
+    A(0),   A(1),   A(8),   A(18),  A(19),  A(2),   A(20),  A(21),  A(22),  A(23),  A(24),  A(3),
+    A(25),  A(26),  A(4),   A(27),  A(17),  A(28),  A(29),  A(30),  A(31),  A(32),  A(33),  A(34),
+    A(35),  A(5),   A(36),  A(6),   A(37),  A(38),  A(39),  A(40),  A(9),   A(41),  A(42),  A(43),
+    A(44),  A(45),  A(46),  A(10),  A(11),  A(12),  A(47),  A(48),  A(49),  A(50),  A(51),  A(52),
+    A(13),  A(53),  A(54),  A(55),  A(57),  A(58),  A(59),  A(60),  A(61),  A(62),  A(63),  A(64),
+    A(65),  A(66),  A(67),  A(68),  A(69),  A(70),  A(71),  A(72),  A(73),  A(74),  A(75),  A(76),
+    A(77),  A(78),  A(79),  A(80),  A(81),  A(82),  A(83),  A(84),  A(85),  A(86),  A(87),  A(56),
+    A(88),  A(89),  A(90),  A(91),  A(92),  A(93),  A(14),  A(7),   A(94),  A(95),  A(96),  A(97),
+    A(98),  A(99),  A(100), A(101), A(102), A(103), A(104), A(105), A(106), A(107), A(108), A(109),
+    A(110), A(111), A(112), A(113), A(114), A(115), A(116), A(117), A(118), A(119), A(120), A(121),
+    A(122), A(123), A(124), A(125), A(126), A(127), A(128), A(129), A(130), A(131), A(132), A(133),
+    A(134), A(15),  A(135), A(136), A(16),  A(137), A(138), A(139), A(140), A(141),
+#undef A
+};
+
 const NMDhcpOption _nm_dhcp_option_dhcp6_options[] = {
     REQ(NM_DHCP_OPTION_DHCP6_CLIENTID, "dhcp6_client_id", FALSE),
 
@@ -197,27 +216,160 @@ const NMDhcpOption _nm_dhcp_option_dhcp6_options[] = {
 
 #undef REQ
 
-const NMDhcpOption *
-nm_dhcp_option_find(int addr_family, guint option)
+static const NMDhcpOption *const _sorted_options_6[G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options)] = {
+#define A(idx) (&_nm_dhcp_option_dhcp6_options[(idx)])
+    A(0),
+    A(1),
+    A(2),
+    A(3),
+    A(4),
+    A(5),
+    A(6),
+    A(7),
+    A(8),
+    A(9),
+    A(10),
+    A(11),
+    A(12),
+    A(13),
+    A(14),
+    A(15),
+#undef A
+};
+
+/*****************************************************************************/
+
+static int
+_sorted_options_generate_sort(gconstpointer pa, gconstpointer pb, gpointer user_data)
+{
+    const NMDhcpOption *const *a = pa;
+    const NMDhcpOption *const *b = pb;
+
+    NM_CMP_DIRECT((*a)->option_num, (*b)->option_num);
+    return nm_assert_unreachable_val(0);
+}
+
+static char *
+_sorted_options_generate(const NMDhcpOption *base, const NMDhcpOption *const *sorted, guint n)
+{
+    gs_free const NMDhcpOption **sort2 = NULL;
+    NMStrBuf                     sbuf  = NM_STR_BUF_INIT(0, FALSE);
+    guint                        i;
+
+    sort2 = nm_memdup(sorted, n * sizeof(sorted[0]));
+
+    g_qsort_with_data(sort2, n, sizeof(sort2[0]), _sorted_options_generate_sort, NULL);
+
+    for (i = 0; i < n; i++) {
+        if (i > 0)
+            nm_str_buf_append(&sbuf, ", ");
+        nm_str_buf_append_printf(&sbuf, "A(%d)", (int) (sort2[i] - base));
+    }
+
+    return nm_str_buf_finalize(&sbuf, NULL);
+}
+
+_nm_unused static void
+_ASSERT_sorted(int IS_IPv4, const NMDhcpOption *const *const sorted, int n)
+
 {
-    const int                 IS_IPv4 = NM_IS_IPv4(addr_family);
     const NMDhcpOption *const options =
         IS_IPv4 ? _nm_dhcp_option_dhcp4_options : _nm_dhcp_option_dhcp6_options;
-    int n_options = IS_IPv4 ? G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)
-                            : G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options);
-    int i;
+    int           i;
+    int           j;
+    gs_free char *sorted_msg = NULL;
 
-    for (i = 0; i < n_options; i++) {
-        const NMDhcpOption *opt = &options[i];
+    for (i = 0; i < n; i++) {
+        const NMDhcpOption *opt = sorted[i];
+
+        g_assert(opt);
+        g_assert(opt >= options);
+        g_assert(opt < &options[n]);
+
+        for (j = 0; j < i; j++) {
+            const NMDhcpOption *opt2 = sorted[j];
+
+            if (opt == opt2) {
+                g_error("%s:%d: the _sorted_options_%c at [%d] (opt=%u, %s) is duplicated at "
+                        "[%d] (SORT: %s)",
+                        __FILE__,
+                        __LINE__,
+                        IS_IPv4 ? '4' : '6',
+                        i,
+                        opt->option_num,
+                        opt->name,
+                        j,
+                        (sorted_msg = _sorted_options_generate(options, sorted, n)));
+            }
+        }
 
-        if (opt->option_num == option)
-            return opt;
+        if (i > 0) {
+            const NMDhcpOption *opt2 = sorted[i - 1];
+
+            if (opt2->option_num >= opt->option_num) {
+                g_error("%s:%d: the _sorted_options_%c at [%d] (opt=%u, %s) should come before "
+                        "[%d] (opt=%u, %s) (SORT: %s)",
+                        __FILE__,
+                        __LINE__,
+                        IS_IPv4 ? '4' : '6',
+                        i,
+                        opt->option_num,
+                        opt->name,
+                        i - 1,
+                        opt2->option_num,
+                        opt2->name,
+                        (sorted_msg = _sorted_options_generate(options, sorted, n)));
+            }
+        }
+    }
+}
+
+/*****************************************************************************/
+
+const NMDhcpOption *
+nm_dhcp_option_find(int addr_family, guint option)
+{
+    const int                        IS_IPv4 = NM_IS_IPv4(addr_family);
+    const NMDhcpOption *const *const sorted  = IS_IPv4 ? _sorted_options_4 : _sorted_options_6;
+    const int                        n       = IS_IPv4 ? G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)
+                                                       : G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options);
+    int                              imin    = 0;
+    int                              imax    = n - 1;
+    int                              imid    = (n - 1) / 2;
+
+#if NM_MORE_ASSERTS > 10
+    nm_assert(n < G_MAXINT / 2);
+    if (IS_IPv4 && !NM_MORE_ASSERT_ONCE(10)) {
+        /* already checked */
+    } else if (!IS_IPv4 && !NM_MORE_ASSERT_ONCE(10)) {
+        /* already checked */
+    } else
+        _ASSERT_sorted(IS_IPv4, sorted, n);
+#endif
+
+    for (;;) {
+        const guint o = sorted[imid]->option_num;
+
+        if (G_UNLIKELY(o == option))
+            return sorted[imid];
+
+        if (o < option)
+            imin = imid + 1;
+        else
+            imax = imid - 1;
+
+        if (G_UNLIKELY(imin > imax))
+            break;
+
+        imid = (imin + imax) / 2;
     }
 
     /* Option should always be found */
     return nm_assert_unreachable_val(NULL);
 }
 
+/*****************************************************************************/
+
 void
 nm_dhcp_option_take_option(GHashTable *options, int addr_family, guint option, char *value)
 {