[PATCH v4] generic string skeleton.

[PATCH v4] generic string skeleton.

[Ondřej Bílka]

Hi, this is next iteration of string skeleton.

I moved these to generic with brief description of primitives. Adding
hardware instructions for fast zero/equality check should be easy.

However what wouldn't is bytewise minimum. Its one of main advantages of
x64 string handling as it offers considerable speedup but we would need
different skeletons.

What also needs to be solved on per-arch basis is how fast is clz/ctz
for determining last byte. I don't know so testing alternatives is
needed.

Also I have idea that one could first do byteswap on big endian
architecture to be able use little-endian tricks. How good is byteswap
and would it work?

Then I also encoded to skeleton some tricks from x64 which also needs to
be checked. There are several tunable variables that need to be
adjusted. My plan is to do that automatically and use dryrun profile
trace to find optimal setting without much effort.

That results on more macroized skeleton, which is needed to specify
unrolling and other options.

Next is that I added support for multibyte patterns. That will improve 
strstr, strcasestr and memmem. These could be also adapted for generic
strcpy.

Comments?

diff --git a/sysdeps/generic/string_vector.h b/sysdeps/generic/string_vector.h
new file mode 100644
index 0000000..5a835e1
--- /dev/null
+++ b/sysdeps/generic/string_vector.h
@@ -0,0 +1,211 @@
+/* Vectorized arithmetic used in string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdint.h>
+
+/* This is intended for optimized string functions by using vectorization.
+
+   Main idea is simple. Most string functions can be described as searching
+   for first byte that satisfies certain expression followed by
+   simple output conversion. For example in strlen we look for first byte x
+   where x == 0 followed by subtracting pointer from start to get length.
+
+   When you have expression you use skeleton to execute it in parallel for
+   eigth bytes at once which will give you considerable speedup.
+
+   You need to make expression from primitives that allow vectorization.
+
+   Bitwise arithmetic (&,|,^,~) is allowed. For most tricks you also need
+   to do addition and subtraction where you must be more careful.
+   If you could ensure that your expression don't overflows then you can
+   use it as well. However expressions that could overflow are considerably
+   faster and you can use them when you are bit careful. When you only want
+   to find first byte where expression is true then you most of time
+   don't care that on success it could corrupt following bytes. However you
+   can't overflow on failure. You need to supply two versions of expression,
+   EXPRESSION macro that can overflow on success and EXPRESSION_NOCARRY that
+   can't.
+
+   Use vector arithmetic tricks. Idea is to take expression works on
+   unsigned byte and evaluates 0 for nozero byte and nonzero on zero byte.
+   Our expression is ((s - 1) & (~s)) & 128
+   Now we evaluate this expression on each byte in parallel and on first
+   nonzero byte our expression will have nonzero value.
+
+   We need to provide version of expression that doesn't cause carry
+   propagation and opperations could be done in parallel. However its
+   not needed on little endian architectures as we end on first byte
+   that succeeds and we don't care that next ones could be corrupted.
+
+   Then you could use premade predicates. There are contains_zero(x) that
+   returns 128 when x is zero, 0 otherwise and bytes_equal(x, y) that
+   returns 128 when x == y, zero otherwise, these come with variants that
+   don't cause overflow.
+
+   For performance architecture with hardware support should redefine
+   primitives. Most often one wants to supply its own first_nonzero_byte
+   and define CUSTOM_FIRST_NONZERO_BYTE to avoid defining default one.
+
+   Others are contains_zero and bytes_equal that need to be redefined
+   along with their nocarry counterparts.
+
+   Having hardware fast bytewise minimum is game changer as it allows
+   considerable speedup. However it would need to create separate skeletons
+   as main benefit is in faster aggregation.
+
+   After that there comes tuning as there are several variables that
+   affect performance like number of times unrolled. These could be
+   automated by running with different options versus dryrun profile
+   trace and selecting best one.
+ */
+
+#ifndef VECTOR_INT
+# define VECTOR_INT unsigned long int
+#endif
+
+#if _STRING_ARCH_unaligned
+# define UNALIGNED_HEADER_UNROLL 4
+#else
+# define UNALIGNED_HEADER_UNROLL 0
+#endif
+#define ALIGNED_HEADER_UNROLL 4
+#define LOOP_UNROLL 4
+
+typedef VECTOR_INT vector_int;
+
+static const vector_int ones = (~0UL / 255); /* 0x0101...*/
+static const vector_int add = 127 * (~0UL / 255);
+static const vector_int high_bits = 128 * (~0UL / 255);
+
+
+#define LSIZE sizeof (vector_int)
+#ifdef PAGE_SIZE
+# define CROSS_PAGE(x, n) (((uintptr_t) x) % PAGE_SIZE > PAGE_SIZE - n)
+#else
+# define CROSS_PAGE(x, n) (((uintptr_t) x) % 4096 > 4096 - n)
+#endif
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+# define SHIFT_BYTES(x, n) ((x) << (8 * (n)))
+# define SHIFT_BYTES_UP(x, n) ((x) >> (8 * (n)))
+#else
+# define SHIFT_BYTES(x, n) ((x) >> (8 * (n)))
+# define SHIFT_BYTES_UP(x, n) ((x) << (8 * (n)))
+#endif
+
+/* Sets n first bytes to zero.  */
+#define FORGET_BYTES(x, n) SHIFT_BYTES_UP (SHIFT_BYTES (x, n), n)
+
+
+/* Load vector. Needs to be macro for cast.
+   While for LOAD(x) needs to be aligned for LOADU it dont have to.
+   Unaligned loads are emulated on platforms that dont support it.  */
+
+#define LOAD(x) (*((vector_int *) (x)))
+#if _STRING_ARCH_unaligned == 0
+/* Here we could combine shifts if architecture sets x << 64 to zero.  */
+
+# define LOADU(x) ({ \
+		     char *aligned = PTR_ALIGN_DOWN ((char *) (x), LSIZE);                  \
+		     unsigned int align = ((char *) (x)) - aligned;                         \
+		     (SHIFT_BYTES (SHIFT_BYTES (LOAD (aligned), LSIZE - 1 - align), 1)      \
+		      | SHIFT_BYTES_UP (LOAD (aligned + LSIZE), align));                    \
+		   })
+
+#else
+# define LOADU(x) LOAD (x)
+#endif
+
+
+#ifndef CUSTOM_CONTAINS_ZERO
+# if __BYTE_ORDER == __LITTLE_ENDIAN
+/* A possible question is how fast is byteswap on big endian
+   architectures. If it can be done withing cycle it migth be
+   profitable to emulate little endian there by overriding LOAD and LOADU.  */
+
+static __always_inline
+vector_int
+contains_zero (vector_int s)
+{
+  return (s - ones) & ~s & high_bits;
+}
+# else
+#  define contains_zero contains_zero_nocarry
+# endif
+
+static __always_inline
+vector_int
+contains_zero_nocarry (vector_int s)
+{
+  return (((s | high_bits) - ones) ^ high_bits) & ~s & high_bits;
+}
+#endif
+
+#ifndef CUSTOM_BYTES_EQUAL
+static __always_inline
+vector_int
+bytes_equal (vector_int x, vector_int y)
+{
+  return contains_zero (x ^ y);
+}
+
+static __always_inline
+vector_int
+bytes_equal_nocarry (vector_int x, vector_int y)
+{
+  return contains_zero_nocarry (x ^ y);
+}
+#endif
+
+/*
+  When you have hardware ctz/clz its probably best bet. However
+  for softare emulation you could get better than generic one as you
+  dont need to consider each bit, just highest bits in byte which can be
+  calculated more effectively.
+ */
+#ifndef CUSTOM_FIRST_NONZERO_BYTE
+static __always_inline
+size_t
+first_nonzero_byte (vector_int u)
+{
+# if __BYTE_ORDER == __BIG_ENDIAN
+#  ifdef NEED_BITWISE
+  u = u | (u >> 1);
+  u = u | (u >> 2);
+  u = u | (u >> 4);
+#  else
+  u = u >> 7;
+#  endif
+  u = u | (u >> 8);
+  u = u | (u >> 16);
+  u = u | (u >> 32);
+#  ifdef NEED_BITWISE
+  u = u & ones;
+#  endif
+  u = u * ones;
+  return 8 - (u >> (8 * LSIZE - 8));
+
+# else
+  /* Note that this works also in bitwise case.  */
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+# endif
+}
+#endif
diff --git a/sysdeps/generic/string_vector_skeleton.h b/sysdeps/generic/string_vector_skeleton.h
new file mode 100644
index 0000000..5f9bfeb
--- /dev/null
+++ b/sysdeps/generic/string_vector_skeleton.h
@@ -0,0 +1,239 @@
+/* Skeleton of generic string functions.
+   Copyright (C) 1991-2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <assert.h>
+#include <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+/* On high endian an positive could cause false positive in previous byte.  */
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+# undef EXPRESSION
+# define EXPRESSION(x, y) EXPRESSION_NOCARRY (x, y)
+#endif
+
+#ifdef CUSTOM_CMASK
+# define CMASK_PARAM_MASK CMASK_PARAM
+#else
+# define CMASK_PARAM int c_in
+# define CMASK_PARAM_MASK vector_int cmask
+#endif
+
+#ifdef LOOKAHEAD
+# define BYTE(n) \
+  (SHIFT_BYTES (SHIFT_BYTES (previous, LSIZE - (LOOKAHEAD - n) - 1), 1)  \
+   | SHIFT_BYTES_UP (v, LOOKAHEAD - n))
+#endif
+
+#ifdef LOOKAHEAD
+# define SHIFT_LOOKAHEAD(x) FORGET_BYTES (x, LOOKAHEAD)
+# define ADJUST LOOKAHEAD
+#else
+# define SHIFT_LOOKAHEAD(x) x
+# define ADJUST 0
+#endif
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, CMASK_PARAM, char *end)
+{
+  vector_int mask;
+  char *s = (char *) s_in;
+  vector_int v = 0;
+  vector_int __attribute__ ((unused)) previous = 0;
+#ifndef CUSTOM_CMASK
+  unsigned char c = (unsigned char) c_in;
+  vector_int __attribute__ ((unused)) cmask = c * ones;
+#endif
+
+  /* We fetch 32 bytes while not crossing page boundary.
+     Most strings in practice are of that size and we avoid a loop.
+     This looks as best in practice, alternative below uses aligned load
+     but is slower when string starts just few
+     bytes before 32 byte boundary. A tradeoff is that we rarely could
+     fetch extra cache line without needing it but this optimization
+     does pay for that. */
+
+  if (!CROSS_PAGE (s, 32) && UNALIGNED_HEADER_UNROLL > 0)
+    {
+#define UNALIGNED_HEADER_CHECK(i) \
+  if (UNALIGNED_HEADER_UNROLL >= i)                                      \
+    {                                                                    \
+      previous = v;                                                      \
+      v = LOADU (s + (i - 1) * LSIZE);                                   \
+      mask = EXPRESSION (v, cmask);                                      \
+      if (i == 1)                                                        \
+	mask = SHIFT_LOOKAHEAD (mask);                                   \
+      if (mask)                                                          \
+	return s + (i - 1) * LSIZE + first_nonzero_byte (mask) - ADJUST; \
+    }
+
+      UNALIGNED_HEADER_CHECK (1);
+      UNALIGNED_HEADER_CHECK (2);
+      UNALIGNED_HEADER_CHECK (3);
+      UNALIGNED_HEADER_CHECK (4);
+      UNALIGNED_HEADER_CHECK (5);
+      UNALIGNED_HEADER_CHECK (6);
+      UNALIGNED_HEADER_CHECK (7);
+      UNALIGNED_HEADER_CHECK (8);
+
+      if (BOUND (s + LSIZE * UNALIGNED_HEADER_UNROLL))
+	return NULL;
+    }
+  else
+    {
+      /* We need use aligned loads. For first load we read some bytes before
+         start that we discard by shifting them down. */
+
+      char *s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      v = LOAD (s_aligned);
+      /* We need be careful here as bytes before start can corrupt it.  */
+      mask = SHIFT_BYTES ((EXPRESSION_NOCARRY (v, cmask)), s - s_aligned);
+      mask = SHIFT_LOOKAHEAD (mask);
+      if (mask)
+	return s + first_nonzero_byte (mask) - ADJUST;
+
+      /* When lookahead is i we need to ignore matches in first i bytes as
+         false positives. For lookahead 2 or more it could cross word
+         boundary and we need to mask these.  */
+
+#if defined (LOOKAHEAD) && LOOKAHEAD > 1
+# define FIX_LOOKAHEAD(i) \
+  if (i == 2 && s + LOOKAHEAD > s_aligned + LSIZE)                     \
+    mask = FORGET_BYTES (mask, s + LOOKAHEAD - (s_aligned + LSIZE));
+#else
+# define FIX_LOOKAHEAD(i)
+#endif
+
+      /* We need to check for crossing end of string after each iteration
+         as each one could cross page boundary. Note that we don't have
+         to make check after last iteration as it would duplicate check in
+         loop.  */
+
+#define ALIGNED_HEADER_CHECK(i) \
+  if (ALIGNED_HEADER_UNROLL >= i)                                       \
+    {                                                                   \
+      if (BOUND (s_aligned + (i - 1) + LSIZE))                          \
+	return NULL;                                                     \
+      previous = v;                                                     \
+      v = LOAD (s_aligned + (i - 1) * LSIZE);                           \
+      mask = EXPRESSION (v, cmask);                                     \
+      FIX_LOOKAHEAD (i);                                                \
+      if (mask)                                                         \
+	return s_aligned + (i - 1) * LSIZE + first_nonzero_byte (mask)  \
+	       - ADJUST;                                                \
+    }
+      ALIGNED_HEADER_CHECK (2);
+      ALIGNED_HEADER_CHECK (3);
+      ALIGNED_HEADER_CHECK (4);
+      ALIGNED_HEADER_CHECK (5);
+      ALIGNED_HEADER_CHECK (6);
+      ALIGNED_HEADER_CHECK (7);
+      ALIGNED_HEADER_CHECK (8);
+    }
+
+  /* Now we read enough bytes to start a loop, assuming following:  */
+
+  assert (UNALIGNED_HEADER_UNROLL <= 8);
+  assert (ALIGNED_HEADER_UNROLL <= 8);
+
+  assert (LOOP_UNROLL <= ALIGNED_HEADER_UNROLL);
+  assert (LOOP_UNROLL <= UNALIGNED_HEADER_UNROLL
+	  || UNALIGNED_HEADER_UNROLL == 0);
+
+  char *s_loop = PTR_ALIGN_DOWN (s, LOOP_UNROLL * LSIZE);
+
+#ifdef LOOKAHEAD
+  v = LOAD (s_loop + (LOOP_UNROLL - 1) * LSIZE);
+#endif
+
+  while (!BOUND (s_loop + LOOP_UNROLL * LSIZE))
+    {
+      s_loop += LOOP_UNROLL * LSIZE;
+      vector_int masks[9];
+      masks[0] = 0;
+
+#define MERGE_MASK(i) \
+  if (LOOP_UNROLL >= i)                                                 \
+    {                                                                   \
+      previous = v;                                                     \
+      v = LOAD (s_loop + (i - 1) * LSIZE);                              \
+      masks[i] = masks[i - 1] | EXPRESSION (v, cmask);                  \
+    }
+
+      MERGE_MASK (1);
+      MERGE_MASK (2);
+      MERGE_MASK (3);
+      MERGE_MASK (4);
+      MERGE_MASK (5);
+      MERGE_MASK (6);
+      MERGE_MASK (7);
+      MERGE_MASK (8);
+
+      if (masks[LOOP_UNROLL])
+	{
+
+          /* Here we have two possibilities depending on register pressure.
+             When you don't have enough registers this recalculating of
+             results would create fastest loop for large inputs. However
+             its likely affected by gcc bug where gcc will try to save
+             intermediate results causing spill in each iteration to speed
+             up final iteration a bit. To avoid that we need compiler barrier
+             here.  */
+
+#ifdef RECALCULATE_ON_TAIL
+          asm volatile ("" : : : "memory");
+# define CHECK_MASK(i) \
+      previous = v;                                                     \
+      v = LOAD (s_aligned + (i - 1) * LSIZE);                           \
+      mask = EXPRESSION (v, cmask);                                     \
+      if (mask)                                                         \
+	return s_aligned + (i - 1) * LSIZE + first_nonzero_byte (mask)  \
+	       - ADJUST;                                            
+
+# else
+          /* On other hand when you have enough free registers then you can
+             save intermediate ors. When you checks masks then as you know
+             that to reach each one previous ones must be zero you know that
+             or of previous masks will be exactly current one.  */
+
+# define CHECK_MASK(i) \
+  if (masks[i])                                                              \
+    return s_loop + (i - 1) * LSIZE + first_nonzero_byte (masks[i]) - ADJUST;
+# endif
+
+#ifdef LOOKAHEAD
+	  v = LOAD (s_loop - LSIZE);
+#endif
+	  CHECK_MASK (1);
+	  CHECK_MASK (2);
+	  CHECK_MASK (3);
+	  CHECK_MASK (4);
+	  CHECK_MASK (5);
+	  CHECK_MASK (6);
+	  CHECK_MASK (7);
+	  CHECK_MASK (8);
+	}
+    }
+  return NULL;
+}

