v2: Based on Alexander's feedback, make use of the padding to get further
speedup. Improve the algorithm to use single-reg TBL lookup.
The existing AdvSIMD search_line_neon is ancient and not well optimized.
Optimize it for typical inputs (short lines) - what matters is to quickly
get the match result for the first few vectors with minimal initialization
overhead. We simply loop until a match is found even if the input pointer
is unaligned or close to the end. Since this may overread, it relies on
*end containing a match and CPP_BUFFER_PADDING >= 16.
Lookup the low 4 bits of each character using TBL and compare the result
with the original input. The lookup table contains the 4 search characters
at entries MOD 16, so a match results in the same character. This works
because the low 4 bits of the search characters are unique.
The optimized sequence is less than half that of the old code:
.L44:
ldr q30, [x0, 16]!
.L43:
and v31.16b, v30.16b, v28.16b
tbl v31.16b, {v29.16b}, v31.16b
cmeq v31.16b, v31.16b, v30.16b
addhn v31.8b, v31.8h, v31.8h
fmov x1, d31
cbz x1, .L44
and x1, x1, 1229782938247303441
rbit x1, x1
clz x1, x1
add x0, x0, x1, lsr 2
ret
Performance is significantly better as a result: on a huge trace that replays
the calls from libcpp it is ~54% faster on Neoverse V2 and ~42% on Neoverse N1.
Passes bootstrap, OK for commit?
libcpp/ChangeLog:
* lex.cc (search_line_neon): New optimized AdvSIMD implementation.
---
diff --git a/libcpp/lex.cc b/libcpp/lex.cc
index
ee6d6e01803d8a98b2136e51ed92136af30f32fd..84318db97ec8168a9022a4493a050e3f09fbb61b
100644
--- a/libcpp/lex.cc
+++ b/libcpp/lex.cc
@@ -644,96 +644,55 @@ 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. */
-
-#define AARCH64_MIN_PAGE_SIZE 4096
+/* A fast AdvSIMD scanner implementation using table lookup.
+
+ Lookup the low 4 bits of each character using TBL and compare the
+ result with the original input. The lookup table contains the 4
+ search characters at entries MOD 16, so a match results in the same
+ character. This works because the low 4 bits of the search
+ characters are unique.
+
+ 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%
+
+ To get good performance, what matters is to quickly get the match result
+ for the first few vectors with minimal initialization overhead.
+ We simply loop until a match is found even if the input pointer is
+ unaligned or close to the end. Since this may overread, it relies on
+ *end containing a match and CPP_BUFFER_PADDING >= 16. */
+
+static_assert (CPP_BUFFER_PADDING >= 16, "");
+
+/* TBL lookup with each search char at (ch % 16). Avoid matching NUL by
+ setting the first entry to 1. */
+static const uint8_t table[16] =
+ { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, '\n', 0, '\\', '\r', 0, '?' };
static const uchar *
search_line_neon (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);
+ uint8x16_t d, res, tab, m;
+ uint16x8_t t;
+ uint64_t mask;
+ m = vdupq_n_u8 (0xf);
+ tab = vld1q_u8 (table);
+ d = vld1q_u8 (s);
-#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
-
- unsigned int found;
- const uint8_t *p;
- uint8x16_t data;
- uint8x16_t t;
- uint16x8_t m;
- uint8x16_t u, v, w;
-
- /* Align the source pointer. */
- p = (const uint8_t *)((uintptr_t)s & -16);
-
- /* 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;
-
- 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 (1)
{
- 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;
+ t = (uint16x8_t) vceqq_u8 (vqtbl1q_u8 (tab, vandq_u8 (d, m)), d);
+ mask = vget_lane_u64 ((uint64x1_t)vaddhn_u16 (t, t), 0);
+ if (mask != 0)
+ return s + (__builtin_ctzl (mask & 0x1111111111111111UL) >> 2);
+ s += 16;
+ d = vld1q_u8 (s);
}
-
- 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));
}
#ifdef HAVE_SVE2
