On 02/09/2026 16:00, Wilco Dijkstra wrote:
> Hi Richard,
>
> I've updated the comments to mention ASCII and added a static assert to
> Arm and AArch64 versions. The explanation of the algorithm is clearer too.
>
> Cheers,
> Wilco
>
>
> v2: Improve comments describing the algorithm, assert if not ASCII.
>
OK.
Thanks for making the clarifications.
R.
> 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, thus if tab[ch % 8] == ch, we
> have found a match. This works because the low 3 bits of the search
> characters are unique in ASCII, allowing the use of TBL. Use a special
> value in tab[0] to avoid matching NUL.
>
> 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.
>
> ---
>
> diff --git a/libcpp/lex.cc b/libcpp/lex.cc
> index
> 0e4d29a2950a45b9e43f4673bf69394134264660..3307d93622a0796990826e8b6c73b4ef82ca30b4
> 100644
> --- a/libcpp/lex.cc
> +++ b/libcpp/lex.cc
> @@ -647,10 +647,11 @@ search_line_fast (const uchar *s, const uchar *end
> ATTRIBUTE_UNUSED)
> /* 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.
> + the 128-bit result with the original input. The lookup table contains
> + the 4 search characters at entries MOD 16, thus if tab[ch % 16] == ch, we
> + have found a match. This works because the low 4 bits of the search
> + characters are unique in ASCII, allowing the use of TBL. Use a special
> + value in tab[0] to avoid matching NUL.
>
> Typical statistics for number of characters till a match:
> 1-15: 30.9%
> @@ -668,6 +669,8 @@ search_line_fast (const uchar *s, const uchar *end
> ATTRIBUTE_UNUSED)
> *end containing a match and CPP_BUFFER_PADDING >= 16. */
>
> static_assert (CPP_BUFFER_PADDING >= 16, "");
> +static_assert ('\n' == 10 && '\r' == 13 && '\\' == 92 && '?' == 63,
> + "non-ASCII encoding");
>
> /* TBL lookup with each search char at (ch % 16). Avoid matching NUL by
> setting the first entry to 1. */
> @@ -785,64 +788,53 @@ 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, thus if tab[ch % 8] == ch, we
> + have found a match. This works because the low 3 bits of the search
> + characters are unique in ASCII, allowing the use of TBL. Use a special
> + value in tab[0] to avoid matching NUL.
>
> - /* 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, "");
> +static_assert ('\n' == 10 && '\r' == 13 && '\\' == 92 && '?' == 63,
> + "non-ASCII encoding");
>
> - /* 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);
> + /* Equivalent: uint8_t tab[8] = { 1, 0, '\n', 0, '\\', '\r', 0, '?' }. */
> + tab = (uint8x8_t) vdup_n_u64 (0x3f000d5c000a0001UL);
>
> - 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
