Re: [PATCH]: Optimization for strpbrk on PowerPC

[OndÅej BÃlka <neleai at seznam dot cz>]

On Thu, Feb 27, 2014 at 11:29:34PM +0530, R Vidya wrote:
> 

> >From 2784371b29cf426603438fb5cac2b2a1f41940bd Mon Sep 17 00:00:00 2001
> From: Vidya Ranganathan <vidya@linux.vnet.ibm.com>
> Date: Thu, 27 Feb 2014 09:34:10 -0500
> Subject: [PATCH] Optimization for strpbrk() on ppc64 and ppc64le. I have
>  attached the benchtest output to show the performance improvement.
> 
> The optimization is achieved by following techniques:
> 1.aligned memory access
> 2.loop unrolling P7 gain
> 3.CPU pre-fetch to avoid cache miss
> 
These optimizations migth not be enough, a generic x64 uses standard
trick of creating array from needle and then do lookup per charecter
which should be faster when needle is say abcd...xyz. A bit optimized c
implementation of that is below, I will send patch with that.

A main problem of optimizing strbrk is that you often spend more time in
preprocessing than in actual matches. For small constant needles a separate
implementation gets called.

I have in my todo list to cache preprocessed needle information, it
would allow match needles that consist from up to three character ranges
quite quickly but is not feasible now due of long startup time.

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#undef strpbrk

char *
strpbrk (const char *_s, const char *n)
{
  unsigned char *s = (unsigned char *) _s;
  size_t i;
  unsigned char chars[256];
  memset (chars, 0, 256);
  for (i = 0; n[i]; i++)
    chars[(unsigned char) n[i]] = 1;
  chars[0] = 1;
  i = 0;
  while (1)
    {
      if (chars[s[i++]] == 1)
	return s[i - 1] ? s + i - 1 : NULL;

      if (chars[s[i++]] == 1)
	return s[i - 1] ? s + i - 1 : NULL;

      if (chars[s[i++]] == 1)
	return s[i - 1] ? s + i - 1 : NULL;

      if (chars[s[i++]] == 1)
	return s[i - 1] ? s + i - 1 : NULL;
    }
}