在一个64位整数中减去1个并行的8位整数，没有硬件 SIMD 的 SWAR

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

我目前有这个代码，它工作，但我需要一个解决方案，做每个打包8位整数并行减法，并没有内存访问。在 x86上，我可以使用像 psubb这样的 SIMD 指令，它可以并行地减去包装好的8位整数，但是我正在编写代码的平台不支持 SIMD 指令。(本例中为 RISC-V)。

因此，我尝试用 SWAR (寄存器内的 SIMD)手动取消 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 + + 的解决方案，这是相当可移植的，或只是它背后的理论，这样我就可以实现我自己的解决方案。

5528 次浏览
小开 
int subtractone(int x)
{
int f = 1;


// Flip all the set bits until we find a 1 at position y
while (!(x & f)) {
x = x^f;
f <<= 1;
}


return x^f; // return answer but remember to flip the 1 at y
}

您可以使用上面的按位操作来完成，只需要将整数分成8个位块，就可以向这个函数发送8次。下面的部分是从 如何将一个64位数字分割成8个8位值？中选取的，我添加了上面的函数

uint64_t v= _64bitVariable;
uint8_t i=0,parts[8]={0};
do parts[i++] = subtractone(v&0xFF); while (v>>=8);

它是有效的 C 或 C + + ，不管人们如何看待它

小开

我要指出的是，一旦您开始处理多个 uint64 _ t，您编写的代码实际上是向量化的。

Https://godbolt.org/z/j9drzd

小开

不知道这是不是你想要的，但它可以做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 _ cover 中将相应的位设置为0来完成的。如果我们有一个0，我们将它设置为1，并且必须进位，所以位保持1，我们将掩码向左移动。你最好自己检查一下新一代的面具是否按照预期的工作，我认为是这样的，但是第二个意见也不错。

PS: 我实际上不确定在循环中检查 mask_cp是否不为空可能会减慢程序的运行速度。如果没有它，代码仍然是正确的(因为0掩码什么也不做) ，编译器将更容易执行循环展开。

小开
最佳答案

如果您有一个具有有效 SIMD 指令的 CPU，SSE/MMX paddb(_mm_add_epi8)也是可行的。Peter Cordes 的回答还描述了 GNU C (gcc/clang)向量语法，以及严格混叠 UB 的安全性。我强烈建议你也回顾一下这个答案。

自己使用 uint64_t完全可移植，但是在使用 uint64_t*访问 uint8_t数组时仍然需要注意避免对齐问题和严格混淆 UB。您已经从 uint64_t中的数据开始，但是对于 GNU C 来说，may_alias typedef 解决了这个问题(请参阅 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的所有 MSB 都是干净的，所以我们可以跳过其中一个掩码步骤(例如，在我们的例子中，y & ~H与 y相同)。计算结果如下:

  1. 我们将 x的每个组件的 MSB 设置为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程序集。为了获得更好的性能，应该将希望寄存器中的常量尽可能长地保存在内联中。在一个紧凑的循环中，常量驻留在一个寄存器中，实际的递减需要五个指令: 或 + not + 和 + 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 机器上，执行递减、 xor 和比较 + 跳转可以在每次迭代的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或者 movq加载到 paddb的 XMM reg 中，因此了解它如何为像 RISC-V 这样的 ISA 编译可能会更有趣。)

小开

把注意力完全集中在每个字节上，然后把它放回原处。

uint64_t sub(uint64_t arg) {
uint64_t res = 0;


for (int i = 0; i < 64; i+=8)
res += ((arg >> i) - 1 & 0xFFU) << i;


return res;
}
小开

你可以确保减法不会溢出，然后修正高位:

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;
}
小开

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

有趣的事实: GCC 知道一些 SWAR 双向技巧(在其他答案中显示) ，并且可以在编译目标代码时使用它们，而不需要硬件 SIMD 指令。(但是对于 RISC-V，clang 只会天真地将其展开为标量操作，所以如果您想要在编译器之间获得良好的性能，就必须自己做这件事)。

本地向量语法的一个优点是，当针对机器 和硬件 SIMD 时，它将使用它来代替自动向量化您的后背或类似的东西。

它使得编写 vector -= scalar操作变得非常容易; 语法 Just Works 为您隐式地广播了标量。

还要注意，来自 uint8_t array[]的 uint64_t*加载是严格混淆的 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)));

另一种做别名安全加载的方法是将 memcpy加载到 uint64_t中，这也消除了 alignof(uint64_t)对齐要求。但是在没有有效未对齐负载的 ISA 上，gcc/clang 不会内联，当它们不能证明指针是对齐的时候，它们会优化掉 memcpy，这将对性能造成灾难性的影响。

DR: 您最好的选择是将数据声明为 uint64_t array[...] ，或者将其动态分配为 uint64_t、 最好是 alignas(16) uint64_t array[];，这样可以确保对齐至少为8字节，如果指定为 alignas，则为16字节。

因为 uint8_t几乎肯定是 unsigned char*，所以通过 uint8_t*访问 uint64_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.
}

对于没有任何 HW SIMD 的 RISC-V，您可以使用 vector_size(8)来表示您可以有效使用的粒度，并且执行两倍于此的更小的向量。

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

但对于 vector_size (16)(戈德博尔特) ，我们得到了期望的 movdqa/paddb。(使用由 pcmpeqd same,same生成的 all-one 向量)。使用 -march=skylake，我们仍然可以得到两个独立的 XMM 操作，而不是一个 YMM，所以不幸的是，当前的编译器也不能“自动向量化”向量操作到更广泛的向量:/

对于 AArch64来说，使用 vector_size(8)(戈德博尔特)也不错; ARM/AArch64可以与 d或 q寄存器一起在8或16字节的块中工作。

因此，如果希望跨 x86、 RISC-V、 ARM/AArch64和 POWER 实现可移植性能，那么可能需要使用 vector_size(16)进行实际编译。然而，一些其他的 ISA 在64位整数寄存器中执行 SIMD，比如 MIPS MSA。

vector_size(8)使得查看资料更容易(只有一个寄存器值的数据) : 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个周期，有两个2指令链，每个链都指向异或。@ Reinstate Monica-ζ ——的答案汇编成一个4周期的深度链(x86)。5个循环的循环吞吐量也因为在关键路径上包含一个初始的 sub而受到瓶颈，并且循环在延迟方面造成瓶颈。

然而，这对于 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
小开

我们不打算尝试编写代码，但是对于递减1，您可以递减8个1组，然后检查结果的 LSBs 是否“翻转”。任何未切换的 LSB 都表示从相邻的8位进位发生了进位。应该可以编写一个 AND/OR/XOR 序列来处理这个问题，而不需要任何分支。


提交答案