10

我有一个巨大的vector<vector<int>>（18M x 128）。我经常想取 2 行这个向量并通过这个函数比较它们：

    int getDiff(int indx1, int indx2) {
    int result = 0;
    int pplus, pminus, tmp;

    for (int k = 0; k < 128; k += 2) {
        pplus = nodeL[indx2][k] - nodeL[indx1][k];
        pminus = nodeL[indx1][k + 1] - nodeL[indx2][k + 1];

        tmp = max(pplus, pminus);
        if (tmp > result) {
            result = tmp;
        }
    }
    return result;
}

如您所见，函数循环通过两个行向量进行一些减法，最后返回最大值。这个函数将被使用一百万次，所以我想知道它是否可以通过 SSE 指令加速。我使用 Ubuntu 12.04 和 gcc。

当然这是微优化，但如果你能提供一些帮助会很有帮助，因为我对 SSE 一无所知。提前致谢

基准：

    int nofTestCases = 10000000;

    vector<int> nodeIds(nofTestCases);
    vector<int> goalNodeIds(nofTestCases);
    vector<int> results(nofTestCases);

    for (int l = 0; l < nofTestCases; l++) {
        nodeIds[l] = randomNodeID(18000000);
        goalNodeIds[l] = randomNodeID(18000000);
    }



    double time, result;

    time = timestamp();
    for (int l = 0; l < nofTestCases; l++) {
        results[l] = getDiff2(nodeIds[l], goalNodeIds[l]);
    }
    result = timestamp() - time;
    cout << result / nofTestCases << "s" << endl;

    time = timestamp();
    for (int l = 0; l < nofTestCases; l++) {
        results[l] = getDiff(nodeIds[l], goalNodeIds[l]);
    }
    result = timestamp() - time;
    cout << result / nofTestCases << "s" << endl;

在哪里

int randomNodeID(int n) {
    return (int) (rand() / (double) (RAND_MAX + 1.0) * n);
}

/** Returns a timestamp ('now') in seconds (incl. a fractional part). */
inline double timestamp() {
    struct timeval tp;
    gettimeofday(&tp, NULL);
    return double(tp.tv_sec) + tp.tv_usec / 1000000.;
}
4

4 回答 4

7

FWIW 我整理了一个纯 SSE 版本（SSE4.1），它的运行速度似乎比 Core i7 上的原始标量代码快 20% 左右：

#include <smmintrin.h>

int getDiff_SSE(int indx1, int indx2)
{
    int result[4] __attribute__ ((aligned(16))) = { 0 };

    const int * const p1 = &nodeL[indx1][0];
    const int * const p2 = &nodeL[indx2][0];

    const __m128i vke = _mm_set_epi32(0, -1, 0, -1);
    const __m128i vko = _mm_set_epi32(-1, 0, -1, 0);

    __m128i vresult = _mm_set1_epi32(0);

    for (int k = 0; k < 128; k += 4)
    {
        __m128i v1, v2, vmax;

        v1 = _mm_loadu_si128((__m128i *)&p1[k]);
        v2 = _mm_loadu_si128((__m128i *)&p2[k]);
        v1 = _mm_xor_si128(v1, vke);
        v2 = _mm_xor_si128(v2, vko);
        v1 = _mm_sub_epi32(v1, vke);
        v2 = _mm_sub_epi32(v2, vko);
        vmax = _mm_add_epi32(v1, v2);
        vresult = _mm_max_epi32(vresult, vmax);
    }
    _mm_store_si128((__m128i *)result, vresult);
    return max(max(max(result[0], result[1]), result[2]), result[3]);
}
于 2013-07-23T07:14:58.990 回答
3

您可能可以让编译器为此使用 SSE。它会使代码更快吗？可能不是。原因是与计算相比，内存访问量很大。CPU 比内存快得多，上面的简单实现已经让 CPU 在等待数据通过系统总线到达时停止。使 CPU 更快只会增加它的等待时间。

nodeL 的声明会对性能产生影响，因此为您的数据选择一个高效的容器很重要。

优化确实有一个阈值，那就是当您在内存读取之间进行更多计算时 - 即内存读取之间的时间要长得多。发生这种情况在很大程度上取决于您的硬件。

但是，如果您有可以并行运行的非内存受限任务，那么优化代码会很有帮助，以便 CPU 在等待数据时保持忙碌。

于 2013-07-22T16:00:14.960 回答
3

这会更快。向量的向量的双重取消引用是昂贵的。缓存其中一个取消引用会有所帮助。我知道它没有回答发布的问题，但我认为这将是一个更有帮助的答案。

int getDiff(int indx1, int indx2) {
    int result = 0;
    int pplus, pminus, tmp;

    const vector<int>& nodetemp1 = nodeL[indx1];
    const vector<int>& nodetemp2 = nodeL[indx2];

    for (int k = 0; k < 128; k += 2) {
        pplus = nodetemp2[k] - nodetemp1[k];
        pminus = nodetemp1[k + 1] - nodetemp2[k + 1];

        tmp = max(pplus, pminus);
        if (tmp > result) {
            result = tmp;
        }
    }
    return result;
}
于 2013-07-22T16:11:17.503 回答
3

有几件事要看。一是您传递的数据量。这将导致比微不足道的计算更大的问题。

我尝试使用 SSE 指令（AVX）在此处使用库对其进行重写

我系统上的原始代码在 11.5 秒内运行，经过 Neil Kirk 的优化，它降到了 10.5 秒

编辑：用调试器而不是在我的脑海中测试代码！

int getDiff(std::vector<std::vector<int>>& nodeL,int row1, int row2) {
    Vec4i result(0);
    const std::vector<int>& nodetemp1 = nodeL[row1];
const std::vector<int>& nodetemp2 = nodeL[row2];

Vec8i mask(-1,0,-1,0,-1,0,-1,0);
for (int k = 0; k < 128; k += 8) {
    Vec8i nodeA(nodetemp1[k],nodetemp1[k+1],nodetemp1[k+2],nodetemp1[k+3],nodetemp1[k+4],nodetemp1[k+5],nodetemp1[k+6],nodetemp1[k+7]);
    Vec8i nodeB(nodetemp2[k],nodetemp2[k+1],nodetemp2[k+2],nodetemp2[k+3],nodetemp2[k+4],nodetemp2[k+5],nodetemp2[k+6],nodetemp2[k+7]);
    Vec8i tmp = select(mask,nodeB-nodeA,nodeA-nodeB);
    Vec4i tmp_a(tmp[0],tmp[2],tmp[4],tmp[6]);
    Vec4i tmp_b(tmp[1],tmp[3],tmp[5],tmp[7]);
    Vec4i max_tmp = max(tmp_a,tmp_b);
    result = select(max_tmp > result,max_tmp,result);
}
return horizontal_add(result);

}

缺少分支将其加速到 9.5 秒，但数据仍然是最大的影响。

如果您想加快速度，请尝试将数据结构更改为单个数组/向量而不是 2D （ala std::vector），因为这将减少缓存压力。

编辑 我想到了一些东西——你可以添加一个自定义分配器来确保你在一个连续的内存块中分配 2*18M 向量，这样你就可以保持数据结构并仍然快速完成它。但是您需要对其进行分析以确保

编辑 2：使用调试器而不是在我的脑海中测试代码！ 对不起亚历克斯，这应该更好。不确定它会比编译器可以做的更快。我仍然认为这是内存访问的问题，所以我仍然会尝试单数组方法。试一试。

于 2013-07-22T19:26:22.347 回答