[PATCH] Optimize strstr, strcasestr and memmem

[Ondřej Bílka]

On Fri, May 18, 2012 at 02:25:47PM +1200, Maxim Kuvyrkov wrote:
> On 18/05/2012, at 10:20 AM, Joseph S. Myers wrote:
> 
> > Anyone interested in performance of these functions may also be interested 
> > in bug 12100, where the SSE4 version of strstr reintroduces the unwanted 
> > quadratic asymptotic performance.  (This is not a comment on your patch 
> > itself, but a mention of something people looking at this area might also 
> > be interested in.)
> 
> Thanks for the pointer.  For avoidance of doubt, I've benchmarked the patch on a Core2 machine without SSE4.
> 
> I will benchmark the SSE4 implementation against the normal + this patch on short needles.  The benchmark that motivated this patch is libosip message parsing, which heavily uses string functions with small strings.
> 

I posted strstr implementation at this list and got no response. 

I use only SSE2 instructions and my algorithm is faster than using SSE4 instructions.
With trivial modifications I could also use plain arithmetic/AVX2

A trick is to check first two characters or zero terminator in parallel.
This is about 25 times faster on core2 vs glibc one, on i7 its only 3
times faster.

I use these trick for my extension of regular expression engine a
partialy autogenerated strstr follows.


> --
> Maxim Kuvyrkov
> CodeSourcery / Mentor Graphics

-- 

transient bus protocol violation

-------------- next part --------------
#ifdef ARITHMETIC
#include "arithmetic.h"
#else
#include "sse2.h"
#endif
char * strstr2(char *s){ 
  c1=n: c1=n+1;
  int i; char *p; MBTYPE e0;MBTYPE e1;MBTYPE e2;MBTYPE e3;MBTYPE e4;MBTYPE e5;MBTYPE e6;MBTYPE e7;
  MBTYPE m0=make_mask(*c1,0);MBTYPE m1=make_mask(*c2,1);MBTYPE m2=make_mask(0,0);
  int time=0;
  int offset=((long)(s))%BYTES_AT_ONCE;
  s-=offset;
  MBTYPE s2=LOAD(s);
  e0=test_eq(s2, m0);
  e1=test_eq(shift_down(s2,1), m1);

  e3=AND(e0,e1);
  e4=test_eq(s2, m2);

  e6=e4;
  e7=OR(e3,e6);
  MASKTYPE mask=get_mask(e7);
  mask=forget_bits(mask,offset);
  while (1){
    if(mask){
      for(i=0;i<BYTES_AT_ONCE;i++) if (GET_BIT(mask,i)){
        if (GET_BIT(get_mask(e3),i)){p=s+i+2; 
          int j;
          for (j=0;n[j+2] && p[j]==n[j+2];j++);
          if (!n[j+2]) return p-2;
          time+=j;
          if (time>16*(s2-s)) return strstr(p-2,n);
        }
        if (GET_BIT(get_mask(e6),i)){p=s+i+1; return NULL;}

      }
    }
    s+=BYTES_AT_ONCE;
    s2=LOAD(s);
    e0=test_eq(s2, m0);
    e1=test_eq(shift_down(s2,1), m1);

    e3=AND(e0,e1);
    e4=test_eq(s2, m2);

    e6=e4;
    e7=OR(e3,e6);
    mask=get_mask(e7);
  }
}
-------------- next part --------------
#include <stdint.h>
#include <emmintrin.h>
#define BYTES_AT_ONCE 16
#define MBTYPE __m128i

#define MASKTYPE int
inline MASKTYPE forget_bits(MASKTYPE m,int b){return (m >>(b))<<(b);}




const uint64_t ones=0x0101010101010101;
MBTYPE make_mask(unsigned char c,int shift){
  return _mm_set_epi64x(ones*((uint64_t)c),(ones >> (8*shift))*((uint64_t)c));
}
#define LOAD(x) _mm_load_si128(( long long int * )x)
#define test_eq  _mm_cmpeq_epi8
#define AND  _mm_and_si128
#define OR   _mm_or_si128
#define shift_down _mm_srli_si128
#define shift_up   _mm_slli_si128
inline int  get_mask(MBTYPE x){ return  _mm_movemask_epi8(x); }
#define GET_BIT(x,y) (x&(1<<(y)))