并行地将 64 位整数中的压缩 8 位整数减去 1，SWAR 没有硬件 SIMD

Question

如果我有一个 64 位整数，我将其解释为一个包含 8 个元素的压缩 8 位整数数组。我需要1在处理溢出时从每个压缩整数中减去常量，而一个元素的结果不会影响另一个元素的结果。

我现在有这个代码并且它可以工作，但我需要一个解决方案来并行地减去每个打包的 8 位整数并且不进行内存访问。在 x86 上，我可以使用类似的 SIMD 指令psubb并行减去打包的 8 位整数，但我正在编码的平台不支持 SIMD 指令。（在这种情况下为 RISC-V）。

因此，我正在尝试执行SWAR（寄存器内的 SIMD）以手动取消 a 的字节之间的进位传播uint64_t，执行与此等效的操作：

uint64_t sub(uint64_t arg) {
    uint8_t* packed = (uint8_t*) &arg;

    for (size_t i = 0; i < sizeof(uint64_t); ++i) {
        packed[i] -= 1;
    }

    return arg;
}

我认为你可以用按位运算符来做到这一点，但我不确定。我正在寻找一种不使用 SIMD 指令的解决方案。我正在寻找一个非常便携的 C 或 C++ 解决方案，或者只是它背后的理论，这样我就可以实现我自己的解决方案。

Answer 1

如果您的 CPU 具有高效的 SIMD 指令，则 SSE/MMX paddb( _mm_add_epi8) 也是可行的。Peter Cordes 的回答还描述了 GNU C (gcc/clang) 向量语法以及严格别名 UB 的安全性。我也强烈建议您查看该答案。

自己做uint64_t是完全可移植的，但在访问uint8_t带有uint64_t*. 您uint64_t已经从 a 中的数据开始，将那部分排除在问题之外，但是对于 GNU C，may_aliastypedef 可以解决问题（请参阅 Peter 对此的回答或memcpy）。

否则，您可以分配/声明您的数据，uint64_t并uint8_t*在您需要单个字节时通过它来访问它。 unsigned char*允许为任何东西添加别名，以便避开 8 位元素的特定情况的问题。（如果uint8_t存在的话，假设它是一个unsigned char.可能是安全的。）

请注意，这是对先前不正确算法的更改（请参阅修订历史）。

这是可能的，无需循环进行任意减法，并且对于像1每个字节这样的已知常数会更有效。 主要技巧是通过设置高位来防止每个字节的进位，然后纠正减法结果。

我们将稍微优化这里给出的减法技术。他们定义：

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

与H定义为0x8080808080808080U（即每个打包整数的MSB）。对于递减，y是0x0101010101010101U。

我们知道它的y所有 MSB 都已清除，因此我们可以跳过掩码步骤之一（即y & ~H与y我们的情况相同）。计算过程如下：

1. 我们将每个组件的 MSB 设置x为 1，以便借用不能通过 MSB 传播到下一个组件。称其为调整后的输入。
2. 通过0x01010101010101从校正后的输入中减去，我们从每个分量中减去 1 。由于第 1 步，这不会导致组件间借用。将其称为调整后的输出。
3. 我们现在需要更正结果的 MSB。我们将调整后的输出与原始输入的倒置 MSB 进行异或以完成修复结果。

操作可以写成：

#define U64MASK 0x0101010101010101U
#define MSBON 0x8080808080808080U
uint64_t decEach(uint64_t i){
      return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON);
}

最好是由编译器内联（使用编译器指令强制执行），或者将表达式作为另一个函数的一部分内联编写。

测试用例：

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

性能详情

这是用于单个函数调用的 x86_64 程序集。为了获得更好的性能，它应该内联，希望常量可以尽可能长时间地存在于寄存器中。在常量位于寄存器中的紧密循环中，实际递减需要 5 条指令：优化后的 or+not+and+add+xor。我没有看到可以击败编译器优化的替代方案。

uint64t[rax] decEach(rcx):
    movabs  rcx, -9187201950435737472
    mov     rdx, rdi
    or      rdx, rcx
    movabs  rax, -72340172838076673
    add     rax, rdx
    and     rdi, rcx
    xor     rdi, rcx
    xor     rax, rdi
    ret

通过对以下代码段的一些 IACA 测试：

