[PATCH] aarch64: add optimised strspn/strcspn
remph
lhr@disroot.org
Wed Aug 13 00:08:13 GMT 2025
Requires Neon (aka. Advanced SIMD). Looks up 16 characters at a time.
Best case (which should be the vast majority of real-world cases) is a
2-3x perfomance improvement. Worst case trades off more arithmetic for
fewer instructions and memory accesses, and gets a 25% improvement on a
Cortex-A52 and a 10% decline on a better-pipelined Cortex-A72. But
that's academic since no real-world code will hit the worst-case branch.
There is also a ~30% speedup on the strtok & strsep benchtests.
Signed-off-by: remph <lhr@disroot.org>
---
sysdeps/aarch64/strcspn.c | 2 +
sysdeps/aarch64/strspn.c | 248 ++++++++++++++++++++++++++++++++++++++
2 files changed, 250 insertions(+)
create mode 100644 sysdeps/aarch64/strcspn.c
create mode 100644 sysdeps/aarch64/strspn.c
diff --git a/sysdeps/aarch64/strcspn.c b/sysdeps/aarch64/strcspn.c
new file mode 100644
index 00000000..4604b007
--- /dev/null
+++ b/sysdeps/aarch64/strcspn.c
@@ -0,0 +1,2 @@
+#define USE_AS_STRCSPN 1
+#include "strspn.c"
diff --git a/sysdeps/aarch64/strspn.c b/sysdeps/aarch64/strspn.c
new file mode 100644
index 00000000..b6768d21
--- /dev/null
+++ b/sysdeps/aarch64/strspn.c
@@ -0,0 +1,248 @@
+/* Copyright (C) 2025 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <arm_neon.h>
+#include <stdbit.h>
+#include <string.h>
+#include <libc-pointer-arith.h>
+
+#ifdef __AARCH64EB__
+# define SH_FW <<=
+#else
+# define SH_FW >>=
+#endif
+
+static inline uint64_t __attribute__ ((__const__))
+narrow_mask (uint8x16_t wide)
+{
+ union {
+ uint8x16_t wide;
+ uint8x8_t narrow;
+ uint16x8_t hwords;
+ uint64x2_t dwords;
+ } a = {wide};
+ a.narrow = vshrn_n_u16 (a.hwords, 4);
+ return vgetq_lane_u64 (a.dwords, 0);
+}
+
+static inline uint8x16_t __attribute__ ((__const__))
+lookup_first_tbl (uint8x16x4_t table, uint8x16_t vec)
+{
+#ifdef USE_AS_STRCSPN
+ return vqtbl4q_u8 (table, vec);
+#else
+ uint8x16_t res;
+ /* This is the only way the GCC will move from an immediate rather
+ than another register in the loop. This is better, right? */
+ asm volatile ("mvni %0.4s, 0" : "=w" (res));
+ return vqtbx4q_u8 (res, table, vec);
+#endif
+}
+
+#ifdef USE_AS_STRCSPN
+# define STRSPN strcspn
+# define INIT_SET 0
+#else
+# define STRSPN strspn
+# define INIT_SET -1
+#endif
+
+/* Neon's TBL instruction can look up 16 bytes at a time in a 64-byte
+ table, so for 256 possible values of a byte will take 4 TBLs. However,
+ the table need only include the bytes in SET, and anything that doesn't
+ match that can be considered a miss, so it only needs to be as long as
+ the difference between the highest and lowest bytes. Most invocations
+ will only need one TBL, the vast majority two at most, which is fast. */
+
+size_t __attribute__ ((aligned (64), optimize ("align-loops=64:24")))
+STRSPN (const char * __s, const char * __set)
+{
+ /* SET is ACCEPT for strspn, REJECT for strcspn */
+ const unsigned char * s = (const unsigned char*)__s,
+ * set = (const unsigned char*)__set,
+ *const og_s = s;
+ uint8_t byte_table[0460]; /* 0400 possible bytes + 060 wraparound space */
+ uint8x16x4_t table_a;
+ uint8x16_t vec, vres, voff;
+ uint64_t res;
+ int highest, lowest;
+ uintptr_t off = (uintptr_t)s % 16 * 4;
+
+ s = PTR_ALIGN_DOWN (s, 16);
+
+#ifdef USE_AS_STRCSPN
+ if (__builtin_expect_with_probability (!set[0] || !set[1], 0, 1.0))
+ return strchrnul (__s, set[0]) - __s;
+#else
+ if (__builtin_expect_with_probability (!*set, 0, 1.0))
+ return 0;
+#endif
+
+ /* The table has ones for bytes to reject and zeros for bytes to accept */
+ memset (byte_table, INIT_SET, 0400);
+
+ /* This loop never sets byte_table[0], not even for strcspn, since the
+ table may be offset by LOWEST, so byte_table[0] could actually be
+ byte_table[-(uint8_t)lowest]. It is set later if applicable. */
+ lowest = highest = *set;
+ do
+ {
+ if (*set && *set < lowest)
+ lowest = *set;
+ if (*set > highest)
+ highest = *set;
+ byte_table[*set] = ~INIT_SET;
+ }
+ while (*++set);
+
+ lowest &= 0xf0; /* Align for use as an offset into BYTE_TABLE */
+
+ /* All the __glibc_(un)?likely uses are not as redundant as they might seem:
+ they mean the branches are in descending order of likelihood, as each
+ reflects the likely result *should the previous branch not be taken*,
+ and the GCC really does generate better code with them than without. */
+
+ if (__glibc_unlikely (highest & 0300) && !((highest - lowest) & 0200))
+ {
+ /* will need offset */
+ voff = vdupq_n_u8 (lowest);
+ if (lowest > 0300 - ((highest - lowest) & 0100))
+ memcpy (byte_table + 0400, byte_table, 060); /* wraparound space */
+ table_a = vld1q_u8_x4 (byte_table + lowest);
+ }
+ else
+ {
+#ifdef USE_AS_STRCSPN
+ /* No offset, so no separate NUL test, and the table's 0th element
+ will reflect the real 0 byte */
+ byte_table[0] = 0xff;
+#endif
+ table_a = vld1q_u8_x4 (byte_table);
+ }
+
+ if (!(highest & 0300))
+ {
+ /* All the bytes in SET are <64: only one table is needed. */
+ for (;;)
+ {
+ vec = vld1q_u8 (s);
+ s += 16;
+ res = narrow_mask (lookup_first_tbl (table_a, vec));
+ if (res SH_FW off)
+ break;
+ off = 0;
+ }
+ }
+ else if (__glibc_likely (!((highest - lowest) & 0300)))
+ {
+ /* All the bytes we're looking for fit into a 64-byte table (once
+ aligned), and the offset from the beginning of the table must be
+ accounted for, including a separate check for NULs. */
+ for (;;)
+ {
+ vec = vld1q_u8 (s);
+ s += 16;
+ vres = lookup_first_tbl (table_a, vec - voff);
+ asm ("orr %0.16b, %1.16b, %2.16b"
+ : "=w" (vres) : "w" (vres), "w" (vec == 0));
+ res = narrow_mask (vres);
+ if (res SH_FW off)
+ break;
+ off = 0;
+ }
+ }
+ else
+ {
+ uint8x16x4_t table_b;
+ uint8x16_t v64;
+
+ /* The GCC's optimisations merge signed and unsigned, which turns
+ unsigned char <=SCHAR_MAX into signed char >=0, which is good,
+ but also makes a duplicate negative of 64 to add to VEC rather
+ than subtracting the existing vector, which is bad, so this asm
+ `hides' the real value from the optimiser. */
+ asm ("movi %0.16b, 64" : "=w" (v64));
+
+ if (__glibc_likely (!((highest - lowest) & 0200)))
+ {
+ /* Two-table, 128-byte loop. In theory SET is just bytes, but
+ in practice it's invariably ASCII, so we should never need
+ to go beyond this branch. */
+ uint8x16_t has_nul;
+ table_b = vld1q_u8_x4 (byte_table + (lowest + 64) % 0400);
+ for (;;)
+ {
+ vec = vld1q_u8 (s);
+ s += 16;
+ has_nul = vec == 0;
+ vec -= voff;
+ vres = vbslq_u8 ((int8x16_t)vec >= (int8x16_t)v64,
+ vqtbl4q_u8 (table_b, vec - v64),
+ lookup_first_tbl (table_a, vec));
+ asm ("orr %0.16b, %1.16b, %2.16b"
+ : "=w" (vres) : "w" (vres), "w" (has_nul));
+ res = narrow_mask (vres);
+ if (res SH_FW off)
+ break;
+ off = 0;
+ }
+ }
+ else
+ {
+ uint8x16x4_t table_c, table_d;
+ uint8x16_t vec2, v128 = vdupq_n_u8 (0200);
+ /* Load the whole table */
+ table_b = vld1q_u8_x4 (byte_table + 0100);
+ table_c = vld1q_u8_x4 (byte_table + 0200);
+ table_d = vld1q_u8_x4 (byte_table + 0300);
+ for (;;)
+ {
+ vec = vld1q_u8 (s);
+ s += 16;
+ /* Replacing SUB 128 with BIC 128 only works for values {128..255};
+ obviously the 255 limit is implicit and we test for >=128 */
+ vec2 = vbicq_u8 (vec, v128);
+ res = narrow_mask (
+ vbslq_u8 (vec < v128,
+ vbslq_u8 (vec < v64,
+ vqtbl4q_u8 (table_a, vec),
+ vqtbl4q_u8 (table_b, vec - v64)),
+ vbslq_u8 (vec2 < v64,
+ vqtbl4q_u8 (table_c, vec2),
+ vqtbl4q_u8 (table_d, vec2 - v64))));
+ if (res SH_FW off)
+ break;
+ off = 0;
+ }
+ }
+ }
+
+ /* Like the MOVI asm, this is to disable a GCC optimisation by `hiding'
+ an operation from it. Without this, the GCC adds extra instructions
+ to the hot loops to save the previous value of S, which can sometimes
+ push them over a cacheline. */
+ asm ("sub %0, %1, 16" : "=r" (s) : "r" (s));
+
+ return s - og_s + off / 4 +
+#ifdef __AARCH64EB__
+ stdc_leading_zeros (res)
+#else
+ stdc_trailing_zeros (res)
+#endif
+ / 4;
+}
+libc_hidden_builtin_def (STRSPN)
--
2.50.1
More information about the Libc-alpha
mailing list