[PATCH 2/*] generic strstr, strcasestr, memmem

[Ondřej Bílka]

I added a new version of string skeleton also for improving strstr hot
path.

This uses same trick as x64, which is looking for leading digraphs,
switching to two-way algorithm when you reach superlinear number of
comparisons.

This superseedes my previous strstr... patches which were written
without fast way of finding digraphs.

I didn't tuned buy-or-rent cost of switchings yet, that could be upto
discussion.

Also previous strcasestr ascii trick is included.

I didn't tuned a strstr expressions yet. They could be simplified but
thats for separate patch, also I could add strstr with ascii trick.

Other speedup would be that I could add a iterator interface. It would
speed up patterns like

while (s = strchr(s + 1, 'c')
  ...

that would become

  strchr_iterator i;
  strchr_start (s, c, &i);
  while (s = strchr_next(&i))
    {

    }

Implementation would be saving mask created by strchr, then strchr_next
inline would first look up for mask and would resort to call at most
once per 32 bytes when it needs to move for next mask.

Same trick would be used for faster iteration over digraphs and for
strstr itself. 

I wonder if it would be possible to make gcc recognize these patterns
and do transformation automatically. It would be similar analysis like
optimizing out quadratic strcat loop that I mentioned before.

	* benchtests/bench-strcasestr.c: Remove simple_strcasestr.
	* string/test-strcasestr.c: Likewise.
	* sysdeps/generic/string_vector_search.h: New file.
	* string/strstr.c (strstr): Use fast digraph search.
	* string/strcasestr.c (STRCASESTR): Likewise.
	* string/memmem.c (__memmem): Likewise.

diff --git a/benchtests/bench-strcasestr.c b/benchtests/bench-strcasestr.c
index 33531a4..6c6309f 100644
--- a/benchtests/bench-strcasestr.c
+++ b/benchtests/bench-strcasestr.c
@@ -21,10 +21,6 @@
 #include "bench-string.h"
 
 
-#define STRCASESTR simple_strcasestr
-#define NO_ALIAS
-#define __strncasecmp strncasecmp
-#include "../string/strcasestr.c"
 
 
 static char *
@@ -53,7 +49,6 @@ stupid_strcasestr (const char *s1, const char *s2)
 typedef char *(*proto_t) (const char *, const char *);
 
 IMPL (stupid_strcasestr, 0)
-IMPL (simple_strcasestr, 0)
 IMPL (strcasestr, 1)
 
 
diff --git a/string/memmem.c b/string/memmem.c
index 8a81f65..a13e16f 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -35,6 +35,45 @@
 
 #undef memmem
 
+#include <string_vector.h>
+
+struct cmask
+{
+  unsigned long int n0, n1;
+  size_t needle_size;
+};
+#define CUSTOM_CMASK
+#define CMASK_PARAM struct cmask cmask
+
+#define LOOKAHEAD 1
+#define EXPRESSION_NOCARRY(x, cmask) \
+ ( bytes_equal_nocarry (BYTE (0), cmask.n0) 				\
+   &  bytes_equal_nocarry (BYTE (1), cmask.n1))
+
+/* We calculate mask, not look for first byte and carry could corrupt
+   following bytes. Only possible optimization would be use
+   contains_zero (x) as it must end there. */
+#define EXPRESSION(x, cmask) EXPRESSION_NOCARRY(x, cmask)
+
+static int
+check (char *s, char *n, unsigned long *rent, struct cmask cmask)
+{
+  /* First two characters were already checked by vector loop.  */
+  size_t i = 2;
+
+  while (i < cmask.needle_size && s[i] == n[i])
+    i++;
+
+  if (i == cmask.needle_size)
+    return 1;
+
+  rent += i + 10;
+  return 0;
+}
+
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
+#include <string_vector_search.h>
+
 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
    if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
    HAYSTACK.  */
@@ -46,6 +85,7 @@ __memmem (const void *haystack_start, size_t haystack_len,
      not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
   const unsigned char *haystack = (const unsigned char *) haystack_start;
   const unsigned char *needle = (const unsigned char *) needle_start;
+  char *ret;
 
   if (needle_len == 0)
     /* The first occurrence of the empty string is deemed to occur at
@@ -57,6 +97,31 @@ __memmem (const void *haystack_start, size_t haystack_len,
   if (__glibc_unlikely (haystack_len < needle_len))
     return NULL;
 
+  unsigned char *n = (unsigned char *) needle;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN && needle_len >= 2)
+    {
+      struct cmask cmask;
+      cmask.n0 =  n[0] * ones;
+      cmask.n1 =  n[1] * ones;
+      cmask.needle_size = needle_len;
+      char *end_search = (char *) (((uintptr_t) haystack) + haystack_len
+                                                          - needle_len + 1);
+      if ((uintptr_t) end_search < (uintptr_t) haystack)
+        end_search = (char *) UINTPTR_MAX;
+      if (vector_search ((char *) haystack, (char *) needle,
+		         cmask, end_search, &ret))
+        return ((uintptr_t) ret < (uintptr_t) end_search) ? ret : NULL;
+      else
+        {
+	  haystack_len -= (char *) ret - (char *) haystack;
+          haystack = (const unsigned char *) ret;
+
+          if (ret == NULL || haystack_len < needle_len)
+            return NULL;
+        }
+    }
+
+
   /* Use optimizations in memchr when possible, to reduce the search
      size of haystack using a linear algorithm with a smaller
      coefficient.  However, avoid memchr for long needles, since we
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 400fab8..b512134 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -57,6 +57,61 @@
 #define STRCASESTR __strcasestr
 #endif
 
+/* A initial fast vectorized loop looking for first digraph.  */
+
+#include <string_vector.h>
+
+struct cmask
+{
+  vector_int l0, u0, l1, u1;
+};
+#define CUSTOM_CMASK
+#define CMASK_PARAM struct cmask cmask
+
+  /* We use trick that for when character is in ascii and character
+     0 <= c <= 127 could be caselessly equal only one of characters
+     tolower (c), toupper (c) or a character x in range 128 <= x <= 255
+     As these are exactly characters have highest bit set to 1 we adjust
+     a expression from strstr and filter lower bits by anding with high_bits.
+   */
+
+#define LOOKAHEAD 1
+#define BYTE_EXPRESSION(x, l, u) \
+  ( bytes_equal_nocarry (x, l) 				\
+  | bytes_equal_nocarry (x, u)				\
+  | x)
+
+#define EXPRESSION_NOCARRY(x, cmask) (( \
+ ( BYTE_EXPRESSION (BYTE(0), cmask.l0, cmask.u0)		  \
+ & BYTE_EXPRESSION (BYTE(1), cmask.l1, cmask.u1) 		  \
+ ) | contains_zero_nocarry (BYTE (1))) & high_bits)
+
+/* We calculate mask, not look for first byte and carry could corrupt
+   following bytes. Only possible optimization would be use
+   contains_zero (x) as it must end there. */
+#define EXPRESSION(x, cmask) EXPRESSION_NOCARRY (x, cmask)
+
+static int
+check (char *s, char *n, unsigned long *rent, struct cmask cmask)
+{
+  /* We used heuristic. Need to recheck.  */
+  size_t i = 0;
+  if (!s[1])
+    return 1;
+
+  while (n[i] && tolower (s[i]) == tolower (n[i]))
+    i++;
+
+  if (!n[i])
+    return 1;
+
+  rent += i + 10;
+  return 0;
+}
+
+#include <string_vector_search.h>
+
+#include "../locale/localeinfo.h"
 
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
@@ -66,10 +121,33 @@ STRCASESTR (const char *haystack_start, const char *needle_start)
 {
   const char *haystack = haystack_start;
   const char *needle = needle_start;
+  char *ret;
   size_t needle_len; /* Length of NEEDLE.  */
   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
   bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 
+  __locale_t loc = _NL_CURRENT_LOCALE;
+  struct __locale_data *ctype = loc->__locales[LC_CTYPE];
+  int nonascii = ctype->values[_NL_ITEM_INDEX (_NL_CTYPE_NONASCII_CASE)].word;
+
+  unsigned char *n = (unsigned char *) needle;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN && !nonascii && haystack[0] != '\0' &&
+      n[0] != '\0' && n[0] < 128 && n[1] != '\0' && n[1] < 128)
+    {
+      struct cmask cmask;
+      cmask.l0 = tolower (n[0]) * ones;
+      cmask.u0 = toupper (n[0]) * ones;
+      cmask.l1 = tolower (n[1]) * ones;
+      cmask.u1 = toupper (n[1]) * ones;
+
+      if (vector_search ((char *) haystack, (char *) needle, cmask,\
+			 NULL, &ret))
+        return (ret[1] != '\0') ? ret : NULL;
+      else
+        haystack = ret;
+    }
+
+
   /* Determine length of NEEDLE, and in the process, make sure
      HAYSTACK is at least as long (no point processing all of a long
      NEEDLE if HAYSTACK is too short).  */
