基于ARMv8的SWAR范式实现uint16_t数组并行min/max方案问询

问题背景 #

现有两个uint16_t[4]类型数组a和b，每个元素取值范围为[0, 16383]（第14、15位未置位）。原实现通过循环逐元素比较取min/max，现在要求在64位ARMv8平台上采用SWAR（SIMD-within-a-register）范式，通过位操作在单轮迭代中完成4组元素的min/max计算，且性能优于原循环实现，同时不能使用SIMD指令。

实现方案 #

C语言实现（SWAR位操作） #

利用4个uint16_t刚好可以打包为一个64位整数的特性，结合元素仅14位有效、差值不会溢出16位有符号范围的特点，通过位掩码一次性完成所有元素的min/max选择：

#include <stdint.h>

void swar_minmax(uint16_t a[4], uint16_t b[4], uint16_t min[4], uint16_t max[4]) {
    // 将数组打包为64位整数（a[0]对应低16位，a[3]对应高16位）
    uint64_t va = ((uint64_t)a[3] << 48) | ((uint64_t)a[2] << 32) | ((uint64_t)a[1] << 16) | a[0];
    uint64_t vb = ((uint64_t)b[3] << 48) | ((uint64_t)b[2] << 32) | ((uint64_t)b[1] << 16) | b[0];

    // 计算有符号差值，元素仅14位有效，差值不会溢出int16_t范围
    int64_t diff = (int64_t)va - (int64_t)vb;
    // 构造掩码：每个16位块中，若a[i] < b[i]则为0xFFFF，否则为0x0000
    uint64_t mask = (uint64_t)(diff >> 15);

    // 一次性计算所有元素的min和max打包值
    uint64_t min_packed = (va & mask) | (vb & ~mask);
    uint64_t max_packed = (va & ~mask) | (vb & mask);

    // 将打包值拆包回数组
    min[0] = (uint16_t)min_packed;
    min[1] = (uint16_t)(min_packed >> 16);
    min[2] = (uint16_t)(min_packed >> 32);
    min[3] = (uint16_t)(min_packed >> 48);

    max[0] = (uint16_t)max_packed;
    max[1] = (uint16_t)(max_packed >> 16);
    max[2] = (uint16_t)(max_packed >> 32);
    max[3] = (uint16_t)(max_packed >> 48);
}

原理说明：

• 元素仅14位有效，因此两个元素的差值范围为[-16383, 16383]，完全落在int16_t的表示范围内，用int64_t计算差值时，每个16位块的符号位能准确反映a[i]和b[i]的大小关系。
• 对差值做算术右移15位，每个16位块会被符号扩展为全0（a[i] >= b[i]）或全1（a[i] < b[i]），生成的掩码可直接用于选择对应元素的min和max。
• 整个过程无分支、无循环，所有操作均为64位寄存器级运算，ARMv8平台上这些位操作均为单周期指令，性能远优于原循环实现。

ARMv8内联汇编实现 #

直接使用ARMv8指令集完成打包、差值计算、掩码生成及min/max选择，进一步优化性能：

#include <stdint.h>

void swar_minmax_asm(uint16_t a[4], uint16_t b[4], uint16_t min[4], uint16_t max[4]) {
    uint64_t min_packed, max_packed;

    __asm__ volatile (
        // 加载数组a并打包为64位整数va
        "ldp    %w0, %w1, [%[a_ptr]]\n"
        "ldp    %w2, %w3, [%[a_ptr], #8]\n"
        "orr    %x0, %x0, %x1, lsl #16\n"
        "orr    %x0, %x0, %x2, lsl #32\n"
        "orr    %x0, %x0, %x3, lsl #48\n"

        // 加载数组b并打包为64位整数vb
        "ldp    %w1, %w2, [%[b_ptr]]\n"
        "ldp    %w3, %w4, [%[b_ptr], #8]\n"
        "orr    %x1, %x1, %x2, lsl #16\n"
        "orr    %x1, %x1, %x3, lsl #32\n"
        "orr    %x1, %x1, %x4, lsl #48\n"

        // 计算差值、生成掩码
        "subs   %x2, %x0, %x1\n"
        "asr    %x2, %x2, #15\n"

        // 计算max_packed = (va & ~mask) | (vb & mask)
        "bic    %x3, %x0, %x2\n"
        "and    %x4, %x1, %x2\n"
        "orr    %x3, %x3, %x4\n"

        // 计算min_packed = (va & mask) | (vb & ~mask)
        "and    %x4, %x0, %x2\n"
        "bic    %x0, %x1, %x2\n"
        "orr    %x0, %x4, %x0\n"

        // 输出结果
        "mov    %[min_packed], %x0\n"
        "mov    %[max_packed], %x3\n"
        : [min_packed] "=&r"(min_packed), [max_packed] "=&r"(max_packed),
          "=&r"(va), "=&r"(vb), "=&r"(diff), "=&r"(tmp)
        : [a_ptr] "r"(a), [b_ptr] "r"(b)
        : "w1", "w2", "w3", "w4", "cc"
    );

    // 拆包回数组
    min[0] = (uint16_t)min_packed;
    min[1] = (uint16_t)(min_packed >> 16);
    min[2] = (uint16_t)(min_packed >> 32);
    min[3] = (uint16_t)(min_packed >> 48);

    max[0] = (uint16_t)max_packed;
    max[1] = (uint16_t)(max_packed >> 16);
    max[2] = (uint16_t)(max_packed >> 32);
    max[3] = (uint16_t)(max_packed >> 48);
}

原理说明：

• 使用ldp指令批量加载数组元素，减少内存访问次数；
• 用orr指令直接将32位寄存器中的元素组合为64位整数；
• subs做有符号减法得到差值，asr算术右移生成掩码；
• 通过bic（位清除，等效于&~）、and、orr指令完成min/max的选择，所有指令均为单周期执行，无分支开销，性能达到最优。

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