public inbox for libc-alpha@sourceware.org
 help / color / mirror / Atom feed
* [PATCH 1/*] Generic string function optimization: Add skeleton
@ 2015-05-27  9:19 Ondřej Bílka
  2015-05-27  9:19 ` [PATCH 2/*] Optimize generic strchrnul and strchr Ondřej Bílka
                   ` (4 more replies)
  0 siblings, 5 replies; 26+ messages in thread
From: Ondřej Bílka @ 2015-05-27  9:19 UTC (permalink / raw)
  To: libc-alpha

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;
+}
-- 


^ permalink raw reply	[flat|nested] 26+ messages in thread
* Re: [PATCH 2/*] Optimize generic strchrnul and strchr
@ 2015-05-27 14:10 Wilco Dijkstra
  2015-05-27 20:33 ` Ondřej Bílka
  2015-05-28 18:05 ` Joseph Myers
  0 siblings, 2 replies; 26+ messages in thread
From: Wilco Dijkstra @ 2015-05-27 14:10 UTC (permalink / raw)
  To: 'Ondřej Bílka'; +Cc: libc-alpha

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


^ permalink raw reply	[flat|nested] 26+ messages in thread
end of thread, other threads:[~2015-06-16 12:36 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-05-27  9:19 [PATCH 1/*] Generic string function optimization: Add skeleton Ondřej Bílka
2015-05-27  9:19 ` [PATCH 2/*] Optimize generic strchrnul and strchr Ondřej Bílka
2015-05-27 10:46   ` [PATCH 2/* v2] " Ondřej Bílka
2015-05-28 15:23     ` [PATCH 2/* v3] " Ondřej Bílka
2015-05-27 10:41 ` [PATCH 1/* v2] Generic string function optimization: Add skeleton Ondřej Bílka
2015-05-27 10:51   ` [PATCH 3/* v2] Generic string strlen and rawmemchr Ondřej Bílka
2015-05-27 13:12     ` [PATCH 4/*] Generic string memchr and strnlen Ondřej Bílka
2015-05-28 15:39       ` [PATCH 4/* v2] " Ondřej Bílka
2015-05-28 15:29     ` [PATCH 3/* v2] Generic string strlen and rawmemchr Ondřej Bílka
2015-05-28 15:06 ` [PATCH 1/* v3] Generic string function optimization: Add skeleton Ondřej Bílka
2015-05-28 19:29   ` Richard Henderson
2015-05-28 20:10     ` Ondřej Bílka
2015-05-28 22:37       ` Joseph Myers
2015-05-28 23:40         ` Ondřej Bílka
2015-05-29 11:47           ` Joseph Myers
2015-05-29 11:58             ` Ondřej Bílka
2015-05-29 12:56               ` Joseph Myers
2015-06-16 13:43                 ` Ondřej Bílka
2015-05-28 15:57 ` [PATCH 5/*] Generic string function optimization: strcmp and strncmp Ondřej Bílka
2015-05-28 18:41 ` [PATCH 6/*] Generic string function optimization: strcasestr Ondřej Bílka
2015-05-27 14:10 [PATCH 2/*] Optimize generic strchrnul and strchr Wilco Dijkstra
2015-05-27 20:33 ` Ondřej Bílka
2015-05-28 11:27   ` Chris Metcalf
2015-05-28 18:05 ` Joseph Myers
2015-05-28 19:41   ` Ondřej Bílka
2015-05-28 20:36     ` Joseph Myers

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).