The existing AdvSIMD search_line_fast is ancient and not well optimized.
Optimize it for typical inputs (short lines). The algorithm uses hashing
to map the search chars into the range of the table lookup instruction.
The resulting sequence is less than half that of the old code:
ldr q31, [x0]
mul v31.16b, v31.16b, v30.16b
tbl v31.16b, {v24.16b - v27.16b}, v31.16b
addhn v31.8b, v31.8h, v31.8h
umov x2, v31.d[0]
cbz x2, .L23
and x2, x2, 1229782938247303441
rbit x2, x2
clz x2, x2
add x0, x0, x2, lsr 2
ret
Performance is significantly better as a result: 48% faster on Neoverse N1,
67% on Neoverse V1 and 69% on Neoverse V2.
Passes bootstrap, OK for commit?
libcpp/ChangeLog:
(search_line_fast): New optimized AdvSIMD implementation.
---
diff --git a/libcpp/lex.cc b/libcpp/lex.cc
index
391c487bbc1075e7fbad254ae50ebccb002e493f..875b8906616cf63999d6dab7504937a3317a8b18
100644
--- a/libcpp/lex.cc
+++ b/libcpp/lex.cc
@@ -644,97 +644,64 @@ search_line_fast (const uchar *s, const uchar *end
ATTRIBUTE_UNUSED)
#elif defined (__ARM_NEON) && defined (__ARM_64BIT_STATE)
#include "arm_neon.h"
-/* This doesn't have to be the exact page size, but no system may use
- a size smaller than this. ARMv8 requires a minimum page size of
- 4k. The impact of being conservative here is a small number of
- cases will take the slightly slower entry path into the main
- loop. */
+/* A fast AdvSIMD scanner implementation using hashing and table lookup.
-#define AARCH64_MIN_PAGE_SIZE 4096
+ A hash function is used to map the '\n', '\r', '?' and '\\' characters
+ so that both hash(ch) < 64 and (hash(ch) MOD 16) < 8. This allows for
+ a 4-register TBL lookup with 4 MOVI to initialize it. A multiply by 159
+ is used to map the search chars to 19 33 36 and 54.
-static const uchar *
-search_line_fast (const uchar *s, const uchar *end ATTRIBUTE_UNUSED)
-{
- const uint8x16_t repl_nl = vdupq_n_u8 ('\n');
- const uint8x16_t repl_cr = vdupq_n_u8 ('\r');
- const uint8x16_t repl_bs = vdupq_n_u8 ('\\');
- const uint8x16_t repl_qm = vdupq_n_u8 ('?');
- const uint8x16_t xmask = (uint8x16_t) vdupq_n_u64 (0x8040201008040201ULL);
+ Typical statistics for number of characters till a match:
+ 1-15: 30.9%
+ 16-31: 22.2%
+ 32-47: 18.3%
+ 48-63: 14.1%
+ 64-79: 13.0%
+ 80-95: 1.1%
+ >96: 0.3%
-#ifdef __ARM_BIG_ENDIAN
- const int16x8_t shift = {8, 8, 8, 8, 0, 0, 0, 0};
-#else
- const int16x8_t shift = {0, 0, 0, 0, 8, 8, 8, 8};
-#endif
+ To get good performance, what matters is to quickly get the match result
+ for the first few vectors with minimal initialization overhead. Hence we
+ simply loop using the unaligned input till we get close to the end. */
- unsigned int found;
- const uint8_t *p;
- uint8x16_t data;
- uint8x16_t t;
- uint16x8_t m;
- uint8x16_t u, v, w;
+/* Helper to emit movi d0, 0xff000000 for 128-bit vector initializers. */
+#define V(X) (uint8x16_t) vcombine_u64 (vdup_n_u64 (X), vdup_n_u64 (0))
- /* Align the source pointer. */
- p = (const uint8_t *)((uintptr_t)s & -16);
+static const uchar *
+search_line_fast (const uchar *s, const uchar *end)
+{
+ uint8x16x4_t table =
+ { vdupq_n_u8(0), V(0xff000000), V(0xff0000ff00), V(0xff000000000000UL) };
+ uint8x16_t mulc = vdupq_n_u8 (159);
+ uint8x16_t data, hash;
+ uint16x8_t res;
+ uint8x8_t m;
+ uint64_t mask;
- /* Assuming random string start positions, with a 4k page size we'll take
- the slow path about 0.37% of the time. */
- if (__builtin_expect ((AARCH64_MIN_PAGE_SIZE
- - (((uintptr_t) s) & (AARCH64_MIN_PAGE_SIZE - 1)))
- < 16, 0))
- {
- /* Slow path: the string starts near a possible page boundary. */
- uint32_t misalign, mask;
+ const uchar *limit = (const uchar*) ((uintptr_t)end & ~15);
- misalign = (uintptr_t)s & 15;
- mask = (-1u << misalign) & 0xffff;
- data = vld1q_u8 (p);
- t = vceqq_u8 (data, repl_nl);
- u = vceqq_u8 (data, repl_cr);
- v = vorrq_u8 (t, vceqq_u8 (data, repl_bs));
- w = vorrq_u8 (u, vceqq_u8 (data, repl_qm));
- t = vorrq_u8 (v, w);
- t = vandq_u8 (t, xmask);
- m = vpaddlq_u8 (t);
- m = vshlq_u16 (m, shift);
- found = vaddvq_u16 (m);
- found &= mask;
- if (found)
- return (const uchar*)p + __builtin_ctz (found);
- }
- else
+ while (s <= limit)
{
- data = vld1q_u8 ((const uint8_t *) s);
- t = vceqq_u8 (data, repl_nl);
- u = vceqq_u8 (data, repl_cr);
- v = vorrq_u8 (t, vceqq_u8 (data, repl_bs));
- w = vorrq_u8 (u, vceqq_u8 (data, repl_qm));
- t = vorrq_u8 (v, w);
- if (__builtin_expect (vpaddd_u64 ((uint64x2_t)t) != 0, 0))
- goto done;
+ data = vld1q_u8 (s);
+ hash = vmulq_u8 (data, mulc);
+ res = (uint16x8_t) vqtbl4q_u8 (table, hash);
+ m = vaddhn_u16 (res, res);
+ mask = vget_lane_u64 ((uint64x1_t)m, 0);
+ if (mask != 0)
+ return s + (__builtin_ctzl (mask & 0x1111111111111111UL) >> 2);
+ s += 16;
}
- do
- {
- p += 16;
- data = vld1q_u8 (p);
- t = vceqq_u8 (data, repl_nl);
- u = vceqq_u8 (data, repl_cr);
- v = vorrq_u8 (t, vceqq_u8 (data, repl_bs));
- w = vorrq_u8 (u, vceqq_u8 (data, repl_qm));
- t = vorrq_u8 (v, w);
- } while (!vpaddd_u64 ((uint64x2_t)t));
-
-done:
- /* Now that we've found the terminating substring, work out precisely where
- we need to stop. */
- t = vandq_u8 (t, xmask);
- m = vpaddlq_u8 (t);
- m = vshlq_u16 (m, shift);
- found = vaddvq_u16 (m);
- return (((((uintptr_t) p) < (uintptr_t) s) ? s : (const uchar *)p)
- + __builtin_ctz (found));
+ data = vld1q_u8 (limit);
+ hash = vmulq_u8 (data, mulc);
+ res = (uint16x8_t) vqtbl4q_u8 (table, hash);
+ m = vaddhn_u16 (res, res);
+ mask = vget_lane_u64 ((uint64x1_t)m, 0);
+ mask &= 0x1111111111111111UL;
+ mask >>= (uintptr_t)s * 4;
+ return s + (__builtin_ctzl (mask) >> 2);
}
+#undef V
#elif defined (__ARM_NEON)
#include "arm_neon.h"
