[PATCH 2/*] Optimize generic strchrnul and strchr

[PATCH 2/*] Optimize generic strchrnul and strchr

[Ondřej Bílka]

This is my generic strchr algorithm resubmitted to use skeleton.

Idea to split into cases c<128 and c>128 didn't change.

So comments? How this perform on different architectures?

	* string/strchr.c: Use skeleton.
	* string/strchrnul.c: Likewise.


diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..566ebab 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,162 +16,17 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
 
-/* Find the first occurrence of C in S.  */
+#define AS_STRCHR
+#define STRCHRNUL static_strchrnul
+#include "string/strchrnul.c"
+
 char *
-strchr (const char *s, int c_in)
+strchr (const char *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  char *r = STRCHRNUL (s, c);
+  return (*r == c) ? r : NULL;
 }
 
 #ifdef weak_alias
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..11c3bf6 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,63 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
+
+#include "string/common.h"
+#define EXPRESSION(s, cmask) (((((s & add) + add) & (((s & add) ^ cmask) + add)) | s) ^ high_bits) & high_bits
+
+#include "string/skeleton.h"
 
 #ifndef STRCHRNUL
 # define STRCHRNUL __strchrnul
 #endif
 
-/* Find the first occurrence of C in S or the final NUL byte.  */
+#ifdef AS_STRCHR
+static __always_inline
+#endif
 char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
+STRCHRNUL (const char *s_in, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (contains_zero(*lptr) | contains_zero (*lptr ^ cmask))
+             >> (8 * (s_aligned - s));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

[PATCH 1/*] Generic string function optimization: Add skeleton

[Ondřej Bílka]

Hi,

As i mentioned improving generic string functions this is my second
attempt. As lot of functions will be optimized in same way this uses
generic code flow. Functions will vary just by expression to check and
how interpret return value.

Performance gains of using this are from loop unrolling and better
header that doesn't have to check start byte-by-byte.

Unrolling migth be excessive but its better to tune it in skeleton than
try manually and risk introducing errors.

This implementation would probably be faster than assembly on other
architectures as this will beat it unless you used hardware specific
instruction or gcc messes up compilation and generates suboptimal code.

Comments?

	* string/common.h: New file.
	* string/skeleton.h: Likewise.

---
 string/common.h   |  35 +++++++++++++
 string/skeleton.h | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 180 insertions(+)
 create mode 100644 string/common.h
 create mode 100644 string/skeleton.h

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..09f950f
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,35 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* 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 & 127) + 127) ^ 128) & 128 & ~s
+   Now we evaluate this expression on each byte in parallel and on first 
+   nonzero byte our expression will have nonzero value. */
+
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (((s & add) + add) ^ high_bits) & high_bits & ~s;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t)x) % 4096 >= 4096 - n)
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#ifdef FAST_FFS
+  return ffsl (u) / 8 - 1;
+#else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..42bab9a
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,145 @@
+/* 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 <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* 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))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* 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);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (EXPRESSION (*lptr, cmask)) >> (8 * (s_aligned - s));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 4 * LSIZE))
+        return NULL;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}
-- 

[PATCH 1/* v2] Generic string function optimization: Add skeleton

[Ondřej Bílka]

After testing I found that I added typo in conversion to skeleton. This
fixes it. Here is correct version.

	* string/common.h: New file.
	* string/skeleton.h: Likewise.

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..3b239dd
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,35 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* 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 + 127) & (~s)) & 128  
+   Now we evaluate this expression on each byte in parallel and on first 
+   nonzero byte our expression will have nonzero value. */
+
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (((s & add) + add) ^ high_bits) & high_bits & ~s;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t)x) % 4096 > 4096 - n)
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#ifdef FAST_FFS
+  return ffsl (u) / 8 - 1;
+#else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..563e6e4
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,145 @@
+/* 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 <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* 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))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 5 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 6 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 7 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 8 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* 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);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (EXPRESSION (*lptr, cmask)) >> (8 * (s - s_aligned));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 3 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 4 * LSIZE))
+        return NULL;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}

[PATCH 2/* v2] Optimize generic strchrnul and strchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 08:35:44AM +0200, Ondřej Bílka wrote:
> This is my generic strchr algorithm resubmitted to use skeleton.
> 
> Idea to split into cases c<128 and c>128 didn't change.
> 
> So comments? How this perform on different architectures?
> 
This also needed to change as I used older strchr wrapper. Here is
correct one.

 	* string/strchr.c: Use skeleton.
 	* string/strchrnul.c: Likewise.


diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..e7c2e4c 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,166 +16,21 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
+#undef index
+
+#define AS_STRCHR
+#define STRCHRNUL strchrnul_static
+#include "string/strchrnul.c"
+
 
-/* Find the first occurrence of C in S.  */
 char *
 strchr (const char *s, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  unsigned char c = (unsigned char) c_in;
+  unsigned char *r = (unsigned char *) STRCHRNUL (s, c);
+  return (*r == c) ? (char *) r : NULL;
 }
 
-#ifdef weak_alias
-#undef index
 weak_alias (strchr, index)
-#endif
 libc_hidden_builtin_def (strchr)
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..95fa11d 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,63 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
+
+#include "string/common.h"
+/* #define EXPRESSION(s, cmask) (((((s & add) + add) & (((s & add) ^ cmask) + add)) | s) ^ high_bits) & high_bits */
+
+#define EXPRESSION(s, cmask) (contains_zero(s) | contains_zero (s ^ cmask))
+#include "string/skeleton.h"
 
 #ifndef STRCHRNUL
 # define STRCHRNUL __strchrnul
 #endif
 
-/* Find the first occurrence of C in S or the final NUL byte.  */
+#ifdef AS_STRCHR
+static __always_inline
+#endif
 char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
+STRCHRNUL (const char *s_in, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = (contains_zero(*lptr) | contains_zero (*lptr ^ cmask))
+             >> (8 * (s - s_aligned));
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

[PATCH 3/* v2] Generic string strlen and rawmemchr

[Ondřej Bílka]

With strlen and rawmemchr I use same idea.

As one could get rawmemchr with strlen by first xoring input and
strlen from rawmemchr by letting gcc optimize rawmemchr(x,0) these
belong together. I keep them separate now but it could change if you
want it.

 	* string/strlen.c: Use skeleton.
 	* string/rawmemchr.c: Likewise.

diff --git a/string/rawmemchr.c b/string/rawmemchr.c
index 05b22be..4aeaf03 100644
--- a/string/rawmemchr.c
+++ b/string/rawmemchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,166 +15,23 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
+#include <string.h>
+#include <stdlib.h>
 
-#undef __ptr_t
-#define __ptr_t void *
+#undef rawmemchr
+#undef __rawmemchr
 
-#if defined (_LIBC)
-# include <string.h>
-# include <memcopy.h>
-# include <stdlib.h>
-#endif
 
-#if defined (HAVE_LIMITS_H) || defined (_LIBC)
-# include <limits.h>
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#include "string/skeleton.h"
 
-#define LONG_MAX_32_BITS 2147483647
-
-#ifndef LONG_MAX
-#define LONG_MAX LONG_MAX_32_BITS
-#endif
-
-#include <sys/types.h>
-
-#undef memchr
-
-#ifndef RAWMEMCHR
-# define RAWMEMCHR __rawmemchr
-#endif
-
-/* Find the first occurrence of C in S.  */
-__ptr_t
-RAWMEMCHR (s, c_in)
-     const __ptr_t s;
-     int c_in;
+void *
+__rawmemchr (const void *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (__ptr_t) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-
-  if (sizeof (longword) != 4 && sizeof (longword) != 8)
-    abort ();
-
-#if LONG_MAX <= LONG_MAX_32_BITS
-  magic_bits = 0x7efefeff;
-#else
-  magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
-#endif
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-#if LONG_MAX > LONG_MAX_32_BITS
-  charmask |= charmask << 32;
-#endif
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (1)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C, not zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++ ^ charmask;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (cp[0] == c)
-	    return (__ptr_t) cp;
-	  if (cp[1] == c)
-	    return (__ptr_t) &cp[1];
-	  if (cp[2] == c)
-	    return (__ptr_t) &cp[2];
-	  if (cp[3] == c)
-	    return (__ptr_t) &cp[3];
-#if LONG_MAX > 2147483647
-	  if (cp[4] == c)
-	    return (__ptr_t) &cp[4];
-	  if (cp[5] == c)
-	    return (__ptr_t) &cp[5];
-	  if (cp[6] == c)
-	    return (__ptr_t) &cp[6];
-	  if (cp[7] == c)
-	    return (__ptr_t) &cp[7];
-#endif
-	}
-    }
+  return (void *) string_skeleton (s, c, NULL);
 }
+
 libc_hidden_def (__rawmemchr)
 weak_alias (__rawmemchr, rawmemchr)
+
diff --git a/string/strlen.c b/string/strlen.c
index d066bde..2cc0369 100644
--- a/string/strlen.c
+++ b/string/strlen.c
@@ -1,8 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -25,81 +22,15 @@
 
 /* Return the length of the null-terminated string STR.  Scan for
    the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p))
+#include "string/skeleton.h"
+
 size_t
 strlen (const char *str)
 {
-  const char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      return char_ptr - str;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      longword = *longword_ptr++;
-
-      if (((longword - lomagic) & ~longword & himagic) != 0)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  if (cp[0] == 0)
-	    return cp - str;
-	  if (cp[1] == 0)
-	    return cp - str + 1;
-	  if (cp[2] == 0)
-	    return cp - str + 2;
-	  if (cp[3] == 0)
-	    return cp - str + 3;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (cp[4] == 0)
-		return cp - str + 4;
-	      if (cp[5] == 0)
-		return cp - str + 5;
-	      if (cp[6] == 0)
-		return cp - str + 6;
-	      if (cp[7] == 0)
-		return cp - str + 7;
-	    }
-	}
-    }
+  return string_skeleton (str, 0, 0) - str;
 }
+
 libc_hidden_builtin_def (strlen)

[PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

Here we first deal with functions that use size bound.
Main technical complication is pointer wraparound for large n so it
needs to be handled accordingly. Otherwise its almost same as rawmemchr.

As I wrote before that we could optimize  memchr(x,0,n) to strnlen
opposite is also true. Here strnlen uses memchr and lets gcc simply
that.

Comments?

	* string/memchr.c: Use skeleton.
	* string/strnlen.c: Likewise.

diff --git a/string/memchr.c b/string/memchr.c
index 6896465..fede01a 100644
--- a/string/memchr.c
+++ b/string/memchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,143 +15,41 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifndef _LIBC
-# include <config.h>
-#endif
-
 #include <string.h>
-
-#include <stddef.h>
-
-#include <limits.h>
+#include <stdlib.h>
 
 #undef __memchr
-#ifdef _LIBC
-# undef memchr
-#endif
+#undef memchr
 
-#ifndef weak_alias
-# define __memchr memchr
-#endif
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
+#include "string/skeleton.h"
 
 #ifndef MEMCHR
 # define MEMCHR __memchr
 #endif
 
-/* Search no more than N bytes of S for C.  */
+#ifdef STATIC
+static __always_inline
+#endif
 void *
-MEMCHR (void const *s, int c_in, size_t n)
+MEMCHR (const void *_str, int c, size_t n)
 {
-  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
-     long instead of a 64-bit uintmax_t tends to give better
-     performance.  On 64-bit hardware, unsigned long is generally 64
-     bits already.  Change this typedef to experiment with
-     performance.  */
-  typedef unsigned long int longword;
-
-  const unsigned char *char_ptr;
-  const longword *longword_ptr;
-  longword repeated_one;
-  longword repeated_c;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few bytes by reading one byte at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
-       --n, ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-
-  longword_ptr = (const longword *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to any size longwords.  */
-
-  /* Compute auxiliary longword values:
-     repeated_one is a value which has a 1 in every byte.
-     repeated_c has c in every byte.  */
-  repeated_one = 0x01010101;
-  repeated_c = c | (c << 8);
-  repeated_c |= repeated_c << 16;
-  if (0xffffffffU < (longword) -1)
-    {
-      repeated_one |= repeated_one << 31 << 1;
-      repeated_c |= repeated_c << 31 << 1;
-      if (8 < sizeof (longword))
-	{
-	  size_t i;
-
-	  for (i = 64; i < sizeof (longword) * 8; i *= 2)
-	    {
-	      repeated_one |= repeated_one << i;
-	      repeated_c |= repeated_c << i;
-	    }
-	}
-    }
-
-  /* Instead of the traditional loop which tests each byte, we will test a
-     longword at a time.  The tricky part is testing if *any of the four*
-     bytes in the longword in question are equal to c.  We first use an xor
-     with repeated_c.  This reduces the task to testing whether *any of the
-     four* bytes in longword1 is zero.
-
-     We compute tmp =
-       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
-     That is, we perform the following operations:
-       1. Subtract repeated_one.
-       2. & ~longword1.
-       3. & a mask consisting of 0x80 in every byte.
-     Consider what happens in each byte:
-       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
-	 and step 3 transforms it into 0x80.  A carry can also be propagated
-	 to more significant bytes.
-       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
-	 position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
-	 the byte ends in a single bit of value 0 and k bits of value 1.
-	 After step 2, the result is just k bits of value 1: 2^k - 1.  After
-	 step 3, the result is 0.  And no carry is produced.
-     So, if longword1 has only non-zero bytes, tmp is zero.
-     Whereas if longword1 has a zero byte, call j the position of the least
-     significant zero byte.  Then the result has a zero at positions 0, ...,
-     j-1 and a 0x80 at position j.  We cannot predict the result at the more
-     significant bytes (positions j+1..3), but it does not matter since we
-     already have a non-zero bit at position 8*j+7.
-
-     So, the test whether any byte in longword1 is zero is equivalent to
-     testing whether tmp is nonzero.  */
-
-  while (n >= sizeof (longword))
-    {
-      longword longword1 = *longword_ptr ^ repeated_c;
-
-      if ((((longword1 - repeated_one) & ~longword1)
-	   & (repeated_one << 7)) != 0)
-	break;
-      longword_ptr++;
-      n -= sizeof (longword);
-    }
-
-  char_ptr = (const unsigned char *) longword_ptr;
-
-  /* At this point, we know that either n < sizeof (longword), or one of the
-     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
-     machines, we could determine the first such byte without any further
-     memory accesses, just by looking at the tmp result from the last loop
-     iteration.  But this does not work on big-endian machines.  Choose code
-     that works in both cases.  */
-
-  for (; n > 0; --n, ++char_ptr)
-    {
-      if (*char_ptr == c)
-	return (void *) char_ptr;
-    }
-
-  return NULL;
+  if (n == 0)
+    return NULL;
+  char *str = (char *) _str;
+  char *end = (char *) (((uintptr_t) str) + n);
+  if ((uintptr_t) end < (uintptr_t) str)
+    end = (char *) UINTPTR_MAX;
+  char *ret = string_skeleton (str, c, end);
+  return (void *)((uintptr_t) ret < (uintptr_t) end ? ret : NULL);
 }
-#ifdef weak_alias
+
+#ifndef STATIC
 weak_alias (__memchr, memchr)
-#endif
 libc_hidden_builtin_def (memchr)
+#endif
diff --git a/string/strnlen.c b/string/strnlen.c
index 803d78b..a5917de 100644
--- a/string/strnlen.c
+++ b/string/strnlen.c
@@ -1,15 +1,10 @@
-/* Find the length of STRING, but scan at most MAXLEN characters.
-   Copyright (C) 1991-2015 Free Software Foundation, Inc.
-   Contributed by Jakub Jelinek <jakub@redhat.com>.
-
-   Based on strlen written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
+/* 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.
+   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
@@ -17,149 +12,28 @@
    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; see the file COPYING.LIB.  If
-   not, see <http://www.gnu.org/licenses/>.  */
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
 #include <stdlib.h>
 
-/* Find the length of S, but scan at most MAXLEN characters.  If no
-   '\0' terminator is found in that many characters, return MAXLEN.  */
+#undef strlen
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#ifdef STRNLEN
-# define __strnlen STRNLEN
-#endif
+#define STATIC
+#define MEMCHR memchr_static
+#include "string/memchr.c"
 
 size_t
-__strnlen (const char *str, size_t maxlen)
+__strnlen (const char *str, size_t n)
 {
-  const char *char_ptr, *end_ptr = str + maxlen;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  if (maxlen == 0)
-    return 0;
-
-  if (__glibc_unlikely (end_ptr < str))
-    end_ptr = (const char *) ~0UL;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      {
-	if (char_ptr > end_ptr)
-	  char_ptr = end_ptr;
-	return char_ptr - str;
-      }
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (longword_ptr < (unsigned long int *) end_ptr)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.  */
-
-      longword = *longword_ptr++;
-
-      if ((longword - lomagic) & himagic)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  char_ptr = cp;
-	  if (cp[0] == 0)
-	    break;
-	  char_ptr = cp + 1;
-	  if (cp[1] == 0)
-	    break;
-	  char_ptr = cp + 2;
-	  if (cp[2] == 0)
-	    break;
-	  char_ptr = cp + 3;
-	  if (cp[3] == 0)
-	    break;
-	  if (sizeof (longword) > 4)
-	    {
-	      char_ptr = cp + 4;
-	      if (cp[4] == 0)
-		break;
-	      char_ptr = cp + 5;
-	      if (cp[5] == 0)
-		break;
-	      char_ptr = cp + 6;
-	      if (cp[6] == 0)
-		break;
-	      char_ptr = cp + 7;
-	      if (cp[7] == 0)
-		break;
-	    }
-	}
-      char_ptr = end_ptr;
-    }
-
-  if (char_ptr > end_ptr)
-    char_ptr = end_ptr;
-  return char_ptr - str;
+  char *ret = MEMCHR (str, 0, n); 
+  return ret ? ret - str : n;
 }
-#ifndef STRNLEN
+
 weak_alias (__strnlen, strnlen)
-#endif
 libc_hidden_def (strnlen)
