c++ - 我应该如何提高此 C++ 代码的性能？

Question

以下代码对两个 std::vectors v1 和 v2 进行操作，每个都包含多个 128 元素 vector 。通过外部 vector 的循环(使用 i1 和 i2)包含一个内部循环，旨在限制 i1 和 i2< 的组合 对其执行进一步的复杂处理。过滤掉大约 99.9% 的组合。

不幸的是，过滤循环是我程序中的一个主要瓶颈 - 分析显示整个运行时间的 26% 花在了行 if(a[k] + b[k] > LIMIT).

const vector<vector<uint16_t>> & v1 = ...
const vector<vector<uint16_t>> & v2 = ...

for(size_t i1 = 0; i1 < v1.size(); ++i1) { //v1.size() and v2.size() about 20000
    for(size_t i2 = 0; i2 < v2.size(); ++i2) {

        const vector<uint16_t> & a = v1[i1];
        const vector<uint16_t> & b = v2[i2];

        bool good = true;
        for(std::size_t k = 0; k < 128; ++k) {
            if(a[k] + b[k] > LIMIT) { //LIMIT is a const uint16_t: approx 16000
                good = false;
                break;
            }
        }
        if(!good) continue;

        // Further processing involving i1 and i2
    }
}

我认为可以通过增加内存局部性以及可能的矢量化来提高此代码的性能。有关如何执行此操作或可以进行其他改进的任何建议？

Answer 1

您可以将 SIMD 应用于内部循环:

    bool good = true;
    for(std::size_t k = 0; k < 128; ++k) {
        if(a[k] + b[k] > LIMIT) { //LIMIT is a const uint16_t: approx 16000
            good = false;
            break;
        }

如下:

#include <emmintrin.h>  // SSE2 intrinsics
#include <limits.h>     // SHRT_MIN

// ...

    // some useful constants - declare these somewhere before the outermost loop

    const __m128i vLIMIT = _mm_set1_epi16(LIMIT + SHRT_MIN); // signed version of LIMIT
    const __m128i vOFFSET = _mm_set1_epi16(SHRT_MIN);        // offset for uint16_t -> int16_t conversion

// ...

    bool good = true;
    for(std::size_t k = 0; k < 128; k += 8) {
        __m128i v, va, vb;              // iterate through a, b, 8 elements at a time
        int mask;
        va = _mm_loadu_si128(&a[k]);    // get 8 elements from a[k], b[k]
        vb = _mm_loadu_si128(&b[k]);
        v = _mm_add_epi16(va, vb);      // add a and b vectors
        v = _mm_add_epi16(v, vOFFSET);  // subtract 32768 to make signed
        v = _mm_cmpgt_epi16(v, vLIMIT); // compare against LIMIT
        mask = _mm_maskmove_epi8(v);    // get comparison results as 16 bit mask
        if (mask != 0) {                // if any value exceeded limit
            good = false;               // clear good flag and exit loop
            break;
        }

警告:未经测试的代码 - 可能需要调试，但一般方法应该是合理的。