diff --git a/string/strstr.c b/string/strstr.c
index 045e878..9429cc6 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -45,6 +45,48 @@
 #define STRSTR strstr
 #endif
 
+#include <string_vector.h>
+
+struct cmask
+{
+  vector_int n0, n1;
+};
+#define CUSTOM_CMASK
+#define CMASK_PARAM struct cmask cmask
+
+#define LOOKAHEAD 1
+#define EXPRESSION_NOCARRY(x, cmask) (\
+ ( bytes_equal_nocarry (BYTE (0), cmask.n0)				\
+   & bytes_equal_nocarry (BYTE (1), cmask.n1))				\
+ | contains_zero_nocarry (BYTE (1)))
+
+/* We calculate mask, not look for first byte and carry could corrupt
+   following bytes. Only possible optimization would be use
+   contains_zero (x) as it must end there. */
+#define EXPRESSION(x, cmask) EXPRESSION_NOCARRY(x, cmask)
+
+static int
+check (char *s, char *n, unsigned long *rent, struct cmask cmask)
+{
+  /* First two characters were already checked by vector loop.  */
+  size_t i = 2;
+  if (!s[1])
+    return 1;
+
+  while (n[i] && s[i] == n[i])
+    i++;
+
+  if (!n[i])
+    return 1;
+
+  rent += i + 10;
+  return 0;
+}
+
+#include <string_vector_search.h>
+
+
+
 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
    if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
    HAYSTACK.  */