+

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Wed, May 27, 2015 at 08:01:21AM +0200, Ondřej Bílka wrote:
> Hi,
> 
> As i mentioned improving generic string functions this is my second
> attempt. As lot of functions will be optimized in same way this uses
> generic code flow. Functions will vary just by expression to check and
> how interpret return value.
> 
> Performance gains of using this are from loop unrolling and better
> header that doesn't have to check start byte-by-byte.
> 
> Unrolling migth be excessive but its better to tune it in skeleton than
> try manually and risk introducing errors.
> 
> This implementation would probably be faster than assembly on other
> architectures as this will beat it unless you used hardware specific
> instruction or gcc messes up compilation and generates suboptimal code.
> 
> Comments?
> 

Here is a new version of skeleton. I added a big endian support. This
reminded me that when I first wrote it I wanted to use opperations that
dont cause carry, then forgotten about it. As thats needed only for
first aligned load or always on big endian you need to supply expression
twice. one version shouldn't cause carry propagation.

 	* string/common.h: New file.
 	* string/skeleton.h: Likewise.

diff --git a/string/common.h b/string/common.h
new file mode 100644
index 0000000..481c99f
--- /dev/null
+++ b/string/common.h
@@ -0,0 +1,80 @@
+#include <stdint.h>
+
+static const unsigned long int ones = (~0UL / 255); /* 0x0101...*/
+static const unsigned long int add = 127 * (~0UL / 255);
+static const unsigned long int high_bits = 128 * (~0UL / 255);
+
+/* 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.
+  */
+
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+static __always_inline
+unsigned long int 
+contains_zero (unsigned long int s)
+{
+  return (s - ones) & ~s & high_bits;
+}
+#else
+#define contains_zero contains_zero_nocarry
+#endif
+
+static __always_inline
+unsigned long int 
+contains_zero_nocarry (unsigned long int s)
+{
+  return (((s | high_bits) - ones) ^ high_bits) & ~s & high_bits;
+}
+
+#define LSIZE sizeof (unsigned long int)
+#define CROSS_PAGE(x, n) (((uintptr_t) x) % 4096 > 4096 - n)
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#define SHIFT_BYTES(x, n) ((x) << (8 * (n)))
+#else
+#define SHIFT_BYTES(x, n) ((x) >> (8 * (n)))
+#endif
+
+static __always_inline
+size_t
+first_nonzero_byte (unsigned long int u)
+{
+#if __BYTE_ORDER == __BIG_ENDIAN
+# ifdef FAST_CLZ
+  return clz (u) / 8;
+# else
+#  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));
+# endif
+#else
+# ifdef FAST_FFS
+  return (ffsl (u) - 1) / 8;
+# else
+  u = u ^ (u - 1);
+  u = u & ones;
+  u = u * ones;
+  return (u >> (8 * LSIZE - 8)) - 1;
+# endif
+#endif
+}
diff --git a/string/skeleton.h b/string/skeleton.h
new file mode 100644
index 0000000..76bd08f
--- /dev/null
+++ b/string/skeleton.h
@@ -0,0 +1,150 @@
+/* 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 <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
+
+static __always_inline
+int
+found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+{
+  const unsigned long int *lptr = (const unsigned long int *) s;
+  unsigned long int mask = EXPRESSION(*lptr, cmask);
+  if (mask)
+    {
+      *result = s + first_nonzero_byte (mask);
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+char *
+string_skeleton (const char *s_in, int c_in, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  char *r;
+  unsigned long int __attribute__ ((unused)) cmask = c * ones;
+
+#if _STRING_ARCH_unaligned
+  /* 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))
+    {
+      if (found_in_long_bytes (s + 0 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 1 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 2 * LSIZE, cmask, &r))
+        return r;
+      if (found_in_long_bytes (s + 3 * LSIZE, cmask, &r))
+        return r;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s + 5 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 6 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 7 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s + 8 * LSIZE, cmask, &r))
+            return r;
+        }
+
+      if (BOUND (s + 32))
+        return NULL;
+    }
+  else
+    {
+#endif
+  /* 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);
+      lptr = (const unsigned long int *) s_aligned;
+      /* We need be careful here as bytes before start can corrupt it.  */
+      mask = SHIFT_BYTES ((EXPRESSION_NOCARRY (*lptr, cmask)), s - s_aligned);
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      if (BOUND (s_aligned + 1 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 1 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 2 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 2 * LSIZE, cmask, &r))
+        return r;
+      if (BOUND (s_aligned + 3 * LSIZE))
+        return NULL;
+      if (found_in_long_bytes (s_aligned + 3 * LSIZE, cmask, &r))
+        return r;
+#if _STRING_ARCH_unaligned
+    }
+#endif
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s_loop = PTR_ALIGN_DOWN (s, 4 * LSIZE);
+  while (!BOUND (s_loop + 4 * LSIZE))
+    {
+      s_loop += 4 * LSIZE;
+      lptr = (const unsigned long int *) (s_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+      lptr = (const unsigned long int *) (s_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr, cmask);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s_loop + 0 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 1 * LSIZE, cmask, &r))
+            return r;
+          if (found_in_long_bytes (s_loop + 2 * LSIZE, cmask, &r))
+            return r;
+
+          return s_loop + 3 * LSIZE + first_nonzero_byte (mask);
+        }
+    }
+ return NULL;
+}

Re: [PATCH 2/* v3] Optimize generic strchrnul and strchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 11:11:48AM +0200, Ondřej Bílka wrote:
> On Wed, May 27, 2015 at 08:35:44AM +0200, Ondřej Bílka wrote:
> > This is my generic strchr algorithm resubmitted to use skeleton.
> > 
> > Idea to split into cases c<128 and c>128 didn't change.
> > 
> > So comments? How this perform on different architectures?
> > 
> This also needed to change as I used older strchr wrapper. Here is
> correct one.
> 
And here is updated version with better expression and big endian
support.

  	* string/strchr.c: Use skeleton.
  	* string/strchrnul.c: Likewise.

diff --git a/string/strchr.c b/string/strchr.c
index 5f90075..e7c2e4c 100644
--- a/string/strchr.c
+++ b/string/strchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,166 +16,21 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <stdlib.h>
-
 #undef strchr
+#undef index
+
+#define AS_STRCHR
+#define STRCHRNUL strchrnul_static
+#include "string/strchrnul.c"
+
 
-/* Find the first occurrence of C in S.  */
 char *
 strchr (const char *s, int c_in)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-    else if (*char_ptr == '\0')
-      return NULL;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (*++cp == c)
-	    return (char *) cp;
-	  else if (*cp == '\0')
-	    return NULL;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	      if (*++cp == c)
-		return (char *) cp;
-	      else if (*cp == '\0')
-		return NULL;
-	    }
-	}
-    }
-
-  return NULL;
+  unsigned char c = (unsigned char) c_in;
+  unsigned char *r = (unsigned char *) STRCHRNUL (s, c);
+  return (*r == c) ? (char *) r : NULL;
 }
 
-#ifdef weak_alias
-#undef index
 weak_alias (strchr, index)
-#endif
 libc_hidden_builtin_def (strchr)
diff --git a/string/strchrnul.c b/string/strchrnul.c
index 2678f1d..e1aebf4 100644
--- a/string/strchrnul.c
+++ b/string/strchrnul.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   bug fix and commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to strchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -21,153 +16,69 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 #include <stdlib.h>
 
-#undef __strchrnul
 #undef strchrnul
+#undef __strchrnul
 
-#ifndef STRCHRNUL
-# define STRCHRNUL __strchrnul
-#endif
-
-/* Find the first occurrence of C in S or the final NUL byte.  */
-char *
-STRCHRNUL (s, c_in)
-     const char *s;
-     int c_in;
-{
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c || *char_ptr == '\0')
-      return (void *) char_ptr;
+/* Here idea is still use the result of expression
+   contains_zero (*p) | contains_zero (*p ^ cmask)
+   but we can optimize it by using commutativity of operations.  */
 
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
+#include "string/common.h"
+#define EXPRESSION(s, cmask) ((((s) - ones) | (((s) ^ cmask) - ones)) \
+			      & high_bits & (~s))
 
-  longword_ptr = (unsigned long int *) char_ptr;
+/* TODO simplify.  */
+#define EXPRESSION_NOCARRY(s, cmask) contains_zero_nocarry (s) \
+				     | contains_zero_nocarry (s ^ cmask)
 
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
 
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
+#include "string/skeleton.h"
 
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  switch (sizeof (longword))
-    {
-    case 4: magic_bits = 0x7efefeffL; break;
-    case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
-    default:
-      abort ();
-    }
+#ifndef STRCHRNUL
+# define STRCHRNUL __strchrnul
+#endif
 
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-  if (sizeof (longword) > 4)
-    /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-    charmask |= (charmask << 16) << 16;
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
+#ifdef AS_STRCHR
+static __always_inline
+#endif
+char *
+STRCHRNUL (const char *s_in, int c_in)
+{
+  char *s_aligned;
+  unsigned long int mask;
+  const unsigned long int *lptr;
+  char *s = (char *) s_in;
+  unsigned char c = (unsigned char) c_in;
+  unsigned long int cmask = c * ones;
+  if (__glibc_unlikely (c > 127))
     {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C as well as zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0 ||
-
-	  /* That caught zeroes.  Now test for C.  */
-	  ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C or zero?
-	     If none of them were, it was a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (*cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (*++cp == c || *cp == '\0')
-	    return (char *) cp;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	      if (*++cp == c || *cp == '\0')
-		return (char *) cp;
-	    }
-	}
+      s_aligned = PTR_ALIGN_DOWN (s, LSIZE);
+      lptr = (const unsigned long int *) s_aligned;
+      mask = SHIFT_BYTES (contains_zero_nocarry (*lptr)
+                          | contains_zero_nocarry (*lptr ^ cmask),
+                          s - s_aligned);
+
+      if (mask)
+        return s + first_nonzero_byte (mask);
+
+      while (1)
+        {
+          s_aligned += LSIZE;
+          lptr = (const unsigned long int *) s_aligned;
+          mask = contains_zero(*lptr) | contains_zero (*lptr ^ cmask);
+          if (mask)
+            return s_aligned + first_nonzero_byte (mask);
+        }
     }
-
-  /* This should never happen.  */
-  return NULL;
+  else
+    return string_skeleton (s, c, 0);
 }
 
+#ifndef AS_STRCHR
 weak_alias (__strchrnul, strchrnul)
+#endif

Re: [PATCH 3/* v2] Generic string strlen and rawmemchr

[Ondřej Bílka]

On Wed, May 27, 2015 at 11:18:58AM +0200, Ondřej Bílka wrote:
> With strlen and rawmemchr I use same idea.
> 
> As one could get rawmemchr with strlen by first xoring input and
> strlen from rawmemchr by letting gcc optimize rawmemchr(x,0) these
> belong together. I keep them separate now but it could change if you
> want it.
>
Again resending with added big endian expression. 

  	* string/strlen.c: Use skeleton.
  	* string/rawmemchr.c: Likewise.

diff --git a/string/rawmemchr.c b/string/rawmemchr.c
index 05b22be..aa6fc06 100644
--- a/string/rawmemchr.c
+++ b/string/rawmemchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,166 +15,25 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
+#include <string.h>
+#include <stdlib.h>
 
-#undef __ptr_t
-#define __ptr_t void *
+#undef rawmemchr
+#undef __rawmemchr
 
-#if defined (_LIBC)
-# include <string.h>
-# include <memcopy.h>
-# include <stdlib.h>
-#endif
 
-#if defined (HAVE_LIMITS_H) || defined (_LIBC)
-# include <limits.h>
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p ^ c))
 
-#define LONG_MAX_32_BITS 2147483647
+#include "string/skeleton.h"
 
-#ifndef LONG_MAX
-#define LONG_MAX LONG_MAX_32_BITS
-#endif
-
-#include <sys/types.h>
-
-#undef memchr
-
-#ifndef RAWMEMCHR
-# define RAWMEMCHR __rawmemchr
-#endif
-
-/* Find the first occurrence of C in S.  */
-__ptr_t
-RAWMEMCHR (s, c_in)
-     const __ptr_t s;
-     int c_in;
+void *
+__rawmemchr (const void *s, int c)
 {
-  const unsigned char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, magic_bits, charmask;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == c)
-      return (__ptr_t) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-
-  if (sizeof (longword) != 4 && sizeof (longword) != 8)
-    abort ();
-
-#if LONG_MAX <= LONG_MAX_32_BITS
-  magic_bits = 0x7efefeff;
-#else
-  magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
-#endif
-
-  /* Set up a longword, each of whose bytes is C.  */
-  charmask = c | (c << 8);
-  charmask |= charmask << 16;
-#if LONG_MAX > LONG_MAX_32_BITS
-  charmask |= charmask << 32;
-#endif
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (1)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.
-
-	 3) But wait!  Aren't we looking for C, not zero?
-	 Good point.  So what we do is XOR LONGWORD with a longword,
-	 each of whose bytes is C.  This turns each byte that is C
-	 into a zero.  */
-
-      longword = *longword_ptr++ ^ charmask;
-
-      /* Add MAGIC_BITS to LONGWORD.  */
-      if ((((longword + magic_bits)
-
-	    /* Set those bits that were unchanged by the addition.  */
-	    ^ ~longword)
-
-	   /* Look at only the hole bits.  If any of the hole bits
-	      are unchanged, most likely one of the bytes was a
-	      zero.  */
-	   & ~magic_bits) != 0)
-	{
-	  /* Which of the bytes was C?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
-
-	  if (cp[0] == c)
-	    return (__ptr_t) cp;
-	  if (cp[1] == c)
-	    return (__ptr_t) &cp[1];
-	  if (cp[2] == c)
-	    return (__ptr_t) &cp[2];
-	  if (cp[3] == c)
-	    return (__ptr_t) &cp[3];
-#if LONG_MAX > 2147483647
-	  if (cp[4] == c)
-	    return (__ptr_t) &cp[4];
-	  if (cp[5] == c)
-	    return (__ptr_t) &cp[5];
-	  if (cp[6] == c)
-	    return (__ptr_t) &cp[6];
-	  if (cp[7] == c)
-	    return (__ptr_t) &cp[7];
-#endif
-	}
-    }
+  return (void *) string_skeleton (s, c, NULL);
 }
+
 libc_hidden_def (__rawmemchr)
 weak_alias (__rawmemchr, rawmemchr)
+
diff --git a/string/strlen.c b/string/strlen.c
index d066bde..621196c 100644
--- a/string/strlen.c
+++ b/string/strlen.c
@@ -1,8 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -25,81 +22,16 @@
 
 /* Return the length of the null-terminated string STR.  Scan for
    the null terminator quickly by testing four bytes at a time.  */
+
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p))
+#include "string/skeleton.h"
+
 size_t
 strlen (const char *str)
 {
-  const char *char_ptr;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      return char_ptr - str;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  for (;;)
-    {
-      longword = *longword_ptr++;
-
-      if (((longword - lomagic) & ~longword & himagic) != 0)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  if (cp[0] == 0)
-	    return cp - str;
-	  if (cp[1] == 0)
-	    return cp - str + 1;
-	  if (cp[2] == 0)
-	    return cp - str + 2;
-	  if (cp[3] == 0)
-	    return cp - str + 3;
-	  if (sizeof (longword) > 4)
-	    {
-	      if (cp[4] == 0)
-		return cp - str + 4;
-	      if (cp[5] == 0)
-		return cp - str + 5;
-	      if (cp[6] == 0)
-		return cp - str + 6;
-	      if (cp[7] == 0)
-		return cp - str + 7;
-	    }
-	}
-    }
+  return string_skeleton (str, 0, 0) - str;
 }
+
 libc_hidden_builtin_def (strlen)

