79

如果我有一个 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++ 解决方案,或者只是它背后的理论,以便我可以实现自己的解决方案。

4

8 回答 8

77

如果您的 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 的答案 or memcpy)。

否则,您可以在需要单个字节时 分配/声明您的数据uint64_t并访问它。允许为任何东西起别名,以便回避 8 位元素的特定情况的问题。(如果确实存在,假设它是一个 . 可能是安全的。)uint8_t*unsigned char*uint8_tunsigned char


请注意,这是对先前错误算法的更改(请参阅修订历史记录)。

1这在不循环任意减法的情况下是可能的,并且对于每个字节中的已知常量更有效。 主要技巧是通过设置高位来防止每个字节的进位,然后纠正减法结果。

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

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

H定义为(0x8080808080808080U即每个压缩整数的 MSB)。对于减量,y0x0101010101010101U

我们知道它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 程序集。为了获得更好的性能,应该内联希望常量可以尽可能长时间地存在于寄存器中。在常量位于寄存器中的紧密循环中,实际递减需要五个指令:优化后的 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 上,您只需movqpaddb.

于 2020-01-08T00:40:02.210 回答
17

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

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

本机向量语法的一个优点是,当针对具有硬件 SIMD 的机器时,它将使用它而不是自动向量化您的 bithack 或类似的东西。

它使编写vector -= scalar操作变得容易;语法 Just Works,隐式广播,也就是为你喷出标量。


另请注意,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/clang 在memcpy无法证明指针对齐时不会内联和优化,这将对性能造成灾难性影响。

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但不能floatuint8_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。(使用由 生成的全为向量pcmpeqd same,same)。由于-march=skylake我们仍然得到两个单独的 XMM 操作而不是一个 YMM,所以不幸的是,当前的编译器也没有将向量操作“自动向量化”为更广泛的向量:/

对于 AArch64,使用vector_size(8)Godbolt)还不错;ARM/AArch64 可以在 8 或 16 字节块中使用dq寄存器本机工作。

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

vector_size(8)更容易查看 asm(只有一个寄存器的数据):Godbolt compiler explorer

# 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 周期 dep 链(对于 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
于 2020-01-08T21:42:35.617 回答
13

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

https://godbolt.org/z/J9DRzd

于 2020-01-08T00:19:56.243 回答
11

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

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;
}
于 2020-01-08T16:49:57.983 回答
7

不确定这是否是您想要的,但它会并行执行 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;
}

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

PS:我实际上不确定mask_cp循环中不为空的检查是否会减慢程序的速度。没有它,代码仍然是正确的(因为 0 掩码什么都不做)并且编译器会更容易进行循环展开。

于 2020-01-08T00:26:52.690 回答
4
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++

于 2020-01-08T00:14:29.033 回答
2

不会尝试提出代码,但要减少 1,您可以减少 8 个 1 的组,然后检查以确保结果的 LSB 已“翻转”。任何未切换的 LSB 都表示相邻 8 位发生了进位。应该可以计算出一系列 AND/OR/XOR 来处理这个问题,而无需任何分支。

于 2020-01-09T22:44:49.943 回答
0

完全单独专注于每个字节,然后将其放回原处。

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;
   }
于 2020-01-08T03:12:30.953 回答