@@ -53,10 +95,28 @@ STRSTR (const char *haystack_start, const char *needle_start)
 {
   const char *haystack = haystack_start;
   const char *needle = needle_start;
+  char *ret;
   size_t needle_len; /* Length of NEEDLE.  */
   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
   bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 
+  unsigned char *n = (unsigned char *) needle;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN
+      && haystack[0] != '\0' && n[0] != '\0' && n[1] != '\0')
+    {
+      struct cmask cmask;
+      cmask.n0 =  n[0] * ones;
+      cmask.n1 =  n[1] * ones;
+
+      if (vector_search ((char *) haystack, (char *) needle, cmask,\
+			 NULL, &ret))
+        return ret[1] != '\0' ? ret : NULL;
+      else
+        haystack = ret;
+    }
+
+
+
   /* Determine length of NEEDLE, and in the process, make sure
      HAYSTACK is at least as long (no point processing all of a long
      NEEDLE if HAYSTACK is too short).  */
diff --git a/string/test-strcasestr.c b/string/test-strcasestr.c
index 489dc84..3c01881 100644
--- a/string/test-strcasestr.c
+++ b/string/test-strcasestr.c
@@ -25,7 +25,6 @@
 #define STRCASESTR simple_strcasestr
 #define NO_ALIAS
 #define __strncasecmp strncasecmp