// Repeat the SWAR dec in a loop as a microbenchmark
uint64_t perftest(uint64_t dummyArg){
    uint64_t dummyCounter = 0;
    uint64_t i = 0x74656a6d27080100U; // another dummy value.
    while(i ^ dummyArg) {
        IACA_START
        uint64_t naive = i - U64MASK;
        i = naive + ((i ^ naive ^ U64MASK) & U64MASK);
        dummyCounter++;
    }
    IACA_END
    return dummyCounter;
}

我们可以证明，在 Skylake 机器上，执行递减、异或和比较+跳转可以在每次迭代不到 5 个周期的情况下执行：

Throughput Analysis Report
--------------------------
Block Throughput: 4.96 Cycles       Throughput Bottleneck: Backend
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.5     0.0  |  1.5  |  0.0     0.0  |  0.0     0.0  |  0.0  |  1.5  |  1.5  |  0.0  |
--------------------------------------------------------------------------------------------------

（当然，对X86-64你只是加载或movq成XMM章第paddb，所以它可能是更有趣的来看看它是如何编译像RISC-V的ISA）。

Answer 2

对于 RISC-V，您可能正在使用 GCC/clang。

有趣的事实：GCC 知道其中一些 SWAR bithack 技巧（显示在其他答案中），并且可以在使用GNU C 本机向量为没有硬件 SIMD 指令的目标编译代码时为您使用它们。（但是 RISC-V 的 clang 只会天真地将其展开为标量操作，因此如果您希望跨编译器获得良好的性能，则必须自己进行操作）。

原生向量语法的一个优点是，当以硬件 SIMD为目标机器时，它将使用它而不是自动向量化你的 bithack 或类似的东西。

它使编写vector -= scalar操作变得容易；语法 Just Works，隐式广播又名 splatting 标量。

还要注意，uint64_t*来自 a的负载uint8_t array[]是严格别名 UB，所以要小心。（另请参阅为什么 glibc 的 strlen 需要如此复杂才能快速运行？ re：在纯 C 中使 SWAR bithacks 严格别名安全）。您可能需要这样的东西来声明一个uint64_t您可以通过指针转换来访问任何其他对象的东西，例如char*在 ISO C/C++ 中的工作方式。

使用这些将 uint8_t 数据放入 uint64_t 以与其他答案一起使用：

// GNU C: gcc/clang/ICC but not MSVC
typedef uint64_t  aliasing_u64 __attribute__((may_alias));  // still requires alignment
typedef uint64_t  aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

进行混叠安全加载的另一种方法是使用memcpyinto a uint64_t，这也消除了alignof(uint64_t) 对齐要求。但是在没有有效未对齐加载的 ISA 上，gcc/clangmemcpy在无法证明指针对齐时不会内联和优化掉，这对性能来说是灾难性的。

TL：DR：最​​好的办法是将数据声明为uint64_t array[...]或动态分配为uint64_t，或者最好alignas(16) uint64_t array[]; 确保对齐到至少 8 个字节，或者如果指定 16 个字节alignas。

由于uint8_t几乎可以肯定unsigned char*，访问uint64_tvia的字节是安全的uint8_t*（但对于 uint8_t 数组则反之亦然）。因此，对于窄元素类型为 的这种特殊情况unsigned char，您可以避开严格别名问题，因为它char很特殊。

GNU C 原生向量语法示例：

GNU C 本机向量总是允许使用它们的底层类型int __attribute__((vector_size(16)))别名（例如，可以安全地别名int但不能float或uint8_t或其他任何东西。

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

// assumes array is 16-byte aligned
void dec_mem_gnu(uint8_t *array) {
    typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias));
    v16u8 *vecs = (v16u8*) array;
    vecs[0] -= 1;
    vecs[1] -= 1;   // can be done in a loop.
}

对于没有任何硬件 SIMD 的 RISC-V，您可以使用vector_size(8)来表达您可以有效使用的粒度，并执行两倍的较小向量。

但是vector_size(8)对于带有 GCC 和 clang 的 x86 编译非常愚蠢：GCC 在 GP 整数寄存器中使用 SWAR bithacks，clang 解包为 2 字节元素以填充 16 字节 XMM 寄存器，然后重新打包。（MMX 已经过时了，以至于 GCC/clang 甚至都懒得使用它，至少对于 x86-64 来说不是。）

