找到一种有效的方法来在2个巨大的缓冲区上执行MAX，每个字节一个字节

Question

为了保持每个字节的最大值，我需要非常快速地比较900万个字节。这是我的工作：

int bufSize = 9000000;
byte_t *buf = /* ... */;
byte_t *maxBuf = /* ... */;

for (int i = 0; i < bufSize; ++i) {
  if (buf[i] > maxBuf[i]) {
    maxBuf[i] = buf[i];
  }
}

它可以，但是我需要将处理时间减少3。

特别是，有没有一种方法可以使用CPU的64位？

您知道numpy数组是否可以提供帮助？

Answer 1

就您所拥有的而言，没有更快的方法。使用python的numpy实际上只能改善python的类C行为。

我认为您最好的选择是使用OpenMP。 Here是一个简单的教程。由于每个迭代彼此独立，因此我认为您的代码应如下所示：

#pragma omp parallel for
for (int i = 0; i < bufSize; ++i) {
    #pragma omp simd
    if (buf[i] > maxBuf[i]) {
        maxBuf[i] = buf[i];
    }
}

然后您使用-fopenmp进行编译。我不确定#pragma omp simd行是否会有所帮助。

您还可以添加编译器优化。 Here是一个列表。另请参阅man page。但是，这些方法并不总是会提高速度，这取决于许多因素。只需尝试一下，它就会严重优化您的代码。

例如，我的算法花了几个小时。在完成编译器优化和OpenMP之后，我可以将其降低到大约30秒。但是，这方面的编程会变得非常困难，要考虑的因素太多。

Answer 2

[如果您具有支持AVX2的CPU并使用Intels SIMD内部函数（Intel Intrinsics Guide - max）一次处理32字节，则可以获得高效的解决方案（在我的系统[Intel i5-8250U]上为〜45ms与〜1ms）] >

因为9000000可被32整除，所以您甚至不需要额外的循环即可完成。

// #include <immintrin.h>, also for g++ add `-mavx2`-flag

int bufSize = 9000000;
byte *buf = static_cast<byte *>(_mm_malloc(sizeof(*buf) * bufSize, 32));
byte *maxBuf = static_cast<byte *>(_mm_malloc(sizeof(*maxBuf) * bufSize, 32));

for (int i = 0; i < bufSize; ++i) 
{
    buf[i] = (byte) rand();
    maxBuf[i] = (byte) rand();
}

for (int i = 0; i < bufSize; i += 32) 
{
    __m256i *buf_simd = (__m256i *) &buf[i];
    __m256i *maxBuf_simd = (__m256i *) &maxBuf[i];

    *maxBuf_simd = _mm256_max_epu8(*maxBuf_simd, *buf_simd);
}

_mm_free(buf);
_mm_free(maxBuf);
因为我没有您的数据，所以我创建了两个包含随机数据的数组。在这里，它们必须是32Byte对齐的，这一点非常重要。

[此后，在for循环的每次迭代中，我将32Byte加载到向量寄存器中并执行_mm256_max_epu8，该操作基本上将256位划分为32字节的“数据包”（所谓的打包向量），并选择每个字节的最大值（可以在上面的链接中找到更详细的说明）。

[如果仅具有支持SSE2的CPU，则可以将_mm_max_epu8与128位向量一起使用。