-#include "strcasestr.c"
 
 
 static char *
@@ -54,7 +53,6 @@ stupid_strcasestr (const char *s1, const char *s2)
 typedef char *(*proto_t) (const char *, const char *);
 
 IMPL (stupid_strcasestr, 0)
-IMPL (simple_strcasestr, 0)
 IMPL (strcasestr, 1)
 
 
diff --git a/sysdeps/generic/string_vector_search.h b/sysdeps/generic/string_vector_search.h
new file mode 100644
index 0000000..5ad714b
--- /dev/null
+++ b/sysdeps/generic/string_vector_search.h
@@ -0,0 +1,85 @@
+/* Algorithm to select a faster string search implementation.
+   Copyright (C) 2015 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+/*
+   For string search algorithms there are two ways how you could look
+   at performance.
+
+   From practical standpoint a naive algorithm is baseline.  Most theoretical
+   algorithms (BW, KMP, ...) are slower because they need to do expensive random   access.  This makes prohibitive constant cost per character while naive
+   algorithm is linear on random inputs as most of time you don't match string.
+   Also potential gains are nonexistent, user supplies needle so you could be
+   happy when its at least 8 characters long and most haystacks are less than 64   bytes large.
+
+   On other hand we need to ensure a linear worst-case of our algorithm.
+
+   We do that with bit of accounting. We count number of comparisons and when
+   it exceeds a size of haystack times some constant we switch to two-way
+   algorithm with guaranteed linear time.
+
+   Main performance boost is gained by vectorizing naive algorithm checks.
+   We will check in parallel if first digraph matches. That should be quite rare,  in english most frequent digraph is th with frequency around 1%.
+
+   Then after each digraph found we face decision if to keep looking for
+   digraphs or switch to two-way algorithm. These are covered as common
+   problem in online algorithm setting: buy-or-rent problem.
+   A precomputation in two-way algorithm with needle size n takes
+   around same time as 20 character comparisons so in worst case a two-way
+   algorithm would be twenty times slower than naive for haystacks of size n+1.
+   A solution would be pay higher rent rate until it accumulates to buy cost.
+   Then we would in worst case be twice slower than selecting optimal
+   implementation from start.
+
+   That would work except it needs strlen (needle) which is unnecessary
+   in practice. To show that haystack cannot match needle it suffices to know
+   that there is no leading triplet from needle in haystack. As unless there
+   was a planted needle in haystack and false positive is unlikely we likely
+   don't have to inspect more than three or four characters from needle. Also
+   correct accounting takes time so we approximate cost based on number of
+   comparisons and vector searchs.
+
+ */
+
+#include <string_vector_skeleton.h>
+
+static int
+vector_search (char *haystack, char *needle, CMASK_PARAM,
+	       char *end, char **ret)
+{
+  char *s = haystack;
+  unsigned long rent = 0;
+  while (rent < 256 + (s - haystack))
+    {
+      s = string_skeleton (s, cmask, end);
+      if (s == NULL || BOUND (s))
+	{
+	  *ret = s;
+	  return 0;
+	}
+      if (check (s, needle, &rent, cmask))
+	{
+	  *ret = s;
+	  return 1;
+	}
+      else
+	s++;
+    }
+  /* Superlinear behaviour detected, switch to two-way algorithm.  */
+  *ret = s;
+  return 0;
+}

