> On 18 Aug 2026, at 22:33, Wilco Dijkstra <[email protected]> wrote:
>
> 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?
Ok.
Thanks,
Kyrill
>
> 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
>
