benchtests/bench-strcasestr.c

   1 /* Measure strcasestr functions.
   2    Copyright (C) 2013-2024 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #define MIN_PAGE_SIZE 131072
  20 #define TEST_MAIN
  21 #define TEST_NAME "strcasestr"
  22 #include "bench-string.h"
  23
  24 #include "json-lib.h"
  25
  26 static const char input[] =
  27 "This manual is written with the assumption that you are at least "
  28 "somewhat familiar with the C programming language and basic programming "
  29 "concepts.  Specifically, familiarity with ISO standard C (*note ISO "
  30 "C::), rather than “traditional” pre-ISO C dialects, is assumed.\n"
  31
  32 "   The GNU C Library includes several “header files”, each of which "
  33 "provides definitions and declarations for a group of related facilities; "
  34 "this information is used by the C compiler when processing your program. "
  35 "For example, the header file ‘stdio.h’ declares facilities for "
  36 "performing input and output, and the header file ‘string.h’ declares "
  37 "string processing utilities.  The organization of this manual generally "
  38 "follows the same division as the header files.\n"
  39
  40 "   If you are reading this manual for the first time, you should read "
  41 "all of the introductory material and skim the remaining chapters.  There "
  42 "are a _lot_ of functions in the GNU C Library and it’s not realistic to "
  43 "expect that you will be able to remember exactly _how_ to use each and "
  44 "every one of them.  It’s more important to become generally familiar "
  45 "with the kinds of facilities that the library provides, so that when you "
  46 "are writing your programs you can recognize _when_ to make use of "
  47 "library functions, and _where_ in this manual you can find more specific "
  48 "information about them.\n";
  49
  50 #define STRCASESTR simple_strcasestr
  51 #define NO_ALIAS
  52 #define __strncasecmp strncasecmp
  53 #define __strnlen strnlen
  54 #include "../string/strcasestr.c"
  55
  56 typedef char *(*proto_t) (const char *, const char *);
  57
  58 IMPL (simple_strcasestr, 0)
  59 IMPL (strcasestr, 1)
  60
  61 static void
  62 do_one_test (json_ctx_t *json_ctx, impl_t *impl, const char *s1,
  63              const char *s2, char *exp_result)
  64 {
  65   size_t i, iters = INNER_LOOP_ITERS_SMALL / 8;
  66   timing_t start, stop, cur;
  67   char *res;
  68
  69   TIMING_NOW (start);
  70   for (i = 0; i < iters; ++i)
  71     res = CALL (impl, s1, s2);
  72   TIMING_NOW (stop);
  73
  74   TIMING_DIFF (cur, start, stop);
  75
  76   json_element_double (json_ctx, (double) cur / (double) iters);
  77
  78   if (res != exp_result)
  79     {
  80       error (0, 0, "Wrong result in function %s %s %s", impl->name,
  81              (res == NULL) ? "(null)" : res,
  82              (exp_result == NULL) ? "(null)" : exp_result);
  83       ret = 1;
  84     }
  85 }
  86
  87 static void
  88 do_test (json_ctx_t *json_ctx, size_t align1, size_t align2, size_t len1,
  89          size_t len2, int fail)
  90 {
  91   char *s1 = (char *) (buf1 + align1);
  92   char *s2 = (char *) (buf2 + align2);
  93
  94   size_t size = sizeof (input) - 1;
  95   size_t pos = (len1 + len2) % size;
  96
  97   char *ss2 = s2;
  98   for (size_t l = len2; l > 0; l = l > size ? l - size : 0)
  99     {
 100       size_t t = l > size ? size : l;
 101       if (pos + t <= size)
 102         ss2 = mempcpy (ss2, input + pos, t);
 103       else
 104         {
 105           ss2 = mempcpy (ss2, input + pos, size - pos);
 106           ss2 = mempcpy (ss2, input, t - (size - pos));
 107         }
 108     }
 109   s2[len2] = '\0';
 110
 111   char *ss1 = s1;
 112   for (size_t l = len1; l > 0; l = l > size ? l - size : 0)
 113     {
 114       size_t t = l > size ? size : l;
 115       memcpy (ss1, input, t);
 116       ss1 += t;
 117     }
 118
 119   if (!fail)
 120     memcpy (s1 + len1 - len2, s2, len2);
 121   s1[len1] = '\0';
 122
 123   /* Remove any accidental matches except for the last if !fail.  */
 124   for (ss1 = simple_strcasestr (s1, s2);
 125        ss1 != NULL;
 126        ss1 = simple_strcasestr (ss1 + 1, s2))
 127     if (fail || ss1 != s1 + len1 - len2)
 128       ++ss1[len2 / 2];
 129
 130   json_element_object_begin (json_ctx);
 131   json_attr_uint (json_ctx, "len_haystack", len1);
 132   json_attr_uint (json_ctx, "len_needle", len2);
 133   json_attr_uint (json_ctx, "align_haystack", align1);
 134   json_attr_uint (json_ctx, "align_needle", align2);
 135   json_attr_uint (json_ctx, "fail", fail);
 136
 137   json_array_begin (json_ctx, "timings");
 138
 139   FOR_EACH_IMPL (impl, 0)
 140     do_one_test (json_ctx, impl, s1, s2, fail ? NULL : s1 + len1 - len2);
 141
 142   json_array_end (json_ctx);
 143   json_element_object_end (json_ctx);
 144
 145 }
 146
 147 /* Test needles which exhibit worst-case performance for naive quadradic
 148    implementations.  */
 149
 150 static void
 151 test_hard_needle (json_ctx_t *json_ctx, size_t ne_len, size_t hs_len)
 152 {
 153   char *ne = (char *) buf1;
 154   char *hs = (char *) buf2;
 155
 156   /* Hard needle for strstr algorithm using skip table.  This results in many
 157      memcmp calls comparing most of the needle.  */
 158   {
 159     memset (ne, 'a', ne_len);
 160     ne[ne_len] = '\0';
 161     ne[ne_len - 14] = 'b';
 162
 163     memset (hs, 'a', hs_len);
 164     for (size_t i = ne_len; i <= hs_len; i += ne_len)
 165       {
 166         hs[i - 5] = 'b';
 167         hs[i - 62] = 'b';
 168       }
 169
 170     json_element_object_begin (json_ctx);
 171     json_attr_uint (json_ctx, "len_haystack", hs_len);
 172     json_attr_uint (json_ctx, "len_needle", ne_len);
 173     json_attr_uint (json_ctx, "align_haystack", 0);
 174     json_attr_uint (json_ctx, "align_needle", 0);
 175     json_attr_uint (json_ctx, "fail", 1);
 176     json_attr_string (json_ctx, "desc", "Difficult skiptable(0)");
 177
 178     json_array_begin (json_ctx, "timings");
 179
 180     FOR_EACH_IMPL (impl, 0)
 181       do_one_test (json_ctx, impl, hs, ne, NULL);
 182
 183     json_array_end (json_ctx);
 184     json_element_object_end (json_ctx);
 185   }
 186
 187   /* 2nd hard needle for strstr algorithm using skip table.  This results in
 188      many memcmp calls comparing most of the needle.  */
 189   {
 190     memset (ne, 'a', ne_len);
 191     ne[ne_len] = '\0';
 192     ne[ne_len - 6] = 'b';
 193
 194     memset (hs, 'a', hs_len);
 195     for (size_t i = ne_len; i <= hs_len; i += ne_len)
 196       {
 197         hs[i - 5] = 'b';
 198         hs[i - 6] = 'b';
 199       }
 200
 201     json_element_object_begin (json_ctx);
 202     json_attr_uint (json_ctx, "len_haystack", hs_len);
 203     json_attr_uint (json_ctx, "len_needle", ne_len);
 204     json_attr_uint (json_ctx, "align_haystack", 0);
 205     json_attr_uint (json_ctx, "align_needle", 0);
 206     json_attr_uint (json_ctx, "fail", 1);
 207     json_attr_string (json_ctx, "desc", "Difficult skiptable(1)");
 208
 209     json_array_begin (json_ctx, "timings");
 210
 211     FOR_EACH_IMPL (impl, 0)
 212       do_one_test (json_ctx, impl, hs, ne, NULL);
 213
 214     json_array_end (json_ctx);
 215     json_element_object_end (json_ctx);
 216   }
 217
 218   /* Hard needle for Two-way algorithm - the random input causes a large number
 219      of branch mispredictions which significantly reduces performance on modern
 220      micro architectures.  */
 221   {
 222     for (int i = 0; i < hs_len; i++)
 223       hs[i] = (rand () & 255) > 155 ? 'a' : 'b';
 224     hs[hs_len] = 0;
 225
 226     memset (ne, 'a', ne_len);
 227     ne[ne_len - 2] = 'b';
 228     ne[0] = 'b';
 229     ne[ne_len] = 0;
 230
 231     json_element_object_begin (json_ctx);
 232     json_attr_uint (json_ctx, "len_haystack", hs_len);
 233     json_attr_uint (json_ctx, "len_needle", ne_len);
 234     json_attr_uint (json_ctx, "align_haystack", 0);
 235     json_attr_uint (json_ctx, "align_needle", 0);
 236     json_attr_uint (json_ctx, "fail", 1);
 237     json_attr_string (json_ctx, "desc", "Difficult 2-way");
 238
 239     json_array_begin (json_ctx, "timings");
 240
 241     FOR_EACH_IMPL (impl, 0)
 242       do_one_test (json_ctx, impl, hs, ne, NULL);
 243
 244     json_array_end (json_ctx);
 245     json_element_object_end (json_ctx);
 246   }
 247
 248   /* Hard needle for standard algorithm testing first few characters of
 249    * needle.  */
 250   {
 251     for (int i = 0; i < hs_len; i++)
 252       hs[i] = (rand () & 255) >= 128 ? 'a' : 'b';
 253     hs[hs_len] = 0;
 254
 255     for (int i = 0; i < ne_len; i++)
 256       {
 257         if (i % 3 == 0)
 258           ne[i] = 'a';
 259         else if (i % 3 == 1)
 260           ne[i] = 'b';
 261         else
 262           ne[i] = 'c';
 263       }
 264     ne[ne_len] = 0;
 265
 266     json_element_object_begin (json_ctx);
 267     json_attr_uint (json_ctx, "len_haystack", hs_len);
 268     json_attr_uint (json_ctx, "len_needle", ne_len);
 269     json_attr_uint (json_ctx, "align_haystack", 0);
 270     json_attr_uint (json_ctx, "align_needle", 0);
 271     json_attr_uint (json_ctx, "fail", 1);
 272     json_attr_string (json_ctx, "desc", "Difficult testing first 2");
 273
 274     json_array_begin (json_ctx, "timings");
 275
 276     FOR_EACH_IMPL (impl, 0)
 277       do_one_test (json_ctx, impl, hs, ne, NULL);
 278
 279     json_array_end (json_ctx);
 280     json_element_object_end (json_ctx);
 281   }
 282 }
 283
 284 static int
 285 test_main (void)
 286 {
 287   json_ctx_t json_ctx;
 288   test_init ();
 289
 290   json_init (&json_ctx, 0, stdout);
 291
 292   json_document_begin (&json_ctx);
 293   json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
 294
 295   json_attr_object_begin (&json_ctx, "functions");
 296   json_attr_object_begin (&json_ctx, TEST_NAME);
 297   json_attr_string (&json_ctx, "bench-variant", "");
 298
 299   json_array_begin (&json_ctx, "ifuncs");
 300   FOR_EACH_IMPL (impl, 0)
 301     json_element_string (&json_ctx, impl->name);
 302   json_array_end (&json_ctx);
 303
 304   json_array_begin (&json_ctx, "results");
 305
 306   for (size_t hlen = 8; hlen <= 256;)
 307     for (size_t klen = 1; klen <= 16; klen++)
 308       {
 309         do_test (&json_ctx, 1, 3, hlen, klen, 0);
 310         do_test (&json_ctx, 0, 9, hlen, klen, 1);
 311
 312         do_test (&json_ctx, 1, 3, hlen + 1, klen, 0);
 313         do_test (&json_ctx, 0, 9, hlen + 1, klen, 1);
 314
 315         do_test (&json_ctx, getpagesize () - 15, 9, hlen, klen, 1);
 316         if (hlen < 64)
 317           {
 318             hlen += 8;
 319           }
 320         else
 321           {
 322             hlen += 32;
 323           }
 324       }
 325
 326   for (size_t hlen = 256; hlen <= 65536; hlen *= 2)
 327     for (size_t klen = 4; klen <= 256; klen *= 2)
 328       {
 329         do_test (&json_ctx, 1, 11, hlen, klen, 0);
 330         do_test (&json_ctx, 14, 5, hlen, klen, 1);
 331
 332     do_test (&json_ctx, 1, 11, hlen + 1, klen + 1, 0);
 333     do_test (&json_ctx, 14, 5, hlen + 1, klen + 1, 1);
 334
 335         do_test (&json_ctx, 1, 11, hlen + 1, klen, 0);
 336         do_test (&json_ctx, 14, 5, hlen + 1, klen, 1);
 337
 338         do_test (&json_ctx, getpagesize () - 15, 5, hlen + 1, klen, 1);
 339       }
 340
 341   test_hard_needle (&json_ctx, 64, 65536);
 342   test_hard_needle (&json_ctx, 256, 65536);
 343   test_hard_needle (&json_ctx, 1024, 65536);
 344
 345   json_array_end (&json_ctx);
 346   json_attr_object_end (&json_ctx);
 347   json_attr_object_end (&json_ctx);
 348   json_document_end (&json_ctx);
 349
 350   return ret;
 351 }
 352
 353 #include <support/test-driver.c>