Re: [PATCH 4/* v2] Generic string memchr and strnlen

[Ondřej Bílka]

On Wed, May 27, 2015 at 01:42:01PM +0200, Ondřej Bílka wrote:
> Here we first deal with functions that use size bound.
> Main technical complication is pointer wraparound for large n so it
> needs to be handled accordingly. Otherwise its almost same as rawmemchr.
> 
> As I wrote before that we could optimize  memchr(x,0,n) to strnlen
> opposite is also true. Here strnlen uses memchr and lets gcc simply
> that.
> 
> Comments?
> 
Again added big endian.

 	* string/memchr.c: Use skeleton.
 	* string/strnlen.c: Likewise.


diff --git a/string/memchr.c b/string/memchr.c
index 6896465..42a6c27 100644
--- a/string/memchr.c
+++ b/string/memchr.c
@@ -1,10 +1,5 @@
 /* Copyright (C) 1991-2015 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se) and
-   commentary by Jim Blandy (jimb@ai.mit.edu);
-   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
-   and implemented by Roland McGrath (roland@ai.mit.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,143 +15,43 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-#ifndef _LIBC
-# include <config.h>
-#endif
-
 #include <string.h>
+#include <stdlib.h>
 
-#include <stddef.h>
+#undef __memchr
+#undef memchr
 
-#include <limits.h>
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#undef __memchr
-#ifdef _LIBC
-# undef memchr
-#endif
+#include "string/common.h"
+#define EXPRESSION(p, c) (contains_zero (p ^ c))
+#define EXPRESSION_NOCARRY(p, c) (contains_zero_nocarry (p ^ c))
 
-#ifndef weak_alias
-# define __memchr memchr
-#endif
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
+#include "string/skeleton.h"
 
 #ifndef MEMCHR
 # define MEMCHR __memchr
 #endif
 
-/* Search no more than N bytes of S for C.  */
+#ifdef STATIC
+static __always_inline
+#endif
 void *
-MEMCHR (void const *s, int c_in, size_t n)
+MEMCHR (const void *_str, int c, size_t n)
 {
-  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
-     long instead of a 64-bit uintmax_t tends to give better
-     performance.  On 64-bit hardware, unsigned long is generally 64
-     bits already.  Change this typedef to experiment with
-     performance.  */
-  typedef unsigned long int longword;
-
-  const unsigned char *char_ptr;
-  const longword *longword_ptr;
-  longword repeated_one;
-  longword repeated_c;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
-
-  /* Handle the first few bytes by reading one byte at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = (const unsigned char *) s;
-       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
-       --n, ++char_ptr)
-    if (*char_ptr == c)
-      return (void *) char_ptr;
-
-  longword_ptr = (const longword *) char_ptr;
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to any size longwords.  */
-
-  /* Compute auxiliary longword values:
-     repeated_one is a value which has a 1 in every byte.
-     repeated_c has c in every byte.  */
-  repeated_one = 0x01010101;
-  repeated_c = c | (c << 8);
-  repeated_c |= repeated_c << 16;
-  if (0xffffffffU < (longword) -1)
-    {
-      repeated_one |= repeated_one << 31 << 1;
-      repeated_c |= repeated_c << 31 << 1;
-      if (8 < sizeof (longword))
-	{
-	  size_t i;
-
-	  for (i = 64; i < sizeof (longword) * 8; i *= 2)
-	    {
-	      repeated_one |= repeated_one << i;
-	      repeated_c |= repeated_c << i;
-	    }
-	}
-    }
-
-  /* Instead of the traditional loop which tests each byte, we will test a
-     longword at a time.  The tricky part is testing if *any of the four*
-     bytes in the longword in question are equal to c.  We first use an xor
-     with repeated_c.  This reduces the task to testing whether *any of the
-     four* bytes in longword1 is zero.
-
-     We compute tmp =
-       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
-     That is, we perform the following operations:
-       1. Subtract repeated_one.
-       2. & ~longword1.
-       3. & a mask consisting of 0x80 in every byte.
-     Consider what happens in each byte:
-       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
-	 and step 3 transforms it into 0x80.  A carry can also be propagated
-	 to more significant bytes.
-       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
-	 position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
-	 the byte ends in a single bit of value 0 and k bits of value 1.
-	 After step 2, the result is just k bits of value 1: 2^k - 1.  After
-	 step 3, the result is 0.  And no carry is produced.
-     So, if longword1 has only non-zero bytes, tmp is zero.
-     Whereas if longword1 has a zero byte, call j the position of the least
-     significant zero byte.  Then the result has a zero at positions 0, ...,
-     j-1 and a 0x80 at position j.  We cannot predict the result at the more
-     significant bytes (positions j+1..3), but it does not matter since we
-     already have a non-zero bit at position 8*j+7.
-
-     So, the test whether any byte in longword1 is zero is equivalent to
-     testing whether tmp is nonzero.  */
-
-  while (n >= sizeof (longword))
-    {
-      longword longword1 = *longword_ptr ^ repeated_c;
-
-      if ((((longword1 - repeated_one) & ~longword1)
-	   & (repeated_one << 7)) != 0)
-	break;
-      longword_ptr++;
-      n -= sizeof (longword);
-    }
-
-  char_ptr = (const unsigned char *) longword_ptr;
-
-  /* At this point, we know that either n < sizeof (longword), or one of the
-     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
-     machines, we could determine the first such byte without any further
-     memory accesses, just by looking at the tmp result from the last loop
-     iteration.  But this does not work on big-endian machines.  Choose code
-     that works in both cases.  */
-
-  for (; n > 0; --n, ++char_ptr)
-    {
-      if (*char_ptr == c)
-	return (void *) char_ptr;
-    }
-
-  return NULL;
+  if (n == 0)
+    return NULL;
+  char *str = (char *) _str;
+  char *end = (char *) (((uintptr_t) str) + n);
+  if ((uintptr_t) end < (uintptr_t) str)
+    end = (char *) UINTPTR_MAX;
+  char *ret = string_skeleton (str, c, end);
+  return (void *)((uintptr_t) ret < (uintptr_t) end ? ret : NULL);
 }
-#ifdef weak_alias
+
+#ifndef STATIC
 weak_alias (__memchr, memchr)
-#endif
 libc_hidden_builtin_def (memchr)
+#endif
diff --git a/string/strnlen.c b/string/strnlen.c
index 803d78b..9a71e4d 100644
--- a/string/strnlen.c
+++ b/string/strnlen.c
@@ -1,15 +1,10 @@
-/* Find the length of STRING, but scan at most MAXLEN characters.
-   Copyright (C) 1991-2015 Free Software Foundation, Inc.
-   Contributed by Jakub Jelinek <jakub@redhat.com>.
-
-   Based on strlen written by Torbjorn Granlund (tege@sics.se),
-   with help from Dan Sahlin (dan@sics.se);
-   commentary by Jim Blandy (jimb@ai.mit.edu).
+/* 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.
+   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
@@ -17,149 +12,27 @@
    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; see the file COPYING.LIB.  If
-   not, see <http://www.gnu.org/licenses/>.  */
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
 #include <stdlib.h>
 
-/* Find the length of S, but scan at most MAXLEN characters.  If no
-   '\0' terminator is found in that many characters, return MAXLEN.  */
+#undef strlen
+
+/* Return the length of the null-terminated string STR.  Scan for
+   the null terminator quickly by testing four bytes at a time.  */
 
-#ifdef STRNLEN
-# define __strnlen STRNLEN
-#endif
+#define STATIC
+#define MEMCHR memchr_static
+#include "string/memchr.c"
 
 size_t
-__strnlen (const char *str, size_t maxlen)
+__strnlen (const char *str, size_t n)
 {
-  const char *char_ptr, *end_ptr = str + maxlen;
-  const unsigned long int *longword_ptr;
-  unsigned long int longword, himagic, lomagic;
-
-  if (maxlen == 0)
-    return 0;
-
-  if (__glibc_unlikely (end_ptr < str))
-    end_ptr = (const char *) ~0UL;
-
-  /* Handle the first few characters by reading one character at a time.
-     Do this until CHAR_PTR is aligned on a longword boundary.  */
-  for (char_ptr = str; ((unsigned long int) char_ptr
-			& (sizeof (longword) - 1)) != 0;
-       ++char_ptr)
-    if (*char_ptr == '\0')
-      {
-	if (char_ptr > end_ptr)
-	  char_ptr = end_ptr;
-	return char_ptr - str;
-      }
-
-  /* All these elucidatory comments refer to 4-byte longwords,
-     but the theory applies equally well to 8-byte longwords.  */
-
-  longword_ptr = (unsigned long int *) char_ptr;
-
-  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
-     the "holes."  Note that there is a hole just to the left of
-     each byte, with an extra at the end:
-
-     bits:  01111110 11111110 11111110 11111111
-     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
-
-     The 1-bits make sure that carries propagate to the next 0-bit.
-     The 0-bits provide holes for carries to fall into.  */
-  himagic = 0x80808080L;
-  lomagic = 0x01010101L;
-  if (sizeof (longword) > 4)
-    {
-      /* 64-bit version of the magic.  */
-      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
-      himagic = ((himagic << 16) << 16) | himagic;
-      lomagic = ((lomagic << 16) << 16) | lomagic;
-    }
-  if (sizeof (longword) > 8)
-    abort ();
-
-  /* Instead of the traditional loop which tests each character,
-     we will test a longword at a time.  The tricky part is testing
-     if *any of the four* bytes in the longword in question are zero.  */
-  while (longword_ptr < (unsigned long int *) end_ptr)
-    {
-      /* We tentatively exit the loop if adding MAGIC_BITS to
-	 LONGWORD fails to change any of the hole bits of LONGWORD.
-
-	 1) Is this safe?  Will it catch all the zero bytes?
-	 Suppose there is a byte with all zeros.  Any carry bits
-	 propagating from its left will fall into the hole at its
-	 least significant bit and stop.  Since there will be no
-	 carry from its most significant bit, the LSB of the
-	 byte to the left will be unchanged, and the zero will be
-	 detected.
-
-	 2) Is this worthwhile?  Will it ignore everything except
-	 zero bytes?  Suppose every byte of LONGWORD has a bit set
-	 somewhere.  There will be a carry into bit 8.  If bit 8
-	 is set, this will carry into bit 16.  If bit 8 is clear,
-	 one of bits 9-15 must be set, so there will be a carry
-	 into bit 16.  Similarly, there will be a carry into bit
-	 24.  If one of bits 24-30 is set, there will be a carry
-	 into bit 31, so all of the hole bits will be changed.
-
-	 The one misfire occurs when bits 24-30 are clear and bit
-	 31 is set; in this case, the hole at bit 31 is not
-	 changed.  If we had access to the processor carry flag,
-	 we could close this loophole by putting the fourth hole
-	 at bit 32!
-
-	 So it ignores everything except 128's, when they're aligned
-	 properly.  */
-
-      longword = *longword_ptr++;
-
-      if ((longword - lomagic) & himagic)
-	{
-	  /* Which of the bytes was the zero?  If none of them were, it was
-	     a misfire; continue the search.  */
-
-	  const char *cp = (const char *) (longword_ptr - 1);
-
-	  char_ptr = cp;
-	  if (cp[0] == 0)
-	    break;
-	  char_ptr = cp + 1;
-	  if (cp[1] == 0)
-	    break;
-	  char_ptr = cp + 2;
-	  if (cp[2] == 0)
-	    break;
-	  char_ptr = cp + 3;
-	  if (cp[3] == 0)
-	    break;
-	  if (sizeof (longword) > 4)
-	    {
-	      char_ptr = cp + 4;
-	      if (cp[4] == 0)
-		break;
-	      char_ptr = cp + 5;
-	      if (cp[5] == 0)
-		break;
-	      char_ptr = cp + 6;
-	      if (cp[6] == 0)
-		break;
-	      char_ptr = cp + 7;
-	      if (cp[7] == 0)
-		break;
-	    }
-	}
-      char_ptr = end_ptr;
-    }
-
-  if (char_ptr > end_ptr)
-    char_ptr = end_ptr;
-  return char_ptr - str;
+  char *ret = MEMCHR (str, 0, n);
+  return ret ? ret - str : n;
 }
-#ifndef STRNLEN
+
 weak_alias (__strnlen, strnlen)
-#endif
 libc_hidden_def (strnlen)

[PATCH 5/*] Generic string function optimization: strcmp and strncmp

[Ondřej Bílka]

This adds a platform generic optimization of strcmp and strncmp.
I adapted a x64 skeleton from strcmp. I correctly added end checks which 
I didn't do before so I will also send optimized strncmp.

 	* string/diff_skeleton.h: New file.
 	* string/strcmp.c: Use diff skeleton.
	* string/strncmp.c: Likewise. 

diff --git a/string/diff_skeleton.h b/string/diff_skeleton.h
new file mode 100644
index 0000000..a2cdccc
--- /dev/null
+++ b/string/diff_skeleton.h
@@ -0,0 +1,181 @@
+/* Skeleton of *cmp 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 <string.h>
+#include <libc-internal.h>
+#include <stdint.h>
+
+#ifndef BOUND
+# define BOUND(x) 0
+#endif
+
+
+static __always_inline
+int
+found_in_long_bytes(char *s1, char *s2, char **r1, char **r2)
+{
+  const unsigned long int *lptr1 = (const unsigned long int *) s1;
+  const unsigned long int *lptr2 = (const unsigned long int *) s2;
+
+  unsigned long int mask = EXPRESSION(*lptr1, *lptr2);
+  if (mask)
+    {
+      size_t found = first_nonzero_byte (mask);
+      *r1 = s1 + found;
+      *r2 = s2 + found;
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static __always_inline
+int
+diff_skeleton (char **p1, char **p2, char *end)
+{
+  unsigned long int mask;
+  const unsigned long int *lptr1, *lptr2;
+  char *s1 = *p1, *s2 = *p2;
+
+
+#if _STRING_ARCH_unaligned == 0
+  /* We don't optimize for architectures without aligned load yet.
+     Problem is that header is hot and you need different tricks 
+     with aligned load. However loop would be relatively easy by 
+     emulating loads with mix of byte shifts. */
+
+  size_t i = byte_loop(s1, s2, SIZE_MAX, end);
+  *p1 = s1 + i;
+  *p2 = s2 + i;
+  return i != SIZE_MAX;
+#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 (s1, 32) && !CROSS_PAGE (s2, 32))
+    {
+      if (found_in_long_bytes (s1 + 0 * LSIZE, s2 + 0 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 1 * LSIZE, s2 + 1 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 2 * LSIZE, s2 + 2 * LSIZE, p1, p2))
+        return 1;
+      if (found_in_long_bytes (s1 + 3 * LSIZE, s2 + 3 * LSIZE, p1, p2))
+        return 1;
+      if (sizeof (unsigned long int) == 4)
+        {
+          if (found_in_long_bytes (s1 + 4 * LSIZE, s2 + 4 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 5 * LSIZE, s2 + 5 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 6 * LSIZE, s2 + 6 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1 + 7 * LSIZE, s2 + 7 * LSIZE, p1, p2))
+            return 1;
+        }
+
+      if (BOUND (s1 + 32))
+        return 0;
+    }
+  else
+    {
+      size_t i = byte_loop(s1, s2, 32, end);
+
+      if (i==SIZE_MAX)
+        return 0;
+
+      if (i < 32)
+        {
+          *p1 = s1 + i;
+	  *p2 = s2 + i;
+          return 1;
+        }    
+    }
+   /* Now we read enough bytes to start a loop.  */
+
+  char *s1_loop = PTR_ALIGN_DOWN (s1, 4 * LSIZE);
+  char *s2_loop = s2 - (s1 - s1_loop);
+  int until_cross_page = (4096 - (((uintptr_t) (s2_loop + 4 * LSIZE)) % 4096))\
+                         / (4 * LSIZE);
+
+#ifdef COALIGN_HELP
+  if (((uintptr_t)s2_loop)%32==0)
+    until_cross_page = 1000000;
+#endif
+  while (!BOUND (s1_loop + 4 * LSIZE))
+    {
+      s1_loop += 4 * LSIZE;
+      s2_loop += 4 * LSIZE;
+
+
+      if (until_cross_page == 0)
+        {
+          uintptr_t shift = ((uintptr_t) s2_loop) % (4 * LSIZE);
+          if (found_in_long_bytes (s1_loop - shift + 0 * LSIZE, 
+                                   s2_loop - shift + 0 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 1 * LSIZE, 
+                                   s2_loop - shift + 1 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 2 * LSIZE, 
+                                   s2_loop - shift + 2 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop - shift + 3 * LSIZE, 
+                                   s2_loop - shift + 3 * LSIZE, p1, p2))
+            return 1;
+
+          until_cross_page = 4096 / (4 * LSIZE);
+          if (BOUND (s1_loop + 4 * LSIZE - shift))
+            return 0;
+        }
+
+      until_cross_page--;
+
+      lptr1 = (const unsigned long int *) (s1_loop + 0 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 0 * LSIZE);
+      mask = EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 1 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 1 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 2 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 2 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+      lptr1 = (const unsigned long int *) (s1_loop + 3 * LSIZE);
+      lptr2 = (const unsigned long int *) (s2_loop + 3 * LSIZE);
+      mask |= EXPRESSION (*lptr1, *lptr2);
+
+      if (mask)
+        {
+          if (found_in_long_bytes (s1_loop + 0 * LSIZE, s2_loop + 0 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop + 1 * LSIZE, s2_loop + 1 * LSIZE, p1, p2))
+            return 1;
+          if (found_in_long_bytes (s1_loop + 2 * LSIZE, s2_loop + 2 * LSIZE, p1, p2))
+            return 1;
+
+          found_in_long_bytes (s1_loop + 3 * LSIZE, s2_loop + 3 * LSIZE, p1, p2);
+          return 1;
+        }
+    }
+ return 0;
+}
diff --git a/string/strcmp.c b/string/strcmp.c
index 4d4c044..c1d4c22 100644
--- a/string/strcmp.c
+++ b/string/strcmp.c
@@ -16,28 +16,37 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-
 #undef strcmp
 
 /* Compare S1 and S2, returning less than, equal to or
    greater than zero if S1 is lexicographically less than,
    equal to or greater than S2.  */
+
+#include "string/common.h"
+#define EXPRESSION(c1, c2) (c1 ^ c2) | contains_zero (c2)
+
+static __always_inline
+size_t 
+byte_loop(char *x, char *y, size_t n, char *end)
+{
+  size_t i;
+  for (i = 0; i < n; i++)
+    if (x[i] == '\0' || x[i] != y[i])
+      return i;
+
+  return n;
+}
+
+#include "string/diff_skeleton.h"
+
 int
-strcmp (const char *p1, const char *p2)
+strcmp (const char *s1_start, const char *s2_start)
 {
-  const unsigned char *s1 = (const unsigned char *) p1;
-  const unsigned char *s2 = (const unsigned char *) p2;
-  unsigned char c1, c2;
-
-  do
-    {
-      c1 = (unsigned char) *s1++;
-      c2 = (unsigned char) *s2++;
-      if (c1 == '\0')
-	return c1 - c2;
-    }
-  while (c1 == c2);
-
-  return c1 - c2;
+  unsigned char *p1 = (unsigned char *) s1_start;
+  unsigned char *p2 = (unsigned char *) s2_start;
+
+  diff_skeleton ((char **) &p1, (char **) &p2, NULL); 
+
+  return *p1 - *p2;
 }
 libc_hidden_builtin_def (strcmp)
diff --git a/string/strncmp.c b/string/strncmp.c
index 2a1137a..4c4e9f7 100644
--- a/string/strncmp.c
+++ b/string/strncmp.c
@@ -16,59 +16,55 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <string.h>
-#include <memcopy.h>
 
 #undef strncmp
 
-#ifndef STRNCMP
-#define STRNCMP strncmp
-#endif
+/* Compare S1 and S2, returning less than, equal to or
+   greater than zero if S1 is lexicographically less than,
+   equal to or greater than S2.  */
 
-/* Compare no more than N characters of S1 and S2,
-   returning less than, equal to or greater than zero
-   if S1 is lexicographically less than, equal to or
-   greater than S2.  */
-int
-STRNCMP (const char *s1, const char *s2, size_t n)
-{
-  unsigned char c1 = '\0';
-  unsigned char c2 = '\0';
+#include "string/common.h"
+#define EXPRESSION(c1, c2) (c1 ^ c2) | contains_zero (c2)
+#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end)
 
-  if (n >= 4)
+static __always_inline
+size_t 
+byte_loop(char *x, char *y, size_t c, char *end)
+{
+  size_t i;
+  for (i = 0; i < c; i++)
     {
-      size_t n4 = n >> 2;
-      do
-	{
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	  c1 = (unsigned char) *s1++;
-	  c2 = (unsigned char) *s2++;
-	  if (c1 == '\0' || c1 != c2)
-	    return c1 - c2;
-	} while (--n4 > 0);
-      n &= 3;
+      if (x + i == end)
+        return SIZE_MAX;
+      if (x[i] == '\0' || x[i] != y[i])
+        return i;
     }
 
-  while (n > 0)
+  return c;
+}
+
+#include "string/diff_skeleton.h"
+
+int
+strncmp (const char *s1_start, const char *s2_start, size_t n)
+{
+  unsigned char *p1 = (unsigned char *) s1_start;
+  unsigned char *p2 = (unsigned char *) s2_start;
+  char *end = (char *) (((uintptr_t) p1) + n);
+  if ((uintptr_t) end <= (uintptr_t) p1)
     {
-      c1 = (unsigned char) *s1++;
-      c2 = (unsigned char) *s2++;
-      if (c1 == '\0' || c1 != c2)
-	return c1 - c2;
-      n--;
+      if (n == 0)
+        return 0;
+      end = (char *) UINTPTR_MAX;
     }
 
-  return c1 - c2;
-}
+  if (!diff_skeleton ((char **) &p1, (char **) &p2, end))
+    return 0;
 
-libc_hidden_builtin_def (STRNCMP)
+  if (BOUND (p1))
+    return 0;
+
+
+  return *p1 - *p2;
+}
+libc_hidden_builtin_def (strncmp)

[PATCH 6/*] Generic string function optimization: strcasestr

[Ondřej Bílka]

Hi,

Here I made wrong assumption for long time that prevented me to see
optimization in strcasestr. Now I realized that looking for leading pair
would likely work. I though that it would be necessary to construct
table that assigns to each characters list of characters in same
equivalence class.

I don't have to do that if like in strchr will check if its ascii. Then
I could approximate toupper(x) = toupper(c) by expression 
(x == toupper (c)) | (x == tolower (c)) | (x > 128)
which is easily evaluable in parallel, then and it with shifted
expression for second character.

I added it now just as simple heuristic, a more buy-or-rent approach
will follow in next patch.

I also needed to remove test/bench-strcasestr as I need locale check for
ascii-compatibility of towlower map.

Comments?

	* benchtests/bench-strcasestr.c: Remove simple_strcasestr.
	* string/test-strcasestr.c: Likewise.
	* string/skeleton.h: Customize cmask parameter with CMASK_PARAM macro
	* string/strcasestr.c: Optimize by fast search of leading digraph.

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/skeleton.h b/string/skeleton.h
index 26f2d9f..74d4b9f 100644
--- a/string/skeleton.h
+++ b/string/skeleton.h
@@ -31,9 +31,17 @@
 #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 unsigned long int cmask
+#endif
+
+
 static __always_inline
 int
-found_in_long_bytes(char *s, unsigned long int cmask, char **result)
+found_in_long_bytes(char *s, CMASK_PARAM_MASK, char **result)
 {
   const unsigned long int *lptr = (const unsigned long int *) s;
   unsigned long int mask = EXPRESSION(*lptr, cmask);
@@ -46,16 +54,21 @@ found_in_long_bytes(char *s, unsigned long int cmask, char **result)
     return 0;
 }
 
+
+
+
 static __always_inline
 char *
-string_skeleton (const char *s_in, int c_in, char *end)
+string_skeleton (const char *s_in, CMASK_PARAM, char *end)
 {
   unsigned long int mask;
   const unsigned long int *lptr;
   char *s = (char *) s_in;
-  unsigned char c = (unsigned char) c_in;
   char *r;
+#ifndef CUSTOM_CMASK
+  unsigned char c = (unsigned char) c_in;
   unsigned long int __attribute__ ((unused)) cmask = c * ones;
+#endif
 
 #if _STRING_ARCH_unaligned
   /* We fetch 32 bytes while not crossing page boundary. 
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 400fab8..7c984c8 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -57,6 +57,37 @@
 #define STRCASESTR __strcasestr
 #endif
 
+#include "string/common.h"
+
+struct cmask
+{
+  unsigned long int l0, u0, l1, u1;
+};
+#define CUSTOM_CMASK
+#define CMASK_PARAM struct cmask cmask
+
+#define EXPRESSION(x, cmask) (\
+ ( contains_zero ((x >> 8) ^ cmask.l0) \
+   | contains_zero ((x >> 8) ^ cmask.u0) \
+   | (x >> 8)) \
+   | (1UL << (8 * LSIZE - 1)) \
+ & (contains_zero (x ^ cmask.l1) \
+    | contains_zero (x ^ cmask.l1) \
+    | x))
+#define EXPRESSION_NOCARRY(x,cmask) (\
+ ( contains_zero_nocarry ((x >> 8) ^ cmask.l0) \
+   | contains_zero_nocarry ((x >> 8) ^ cmask.u0) \
+   | (x >> 8)) \
+   | (1UL << (8 * LSIZE - 1)) \
+ & (contains_zero_nocarry (x ^ cmask.l1) \
+    | contains_zero_nocarry (x ^ cmask.l1) \
+    | x))
+
+#include "string/skeleton.h"
+
+#include "../locale/localeinfo.h"
+
+
 
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
@@ -70,6 +101,23 @@ STRCASESTR (const char *haystack_start, const char *needle_start)
   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 (!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;
+      haystack = string_skeleton (haystack + 1, cmask, NULL) - 1;
+    }
+
+
   /* 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)
 
 

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Richard Henderson]

On 05/28/2015 07:29 AM, Ondřej Bílka wrote:
> Here is a new version of skeleton. I added a big endian support. This
> reminded me that when I first wrote it I wanted to use opperations that
> dont cause carry, then forgotten about it. As thats needed only for
> first aligned load or always on big endian you need to supply expression
> twice. one version shouldn't cause carry propagation.
>
>   	* string/common.h: New file.
>   	* string/skeleton.h: Likewise.

I like the idea of this common header for implementing these algorithms. 
Though I'd like to see it not placed in string/, but sysdeps/generic/, so that 
one can provide specialized versions for different targets.

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

We're still using C, not C++.  These are objects requiring static allocation, 
not abstract constants.  Please just use #defines.

> +static __always_inline
> +unsigned long int
> +contains_zero (unsigned long int s)
> +{
> +  return (s - ones) & ~s & high_bits;
> +}

On Alpha or PPC, the target-specific header could use cmpbge or cmpb insns 
respectively.

On armv6t2/armv7, this can be done with the vector saturating addition, uqadd8, 
by adding 0xfe and then inverting.  Of course, this works on other targets for 
which vector insns exist, but on arm uqadd8 works on normal integer registers.

> +#define CROSS_PAGE(x, n) (((uintptr_t) x) % 4096 > 4096 - n)

Certainly different targets would like to override the minimal page size.

> +# ifdef FAST_FFS
> +  return (ffsl (u) - 1) / 8;
> +# else

Why are you stuck on ffs instead of ctz?  The later avoids all the -1 adjustments.

> +    }
> +  else
> +    {
> +#endif
...
> +#if _STRING_ARCH_unaligned
> +    }
> +#endif

Better placement of the first #endif means you don't need the second.


r~

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Thu, May 28, 2015 at 10:48:29AM -0700, Richard Henderson wrote:
> On 05/28/2015 07:29 AM, Ondřej Bílka wrote:
> >Here is a new version of skeleton. I added a big endian support. This
> >reminded me that when I first wrote it I wanted to use opperations that
> >dont cause carry, then forgotten about it. As thats needed only for
> >first aligned load or always on big endian you need to supply expression
> >twice. one version shouldn't cause carry propagation.
> >
> >  	* string/common.h: New file.
> >  	* string/skeleton.h: Likewise.
> 
> I like the idea of this common header for implementing these
> algorithms. Though I'd like to see it not placed in string/, but
> sysdeps/generic/, so that one can provide specialized versions for
> different targets.
>
Will do.

> >+static __always_inline
> >+unsigned long int
> >+contains_zero (unsigned long int s)
> >+{
> >+  return (s - ones) & ~s & high_bits;
> >+}
> 
> On Alpha or PPC, the target-specific header could use cmpbge or cmpb
> insns respectively.
> 
> On armv6t2/armv7, this can be done with the vector saturating
> addition, uqadd8, by adding 0xfe and then inverting.  Of course,
> this works on other targets for which vector insns exist, but on arm
> uqadd8 works on normal integer registers.
> 
> >+# ifdef FAST_FFS
> >+  return (ffsl (u) - 1) / 8;
> >+# else
> 
> Why are you stuck on ffs instead of ctz?  The later avoids all the -1 adjustments.
>
Both comments are correct. We should do it generically and surround
these functions with ifdef to supply arch-specific versions. 

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

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

On Thu, 28 May 2015, Ondřej Bílka wrote:

> Both comments are correct. We should do it generically and surround
> these functions with ifdef to supply arch-specific versions. 

#if, not #ifdef, please, for all architecture choices in these functions.  
The sysdeps/generic version of the header architectures can use to change 
the default choices should have detailed comments on the default 
definitions of all the relevant macros to explain their semantics.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> On Thu, 28 May 2015, Ondřej Bílka wrote:
> 
> > Both comments are correct. We should do it generically and surround
> > these functions with ifdef to supply arch-specific versions. 
> 
> #if, not #ifdef, please, for all architecture choices in these functions.  
> The sysdeps/generic version of the header architectures can use to change 
> the default choices should have detailed comments on the default 
> definitions of all the relevant macros to explain their semantics.
> 
For what purpose? Its pointless except that you would need to have
additional header say precommon.h, then undef and redefine macro when
you want change.

And it doesn't help to catch any errors. If you misspell define then you
will get error with duplicate definition.

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

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

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

> On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > 
> > > Both comments are correct. We should do it generically and surround
> > > these functions with ifdef to supply arch-specific versions. 
> > 
> > #if, not #ifdef, please, for all architecture choices in these functions.  
> > The sysdeps/generic version of the header architectures can use to change 
> > the default choices should have detailed comments on the default 
> > definitions of all the relevant macros to explain their semantics.
> > 
> For what purpose? Its pointless except that you would need to have
> additional header say precommon.h, then undef and redefine macro when
> you want change.

The general principle is that macro uses should be typo-proof.  That means 
avoiding #ifdef, #ifndef and #undef where possible.

The principle of documenting macro semantics applies even if there's a 
good reason typo-proof conventions are problematic in a particular case.  
There should *never* be any sort of architecture hook without clear 
documentation of the semantics of the hook (written from the perspective 
of an architecture maintainer wanting to know how to set the hook for 
their architecture, not from the perspective of the person writing the 
code using the hook).  I always advise writing documentation early in the 
process of developing a patch - the documentation is as important as the 
rest of the code.

> And it doesn't help to catch any errors. If you misspell define then you
> will get error with duplicate definition.

If the code does

#ifdef MACRO

or

#ifndef MACRO

then if an architecture does

#define MCARO

(with or without #undef) that will silently be ignored.

If, instead, the code does

#if MACRO

and there's a sysdeps/generic header that defines MACRO one way, if an 
architecture overrides that header with one that misspells the name, a 
-Wundef warning will be immediately visible (though we still need to fix 
the -Wundef warnings in the testsuite and remove the -Wno-error=undef).

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Fri, May 29, 2015 at 10:42:17AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > On Thu, May 28, 2015 at 08:54:31PM +0000, Joseph Myers wrote:
> > > On Thu, 28 May 2015, Ondřej Bílka wrote:
> > > 
> > > > Both comments are correct. We should do it generically and surround
> > > > these functions with ifdef to supply arch-specific versions. 
> > > 
> > > #if, not #ifdef, please, for all architecture choices in these functions.  
> > > The sysdeps/generic version of the header architectures can use to change 
> > > the default choices should have detailed comments on the default 
> > > definitions of all the relevant macros to explain their semantics.
> > > 
> > For what purpose? Its pointless except that you would need to have
> > additional header say precommon.h, then undef and redefine macro when
> > you want change.
> 
> The general principle is that macro uses should be typo-proof.  That means 
> avoiding #ifdef, #ifndef and #undef where possible.
> 
> The principle of documenting macro semantics applies even if there's a 
> good reason typo-proof conventions are problematic in a particular case.  
> There should *never* be any sort of architecture hook without clear 
> documentation of the semantics of the hook (written from the perspective 
> of an architecture maintainer wanting to know how to set the hook for 
> their architecture, not from the perspective of the person writing the 
> code using the hook).  I always advise writing documentation early in the 
> process of developing a patch - the documentation is as important as the 
> rest of the code.
> 
> > And it doesn't help to catch any errors. If you misspell define then you
> > will get error with duplicate definition.
> 
> If the code does
> 
> #ifdef MACRO
> 
> or
> 
> #ifndef MACRO
> 
> then if an architecture does
> 
> #define MCARO
> 
> (with or without #undef) that will silently be ignored.
> 
> If, instead, the code does
> 
> #if MACRO
> 
> and there's a sysdeps/generic header that defines MACRO one way, if an 
> architecture overrides that header with one that misspells the name, a 
> -Wundef warning will be immediately visible (though we still need to fix 
> the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> 
Joseph, read previous mail before writing. Your suggestion is pointless.

For a code

#ifndef CUSTOM_FOO
int foo()
{
}
#endif

If architecture does
#define CUTSOM_FOO
int foo()
{
}

Then it gets error with redefinition of foo.

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Joseph Myers]

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

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

> > If, instead, the code does
> > 
> > #if MACRO
> > 
> > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > architecture overrides that header with one that misspells the name, a 
> > -Wundef warning will be immediately visible (though we still need to fix 
> > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > 
> Joseph, read previous mail before writing. Your suggestion is pointless.

Which previous mail?  As far as I can tell, your last patch posting adding 
common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>, 
which has a range of within-function #ifdefs (some completely untested, 
e.g. "#  ifdef NEED BITWISE", and all completely undocumented).  Anyway, 
when we have conventions in glibc (such as preferring #if to #ifdef) you 
should follow them unless there is a strong justification for doing 
otherwise (presented in every patch submission).  Likewise, even early 
patches should follow normal glibc formatting conventions.

Throwing out a series of untested, undocumented patches is not a helpful 
way of proposing changes to glibc.  I strongly recommend, in any 
complicated case such as this, that:

(a) each patch submission is self-contained - has the full self-contained 
write-up of the patch itself with the rationale for the patch and all the 
choices made, that would go in the commit message, followed by the 
description of changes from the previous version, rather than requiring a 
trail of previous messages to be followed to get the full rationale; and

(b) the documentation is more important than the code (write first for 
humans to read, only then for computers to execute); documenting the 
interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
before any patches are sent to the list, not an afterthought, and the same 
applies to each internal function and macro in the code, even those that 
are not interfaces for architectures to reimplement.

> For a code
> 
> #ifndef CUSTOM_FOO
> int foo()
> {
> }
> #endif
> 
> If architecture does
> #define CUTSOM_FOO
> int foo()
> {
> }
> 
> Then it gets error with redefinition of foo.

Or you could avoid making readers think about whether the #ifndef is OK in 
a particular case by simply following normal glibc practices and have a 
sysdeps/generic/string-foo.h header that has a default definition with a 
careful comment explaining the semantics, and then architectures can have 
their own version to replace it as needed; no macros needed at all.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH 1/* v3] Generic string function optimization: Add skeleton

[Ondřej Bílka]

On Fri, May 29, 2015 at 11:38:51AM +0000, Joseph Myers wrote:
> On Fri, 29 May 2015, Ondřej Bílka wrote:
> 
> > > If, instead, the code does
> > > 
> > > #if MACRO
> > > 
> > > and there's a sysdeps/generic header that defines MACRO one way, if an 
> > > architecture overrides that header with one that misspells the name, a 
> > > -Wundef warning will be immediately visible (though we still need to fix 
> > > the -Wundef warnings in the testsuite and remove the -Wno-error=undef).
> > > 
> > Joseph, read previous mail before writing. Your suggestion is pointless.
> 
> Which previous mail?  As far as I can tell, your last patch posting adding 
> common.h is <https://sourceware.org/ml/libc-alpha/2015-05/msg00751.html>,

This one. I already explained that for using if you would need
additional header to be able to undefine macros.

https://sourceware.org/ml/libc-alpha/2015-05/msg00812.html


> 
> (a) each patch submission is self-contained - has the full self-contained 
> write-up of the patch itself with the rationale for the patch and all the 
> choices made, that would go in the commit message, followed by the 
> description of changes from the previous version, rather than requiring a 
> trail of previous messages to be followed to get the full rationale; and
>
Almost nobody does that for good reason, see that most v2 on lists are
shorter than previous. You should write mostly what changed. Sure, I
could copy-paste three pages from original mail with rationale but most
readers would skip it as its duplicate and would skip changes made into
it.

I could make recapitulation once per while but for incremental
improvements its best to keep just increments.
 
> (b) the documentation is more important than the code (write first for 
> humans to read, only then for computers to execute); documenting the 
> interfaces (such as FAST_CLZ and NEED_BITWISE) should be a very early step 
> before any patches are sent to the list, not an afterthought, and the same 
> applies to each internal function and macro in the code, even those that 
> are not interfaces for architectures to reimplement.
> 
Thats not completely true as purpose of this is get every bit of
performance before you need to go into assembly. It depends how
technical my interface will become, with strcmp I found that I need
handle another primitive. As documentation its better to have good
overview than overly verbose one. Some macros there are just there for
optimizer to try both branches and select better one.


> > For a code
> > 
> > #ifndef CUSTOM_FOO
> > int foo()
> > {
> > }
> > #endif
> > 
> > If architecture does
> > #define CUTSOM_FOO
> > int foo()
> > {
> > }
> > 
> > Then it gets error with redefinition of foo.
> 
> Or you could avoid making readers think about whether the #ifndef is OK in 
> a particular case by simply following normal glibc practices and have a 
> sysdeps/generic/string-foo.h header that has a default definition with a 
> careful comment explaining the semantics, and then architectures can have 
> their own version to replace it as needed; no macros needed at all.
> 
First its too typo-prone. Architecture maintainer would create
string_foo.h file and never notice that it was silently ignored.


Then why didn't you said that directly? That saves time instead
suggesting if when you mean separate file. Thats correct as there are
several variants and you need to run benchmark to select correct one.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Wed, Aug 12, 2015 at 04:58:20PM +0000, Joseph Myers wrote:
> On Wed, 12 Aug 2015, Ondřej Bílka wrote:
> 
> > On Wed, Aug 12, 2015 at 02:47:46PM +0100, Wilco Dijkstra wrote:
> > > > Ondřej Bílka wrote: 
> > > > On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > > > > > Ondřej Bílka wrote:
> > > > > > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > > > > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> > > 
> > > > Then could you review a generic patch that I am about to ping?
> > > 
> > > Do you mean https://sourceware.org/ml/libc-alpha/2015-08/msg00443.html?
> > > I don't see a patch attached...
> > >
> > I wrote it long ago, here:
> > https://sourceware.org/ml/libc-alpha/2013-10/msg00201.html 
> 
> If a patch was posted so long ago that it isn't in patchwork, it 
> effectively doesn't exist for reviewers.  That means anything before 
> 2014-03-14 (the oldest entry in patchwork).
> 
> It's *also* the case that we have too many unreviewed patches in patchwork 
> and not enough reviewers; I don't have any good solutions to that issue.
>
Yes, its mainly that I ping patches that I think important so number of
patches that work but I don't ping because there is something more
important increases. 
 
> It's *also* the case that any frequent contributors should be cleaning up 
> their own patch state in patchwork so that superseded and committed 
> patches are marked as such and reviewers can more readily find the most 
> recent version of a patch.  You have a particularly large number of 
> patches shown there including what look like many successive variants of 
> the same patch.  As the submitter you're best placed to know which patches 
> have been completely superseded / committed; please clean up the entries 
> for your patches so that exactly one entry shows for the most recent 
> version of each patch that has not been superseded / committed / rejected, 
> and no entries show for superseded / committed rejected patch because they 
> have been marked as such.
> 
I do that semiregularly but didn't have time recently.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Joseph Myers]

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

On Wed, 12 Aug 2015, Ondřej Bílka wrote:

> On Wed, Aug 12, 2015 at 02:47:46PM +0100, Wilco Dijkstra wrote:
> > > Ondřej Bílka wrote: 
> > > On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > > > > Ondřej Bílka wrote:
> > > > > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > > > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> > 
> > > Then could you review a generic patch that I am about to ping?
> > 
> > Do you mean https://sourceware.org/ml/libc-alpha/2015-08/msg00443.html?
> > I don't see a patch attached...
> >
> I wrote it long ago, here:
> https://sourceware.org/ml/libc-alpha/2013-10/msg00201.html 

If a patch was posted so long ago that it isn't in patchwork, it 
effectively doesn't exist for reviewers.  That means anything before 
2014-03-14 (the oldest entry in patchwork).

It's *also* the case that we have too many unreviewed patches in patchwork 
and not enough reviewers; I don't have any good solutions to that issue.

It's *also* the case that any frequent contributors should be cleaning up 
their own patch state in patchwork so that superseded and committed 
patches are marked as such and reviewers can more readily find the most 
recent version of a patch.  You have a particularly large number of 
patches shown there including what look like many successive variants of 
the same patch.  As the submitter you're best placed to know which patches 
have been completely superseded / committed; please clean up the entries 
for your patches so that exactly one entry shows for the most recent 
version of each patch that has not been superseded / committed / rejected, 
and no entries show for superseded / committed rejected patch because they 
have been marked as such.

As stated at 
<https://sourceware.org/glibc/wiki/Patch%20Review%20Workflow>, Siddhesh or 
Carlos can give you write access to patchwork if you don't already have 
it.

-- 
Joseph S. Myers
joseph@codesourcery.com

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Wed, Aug 12, 2015 at 02:47:46PM +0100, Wilco Dijkstra wrote:
> > > Ondřej Bílka wrote:
> > > On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > > > > Ondřej Bílka wrote:
> > > > > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > > > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> >
> > > Then could you review a generic patch that I am about to ping?
> >
> > Do you mean https://sourceware.org/ml/libc-alpha/2015-08/msg00443.html?
> > I don't see a patch attached...
> >
> I wrote it long ago, here:
> https://sourceware.org/ml/libc-alpha/2013-10/msg00201.html

How often is strrchr used to search for zero? What about this alternative?

size_t n = strlen (s);
if (c == 0) 
  return s + n;
return __memrchr (s, c, n); 

> > Still bench-strrchr.c needs to be updated to use realistic inputs so people can
> > optimize for the right dataset.
> 
> depends how you do that, you could now use as benchmark
> 
> ./testrun.sh dryrun/bin/bench_strrchr -u
> 
> I could sync benchmarks to use that benchmark, it depends on preference
> if we use that or keep it as separate project.

As of today the benchtests are still the official benchmarks. So if the patch
doesn't show a gain on the existing bench-strrchr.c, you need to add extra
inputs that show why this is a good idea. We don't need a full trace, just
a few typical cases plus maybe your worst-case example.

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Wed, Aug 12, 2015 at 02:47:46PM +0100, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote: 
> > On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > > > Ondřej Bílka wrote:
> > > > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> 
> > Then could you review a generic patch that I am about to ping?
> 
> Do you mean https://sourceware.org/ml/libc-alpha/2015-08/msg00443.html?
> I don't see a patch attached...
>
I wrote it long ago, here:
https://sourceware.org/ml/libc-alpha/2013-10/msg00201.html 

> > > > > So I'm not sure which point you are making but unless you know
> > > > > something about the average distribution of the characters in the
> > > > > strrchr() string to suggest they are likely to occur in the last third
> > > > > of the string more than 50% of the time, I don't think I'm convinced.
> > >
> > > So what we really need is better statistics on strrchr and friends. Looking
> > > at GLIBC sources, it seems that >90% search for '/' in a path.
> > >
> > > Do you have actual stats for strrchr Ondřej? That would really help solving
> > > this issue. What I'd like to know is:
> > >
> > > 1. Average length of the strings
> > > 2. What percentage fails to match
> > > 3. Average number of matches per string if it matches at least once
> > > 4. Average relative position within string of last match
> > >
> > > With that info we could create a simple patch for bench-strrchr.c to make
> > > it use realistic inputs. Then based on that we can fix the generic code and
> > > let maintainers further tune their optimized implementations if they do not
> > > beat the generic code.
> > >
> > 
> > Yes, I used dryrun for that. You don't need to model microbenchmark from
> > that data which could go wrong in several ways but use dryrun to
> > directly replay these.
> 
> Still bench-strrchr.c needs to be updated to use realistic inputs so people can
> optimize for the right dataset. 

depends how you do that, you could now use as benchmark

./testrun.sh dryrun/bin/bench_strrchr -u 

I could sync benchmarks to use that benchmark, it depends on preference
if we use that or keep it as separate project.

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote: 
> On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > > Ondřej Bílka wrote:
> > > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:

> Then could you review a generic patch that I am about to ping?

Do you mean https://sourceware.org/ml/libc-alpha/2015-08/msg00443.html?
I don't see a patch attached...

> > > > So I'm not sure which point you are making but unless you know
> > > > something about the average distribution of the characters in the
> > > > strrchr() string to suggest they are likely to occur in the last third
> > > > of the string more than 50% of the time, I don't think I'm convinced.
> >
> > So what we really need is better statistics on strrchr and friends. Looking
> > at GLIBC sources, it seems that >90% search for '/' in a path.
> >
> > Do you have actual stats for strrchr Ondřej? That would really help solving
> > this issue. What I'd like to know is:
> >
> > 1. Average length of the strings
> > 2. What percentage fails to match
> > 3. Average number of matches per string if it matches at least once
> > 4. Average relative position within string of last match
> >
> > With that info we could create a simple patch for bench-strrchr.c to make
> > it use realistic inputs. Then based on that we can fix the generic code and
> > let maintainers further tune their optimized implementations if they do not
> > beat the generic code.
> >
> 
> Yes, I used dryrun for that. You don't need to model microbenchmark from
> that data which could go wrong in several ways but use dryrun to
> directly replay these.

Still bench-strrchr.c needs to be updated to use realistic inputs so people can
optimize for the right dataset. 

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Tue, Jul 28, 2015 at 02:07:35PM +0100, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote:
> > On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> > > >Best example is strrchr where almost all architectures got it wrong
> > > >first time until I tell them otherwise. Problem is that they calculate
> > > >position of byte at each iteration instead just at end which is
> > > >ineffective. Now tile and powerpc have this problem. My proposed
> > > >alternative
> > > >
> > > >return memrchr (s, c, strlen (s) + 1);
> > > >
> > > >would beat these on suitable inputs.
> > >
> > > Your comment and your code snippet don't really match, so can I ask
> > > you to elucidate a little what your concern is?
> > >
> > It is mix of two concerns, so its both First a snippet was there
> > mainly to show that generic code could be faster. I mentioned that
> > it applies for some inputs, as it would need larger inputs than usual
> > to overcome initialization and call overhead of assembly one.
> 
> I believe the above sequence is the right one to use in the generic code,
> especially when you have an optimized memrchr that scans backwards
> (simpler inner loop as you quit at first match). The current generic
> implementation repeatedly calls strchr so will be very slow if there
> are multiple matches.
>
Then could you review a generic patch that I am about to ping?
 
> > > So I'm not sure which point you are making but unless you know
> > > something about the average distribution of the characters in the
> > > strrchr() string to suggest they are likely to occur in the last third
> > > of the string more than 50% of the time, I don't think I'm convinced.
> 
> So what we really need is better statistics on strrchr and friends. Looking
> at GLIBC sources, it seems that >90% search for '/' in a path. 
> 
> Do you have actual stats for strrchr Ondřej? That would really help solving
> this issue. What I'd like to know is:
> 
> 1. Average length of the strings
> 2. What percentage fails to match
> 3. Average number of matches per string if it matches at least once
> 4. Average relative position within string of last match
> 
> With that info we could create a simple patch for bench-strrchr.c to make
> it use realistic inputs. Then based on that we can fix the generic code and
> let maintainers further tune their optimized implementations if they do not
> beat the generic code.
> 

Yes, I used dryrun for that. You don't need to model microbenchmark from
that data which could go wrong in several ways but use dryrun to
directly replay these.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Chris Metcalf]

On 07/27/2015 07:22 PM, Ondřej Bílka wrote:
> On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
>> On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
>>> Best example is strrchr where almost all architectures got it wrong
>>> first time until I tell them otherwise. Problem is that they calculate
>>> position of byte at each iteration instead just at end which is
>>> ineffective. Now tile and powerpc have this problem. My proposed
>>> alternative
>>>
>>> return memrchr (s, c, strlen (s) + 1);
>>>
>>> would beat these on suitable inputs.
> I didn't say that a generic is optimal only that it avoids problem with
> tile implementation on some inputs.
>
> A problem is that your analysis is incomplete. It assumes that character
> occurs rarely which doesn't have to be case. A forward scan could be
> very expensive if character has probability 1/16 which causes branch
> misprediction each second iteration.

True that more frequent occurrence leads to a high likelihood of
the string being in the final 1/3rd of the string, which as I said
earlier does mean strlen + memrchr is faster.

Note that tilegx does not do branch prediction dynamically;
the compiler just provides static branch prediction.

> A problem that I described in english is that this isn't inner loop as
> you jump from it each second iteration when c probability is 1/16.

True, and you're right that by restructuring the loop I can
get it to run with conditional moves and only a single loop exit:

string/../sysdeps/tile/tilegx/strrchr.c:58
   38:	{ cmovnez r0, r11, r10 ; addi r10, r10, 8 }
   40:	{ cmovnez r13, r11, r11 ; ld r12, r10 }
string/../sysdeps/tile/tilegx/strrchr.c:46
   48:	{ v1cmpeqi r14, r12, 0 ; v1cmpeq r11, r12, r15 }
string/../sysdeps/tile/tilegx/strrchr.c:48
   50:	{ beqzt r14, 38 <strrchr+0x38> }


With the branch predicted true we will definitely run at
0.625 cycles/byte all the way to the end of the string, so that's
probably a good micro-optimization.

> For example if application uses strrchr to find last / in path name then
> its likely that it would be among last 8 characters and occurs
> frequently previously.

I think this use case is pretty interesting.  As Wilco says, if we can
update the benchtests to show more such than it is probably worth
machine maintainers' time to improve their algorithms.  Or switch
to a framework where we can do word-at-a-time loads with the
machine maintainers just providing the primitives for SIMD ops
and the like (like Linux's <asm/word-at-a-time.h>).

> This mainly depends on size of string, if you assume that each character
> has fixed probability it happens for sufficiently large strings.
>
> A tricky part of writing these is that inputs are short so you need to
> write separate header to get better performance.

What do you mean by "separate header" here?

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

Re: [PATCH 4/*] Generic string memchr and strnlen

[Adhemerval Zanella]

On 27-07-2015 22:00, Ondřej Bílka wrote:
> On Mon, Jul 27, 2015 at 03:37:28PM -0300, Adhemerval Zanella wrote:
>>> Best example is strrchr where almost all architectures got it wrong
>>> first time until I tell them otherwise. Problem is that they calculate
>>> position of byte at each iteration instead just at end which is
>>> ineffective. Now tile and powerpc have this problem. My proposed
>>> alternative
>>>
>>> return memrchr (s, c, strlen (s) + 1);
>>>
>>> would beat these on suitable inputs. I don't know if in practice as
>>> there is extra strlen call.
>>
>> You do a lot of assumptions and I doubt very much that it will be faster
>> on every input.  Assuming assembly implementations (no function call) I
>> do see that this could be faster for long string with the character being
>> found in the end of the string, but I see it could potentially slower
>> if it searches large strings with character in start/middle.  It will
>> really depends in which will be the input char size and distribution.
>>
> No, I don't make any assumptions. I know that performance of these could
> be terrible. For normal benchtest you get following.
> 
>         simple_strrchr  __strrchr_power7        __strrchr_ppc
> Length 2048, alignment in bytes  0:     1334.92 114.344 182.391
> Length  256, alignment in bytes  1:     173.266 22.5625 35.4375
> 
> If I change it to call strrchr("aaaa...aaaa",'a') I get following:
> 
> Length 2048, alignment in bytes  0:     1602    578.984 1555.7
> Length 2048, alignment in bytes  0:     1332.17 485.922 8393.11
> Length  256, alignment in bytes  1:     115.25  63.9531 1018.58
> 
> And when I change benchtest generation to 
> 
>  for (i = 0; i < len; ++i)
>    buf[align + i] = 1 + ((unsigned)(random())) % 8;
> 
> I get following:
> 
> Length 2048, alignment in bytes  0:     1602    578.984 1555.7
> Length 2048, alignment in bytes  1:     1724.23 581.375 1789.81
> Length  256, alignment in bytes  1:     186.875 57.9375 183.5
> 
> 
> where strlen+memrchr are definitely faster. Similar inputs could happen
> if you search for last '/' at paths as their frequency is typically
> less than 1/8.

Regarding this I agree with Wilco [1] remarks and let's continue on that
sub-thread.

[1] https://sourceware.org/ml/libc-alpha/2015-07/msg00937.html

> 
>  
>>>
>>> Second would be strcpy and strncpy where assembly implementations of
>>> some rchitectures look dubious and you could beat these with memcpy
>>> call + strlen. I know definitely about powerpc power7 and powerppc
>>> implementations.
>>
>> >From previous discussion the idea of power7 strcpy/strncpy is to not use
>> unaligned read/writes due architecture constraints.  And again you do
>> a lot of assumptions: I doubt that using power7 memcpy/strlen (which also
>> do only aligned accesses) would be faster than current strcpy/strncpy.
>> It could be the case for large strings, where memcpy will gain because the
>> use of VSX instructions; but even I would like some data before taking
>> conclusions.
>>
> No, I don't make assumptions, just see results. These clearly show that
> implementation is flawed. If I add following implementation and
> ifunc_impl_list and change simple_strcpy to one from string/strcpy.c
> then I get following which clearly shows that current implementation is
> bad, with inlining strlen you could probably decrease treshold to 32 bytes.
> 
> +extern __typeof (memcpy) __memcpy_power7 attribute_hidden;
> +extern __typeof (strlen) __strlen_power7 attribute_hidden;
> +
> +
> +char *__strcpy_power7b (char *dest, const char *src)
> +{
> +  return __memcpy_power7 (dest, src, __strlen_power7 (src) + 1);
> +}
> +
> +extern __typeof (memcpy) __memcpy_ppc attribute_hidden;
> +extern __typeof (strlen) __strlen_ppc attribute_hidden;
> +
> +
> +char *__strcpy_ppcb (char *dest, const char *src)
> +{
> +  return __memcpy_ppc (dest, src, __strlen_ppc (src) + 1);
> +}
> +
> +
> 
> 
>                simple_strcpy   __strcpy_power7 __strcpy_power7b __strcpy_ppcb   __strcpy_ppc
> 
> Length   15, alignments in bytes  0/ 7: 15.8438 9       11.8281 15.3125	10.25
> Length   15, alignments in bytes  7/ 0: 9       8.25    8.09375 9.09375	8.1875
> Length   16, alignments in bytes  0/ 0: 9       5       8.25    8.6875	4.85938
> Length   16, alignments in bytes  7/ 2: 9.53125 9.75    8.26562 9.6875	7.85938
> Length   32, alignments in bytes  0/ 0: 11.4062 4.79688 9.32812 10.7656 5.03125
> Length   32, alignments in bytes  6/ 4: 11.3125 11.2344 10      12.625	16.9219
> Length   64, alignments in bytes  0/ 0: 12.25   6.75    11.2656 13	7.28125
> Length   64, alignments in bytes  5/ 6: 25.4375 17.4844 24.5    25.0625 30.3125
> Length  128, alignments in bytes  0/ 0: 15.5938 8.96875 14.5    17.1562 13
> Length  128, alignments in bytes  4/ 0: 16.5    22.4219 15      22.75	22.7188
> Length  256, alignments in bytes  0/ 0: 20.3438 20      19.0781 27.1875 21.9531
> Length  256, alignments in bytes  3/ 2: 23.0781 40.5    22.1875 41.5	97.5625
> Length  512, alignments in bytes  0/ 0: 35.3906 33.7031 34.8594 44.6094 37.5
> Length  512, alignments in bytes  2/ 4: 58.0625 64.2344 57.4531 78.5	1897.17
> Length 1024, alignments in bytes  0/ 0: 61.2812 61.5156 60.6406 75	69.75
> Length 1024, alignments in bytes  1/ 6: 82.5    118.266 81.4219 128.312 966.078

I checked and your suggestion and it does seems better in mostly of inputs.

>  
>>>
>>> Third would be strcmp et al, there writing a correct loop is very tricky
>>> and only mine x64 implementation does it.
>>>
>>>>> And as I read assembly it isn't particulary well optimized for most
>>>>> architectures. In most cases code looks like you would take current
>>>>> generic implementation and ran gcc -S. For example most assemlbly
>>>>> implementations don't do loop unrolling.
>>>>
>>>> Loop unrolling doesn't always increase performance.
>>>>
>>> But often does by allowing other optimizations like having only one
>>> addition instead four, you could do four loads in parallel without
>>> worrying that speculative load would fault etc.
>>>
>>> While it doesn't have to improve performance in most cases it does.
>>
>> It should be address case by case, like point out specific assembly
>> implementations where you think can be benefits from some loop
>> unrolling.
> 
> Its basically every implementation, question is if its worth code size
> increase. I want to test my four times unrolled strlen versus archs that
> must do search just using arithmetic without bytewise equality
> instruction.
> 

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> > On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> > >Best example is strrchr where almost all architectures got it wrong
> > >first time until I tell them otherwise. Problem is that they calculate
> > >position of byte at each iteration instead just at end which is
> > >ineffective. Now tile and powerpc have this problem. My proposed
> > >alternative
> > >
> > >return memrchr (s, c, strlen (s) + 1);
> > >
> > >would beat these on suitable inputs.
> >
> > Your comment and your code snippet don't really match, so can I ask
> > you to elucidate a little what your concern is?
> >
> It is mix of two concerns, so its both First a snippet was there
> mainly to show that generic code could be faster. I mentioned that
> it applies for some inputs, as it would need larger inputs than usual
> to overcome initialization and call overhead of assembly one.

I believe the above sequence is the right one to use in the generic code,
especially when you have an optimized memrchr that scans backwards
(simpler inner loop as you quit at first match). The current generic
implementation repeatedly calls strchr so will be very slow if there
are multiple matches.

> For example if application uses strrchr to find last / in path name then
> its likely that it would be among last 8 characters and occurs
> frequently previously.
> 
> Here you would need a conditional move instead of branch to avoid that
> issue.

Agreed - the AArch64 implementation does that. It's hard to say what
is best if you don't have such an instruction - it'll depend on the
statistics of real inputs and the relative performance of strlen+partial 
backwards memrchr scan vs a full forward strrchr scan.

> > So I'm not sure which point you are making but unless you know
> > something about the average distribution of the characters in the
> > strrchr() string to suggest they are likely to occur in the last third
> > of the string more than 50% of the time, I don't think I'm convinced.

So what we really need is better statistics on strrchr and friends. Looking
at GLIBC sources, it seems that >90% search for '/' in a path. 

Do you have actual stats for strrchr Ondřej? That would really help solving
this issue. What I'd like to know is:

1. Average length of the strings
2. What percentage fails to match
3. Average number of matches per string if it matches at least once
4. Average relative position within string of last match

With that info we could create a simple patch for bench-strrchr.c to make
it use realistic inputs. Then based on that we can fix the generic code and
let maintainers further tune their optimized implementations if they do not
beat the generic code.

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Mon, Jul 27, 2015 at 03:37:28PM -0300, Adhemerval Zanella wrote:
> > Best example is strrchr where almost all architectures got it wrong
> > first time until I tell them otherwise. Problem is that they calculate
> > position of byte at each iteration instead just at end which is
> > ineffective. Now tile and powerpc have this problem. My proposed
> > alternative
> > 
> > return memrchr (s, c, strlen (s) + 1);
> > 
> > would beat these on suitable inputs. I don't know if in practice as
> > there is extra strlen call.
> 
> You do a lot of assumptions and I doubt very much that it will be faster
> on every input.  Assuming assembly implementations (no function call) I
> do see that this could be faster for long string with the character being
> found in the end of the string, but I see it could potentially slower
> if it searches large strings with character in start/middle.  It will
> really depends in which will be the input char size and distribution.
>
No, I don't make any assumptions. I know that performance of these could
be terrible. For normal benchtest you get following.

        simple_strrchr  __strrchr_power7        __strrchr_ppc
Length 2048, alignment in bytes  0:     1334.92 114.344 182.391
Length  256, alignment in bytes  1:     173.266 22.5625 35.4375

If I change it to call strrchr("aaaa...aaaa",'a') I get following:

Length 2048, alignment in bytes  0:     1602    578.984 1555.7
Length 2048, alignment in bytes  0:     1332.17 485.922 8393.11
Length  256, alignment in bytes  1:     115.25  63.9531 1018.58

And when I change benchtest generation to 

 for (i = 0; i < len; ++i)
   buf[align + i] = 1 + ((unsigned)(random())) % 8;

I get following:

Length 2048, alignment in bytes  0:     1602    578.984 1555.7
Length 2048, alignment in bytes  1:     1724.23 581.375 1789.81
Length  256, alignment in bytes  1:     186.875 57.9375 183.5


where strlen+memrchr are definitely faster. Similar inputs could happen
if you search for last '/' at paths as their frequency is typically
less than 1/8.

 
> > 
> > Second would be strcpy and strncpy where assembly implementations of
> > some rchitectures look dubious and you could beat these with memcpy
> > call + strlen. I know definitely about powerpc power7 and powerppc
> > implementations.
> 
> >From previous discussion the idea of power7 strcpy/strncpy is to not use
> unaligned read/writes due architecture constraints.  And again you do
> a lot of assumptions: I doubt that using power7 memcpy/strlen (which also
> do only aligned accesses) would be faster than current strcpy/strncpy.
> It could be the case for large strings, where memcpy will gain because the
> use of VSX instructions; but even I would like some data before taking
> conclusions.
>
No, I don't make assumptions, just see results. These clearly show that
implementation is flawed. If I add following implementation and
ifunc_impl_list and change simple_strcpy to one from string/strcpy.c
then I get following which clearly shows that current implementation is
bad, with inlining strlen you could probably decrease treshold to 32 bytes.

+extern __typeof (memcpy) __memcpy_power7 attribute_hidden;
+extern __typeof (strlen) __strlen_power7 attribute_hidden;
+
+
+char *__strcpy_power7b (char *dest, const char *src)
+{
+  return __memcpy_power7 (dest, src, __strlen_power7 (src) + 1);
+}
+
+extern __typeof (memcpy) __memcpy_ppc attribute_hidden;
+extern __typeof (strlen) __strlen_ppc attribute_hidden;
+
+
+char *__strcpy_ppcb (char *dest, const char *src)
+{
+  return __memcpy_ppc (dest, src, __strlen_ppc (src) + 1);
+}
+
+


               simple_strcpy   __strcpy_power7 __strcpy_power7b __strcpy_ppcb   __strcpy_ppc

Length   15, alignments in bytes  0/ 7: 15.8438 9       11.8281 15.3125	10.25
Length   15, alignments in bytes  7/ 0: 9       8.25    8.09375 9.09375	8.1875
Length   16, alignments in bytes  0/ 0: 9       5       8.25    8.6875	4.85938
Length   16, alignments in bytes  7/ 2: 9.53125 9.75    8.26562 9.6875	7.85938
Length   32, alignments in bytes  0/ 0: 11.4062 4.79688 9.32812 10.7656 5.03125
Length   32, alignments in bytes  6/ 4: 11.3125 11.2344 10      12.625	16.9219
Length   64, alignments in bytes  0/ 0: 12.25   6.75    11.2656 13	7.28125
Length   64, alignments in bytes  5/ 6: 25.4375 17.4844 24.5    25.0625 30.3125
Length  128, alignments in bytes  0/ 0: 15.5938 8.96875 14.5    17.1562 13
Length  128, alignments in bytes  4/ 0: 16.5    22.4219 15      22.75	22.7188
Length  256, alignments in bytes  0/ 0: 20.3438 20      19.0781 27.1875 21.9531
Length  256, alignments in bytes  3/ 2: 23.0781 40.5    22.1875 41.5	97.5625
Length  512, alignments in bytes  0/ 0: 35.3906 33.7031 34.8594 44.6094 37.5
Length  512, alignments in bytes  2/ 4: 58.0625 64.2344 57.4531 78.5	1897.17
Length 1024, alignments in bytes  0/ 0: 61.2812 61.5156 60.6406 75	69.75
Length 1024, alignments in bytes  1/ 6: 82.5    118.266 81.4219 128.312 966.078
 
> > 
> > Third would be strcmp et al, there writing a correct loop is very tricky
> > and only mine x64 implementation does it.
> > 
> >>> And as I read assembly it isn't particulary well optimized for most
> >>> architectures. In most cases code looks like you would take current
> >>> generic implementation and ran gcc -S. For example most assemlbly
> >>> implementations don't do loop unrolling.
> >>
> >> Loop unrolling doesn't always increase performance.
> >>
> > But often does by allowing other optimizations like having only one
> > addition instead four, you could do four loads in parallel without
> > worrying that speculative load would fault etc.
> > 
> > While it doesn't have to improve performance in most cases it does.
> 
> It should be address case by case, like point out specific assembly
> implementations where you think can be benefits from some loop
> unrolling.

Its basically every implementation, question is if its worth code size
increase. I want to test my four times unrolled strlen versus archs that
must do search just using arithmetic without bytewise equality
instruction.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Mon, Jul 27, 2015 at 02:42:47PM -0400, Chris Metcalf wrote:
> On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> >Best example is strrchr where almost all architectures got it wrong
> >first time until I tell them otherwise. Problem is that they calculate
> >position of byte at each iteration instead just at end which is
> >ineffective. Now tile and powerpc have this problem. My proposed
> >alternative
> >
> >return memrchr (s, c, strlen (s) + 1);
> >
> >would beat these on suitable inputs.
> 
> Your comment and your code snippet don't really match, so can I ask
> you to elucidate a little what your concern is?
> 
It is mix of two concerns, so its both First a snippet was there 
mainly to show that generic code could be faster. I mentioned that
it applies for some inputs, as it would need larger inputs than usual
to overcome initialization and call overhead of assembly one.

> First, are you suggesting that at a high level the right thing to do
> is to do strlen() and then search backwards from the end?  This will
> certainly be faster if there is an instance of the character near the
> end of the string: on tilegx, strlen is 0.375 cycles/byte on hot cache
> vs 0.625 cycles/byte for strrchr.  But if the character is closer to
> the beginning of the string, you have to pay for the strlen, and then
> pay again for scanning the string backwards, and that cost is higher
> than just scanning forward for NUL and 'c' at the same time.  It's
> actually a bit slower to scan backwards since you have to do a counted
> loop, plus examine the loaded words, so you end up running at 0.750
> cycles/byte in reverse, so on average you would need to find the
> character in the last third of the string to make up the difference.
> 
> This is what your strlen + memchrr code snippet suggested.
> 
I didn't say that a generic is optimal only that it avoids problem with
tile implementation on some inputs.

A problem is that your analysis is incomplete. It assumes that character
occurs rarely which doesn't have to be case. A forward scan could be
very expensive if character has probability 1/16 which causes branch
misprediction each second iteration.

With strlen and memrchr you will likely have at most two mispredictions 
when they find zero and character.


> Or, are you concerned about the forward implementation of strrchr for
> tilegx itself?  I reviewed the tilegx implementation of strrchr (in C
> but using our multibyte "v1cmpeq" vector builtins for speed), and the
> inner loop is just four instruction bundles, operating on eight bytes
> at a time (with a one-cycle stall after the ld to fetch from L1D$):
> 
> string/../sysdeps/tile/tilegx/strrchr.c:61
>   40:    { addi r10, r10, 8 ; bnez r11, 90 <__GI_strrchr+0x90> }
> string/../sysdeps/tile/tilegx/strrchr.c:64
>   48:    { ld r11, r10 }
> string/../sysdeps/tile/tilegx/strrchr.c:43
>   50:    { v1cmpeq r12, r11, r13 ; v1cmpeqi r11, r11, 0 }
> string/../sysdeps/tile/tilegx/strrchr.c:49
>   58:    { beqzt r12, 40 <__GI_strrchr+0x40> }
> 
> This is what your English comment suggested (quoted above).  Despite
> the appearance of the C code, the compiler knows better than to waste
> time computing the precise character position at every iteration hit.
> 
A problem that I described in english is that this isn't inner loop as
you jump from it each second iteration when c probability is 1/16.

For example if application uses strrchr to find last / in path name then 
its likely that it would be among last 8 characters and occurs
frequently previously.

Here you would need a conditional move instead of branch to avoid that
issue.


> So I'm not sure which point you are making but unless you know
> something about the average distribution of the characters in the
> strrchr() string to suggest they are likely to occur in the last third
> of the string more than 50% of the time, I don't think I'm convinced.
> 
This mainly depends on size of string, if you assume that each character
has fixed probability it happens for sufficiently large strings.

A tricky part of writing these is that inputs are short so you need to
write separate header to get better performance.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Chris Metcalf]

On 07/27/2015 12:56 PM, Ondřej Bílka wrote:
> Best example is strrchr where almost all architectures got it wrong
> first time until I tell them otherwise. Problem is that they calculate
> position of byte at each iteration instead just at end which is
> ineffective. Now tile and powerpc have this problem. My proposed
> alternative
>
> return memrchr (s, c, strlen (s) + 1);
>
> would beat these on suitable inputs.

Your comment and your code snippet don't really match, so can I ask
you to elucidate a little what your concern is?

First, are you suggesting that at a high level the right thing to do
is to do strlen() and then search backwards from the end?  This will
certainly be faster if there is an instance of the character near the
end of the string: on tilegx, strlen is 0.375 cycles/byte on hot cache
vs 0.625 cycles/byte for strrchr.  But if the character is closer to
the beginning of the string, you have to pay for the strlen, and then
pay again for scanning the string backwards, and that cost is higher
than just scanning forward for NUL and 'c' at the same time.  It's
actually a bit slower to scan backwards since you have to do a counted
loop, plus examine the loaded words, so you end up running at 0.750
cycles/byte in reverse, so on average you would need to find the
character in the last third of the string to make up the difference.

This is what your strlen + memchrr code snippet suggested.

Or, are you concerned about the forward implementation of strrchr for
tilegx itself?  I reviewed the tilegx implementation of strrchr (in C
but using our multibyte "v1cmpeq" vector builtins for speed), and the
inner loop is just four instruction bundles, operating on eight bytes
at a time (with a one-cycle stall after the ld to fetch from L1D$):

string/../sysdeps/tile/tilegx/strrchr.c:61
   40:    { addi r10, r10, 8 ; bnez r11, 90 <__GI_strrchr+0x90> }
string/../sysdeps/tile/tilegx/strrchr.c:64
   48:    { ld r11, r10 }
string/../sysdeps/tile/tilegx/strrchr.c:43
   50:    { v1cmpeq r12, r11, r13 ; v1cmpeqi r11, r11, 0 }
string/../sysdeps/tile/tilegx/strrchr.c:49
   58:    { beqzt r12, 40 <__GI_strrchr+0x40> }

This is what your English comment suggested (quoted above).  Despite
the appearance of the C code, the compiler knows better than to waste
time computing the precise character position at every iteration hit.

So I'm not sure which point you are making but unless you know
something about the average distribution of the characters in the
strrchr() string to suggest they are likely to occur in the last third
of the string more than 50% of the time, I don't think I'm convinced.

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

Re: [PATCH 4/*] Generic string memchr and strnlen

[Adhemerval Zanella]

On 27-07-2015 13:56, Ondřej Bílka wrote:
> On Mon, Jul 27, 2015 at 02:54:21PM +0100, Wilco Dijkstra wrote:
>>> Ondřej Bílka wrote:
>>> On Fri, Jul 24, 2015 at 07:03:10PM +0100, Wilco Dijkstra wrote:
>>>>> Ondřej Bílka wrote:
>>>>> On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
>>>>>>> Ondřej Bílka wrote:
>>>>>>> On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
>>
>>>> Which alternatives? I didn't see a mention of an alternative that would
>>>> actually be faster.
>>>>
>>> As I wrote before for example derive strnlen from memchr assembly.
>>
>> That's not a realistic alternative at all for most targets. I am talking
>> about a generic C solution that applies to all targets, similar to what I
>> did for strcpy, strcat, mempcpy calling optimized strlen and memcpy.
>>
> While this is good first step it still leaves considerable performance
> improvement. For that you need to do assembly tricks.
>  
>>>> I'd find it hard to believe you can beat assembly implementations. Do you
>>>> have any performance results for your patches? There were a lot of patches
>>>> posted but I don't recall any performance results in any.
>>>>
>>> That isn't hard to believe, actually its quite easy. If current assembly
>>> isn't particulary good then c implementation will beat assembly. 
>>
>> That's extremely unlikely. The generic C implementations that we haven't
>> fixed already are quite inefficient, while the assembly implementations I've
>> looked at were all efficient.
>>
> Then you didn't look at many implementations. In lot of cases strlen is
> just copypasted output of gcc string/strlen.c -S with fixed gcc errors.
> While its faster than current generic one a better generic will beat it.
> 
> Best example is strrchr where almost all architectures got it wrong
> first time until I tell them otherwise. Problem is that they calculate
> position of byte at each iteration instead just at end which is
> ineffective. Now tile and powerpc have this problem. My proposed
> alternative
> 
> return memrchr (s, c, strlen (s) + 1);
> 
> would beat these on suitable inputs. I don't know if in practice as
> there is extra strlen call.

You do a lot of assumptions and I doubt very much that it will be faster
on every input.  Assuming assembly implementations (no function call) I
do see that this could be faster for long string with the character being
found in the end of the string, but I see it could potentially slower
if it searches large strings with character in start/middle.  It will
really depends in which will be the input char size and distribution.

> 
> Second would be strcpy and strncpy where assembly implementations of
> some rchitectures look dubious and you could beat these with memcpy
> call + strlen. I know definitely about powerpc power7 and powerppc
> implementations.

From previous discussion the idea of power7 strcpy/strncpy is to not use
unaligned read/writes due architecture constraints.  And again you do
a lot of assumptions: I doubt that using power7 memcpy/strlen (which also
do only aligned accesses) would be faster than current strcpy/strncpy.
It could be the case for large strings, where memcpy will gain because the
use of VSX instructions; but even I would like some data before taking
conclusions.

> 
> Third would be strcmp et al, there writing a correct loop is very tricky
> and only mine x64 implementation does it.
> 
>>> And as I read assembly it isn't particulary well optimized for most
>>> architectures. In most cases code looks like you would take current
>>> generic implementation and ran gcc -S. For example most assemlbly
>>> implementations don't do loop unrolling.
>>
>> Loop unrolling doesn't always increase performance.
>>
> But often does by allowing other optimizations like having only one
> addition instead four, you could do four loads in parallel without
> worrying that speculative load would fault etc.
> 
> While it doesn't have to improve performance in most cases it does.

It should be address case by case, like point out specific assembly
implementations where you think can be benefits from some loop
unrolling.

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Mon, Jul 27, 2015 at 02:54:21PM +0100, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote:
> > On Fri, Jul 24, 2015 at 07:03:10PM +0100, Wilco Dijkstra wrote:
> > > > Ondřej Bílka wrote:
> > > > On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
> > > > > > Ondřej Bílka wrote:
> > > > > > On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> 
> > > Which alternatives? I didn't see a mention of an alternative that would
> > > actually be faster.
> > >
> > As I wrote before for example derive strnlen from memchr assembly.
> 
> That's not a realistic alternative at all for most targets. I am talking
> about a generic C solution that applies to all targets, similar to what I
> did for strcpy, strcat, mempcpy calling optimized strlen and memcpy.
>
While this is good first step it still leaves considerable performance
improvement. For that you need to do assembly tricks.
 
> > > I'd find it hard to believe you can beat assembly implementations. Do you
> > > have any performance results for your patches? There were a lot of patches
> > > posted but I don't recall any performance results in any.
> > >
> > That isn't hard to believe, actually its quite easy. If current assembly
> > isn't particulary good then c implementation will beat assembly. 
> 
> That's extremely unlikely. The generic C implementations that we haven't
> fixed already are quite inefficient, while the assembly implementations I've
> looked at were all efficient.
> 
Then you didn't look at many implementations. In lot of cases strlen is
just copypasted output of gcc string/strlen.c -S with fixed gcc errors.
While its faster than current generic one a better generic will beat it.

Best example is strrchr where almost all architectures got it wrong
first time until I tell them otherwise. Problem is that they calculate
position of byte at each iteration instead just at end which is
ineffective. Now tile and powerpc have this problem. My proposed
alternative

return memrchr (s, c, strlen (s) + 1);

would beat these on suitable inputs. I don't know if in practice as
there is extra strlen call.

Second would be strcpy and strncpy where assembly implementations of
some rchitectures look dubious and you could beat these with memcpy
call + strlen. I know definitely about powerpc power7 and powerppc
implementations.

Third would be strcmp et al, there writing a correct loop is very tricky
and only mine x64 implementation does it.

> > And as I read assembly it isn't particulary well optimized for most
> > architectures. In most cases code looks like you would take current
> > generic implementation and ran gcc -S. For example most assemlbly
> > implementations don't do loop unrolling.
> 
> Loop unrolling doesn't always increase performance.
> 
But often does by allowing other optimizations like having only one
addition instead four, you could do four loads in parallel without
worrying that speculative load would fault etc.

While it doesn't have to improve performance in most cases it does.

> > As for performance results I asked maintainers to run them but didn't
> > get response. I don't have access to exotic architectures so I couldn't
> > provide it.
> 
> All we need is results for a few popular architectures. Without any result
> I am very sceptical that it beats any assembly implementation.
> 
> > > That's only possible in a few cases. I'm talking about missing optimized
> > > implementations. Are you saying we should continue to use slow C code rather
> > > than trying to call an optimized assembler function?
> > >
> > What cases are you talking about. All of strnlen, strlen, rawmemchr
> > could be obtained from memchr assembly by doing dead code elimination of
> > unused code.
> 
> A case where it may be possible is strchrnul vs strchr for example where it is
> just a slightly different return value. Other cases are non-trivial and if you
> don't spend a significant effort on optimizing each function you end up with
> something inefficient.
> 
No, cases where its trivial are widespread. For strnlen its also just a
different return value and changing parameters.
For strlen and rawmemchr you could use strchr and delete zero
check/character check.

> We have lots of targets which are missing optimized functions, but which do have
> some related ones that can be called from generic code instead. Clearly doing
> that is a far more practical and realistic approach than talking about how easy
> it is to do dead-code elimination in assembly code when nobody does that. 
> 
> Or are you planning to do the dead-code elimination yourself? If not, we need
> to fix the generic code.
> 
That isn't completely true as I could do maintainers to do that. That
could save them lot of time if they want to add optimized
implementations as if you know tricks then most functions could be
trivialy derived from another.

> > > > > > Suggestion to express strlen as memchr would just cause regression. On
> > > > > > my system there happened 9535682 calls of strlen while memchr was called
> > > > > > just 11633 times and rawmemchr 1742 times.
> > > > >
> > > > > Why would it cause a regression? If you don't have an optimized strlen,
> > > > > what other implementation would be the fastest alternative?
> > > > >
> > > > It would be my generic strlen implementation. If you don't have
> > > > optimized strlen then you certainly don't have optimized memchr that is
> > > > called 819 times less often.
> > >
> > > Well I'd like to see results that show a C version of strlen beating an
> > > optimized memchr on x64. Still it seems to me there is no real need for an
> > > optimized C version of strlen - every target already provides an optimized
> > > version and it is hard to believe it is possible to beat those.
> > >
> > Thats trivial, I attached what I have. When I compile it I get
> > following:
> 
> Please reread the subject, we're talking about generic C code...
>
No, I wrote original post so we don't. My proposal counts that
maintainer will supply platform specific primitives if there is
instruction to do paralel byte comparison...
 
> > And for strlen being available it was exactly my point as its more important to
> > have assembly strlen than using memchr/rawmechr so your case wont happen.
> 
> Strlen is implemented in most targets so that is not an issue indeed, however
> there are quite a few targets which do have memchr but no strnlen, so that 
> scenario is certainly common.
> 
> > > That's only true for few cases. Note given its rarity, it seems better
> > > to change any call to rawmemchr into memchr(s, c, SIZE_MAX) - the gain
> > > due to cache sharing should far outweigh the small loss due to the extra
> > > length checks.
> > >
> > Thats also false as saving is much more than few cycles. Also that it
> > doesn't follow that if function has low number of total calls it would
> > be cold, just that there are few applications that use them. And in
> > application that uses them it could use it only in one tight loop. Here
> > rawmemchr is used only in mutt while strlen is used everywhere.
> > 
> > A performance difference could be quite big in x64, from benchtests;
> 
> It looks like that implementation isn't very optimal then. Decrementing a
> counter every 64 bytes is not a lot of overhead.
> 
No, it shows that implementation is optimal. On haswell rawmemchr needs
4 cycles per 64 bytes so extra overhead is very noticable.

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Fri, Jul 24, 2015 at 07:03:10PM +0100, Wilco Dijkstra wrote:
> > > Ondřej Bílka wrote:
> > > On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
> > > > > Ondřej Bílka wrote:
> > > > > On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:

> > Which alternatives? I didn't see a mention of an alternative that would
> > actually be faster.
> >
> As I wrote before for example derive strnlen from memchr assembly.

That's not a realistic alternative at all for most targets. I am talking
about a generic C solution that applies to all targets, similar to what I
did for strcpy, strcat, mempcpy calling optimized strlen and memcpy.

> > I'd find it hard to believe you can beat assembly implementations. Do you
> > have any performance results for your patches? There were a lot of patches
> > posted but I don't recall any performance results in any.
> >
> That isn't hard to believe, actually its quite easy. If current assembly
> isn't particulary good then c implementation will beat assembly. 

That's extremely unlikely. The generic C implementations that we haven't
fixed already are quite inefficient, while the assembly implementations I've
looked at were all efficient.

> And as I read assembly it isn't particulary well optimized for most
> architectures. In most cases code looks like you would take current
> generic implementation and ran gcc -S. For example most assemlbly
> implementations don't do loop unrolling.

Loop unrolling doesn't always increase performance.

> As for performance results I asked maintainers to run them but didn't
> get response. I don't have access to exotic architectures so I couldn't
> provide it.

All we need is results for a few popular architectures. Without any result
I am very sceptical that it beats any assembly implementation.

> > That's only possible in a few cases. I'm talking about missing optimized
> > implementations. Are you saying we should continue to use slow C code rather
> > than trying to call an optimized assembler function?
> >
> What cases are you talking about. All of strnlen, strlen, rawmemchr
> could be obtained from memchr assembly by doing dead code elimination of
> unused code.

A case where it may be possible is strchrnul vs strchr for example where it is
just a slightly different return value. Other cases are non-trivial and if you
don't spend a significant effort on optimizing each function you end up with
something inefficient.

We have lots of targets which are missing optimized functions, but which do have
some related ones that can be called from generic code instead. Clearly doing
that is a far more practical and realistic approach than talking about how easy
it is to do dead-code elimination in assembly code when nobody does that. 

Or are you planning to do the dead-code elimination yourself? If not, we need
to fix the generic code.

> > > > > Suggestion to express strlen as memchr would just cause regression. On
> > > > > my system there happened 9535682 calls of strlen while memchr was called
> > > > > just 11633 times and rawmemchr 1742 times.
> > > >
> > > > Why would it cause a regression? If you don't have an optimized strlen,
> > > > what other implementation would be the fastest alternative?
> > > >
> > > It would be my generic strlen implementation. If you don't have
> > > optimized strlen then you certainly don't have optimized memchr that is
> > > called 819 times less often.
> >
> > Well I'd like to see results that show a C version of strlen beating an
> > optimized memchr on x64. Still it seems to me there is no real need for an
> > optimized C version of strlen - every target already provides an optimized
> > version and it is hard to believe it is possible to beat those.
> >
> Thats trivial, I attached what I have. When I compile it I get
> following:

Please reread the subject, we're talking about generic C code...

> And for strlen being available it was exactly my point as its more important to
> have assembly strlen than using memchr/rawmechr so your case wont happen.

Strlen is implemented in most targets so that is not an issue indeed, however
there are quite a few targets which do have memchr but no strnlen, so that 
scenario is certainly common.

> > That's only true for few cases. Note given its rarity, it seems better
> > to change any call to rawmemchr into memchr(s, c, SIZE_MAX) - the gain
> > due to cache sharing should far outweigh the small loss due to the extra
> > length checks.
> >
> Thats also false as saving is much more than few cycles. Also that it
> doesn't follow that if function has low number of total calls it would
> be cold, just that there are few applications that use them. And in
> application that uses them it could use it only in one tight loop. Here
> rawmemchr is used only in mutt while strlen is used everywhere.
> 
> A performance difference could be quite big in x64, from benchtests;

It looks like that implementation isn't very optimal then. Decrementing a
counter every 64 bytes is not a lot of overhead.

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

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

On Fri, Jul 24, 2015 at 07:03:10PM +0100, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote:
> > On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
> > > > Ondřej Bílka wrote:
> > > > On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> > > > > Getting back to this, if you don't have an optimized strnlen then
> > > > > it is always better to try to use memchr (there are 14 optimized
> > > > > implementations of memchr but only 6 for strnlen).
> > > > >
> > > > > So I'd suggest changing strnlen in an independent patch as:
> > > > >
> > > > > __strnlen (const char *str, size_t n)
> > > > > {
> > > > >   char *ret = __memchr (str, 0, n);
> > > > >   return ret ? ret - str : n;
> > > > > }
> > > > >
> > > > > It also looks worthwhile to express strlen and rawmemchr as memchr
> > > > > so that you only need one highly optimized function rather than many.
> > > > > Deferring to more widely implemented optimized assembler functions
> > > > > should result in better performance than trying to optimize these
> > > > > functions in C.
> > > > >
> > > > No, that is bad idea. Unless you inline strnlen or memchr then you add
> > > > extra call overhead.
> > >
> > > The goal is to call the optimized assembler version of memchr when there
> > > isn't one for strnlen - you could inline the above in headers if a target
> > > decides that there will only be an optimized memchr and not a strnlen
> > > (assuming that strnlen shows similar performance as memchr on a particular
> > > target).
> > >
> > Which as I explained is worse than alternatives, unless saving size.
> 
> Which alternatives? I didn't see a mention of an alternative that would
> actually be faster.
>
As I wrote before for example derive strnlen from memchr assembly.
 
> > > > That is unless you want to claim that you want to save size.
> > > >
> > > > As for optimized implementations of strnlen vs memchr it isn't clear
> > > > that we will delete all of them as they are slower.
> > >
> > > Delete what? We could certainly decide on a core set of functions which
> > > every target should implement in assembler. Candidates are memcpy, memset,
> > > memmove, memchr, strchr, strlen. Then for those we do not try to provide
> > > an optimized C implementation as it won't ever be used. But deleting them
> > > seems a bridge too far.
> > >
> > This patch is about generic string functions. When they have good
> > performance they will replace current ones for architectures. So soon
> > there won't be architecture where it holds.
> 
> I'd find it hard to believe you can beat assembly implementations. Do you
> have any performance results for your patches? There were a lot of patches
> posted but I don't recall any performance results in any.
> 
That isn't hard to believe, actually its quite easy. If current assembly
isn't particulary good then c implementation will beat assembly. And as
I read assembly it isn't particulary well optimized for most
architectures. In most cases code looks like you would take current
generic implementation and ran gcc -S. For example most assemlbly
implementations don't do loop unrolling. 

As for performance results I asked maintainers to run them but didn't
get response. I don't have access to exotic architectures so I couldn't
provide it.

> > > > Also its wrong way to solve it, a architecture maintainer should add
> > > > optimized strnlen implementations, that quite easy when you have memchr
> > > > implementation, add few macros to initially add start and different end
> > > > handling.
> > >
> > > The problem with the non-standard functions that are rarely used is that
> > > there are very few optimized implementations. We can't force maintainers to
> > > implement all string functions in assembler, so the generic code should use
> > > the fastest possible alternative if there isn't an optimized implementation.
> > > And that is pretty much always a more commonly used function which does
> > > have an optimized implementation.
> > >
> > But that isn't about what I said. I said that if there is optimized
> > memchr implementation then other function assembly is trivial to add for
> > maintainer. That gives you better performance.
> 
> That's only possible in a few cases. I'm talking about missing optimized
> implementations. Are you saying we should continue to use slow C code rather
> than trying to call an optimized assembler function?
> 
What cases are you talking about. All of strnlen, strlen, rawmemchr
could be obtained from memchr assembly by doing dead code elimination of
unused code.


> > > > Suggestion to express strlen as memchr would just cause regression. On
> > > > my system there happened 9535682 calls of strlen while memchr was called
> > > > just 11633 times and rawmemchr 1742 times.
> > >
> > > Why would it cause a regression? If you don't have an optimized strlen,
> > > what other implementation would be the fastest alternative?
> > >
> > It would be my generic strlen implementation. If you don't have
> > optimized strlen then you certainly don't have optimized memchr that is
> > called 819 times less often.
> 
> Well I'd like to see results that show a C version of strlen beating an
> optimized memchr on x64. Still it seems to me there is no real need for an
> optimized C version of strlen - every target already provides an optimized
> version and it is hard to believe it is possible to beat those.
> 
Thats trivial, I attached what I have. When I compile it I get
following:

gcc -O3 -S s.c
gcc -O3 t.c s.c
gcc -O3 t.c s.o
time ./a.out

real	0m0.934s
user	0m0.804s
sys	0m0.008s

gcc -O3 t.c -DSTRLEN s.o
time ./a.out

real	0m0.309s
user	0m0.308s
sys	0m0.004s


And for strlen being available it was exactly my point as its more important to 
have assembly strlen than using memchr/rawmechr so your case wont happen.

> > > > Also purpose of strlen and rawmechr is to be faster than memchr. Again
> > > > these should be implemented by architecture maintainer by removing size
> > > > checks from memchr implementation.
> > >
> > > Yes it would be perfect if we had optimized assembler implementations for
> > > all functions. However that's unfortunately not the case given there is a
> > > high cost for creating assembler implementations.
> > 
> > No, there isn't. If you have optimized memchr then deriving these is
> > simple mechanic work. Just do equivalent of dead code elimination on
> > memchr and you will get strlen.
> 
> That's only true for few cases. Note given its rarity, it seems better
> to change any call to rawmemchr into memchr(s, c, SIZE_MAX) - the gain
> due to cache sharing should far outweigh the small loss due to the extra
> length checks.
>
Thats also false as saving is much more than few cycles. Also that it
doesn't follow that if function has low number of total calls it would
be cold, just that there are few applications that use them. And in
application that uses them it could use it only in one tight loop. Here
rawmemchr is used only in mutt while strlen is used everywhere.

A performance difference could be quite big in x64, from benchtests;

 memchr  simple_memchr
Length   32, alignment  0:      41.6719 176.562
Length   64, alignment  2:      38.7969 395.953
Length  128, alignment  0:      53.6406 705.078
Length   64, alignment  3:      41.2656 395.969
Length  128, alignment  0:      51.9531 705.328
Length   64, alignment  3:      38.9219 396.234
Length  256, alignment  0:      93.3594 1373.05
Length   64, alignment  4:      38.9375 395.703
Length  256, alignment  0:      87.7656 1375.91
Length   64, alignment  4:      38.9219 395.969
Length  512, alignment  0:      131.25  2684.64

                        rawmemchr       simple_rawmemchr
Length   32, alignment  0:      34.5    156.906
Length   64, alignment  2:      33.7188 333.594
Length  128, alignment  0:      50.3906 613.672
Length   64, alignment  3:      35.0156 333.453
Length  128, alignment  0:      46.2188 615.625
Length   64, alignment  3:      34.8906 333.594
Length  256, alignment  0:      79.1719 1133.47
Length   64, alignment  4:      33.4688 351.828
Length  256, alignment  0:      74.0938 1156.77
Length   64, alignment  4:      33.4531 333.594
Length  512, alignment  0:      108.734 2262.38 

[-- Attachment #2: s.c --]
[-- Type: text/plain, Size: 3712 bytes --]

#define CHAR_BASED

#include <emmintrin.h>
#include <stdint.h>
#include <stdlib.h>
typedef __m128i tp_vector;
#ifdef CHAR_BASED
typedef unsigned char uchar;
typedef uchar tp_scalar;
#define S(x) _mm_##x##_epi8
#else
typedef int tp_scalar;
#define S(x) _mm_##x##_epi32
#endif
typedef uint64_t tp_mask;
#define LOAD(x) _mm_load_si128((tp_vector *) (x))
#define LOADU(x) _mm_loadu_si128((tp_vector *) (x))
#define STOREU(x,y) _mm_storeu_si128((tp_vector *) (x), (y))
#define STORE(x,y) _mm_store_si128((tp_vector *) (x), (y))

#define MIN _mm_min_epu8
#define EQ S(cmpeq)
#define OR _mm_or_si128
#define shift_down(x,y) (x)>>(y)
#define shift_up(x,y)   (x)<<(y)

#define PARA sizeof(tp_vector)/sizeof(tp_scalar)
#define BROADCAST(x) S(set1)(x)
#define get_mask(x) ((long)_mm_movemask_epi8(x))
static inline tp_mask first_bit(tp_mask x)
{
  return __builtin_ctzl(x)/sizeof(tp_scalar);
}
static inline tp_mask last_bit(tp_mask x)
{
  return (sizeof(tp_mask)*8-1-__builtin_clzl(x))/sizeof(tp_scalar);
}

static inline uint64_t find64(tp_scalar e,void *s2){
  tp_vector pe= BROADCAST(e);
  tp_vector v0,v1,v2,v3;
  v0=EQ(pe,LOAD(s2));
  v1=EQ(pe,LOAD(s2+PARA));
  v2=EQ(pe,LOAD(s2+2*PARA));
  v3=EQ(pe,LOAD(s2+3*PARA));
  return get_mask(v0)|(get_mask(v1)<<16)|(get_mask(v2)<<32)|(get_mask(v3)<<48);
}

#define unroll 4

#ifdef NVERSION
#define NVERSION_S(x,y) x
#else
#define NVERSION_S(x,y) y
#endif
size_t strlen2(const char *_s){
  uchar *s=(uchar*)_s;
  tp_mask mask;
  tp_scalar *s2;
#ifdef NVERSION
  if (!no) return NULL;
  tp_scalar *end  = s+no;
  tp_scalar *s2end= ((size_t)end-1)&(~(unroll*sizeof(tp_vector)-1));
#endif
  tp_vector pe= BROADCAST(0);
  tp_vector v0,v1,v2,v3;
  if ((((size_t)s)&4095)<=4096-64){
  s2   = ((size_t)s)&(~(sizeof(tp_vector)-1));
  v0=EQ(pe,LOAD(s2));
  v1=EQ(pe,LOAD(s2+PARA));
  v2=EQ(pe,LOAD(s2+2*PARA));
  v3=EQ(pe,LOAD(s2+3*PARA));

  mask=get_mask(v0)|(get_mask(v1)<<16)|(get_mask(v2)<<32)|(get_mask(v3)<<48);
  mask= shift_down(mask,s-s2);
#ifdef NVERSION
  if((size_t)end-s2<64){ // on x64 strengthen to end-s2<=64
    mask=mask& shift_down((unsigned long)-1,-((long)end-s2));

    if(mask) return first_bit(mask);
    return no;
  }
#endif
  if(mask) {
    return first_bit(mask);
  }
    s2= ((size_t)s)&(~(unroll*sizeof(tp_vector)-1));
    s2+=unroll*PARA;
  } else {
  s2   = ((size_t)s)&(~(unroll*sizeof(tp_vector)-1));
  v0=EQ(pe,LOAD(s2));
  v1=EQ(pe,LOAD(s2+PARA));
  v2=EQ(pe,LOAD(s2+2*PARA));
  v3=EQ(pe,LOAD(s2+3*PARA));

  mask=get_mask(v0)|(get_mask(v1)<<16)|(get_mask(v2)<<32)|(get_mask(v3)<<48);
  mask= shift_down(mask,s-s2);
#ifdef NVERSION
  if((size_t)end-s2<64){
    mask=mask& shift_down((unsigned long)-1,-((long)end-s2));

    if(mask) return first_bit(mask);
    return no;
  }
#endif
  if(mask) {
    return first_bit(mask);
  }
  s2+=unroll*PARA;
  }
  while(NVERSION_S(s2!=s2end,1)){
    v0=EQ(pe,LOAD(s2));
    v1=EQ(pe,LOAD(s2+PARA));
    v2=EQ(pe,LOAD(s2+2*PARA));
    v3=EQ(pe,LOAD(s2+3*PARA));
    if(get_mask(OR(v0,OR(v1,OR(v2,v3))))){
      mask=get_mask(v0)|(get_mask(v1)<<16)|(get_mask(v2)<<32)|(get_mask(v3)<<48);

      if(NVERSION_S(s2!=s2end || mask & shift_down((unsigned long)-1,-(long)end),1))
        return s2+first_bit(mask)-s;
    }
    s2+=unroll*PARA;

    if(get_mask(EQ(pe,MIN(v0,MIN(v1,MIN(v2,v3)))))){
asm volatile ("" : : : "memory");
    
    v0=EQ(pe,LOAD(s2));
    v1=EQ(pe,LOAD(s2+PARA));
    v2=EQ(pe,LOAD(s2+2*PARA));
    v3=EQ(pe,LOAD(s2+3*PARA));
  mask=get_mask(v0)|(get_mask(v1)<<16)|(get_mask(v2)<<32)|(get_mask(v3)<<48);

      if(NVERSION_S(s2!=s2end || mask & shift_down((unsigned long)-1,-(long)end),1))
        return s2+first_bit(mask)-s;
    }
    s2+=unroll*PARA;

  }
  return NVERSION_S(no,1);
}

[-- Attachment #3: t.c --]
[-- Type: text/plain, Size: 251 bytes --]

#include <string.h>
int main() {
  char buf[1024];
  memset(buf,1,1024);
  buf[1023]=0;
  int i;
  int ret;
  for (i=0;i<10000000;i++)
#ifdef STRLEN
    strlen2(buf+i%64);
#else
    ret += memchr(buf+i%64,0,1024) - (void *)buf;
#endif
  return ret;
}

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
> > > Ondřej Bílka wrote:
> > > On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> > > > Getting back to this, if you don't have an optimized strnlen then
> > > > it is always better to try to use memchr (there are 14 optimized
> > > > implementations of memchr but only 6 for strnlen).
> > > >
> > > > So I'd suggest changing strnlen in an independent patch as:
> > > >
> > > > __strnlen (const char *str, size_t n)
> > > > {
> > > >   char *ret = __memchr (str, 0, n);
> > > >   return ret ? ret - str : n;
> > > > }
> > > >
> > > > It also looks worthwhile to express strlen and rawmemchr as memchr
> > > > so that you only need one highly optimized function rather than many.
> > > > Deferring to more widely implemented optimized assembler functions
> > > > should result in better performance than trying to optimize these
> > > > functions in C.
> > > >
> > > No, that is bad idea. Unless you inline strnlen or memchr then you add
> > > extra call overhead.
> >
> > The goal is to call the optimized assembler version of memchr when there
> > isn't one for strnlen - you could inline the above in headers if a target
> > decides that there will only be an optimized memchr and not a strnlen
> > (assuming that strnlen shows similar performance as memchr on a particular
> > target).
> >
> Which as I explained is worse than alternatives, unless saving size.

Which alternatives? I didn't see a mention of an alternative that would
actually be faster.

> > > That is unless you want to claim that you want to save size.
> > >
> > > As for optimized implementations of strnlen vs memchr it isn't clear
> > > that we will delete all of them as they are slower.
> >
> > Delete what? We could certainly decide on a core set of functions which
> > every target should implement in assembler. Candidates are memcpy, memset,
> > memmove, memchr, strchr, strlen. Then for those we do not try to provide
> > an optimized C implementation as it won't ever be used. But deleting them
> > seems a bridge too far.
> >
> This patch is about generic string functions. When they have good
> performance they will replace current ones for architectures. So soon
> there won't be architecture where it holds.

I'd find it hard to believe you can beat assembly implementations. Do you
have any performance results for your patches? There were a lot of patches
posted but I don't recall any performance results in any.

> > > Also its wrong way to solve it, a architecture maintainer should add
> > > optimized strnlen implementations, that quite easy when you have memchr
> > > implementation, add few macros to initially add start and different end
> > > handling.
> >
> > The problem with the non-standard functions that are rarely used is that
> > there are very few optimized implementations. We can't force maintainers to
> > implement all string functions in assembler, so the generic code should use
> > the fastest possible alternative if there isn't an optimized implementation.
> > And that is pretty much always a more commonly used function which does
> > have an optimized implementation.
> >
> But that isn't about what I said. I said that if there is optimized
> memchr implementation then other function assembly is trivial to add for
> maintainer. That gives you better performance.

That's only possible in a few cases. I'm talking about missing optimized
implementations. Are you saying we should continue to use slow C code rather
than trying to call an optimized assembler function?

> > > Suggestion to express strlen as memchr would just cause regression. On
> > > my system there happened 9535682 calls of strlen while memchr was called
> > > just 11633 times and rawmemchr 1742 times.
> >
> > Why would it cause a regression? If you don't have an optimized strlen,
> > what other implementation would be the fastest alternative?
> >
> It would be my generic strlen implementation. If you don't have
> optimized strlen then you certainly don't have optimized memchr that is
> called 819 times less often.

Well I'd like to see results that show a C version of strlen beating an
optimized memchr on x64. Still it seems to me there is no real need for an
optimized C version of strlen - every target already provides an optimized
version and it is hard to believe it is possible to beat those.

> > > Also purpose of strlen and rawmechr is to be faster than memchr. Again
> > > these should be implemented by architecture maintainer by removing size
> > > checks from memchr implementation.
> >
> > Yes it would be perfect if we had optimized assembler implementations for
> > all functions. However that's unfortunately not the case given there is a
> > high cost for creating assembler implementations.
> 
> No, there isn't. If you have optimized memchr then deriving these is
> simple mechanic work. Just do equivalent of dead code elimination on
> memchr and you will get strlen.

That's only true for few cases. Note given its rarity, it seems better
to change any call to rawmemchr into memchr(s, c, SIZE_MAX) - the gain
due to cache sharing should far outweigh the small loss due to the extra
length checks.

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Fri, Jul 24, 2015 at 05:38:43PM +0100, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote:
> > On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> > > Getting back to this, if you don't have an optimized strnlen then
> > > it is always better to try to use memchr (there are 14 optimized
> > > implementations of memchr but only 6 for strnlen).
> > >
> > > So I'd suggest changing strnlen in an independent patch as:
> > >
> > > __strnlen (const char *str, size_t n)
> > > {
> > >   char *ret = __memchr (str, 0, n);
> > >   return ret ? ret - str : n;
> > > }
> > >
> > > It also looks worthwhile to express strlen and rawmemchr as memchr
> > > so that you only need one highly optimized function rather than many.
> > > Deferring to more widely implemented optimized assembler functions
> > > should result in better performance than trying to optimize these
> > > functions in C.
> > >
> > No, that is bad idea. Unless you inline strnlen or memchr then you add
> > extra call overhead.
> 
> The goal is to call the optimized assembler version of memchr when there 
> isn't one for strnlen - you could inline the above in headers if a target
> decides that there will only be an optimized memchr and not a strnlen
> (assuming that strnlen shows similar performance as memchr on a particular
> target).
>
Which as I explained is worse than alternatives, unless saving size.
 
> > That is unless you want to claim that you want to save size.
> > 
> > As for optimized implementations of strnlen vs memchr it isn't clear
> > that we will delete all of them as they are slower.
> 
> Delete what? We could certainly decide on a core set of functions which
> every target should implement in assembler. Candidates are memcpy, memset,
> memmove, memchr, strchr, strlen. Then for those we do not try to provide
> an optimized C implementation as it won't ever be used. But deleting them
> seems a bridge too far.
> 
This patch is about generic string functions. When they have good
performance they will replace current ones for architectures. So soon
there won't be architecture where it holds.

> > Also its wrong way to solve it, a architecture maintainer should add
> > optimized strnlen implementations, that quite easy when you have memchr
> > implementation, add few macros to initially add start and different end
> > handling.
> 
> The problem with the non-standard functions that are rarely used is that 
> there are very few optimized implementations. We can't force maintainers to
> implement all string functions in assembler, so the generic code should use
> the fastest possible alternative if there isn't an optimized implementation. 
> And that is pretty much always a more commonly used function which does 
> have an optimized implementation.
>
But that isn't about what I said. I said that if there is optimized
memchr implementation then other function assembly is trivial to add for
maintainer. That gives you better performance.


> > Suggestion to express strlen as memchr would just cause regression. On
> > my system there happened 9535682 calls of strlen while memchr was called
> > just 11633 times and rawmemchr 1742 times.
> 
> Why would it cause a regression? If you don't have an optimized strlen,
> what other implementation would be the fastest alternative?
> 
It would be my generic strlen implementation. If you don't have
optimized strlen then you certainly don't have optimized memchr that is
called 819 times less often.

> > Also purpose of strlen and rawmechr is to be faster than memchr. Again
> > these should be implemented by architecture maintainer by removing size
> > checks from memchr implementation.
> 
> Yes it would be perfect if we had optimized assembler implementations for
> all functions. However that's unfortunately not the case given there is a
> high cost for creating assembler implementations.

No, there isn't. If you have optimized memchr then deriving these is
simple mechanic work. Just do equivalent of dead code elimination on
memchr and you will get strlen. 

RE: [PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> > Getting back to this, if you don't have an optimized strnlen then
> > it is always better to try to use memchr (there are 14 optimized
> > implementations of memchr but only 6 for strnlen).
> >
> > So I'd suggest changing strnlen in an independent patch as:
> >
> > __strnlen (const char *str, size_t n)
> > {
> >   char *ret = __memchr (str, 0, n);
> >   return ret ? ret - str : n;
> > }
> >
> > It also looks worthwhile to express strlen and rawmemchr as memchr
> > so that you only need one highly optimized function rather than many.
> > Deferring to more widely implemented optimized assembler functions
> > should result in better performance than trying to optimize these
> > functions in C.
> >
> No, that is bad idea. Unless you inline strnlen or memchr then you add
> extra call overhead.

The goal is to call the optimized assembler version of memchr when there 
isn't one for strnlen - you could inline the above in headers if a target
decides that there will only be an optimized memchr and not a strnlen
(assuming that strnlen shows similar performance as memchr on a particular
target).

> That is unless you want to claim that you want to save size.
> 
> As for optimized implementations of strnlen vs memchr it isn't clear
> that we will delete all of them as they are slower.

Delete what? We could certainly decide on a core set of functions which
every target should implement in assembler. Candidates are memcpy, memset,
memmove, memchr, strchr, strlen. Then for those we do not try to provide
an optimized C implementation as it won't ever be used. But deleting them
seems a bridge too far.

> Also its wrong way to solve it, a architecture maintainer should add
> optimized strnlen implementations, that quite easy when you have memchr
> implementation, add few macros to initially add start and different end
> handling.

The problem with the non-standard functions that are rarely used is that 
there are very few optimized implementations. We can't force maintainers to
implement all string functions in assembler, so the generic code should use
the fastest possible alternative if there isn't an optimized implementation. 
And that is pretty much always a more commonly used function which does 
have an optimized implementation.

> Suggestion to express strlen as memchr would just cause regression. On
> my system there happened 9535682 calls of strlen while memchr was called
> just 11633 times and rawmemchr 1742 times.

Why would it cause a regression? If you don't have an optimized strlen,
what other implementation would be the fastest alternative?

> Also purpose of strlen and rawmechr is to be faster than memchr. Again
> these should be implemented by architecture maintainer by removing size
> checks from memchr implementation.

Yes it would be perfect if we had optimized assembler implementations for
all functions. However that's unfortunately not the case given there is a
high cost for creating assembler implementations.

Wilco

Re: [PATCH 4/*] Generic string memchr and strnlen

[Ondřej Bílka]

On Fri, Jul 24, 2015 at 04:10:24PM +0100, Wilco Dijkstra wrote:
> Getting back to this, if you don't have an optimized strnlen then
> it is always better to try to use memchr (there are 14 optimized
> implementations of memchr but only 6 for strnlen).
> 
> So I'd suggest changing strnlen in an independent patch as:
> 
> __strnlen (const char *str, size_t n)
> {
>   char *ret = __memchr (str, 0, n); 
>   return ret ? ret - str : n;
> }
> 
> It also looks worthwhile to express strlen and rawmemchr as memchr
> so that you only need one highly optimized function rather than many.
> Deferring to more widely implemented optimized assembler functions
> should result in better performance than trying to optimize these
> functions in C.
> 
No, that is bad idea. Unless you inline strnlen or memchr then you add
extra call overhead.

That is unless you want to claim that you want to save size.

As for optimized implementations of strnlen vs memchr it isn't clear
that we will delete all of them as they are slower.

Also its wrong way to solve it, a architecture maintainer should add
optimized strnlen implementations, that quite easy when you have memchr
implementation, add few macros to initially add start and different end
handling.

Suggestion to express strlen as memchr would just cause regression. On
my system there happened 9535682 calls of strlen while memchr was called
just 11633 times and rawmemchr 1742 times.

Also purpose of strlen and rawmechr is to be faster than memchr. Again
these should be implemented by architecture maintainer by removing size
checks from memchr implementation.

[PATCH 4/*] Generic string memchr and strnlen

[Wilco Dijkstra]

Getting back to this, if you don't have an optimized strnlen then
it is always better to try to use memchr (there are 14 optimized
implementations of memchr but only 6 for strnlen).

So I'd suggest changing strnlen in an independent patch as:

__strnlen (const char *str, size_t n)
{
  char *ret = __memchr (str, 0, n); 
  return ret ? ret - str : n;
}

It also looks worthwhile to express strlen and rawmemchr as memchr
so that you only need one highly optimized function rather than many.
Deferring to more widely implemented optimized assembler functions
should result in better performance than trying to optimize these
functions in C.

Wilco