c++ - 如何有效地将按位运算应用于(大)压缩位 vector ？

Question

我要实现

void bitwise_and(
    char*       __restrict__  result,
    const char* __restrict__  lhs,
    const char* __restrict__  rhs,
    size_t                    length);

或者可能是 bitwise_or()、bitwise_xor() 或任何其他按位运算。显然，这与算法无关，而与实现细节有关——对齐、从内存中加载最大可能的元素、缓存感知、使用 SIMD 指令等。

我确信这有(不止一个)快速的现有实现，但我猜大多数库实现都需要一些花哨的容器，例如std::bitset 或 boost::dynamic_bit_set - 但我不想花时间构建其中一个。

那么我要...从现有库中复制粘贴吗？找到一个可以用一个漂亮的对象在内存中“包装”原始打包位数组的库？还是滚动我自己的实现？

注意事项:

• 我最感兴趣的是 C++ 代码，但我当然不介意普通的 C 方法。
• 显然，复制输入数组是不可能的——这可能会使执行时间增加近一倍。
• 我有意没有对按位运算符进行模板化，以防对 OR 或 AND 等进行一些特定的优化。
• 同时讨论多个 vector 上的运算可加分，例如V_out = V_1 bitwise-and V_2 bitwise-and V_3 etc.
• 我记下了 this article比较库实现，但它是 5 年前的。我不能问要使用哪个库，因为我猜这会违反 SO 政策...
• 如果对您有任何帮助，假设它是 uint64_t 而不是 char(这并不重要 - 如果 char 数组未对齐，我们可以只处理标题和尾随字符分开)。

Answer 1

这个答案假设您想要最快的方式并且乐于使用平台特定的东西。您优化的编译器可能能够从普通 C 生成与下面类似的代码，但根据我对一些编译器的经验，像这样具体的代码仍然最好手写。

显然，就像所有的优化任务一样，永远不要假设任何事情都变得更好/更坏，并衡量、衡量、衡量。

如果您可以至少使用 SSE3 将您的架构锁定为 x86，您会这样做:

void bitwise_and(
    char*       result,
    const char* lhs,
    const char* rhs,
    size_t      length)
{
    while(length >= 16)
    {
        // Load in 16byte registers
        auto lhsReg = _mm_loadu_si128((__m128i*)lhs);
        auto rhsReg = _mm_loadu_si128((__m128i*)rhs);

        // do the op
        auto res = _mm_and_si128(lhsReg, rhsReg);

        // save off again
        _mm_storeu_si128((__m128i*)result, res);

        // book keeping
        length -= 16;
        result += 16;
        lhs += 16;
        rhs += 16;
    }

    // do the tail end. Assuming that the array is large the
    // most that the following code can be run is 15 times so I'm not
    // bothering to optimise. You could do it in 64 bit then 32 bit
    // then 16 bit then char chunks if you wanted...
    while (length)
    {
        *result = *lhs & *rhs;
        length -= 1;
        result += 1;
        lhs += 1;
        rhs += 1;
    }
}

这编译为每 16 字节约 10 条 asm 指令(+ 改变剩余部分和一点开销)。

像这样(通过手工编写的 asm)执行内部函数的好处在于，编译器仍然可以自由地在您编写的内容之上进行额外的优化(例如循环展开)。它还处理寄存器分配。

如果您可以保证数据对齐，您可以保存一条 asm 指令(改用 _mm_load_si128，编译器将足够聪明地避免第二次加载并将其用作“pand”的直接内存操作数。

如果您可以保证 AVX2+，那么您可以使用 256 位版本并每 32 字节处理 10 条 asm 指令。

在 ARM 上有类似的 NEON 指令。

如果您想执行多个操作，只需在中间添加相关的内在函数，它就会每 16 个字节添加 1 个 asm 指令。

我很确定有了一个像样的处理器，你不需要任何额外的缓存控制。