但是使用vector_size (16)（Godbolt）我们得到了预期的movdqa/ paddb。（使用由 生成的全 1 向量pcmpeqd same,same）。由于-march=skylake我们仍然得到两个单独的 XMM 操作而不是一个 YMM，因此不幸的是，当前的编译器也不会将向量操作“自动向量化”为更宽的向量：/

对于 AArch64，使用vector_size(8)( Godbolt ) 还不错；ARM/AArch64 可以在带有d或q寄存器的8 或 16 字节块中本地工作。

因此vector_size(16)，如果您想要跨 x86、RISC-V、ARM/AArch64 和 POWER 的可移植性能，您可能想要实际编译。但是，其他一些 ISA 在 64 位整数寄存器中执行 SIMD，例如我认为的 MIPS MSA。

vector_size(8)更容易查看 asm（只有一个寄存器的数据）：Godbolt 编译器资源管理器

# GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector

dec_mem_gnu(unsigned char*):
        lui     a4,%hi(.LC1)           # generate address for static constants.
        ld      a5,0(a0)                 # a5 = load from function arg
        ld      a3,%lo(.LC1)(a4)       # a3 = 0x7F7F7F7F7F7F7F7F
        lui     a2,%hi(.LC0)
        ld      a2,%lo(.LC0)(a2)       # a2 = 0x8080808080808080
                             # above here can be hoisted out of loops
        not     a4,a5                  # nx = ~x
        and     a5,a5,a3               # x &= 0x7f... clear high bit
        and     a4,a4,a2               # nx = (~x) & 0x80... inverse high bit isolated
        add     a5,a5,a3               # x += 0x7f...   (128-1)
        xor     a5,a4,a5               # x ^= nx  restore high bit or something.

        sd      a5,0(a0)               # store the result
        ret

我认为这是与其他非循环答案相同的基本思想；防止进位然后修正结果。

这是 5 个 ALU 指令，比我认为的最佳答案还要糟糕。但看起来关键路径延迟只有 3 个周期，有两条指令链，每条指令通向异或。@Reinstate Monica - ?-- 的答案编译为 4-cycle dep 链（适用于 x86）。5 周期循环吞吐量的瓶颈在于sub关键路径上还包含一个 naive ，并且循环在延迟上确实存在瓶颈。

但是，这对 clang 没用。它甚至没有按照加载的顺序添加和存储，所以它甚至没有做好软件流水线！

# RISC-V clang (trunk) -O3
dec_mem_gnu(unsigned char*):
        lb      a6, 7(a0)
        lb      a7, 6(a0)
        lb      t0, 5(a0)
...
        addi    t1, a5, -1
        addi    t2, a1, -1
        addi    t3, a2, -1
...
        sb      a2, 7(a0)
        sb      a1, 6(a0)
        sb      a5, 5(a0)
...
        ret

Answer 3

我要指出的是，一旦您开始处理多个 uint64_t，您编写的代码实际上会进行矢量化。

https://godbolt.org/z/J9DRzd

Answer 4

您可以确保减法不会溢出，然后修复高位：

uint64_t sub(uint64_t arg) {
    uint64_t x1 = arg | 0x80808080808080;
    uint64_t x2 = ~arg & 0x80808080808080;
    // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction
    return (x1 - 0x101010101010101) ^ x2;
}

Answer 5

不确定这是否是您想要的，但它会并行执行 8 次减法：

#include <cstdint>

constexpr uint64_t mask = 0x0101010101010101;

uint64_t sub(uint64_t arg) {
    uint64_t mask_cp = mask;
    for(auto i = 0; i < 8 && mask_cp; ++i) {
        uint64_t new_mask = (arg & mask_cp) ^ mask_cp;
        arg = arg ^ mask_cp;
        mask_cp = new_mask << 1;
    }
    return arg;
}

说明：位掩码在每个 8 位数字中以 1 开头。我们用我们的论点对它进行异或。如果我们在这个地方有一个 1，我们就减去 1 并且必须停止。这是通过将 new_mask 中的相应位设置为 0 来完成的。如果我们有一个 0，我们将它设置为 1 并且必须进行进位，因此该位保持为 1，我们将掩码向左移动。你最好自己检查一下新面具的生成是否按预期工作，我认为是这样，但第二个意见也不错。

PS：我实际上不确定mask_cp循环中对非空的检查是否会减慢程序的速度。没有它，代码仍然是正确的（因为 0 掩码什么也不做），编译器进行循环展开会容易得多。