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

如果您的CPU具有高效的SIMD指令，则SSE/MMX paddb(_mm_add_epi8)也是可行的.还描述了GNUC(GCC/clang)向量语法，以及严格别名UB的安全性.我强烈建议您也回顾一下这个答案.

使用uint64_t自己动手是完全可移植的，但在使用uint64_t*访问uint8_t数组时，仍然需要小心避免对齐问题和严格的别名.你已经从uint64_t中的数据开始了，这一部分就不存在了，但是对于GNU C来说，may_alias typedef解决了这个问题(参见Peter的答案或memcpy).

否则，您可以将数据分配/声明为uint64_t，并在需要单个字节时通过uint8_t*访问它.unsigned char*被允许对任何东西进行别名，以便回避8位元素的特定情况下的问题.(如果uint8_t真的存在的话，那么可以放心地假设它是unsigned char.)

请注意，这是对之前错误算法的更改(请参阅修订历史).

This is possible without looping for arbitrary subtraction, and gets more efficient for a known constant like 100 in each byte.主要技巧是通过设置高位来防止每个字节的执行，然后纠正减法结果.

我们将稍微优化给定here的减法技术.它们定义:

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，这样borrow 就不能通过MSB传播到下一个组件.这就是调整后的输入.
2. 我们从每个分量中减go 1，从修正后的输入中减go 0x01010101010101.由于步骤1，这不会导致组件间borrow .这就是调整后的输出.
3. 我们现在需要更正结果的MSB.我们将调整后的输出与原始输入的反转MSB进行异或，以完成修复结果.

操作可以写成:

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

最好由编译器内联(使用compiler directives强制)，或者将表达式作为另一个函数的一部分内联编写.

测试 case :

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

性能详细信息

这里是用于函数单次调用的x86_64程序集.为了获得更好的性能，应该将其内联，希望这些常量可以在寄存器中尽可能长的存在.在一个紧循环中，常数位于寄存器中，实际减量需要五条指令:或+不+和+加+异或优化后.我看不到比编译器优化更好的替代方案.

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上，您只需将or movq加载到XMM reg for paddb中，因此了解它如何编译类似ISA的RISC-V可能更有趣.)