c++ - 优化位集操作

我正在寻找优化这段代码。 BitSetPattern的大小为512，而BitSetOut的长度为2048位。

基本上，这段代码是做什么的，它需要4个BitSetPatterns并通过隐式创建它们来创建BitSetOut。一点点复制会花费太多时间。

我认为OR或SHIFT可以解决这种情况，但运算符仅采用相同长度的位集。也没有办法用较小的位初始化位集并用零填充其余位。

unsigned outputIter = 0;
BitSetPattern output(0);

for (int i = 3; i >= 0; i--)
{
    BitSetOut currentInput = this->input[ i ]->getOutput();
    for (unsigned j = 0; j < currentInput.size(); j++)
    {
        output[ outputIter ] = currentInput[ j ];
        outputIter++;
    }
}
return output;

我已经剖析了代码，这是花费太多时间的方法。

最佳答案

这是一个非常不安全的解决方案，您应该而不是使用:

assert (sizeof(output) == output.size() / 8);
assert ((output.size() / 8) == 0);

int offset = 0;
for (int i = 3; i >= 0; --i)
{
    auto const sz = input[i].size();

    assert ((sz % 8) == 0);
    assert (offset + (sz / 8) <= output.size());

    memcpy (((char*)&(output)) + offset, (char*)&(input[i]), sz / 8);
    offset += sz / 8;
}

基本上，这是为了安全起见，并确保除了位(没有填充，对齐，大小甚至压缩位)之外，位集中没有其他内容，然后将它们整体复制。

在标准(AFAIK)中，没有任何东西可以保证它能正常工作。它甚至可能不适用于现有的实现，但是我相信它对于简单的std::bitset实现“应该”起作用。

可能可以进一步提高复制速度。由于您知道数据的大小并且非常小，因此您可以直接编写SSE甚至是AVX内部函数，这些内部函数会将源地址的512位复制到目标地址。

您可以尝试以下三件事:

如果您完全确定大小保持不变(例如2048和512位)，请使用常数值并删除算术和断言。这可能会有所帮助，具体取决于您的编译器对待memcpy的方式(某些编译器在某些情况下会对其进行优化，例如，如果大小恒定且是字长的倍数等)

确保将位缓冲区分配给高速缓存行大小的倍数(例如64字节)。这是为了确保不会碰到过多的高速缓存行。)

您可以通过在每次迭代中触摸下一个输入缓冲区来尝试帮助内存“prefetcher”。例如:

char * output_ptr = (char *)&output;
char * input_ptrs [4] = {(char*)&(input[0]), (char*)&(input[1]), ...};
volatile char dummy = 0;

dummy += input_ptrs[2][0];                    // prefetch the next one
memcpy (output_ptr +   0, input_ptrs[3], 64); // copy

dummy += input_ptrs[1][0];                    // prefetch the next one
memcpy (output_ptr +  64, input_ptrs[2], 64); // copy

dummy += input_ptrs[0][0];                    // prefetch the next one
memcpy (output_ptr + 128, input_ptrs[1], 64); // copy

memcpy (output_ptr + 192, input_ptrs[0], 64); // copy

关于c++ - 优化位集操作，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23459424/