On 25/08/2026 14:30, Wilco Dijkstra wrote:
>
> The existing Arm search_line_fast 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 3 bits of each character using 2 64-bit TBLs and compare
> the 128-bit result with the original input. The lookup table contains
> the 4 search characters at entries MOD 8, so a match results in the same
> character. This works because the low 3 bits of the search characters
> are unique.
>
> The optimized sequence is less than a third of the old code:
>
> vmov.i8 q12, #7 @ v16qi
> vldr d22, .L29
> .L25:
> vld1.8 {d18-d19}, [r0]!
> vand q10, q9, q12
> vtbl.8 d16, {d22}, d20
> vtbl.8 d17, {d22}, d21
> vceq.i8 q8, q8, q9
> vaddhn.i16 d16, q8, q8
> vmov r2, r3, d16 @ int
> orrs r1, r2, r3
> beq .L25
> cmp r2, #0
> rbiteq r2, r3
> rbitne r2, r2
> clzeq r2, r2
> clzne r2, r2
> addeq r2, r2, #32
> sub r2, r2, #61
> add r0, r0, r2, asr #2
> bx lr
>
> Performance is significantly better as a result: on a huge trace that replays
> the calls from libcpp it is ~24% faster on Neoverse N1.
>
> Passes bootstrap, OK for commit?
>
> libcpp/ChangeLog:
>
> * lex.cc (search_line_fast): Optimized Arm implementation.
This is really, neat. Thank you. A couple of additional comments I would like
adding, but otherwise this is OK.
>
> ---
>
> diff --git a/libcpp/lex.cc b/libcpp/lex.cc
> index
> 0e4d29a2950a45b9e43f4673bf69394134264660..0c4e479ec4b847fd136a4c1950603d2ef69d6806
> 100644
> --- a/libcpp/lex.cc
> +++ b/libcpp/lex.cc
> @@ -785,64 +785,49 @@ search_line_fast (const uchar *s, const uchar *end)
> #elif defined (__ARM_NEON)
> #include "arm_neon.h"
>
> -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);
> +/* A fast NEON scanner implementation using table lookup.
>
> - unsigned int misalign, found, mask;
> - const uint8_t *p;
> - uint8x16_t data;
> + Lookup the low 3 bits of each character using 2 64-bit TBLs and compare
> + the 128-bit result with the original input. The lookup table contains
> + the 4 search characters at entries MOD 8, so a match results in the same
> + character. This works because the low 3 bits of the search characters
> + are unique.
Add a note that this assumes the ASCII encoding set. I've never seen anything
else used on Arm processors, but it's not beyond the bounds of possibility.
>
> - /* Align the source pointer. */
> - misalign = (uintptr_t)s & 15;
> - p = (const uint8_t *)((uintptr_t)s & -16);
> - data = vld1q_u8 (p);
> + 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.
> +*/
>
> - /* Create a mask for the bytes that are valid within the first
> - 16-byte block. The Idea here is that the AND with the mask
> - within the loop is "free", since we need some AND or TEST
> - insn in order to set the flags for the branch anyway. */
> - mask = (-1u << misalign) & 0xffff;
> +static_assert (CPP_BUFFER_PADDING >= 16, "");
>
> - /* Main loop, processing 16 bytes at a time. */
> - goto start;
> +static const uchar *
> +search_line_fast (const uchar *s, const uchar *end ATTRIBUTE_UNUSED)
> +{
> + uint8x16_t data, res, m;
> + uint8x8_t tab, res1, res2;
> + uint64_t mask;
> + m = vdupq_n_u8 (0x7);
> + tab = (uint8x8_t) vdup_n_u64 (0x3f000d5c000a0001UL);
There are two things that would make this a bit clearer:
Put the 'ascii' characters in a comment alongside the constant (perhaps move it
to a #define)
/* '?', 0, '\r', '\\', 0, '\n', 0, impossible. */
#define BSL_NL_RET_QRY 0x3f000d5c000a0001UL
I think it would be worth a comment on exactly how this code works (it takes
some thinking about). Perhaps
/* The algorithm below performs
(tab[data[lane]%8] == data[lane])
in parallel for each character in the input string, which will be true iff
the character is one we are looking for. The 'impossible' encoding ensures
we cannot match against a NUL byte (other 0 values are also impossible). */
>
> - do
> + while (1)
> {
> - uint8x8_t l;
> - uint16x4_t m;
> - uint32x2_t n;
> - uint8x16_t t, u, v, w;
> -
> - p += 16;
> - data = vld1q_u8 (p);
> - mask = 0xffff;
> -
> - start:
> - 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 = vandq_u8 (vorrq_u8 (v, w), xmask);
> - l = vpadd_u8 (vget_low_u8 (t), vget_high_u8 (t));
> - m = vpaddl_u8 (l);
> - n = vpaddl_u16 (m);
> -
> - found = vget_lane_u32 ((uint32x2_t) vorr_u64 ((uint64x1_t) n,
> - vshr_n_u64 ((uint64x1_t) n, 24)), 0);
> - found &= mask;
> + data = vld1q_u8 (s);
> + s += 16;
> + res = vandq_u8 (data, m);
> + res1 = vtbl1_u8 (tab, vget_low_u8 (res));
> + res2 = vtbl1_u8 (tab, vget_high_u8 (res));
> + res = vcombine_u8 (res1, res2);
> + res = vceqq_u8 (res, data);
> + mask = (uint64_t) vaddhn_u16 ((uint16x8_t)res, (uint16x8_t)res);
> + /* Use asm to ensure the vmov r2, r3, d16 to transfer 'mask' to scalar
> + registers does not get split into 32-bit transfers. */
> + asm ("" : "+r" (mask));
> + /* After CTZ adjust for ADDHN bias and the post-increment of 's'. */
> + if (mask)
> + return s + ((__builtin_ctzll (mask) + 3 - 16 * 4) >> 2);
> }
> - while (!found);
> -
> - /* FOUND contains 1 in bits for which we matched a relevant
> - character. Conversion to the byte index is trivial. */
> - found = __builtin_ctz (found);
> - return (const uchar *)p + found;
> }
>
> #else
R.
