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

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

[Wilco Dijkstra]

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.

Why do this?

> So comments? How this perform on different architectures?

In my view using 9 operations for a combined zero check and test 
for another character is too much, it should be 5-7 operations at 
most (the general form is (x - 0x01010101) & ~x & 0x80808080
which is just 3).

You can optimize things further by calculating partial masks for each
of the unrolled cases, ORing them together and only doing a single test
per loop iteration rather than 4 or 8. This also avoids adding a lot of
code and branches to the inner loop which makes the unrolling pointless.

The other thing is support for big-endian - this is generally tricky as
the mask returned by the zero check won't work even if byte-reversed.

Finally first_nonzero_byte should just use __builtin_ffsl (yet another
function that should be inlined by default in the generic string.h...).

Wilco

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

[Ondřej Bílka]

On Wed, May 27, 2015 at 01:35:58PM +0100, Wilco Dijkstra wrote:
> 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.
> 
> Why do this?
> 
> > So comments? How this perform on different architectures?
> 
> In my view using 9 operations for a combined zero check and test 
> for another character is too much, it should be 5-7 operations at 
> most (the general form is (x - 0x01010101) & ~x & 0x80808080
> which is just 3).
>
yes I lost track of that when I tried debugging skeleton and eliminate
possibilities so its now suboptimal. But still it was around 33% faster than
current on my sandy_bridge. Now I use following combined check
exploiting ascii

((s - 0x0101) | ((s ^ c) - 0x0101)) & (~s) & 0x8080
 
will submit that on v3.

> You can optimize things further by calculating partial masks for each
> of the unrolled cases, ORing them together and only doing a single test
> per loop iteration rather than 4 or 8.

Already done in skeleton. I also rely on that gcc will use
distributivity to do only one & 0x8080 of combined mask.

Code will likely suboptimal based on my experience, for similar loops
gcc decided that when calculating combined mask its beneficial to spill
lot of registers to save individual masks that are useless for all
iterations except last.

I need to recall how I bypassed that gcc bug when I used similar
skeletons as template of x64 assembly.

> This also avoids adding a lot of
> code and branches to the inner loop which makes the unrolling pointless.
> 
> The other thing is support for big-endian - this is generally tricky as
> the mask returned by the zero check won't work even if byte-reversed.
> 
Nice catch, didn't though about that. Short answer is that you need a
more complicated expression that doesn't cause carry propagation like

(((x | 128) - 127) ^ 128) & ~x & 128

Then you could do byte reversal but its isnt needed as it would be
faster to count leading zero bytes directly.

So we will need add separate BIG_ENDIAN_EXPRESSION macro to support
these. Possibly one could squeeze extra performance if he is more
careful but I don't care that much.

Then first_nonzero_byte would need some work to support that, you could
do it directly without reversing.

> Finally first_nonzero_byte should just use __builtin_ffsl (yet another
> function that should be inlined by default in the generic string.h...).
> 
Yes when architecture supports that. When you need to emulate that with
software you can make it faster. You need to focus only on 8 bits
instead 64, a generic function there uses only one multiplication.

For full you need to use something like debruijn method that also needs
array lookup, like one from wiki

table[0..31] initialized by: for i from 0 to 31: table[ ( 0x077CB531 * (
1 << i ) ) >> 27 ] ← i
function ctz_debruijn (x)
    return table[((x & (-x)) * 0x077CB531) >> 27]


Also its possible to combine masks, question is if it saves anything. On
x64 you could use movmskb instruction that extract high bits of xmm
registers and packs them as 16bit int. 

You could emulate that but its more expensive, for example with

unsigned long 
pack (unsigned long p)
{
  return (0x0102040810204080 * (p >> 7)) >> 56;
}

So to check 32 bytes at once you would need evaluate this:

ffsl (pack(mask0) | (pack(mask1) << 8) | (pack(mask2) << 16) | (pack(mask3) << 24))

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

[Chris Metcalf]

On 05/27/2015 12:02 PM, Ondřej Bílka wrote:
>> The other thing is support for big-endian - this is generally tricky as
>> >the mask returned by the zero check won't work even if byte-reversed.
>> >
> Nice catch, didn't though about that. Short answer is that you need a
> more complicated expression that doesn't cause carry propagation like
>
> (((x | 128) - 127) ^ 128) & ~x & 128
>
> Then you could do byte reversal but its isnt needed as it would be
> faster to count leading zero bytes directly.
>
> So we will need add separate BIG_ENDIAN_EXPRESSION macro to support
> these. Possibly one could squeeze extra performance if he is more
> careful but I don't care that much.
>
> Then first_nonzero_byte would need some work to support that, you could
> do it directly without reversing.
>

See sysdeps/tile/tilegx/strchrnul.c, which uses a string-endian.h
header to manage bigendian mode.

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

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

[Joseph Myers]

On Wed, 27 May 2015, Wilco Dijkstra wrote:

> Finally first_nonzero_byte should just use __builtin_ffsl (yet another
> function that should be inlined by default in the generic string.h...).

Will GCC always inline __builtin_ffsl (or call a libgcc function) rather 
than generating a call to ffsl (user namespace) on some architectures?  If 
it can ever call ffsl you need to do something similar to how we handle 
__mempcpy calling __builtin_mempcpy (include/string.h redeclares mempcpy 
with __asm__ ("__mempcpy"), so that libc-internal calls to __mempcpy 
really do call that function at the assembler level if not inlined, rather 
than calling mempcpy and having namespace issues).

-- 
Joseph S. Myers
joseph@codesourcery.com

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

[Ondřej Bílka]

On Thu, May 28, 2015 at 05:36:04PM +0000, Joseph Myers wrote:
> On Wed, 27 May 2015, Wilco Dijkstra wrote:
> 
> > Finally first_nonzero_byte should just use __builtin_ffsl (yet another
> > function that should be inlined by default in the generic string.h...).
> 
> Will GCC always inline __builtin_ffsl (or call a libgcc function) rather 
> than generating a call to ffsl (user namespace) on some architectures?  If 
> it can ever call ffsl you need to do something similar to how we handle 
> __mempcpy calling __builtin_mempcpy (include/string.h redeclares mempcpy 
> with __asm__ ("__mempcpy"), so that libc-internal calls to __mempcpy 
> really do call that function at the assembler level if not inlined, rather 
> than calling mempcpy and having namespace issues).
> 
However it doesn't do it that well, I reported bug about that somewhere.
So after all you need to make assembly dump and fix gcc mistakes.

It don't eliminate ureachable checks when you put zero there, like for

int 
foo(int x)
{
  if (!x)
    return bar();
  return __builtin_ffsl(x);
}

You get following assembly:

    .cfi_startproc
        testl   %edi, %edi
        je      .L4
        movslq  %edi, %rax
        movq    $-1, %rdx
        bsfq    %rax, %rax
        cmove   %rdx, %rax
        addq    $1, %rax
        ret

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

[Joseph Myers]

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

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

> However it doesn't do it that well, I reported bug about that somewhere.
> So after all you need to make assembly dump and fix gcc mistakes.
> 
> It don't eliminate ureachable checks when you put zero there, like for
> 
> int 
> foo(int x)
> {
>   if (!x)
>     return bar();
>   return __builtin_ffsl(x);
> }

Well, if you don't care about the value for zero, using __builtin_clz is 
an option (and guaranteed to expand to a libgcc call, not a call to ffs, 
if not inlined, so no possible namespace issues).

-- 
Joseph S. Myers
joseph@codesourcery.com

[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