M1 Mac上快速查找u16数组中首个小于指定值元素的方法

核心思路 #

M1基于ARMv8.5-A架构，NEON向量指令可一次处理8个16位无符号整数（u16），能大幅提升遍历效率。关键是利用向量比较生成掩码，再快速检测掩码中是否存在符合条件的元素，从而提前中断循环。

处理向量比较结果的方法 #

NEON的vclt.u16指令会对两个向量的对应元素做“小于”比较，结果向量中符合条件的元素设为0xFFFF（全1），不符合的设为0。将结果同步到通用寄存器有两种高效方式：

1. 取向量最大值判断
   使用vmaxv.u16指令将结果向量的最大值存入32位寄存器，若最大值不为0，说明向量中存在符合条件的元素：

   vclt.u16 v1.8h, v0.8h, v2.8h  @ v0是加载的数组元素，v2是重复填充的目标值
   vmaxv.u16 s3, v1.8h           @ 将v1的最大值存入32位寄存器s3
   fmov w3, s3                   @ 转存到通用寄存器w3
   cbnz w3, found_match          @ 若w3≠0，跳转到匹配处理逻辑
   

2. 统计匹配元素数量
   使用cntp指令直接统计结果向量中非零元素的个数，结果存入64位通用寄存器，只要数量大于0就说明存在匹配：

   vclt.u16 v1.8h, v0.8h, v2.8h
   cntp x3, v1.8h                @ 统计v1中非零元素数量到x3
   cbnz x3, found_match          @ 数量>0则跳转
   

中断循环的实现 #

遍历数组的循环中，每次处理一个8元素向量后，用上述方法检测是否存在匹配元素。一旦检测到，立即跳出循环，再逐个检查当前向量内的元素，找到第一个符合条件的元素的精确索引。

完整示例（C内联汇编） #

以下是针对M1优化的C+NEON内联汇编实现：

#include <stdint.h>
#include <stddef.h>

size_t find_first_less_than_u16(const uint16_t* arr, size_t len, uint16_t val) {
    size_t i = 0;
    // 处理16字节对齐的批量元素（一次8个u16）
    for (; i + 7 < len; i += 8) {
        uint32_t match_flag;
        __asm__ volatile (
            "ld1 {v0.8h}, [%1]\n"          // 加载8个u16到v0向量寄存器
            "dup v2.8h, %w2\n"             // 将目标值val重复填充到v2的8个位置
            "vclt.u16 v1.8h, v0.8h, v2.8h\n"// 比较每个元素是否小于val
            "vmaxv.u16 s3, v1.8h\n"        // 取结果向量的最大值到s3
            "fmov %w0, s3\n"               // 转存到通用寄存器
            : "=r"(match_flag)
            : "r"(arr + i), "r"(val)
            : "v0", "v1", "v2", "s3", "memory"
        );
        if (match_flag != 0) {
            // 逐个检查当前向量内的元素，找到第一个匹配项
            for (size_t j = 0; j < 8; j++) {
                if (arr[i + j] < val) {
                    return i + j;
                }
            }
        }
    }
    // 处理剩余不足8个的元素
    for (; i < len; i++) {
        if (arr[i] < val) {
            return i;
        }
    }
    return len; // 未找到匹配元素
}

注意事项 #

• 内存对齐：若数组是16字节对齐的，ld1指令效率更高，可使用aligned_alloc(16, size)保证分配的内存对齐。
• 指令兼容性：cntp指令支持ARMv8.1-A及以上架构（M1完全兼容），若需兼容更老ARM设备，优先使用vmaxv的方式。

内容的提问来源于stack exchange，提问作者Basic Block