Re: [PATCH v4] generic string skeleton.

[Joseph Myers]

[-- Attachment #1: Type: text/plain, Size: 1625 bytes --]

On Fri, 29 May 2015, Ondøej Bílka wrote:

> +#ifndef VECTOR_INT
> +# define VECTOR_INT unsigned long int
> +#endif

I think a separate header for this would be better to avoid the #ifndef 
pattern.  I also wonder if actually this information about register size 
(which is effectively what this is) really ought to go in bits/wordsize.h 
in some way, with other headers then working from that.  Because it's not 
just this code that can use such information - gmp-mparam.h can (it ought 
to be possible to eliminate machine-specific versions of gmp-mparam.h) as 
can sfp-machine.h (quite a bit of the sfp-machine.h files is actually 
generic).  But since bits/wordsize.h is installed, there's a case for this 
going in a non-installed header, where the default version just uses 
bits/wordsize.h.

> +static const vector_int ones = (~0UL / 255); /* 0x0101...*/
> +static const vector_int add = 127 * (~0UL / 255);
> +static const vector_int high_bits = 128 * (~0UL / 255);

These need to use ((vector_int) -1) or similar instead of ~0UL, for when 
the type is wider than int.

> +#define LSIZE sizeof (vector_int)
> +#ifdef PAGE_SIZE
> +# define CROSS_PAGE(x, n) (((uintptr_t) x) % PAGE_SIZE > PAGE_SIZE - n)

If PAGE_SIZE might sometimes be nonconstant (see sysdeps/mach/pagecopy.h), 
I'd tend to think a separate macro (for the minimum size of a page, always 
constant) would be better here.

