Open Radar

 
06-May-2012 01:56 PM Nico Weber:
Summary: libSystem's memchr() is slow (2x slower than naive loop, 5x slower than glibc's)

Steps to Reproduce:

Use a program that uses memchr().

Expected Results:

Program doesn't have memchr() as a bottleneck.

Actual Results:

memchr() shows up as a bottleneck in Instruments.

The attached program reproduces this. See https://gist.github.com/2624336 for a version of the program that also includes the glibc functions for comparison (if you can look at lgpl'd code).

The output of the attached program on my system:

stupid_memchr: 385.0us
memchr: 566.0us

stupid_strchr: 383.0us
strchr: 386.0us

Note that libSystem's memchr is significantly slower than "stupid_memchr", a naive implementation that looks like this:

void* stupid_memchr(const void* s_in, int c, size_t n) {
  const unsigned char* s = (const unsigned char*)s_in;
  for (int i = 0; i < n; ++i)
    if (s[i] == c)
      return (void*)(s + i);
  return NULL;
}


The output of the program that also times the (portable, non-asm-optimized) glibc version of these functions:

stupid_memchr: 376.0us
glibc_memchr: 107.0us
memchr: 575.0us

stupid_strchr: 378.0us
glibc_strchr: 140.0us
strchr: 381.0us

Regression: No

Notes:

06-May-2012 01:56 PM Nico Weber:
'chr_bench.cc' was successfully uploaded

06-May-2012 02:08 PM Nico Weber:
And libSystem's fgets() seems to call memchr(), which means that function is a lot slower than necessary too.

06-May-2012 10:28 PM Nico Weber:
Turns out that clang is bad at compiling memchr() as implemented in libSystem: http://llvm.org/PR12750 (but memchr() should do something smarter than a naive loop either way, see the perf difference to glibc's memchr).