c - 收集位的最快方法(类似于 std::copy_if)

Question

澄清一下，这就是收集位的意思:(在这个问题的上下文中)

size_t gather_bits(size_t source, size_t mask) {
    size_t result = 0, next_bit_index = 0;
    for (size_t i = 0; i < sizeof(size_t) * 8; i++)
        if ((mask >> i) & 1)
            result |= ((source >> i) & 1) << next_bit_index++;
    return result;
}

对于掩码中的每个第 N 位，结果中的第 N 位从源设置为掩码中第 N 位的索引。 (result[mask_on_bit] = source[mask_bit_index])

我添加的片段是最简单的实现，但不幸的是我发现最快的，我无法提供更好的东西。还有比这更快的吗？考虑到 mask 是完全随机的(因此在掩码中搜索大量 0 应该不会有太大好处)

Answer 1

您可能需要考虑无分支解决方案，它通常可以在某些架构上带来显着的性能优势。像这样:

size_t gather_branchless( size_t source, size_t mask )
{
    size_t result = 0, select = 1;
    source &= mask;
    while( source != 0 )
    {
        int used = (mask & 1);
        result |= (source & select);
        select <<= used;
        source >>= !used;
        mask >>= 1;
    }
    return result;
}

这完全避免了任何分支，除了循环终止测试。我使用数百万个随机生成的值来运行此方法的基准测试来比较时间。在使用 Clang 和全面优化编译的 Intel Core i7 2.9GHz 上运行:

+--------------+-------------+
| solution     | approx time |
+--------------+-------------+
| txtechhelp   | 1500 ms     |
| yours        | 1400 ms     |
| SGeorgiades  | 1300 ms     |
| branchless   | 600 ms      |
+--------------+-------------+

精明的人可能会注意到我的无分支版本会在没有剩余的位可以组合时提前终止。为了公平起见，我运行测试时始终为值和掩码设置最高位。这样做会在结果上再增加 50 毫秒。

就是这样。一个无分支解决方案，至少在我测试过的英特尔架构上，它的运行速度是你的两倍多。这样做的另一个好处是，如果您想进一步优化大型数据集上的代码，它可以轻松转换为 SIMD。

您可以 see my benchmark online如果您想尝试其他解决方案。请注意，它是用 C++ 而不是 C 编写的。我的测试使用了 g++ -std=c++11 -O2。这与包含使用 gcc -O2 生成的目标函数的 C 对象文件链接。