> +#ifndef BOUND
> +# define BOUND(x) 0
> +#endif

I've no idea what the semantics of this macro are.  It definitely needs a 
comment.  Similarly for subsequent macros in this header.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH v4] generic string skeleton.

[Ondřej Bílka]

On Fri, May 29, 2015 at 08:36:23PM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > +#ifndef VECTOR_INT
> > +# define VECTOR_INT unsigned long int
> > +#endif
> 
> I think a separate header for this would be better to avoid the #ifndef 
> pattern.  I also wonder if actually this information about register size 
> (which is effectively what this is) really ought to go in bits/wordsize.h 
> in some way, with other headers then working from that.  Because it's not 
> just this code that can use such information - gmp-mparam.h can (it ought 
> to be possible to eliminate machine-specific versions of gmp-mparam.h) as 
> can sfp-machine.h (quite a bit of the sfp-machine.h files is actually 
> generic).  But since bits/wordsize.h is installed, there's a case for this 
> going in a non-installed header, where the default version just uses 
> bits/wordsize.h.
>
Possible but I don't know how to do that yet. A problem I try avoid are
interdependencies. Without making that optional with ifdef to make it
optional you would need include other file. It could result on having
five phases of this header and you need to add redefinition between
correct headers to work. 
 
> > +static const vector_int ones = (~0UL / 255); /* 0x0101...*/
> > +static const vector_int add = 127 * (~0UL / 255);
> > +static const vector_int high_bits = 128 * (~0UL / 255);
> 
> These need to use ((vector_int) -1) or similar instead of ~0UL, for when 
> the type is wider than int.
> 
will do.
> > +#define LSIZE sizeof (vector_int)
> > +#ifdef PAGE_SIZE
> > +# define CROSS_PAGE(x, n) (((uintptr_t) x) % PAGE_SIZE > PAGE_SIZE - n)
> 
> If PAGE_SIZE might sometimes be nonconstant (see sysdeps/mach/pagecopy.h), 
> I'd tend to think a separate macro (for the minimum size of a page, always 
> constant) would be better here.
> 
Will add MIN_PAGE_SIZE in next version.
> > +#ifndef BOUND
> > +# define BOUND(x) 0
> > +#endif
> 
> I've no idea what the semantics of this macro are.  It definitely needs a 
> comment.  Similarly for subsequent macros in this header.
> 
These are for strn* functions to check a if we read past input. My
original implementation of these checks in memchr was overkill so I will
simplify these checks.