This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v2] Improve performance of strstr


Hi Szabolcs,

I wrote a simple testcase (below) that shows the worst cases for both
algorithms. On Cortex-A72 the results are (relative runtime):

                             glibc 2.27  2.28  musl   new
bad needle 1 (hs 1048575, ne 255): 77.5  46.9  50.5   1.0
bad needle 2 (hs 1048575, ne 255):  1.0  17.9  19.7  59.0 

So it shows the same input has huge performance variations between
different implementations, even of the same algorithm.

When comparing the performance of slow cases between the algorithms,
the worst case of the new algorithm is 28% faster than GLIBC 2.27, 29%
slower than GLIBC 2.28 or 20% slower than the Musl version.

Wilco


#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

char hs[MAX_HS_LEN+1];
char ne[MAX_NE_LEN+1];

char *volatile res;

static void
run (size_t hs_len, size_t ne_len, char *name)
{
  clock_t t = clock ();
  for (int i = 0; i < N; i++)
    res = strstr (hs, ne);
  t = clock () - t;
  printf ("%s (hs %d, ne %d): %ld\n", name, hs_len-1, ne_len-1, t);
}

static void
bad_needle_1 (size_t hs_len, size_t ne_len)
{
  for (int i = 0; i < hs_len; i++)
    hs[i] = (rand () & 255) > 155 ? 'a' : 'b';
  hs[hs_len] = 0;

  memset (ne, 'a', ne_len);
  ne[ne_len-2] = 'b';
  ne[0] = 'b';
  ne[ne_len] = 0;

  run (hs_len, ne_len, "bad needle 1");
}

static void
bad_needle_2 (size_t hs_len, size_t ne_len)
{
  memset (ne, 'a', ne_len);
  ne[ne_len] = '\0';
  ne[ne_len - 6] = 'b';

  memset (hs, 'a', hs_len);
  for (size_t i = ne_len; i < hs_len; i += ne_len)
    {
       hs[i-5] = 'b';
       hs[i-6] = 'b';
    }
  hs[hs_len] = 0;

  run (hs_len, ne_len, "bad needle 2");
}

int main (void)
{
  bad_needle_1 (MAX_HS_LEN, 256);
  bad_needle_2 (MAX_HS_LEN, 256);

  return 0;
}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]