使用 Intel Intrinsics 快速找到整数数组的总和

Question

我一直在在线判断上做一个任务：实现int sum(const int* array, unsigned int len) 以便它returns 和的数组。 len可以是20万次，这个函数可以调用20万次；我的程序必须在 0.9 秒内执行。

目前，我的代码如下所示：

#include <immintrin.h>
#include <stdio.h>

int sum(const int* array, unsigned int len) {
    register int i = 8, s = 0;
    __m256i sm = _mm256_loadu_si256((void *)(array));
    for (; i+8 < len; i += 8) {
        const __m256i x = _mm256_loadu_si256((void *)(array+i));
        sm = _mm256_add_epi32(sm, x);
    }
    sm = _mm256_hadd_epi32(sm, sm);
    sm = _mm256_hadd_epi32(sm, sm);
    s = _mm256_extract_epi32(sm, 0);
    s += _mm256_extract_epi32(sm, 4);
    for(; i < len; ++i) s += array[i];
    return s;
}

但是，根据法官的报告，此代码未通过 Time limit exceeded。

谁能指出哪些指令在时间上是昂贵的，以及如何加速我的代码？

Answer 1

快速检查一下，看起来最合理的最新处理器提供了两个加载端口和两个用于添加的端口，因此至少从理论上讲，您应该通过展开循环的两次迭代来获得不错的收益（尽管如果数据非常大，它可能会很快下降到主内存的带宽）。

与任何 AVX 操作一样，您希望确保所处理的数据正确对齐。如果数据未对齐，较旧的处理器将出错。较新的可以工作，但你会得到相当严重的速度损失。

Answer 2

执行@JerryCoffin 的建议：


#include <immintrin.h>
#include <stdio.h>

int sum(const int* array, unsigned int len) {
    if(len < 60) {
        int s = 0;
        for(int i = 0; i < len; ++i) s += array[i];
        return s;
    }
    register int i = 0, s = 0;
    __m256i sm = _mm256_loadu_si256((void *)(array+i));
    __m256i sm2 = _mm256_loadu_si256((void *)(array+i+8));
    i += 16;
    for (; i+16 < len; i += 16) {
        const __m256i x = _mm256_loadu_si256((void *)(array+i));
        sm = _mm256_add_epi32(sm, x);
        const __m256i y = _mm256_loadu_si256((void *)(array+i+8));
        sm2 = _mm256_add_epi32(sm2, y);
    }
    sm = _mm256_add_epi32(sm, sm2);
    sm = _mm256_hadd_epi32(sm, sm);
    sm = _mm256_hadd_epi32(sm, sm);
    s += _mm256_extract_epi32(sm, 0);
    s += _mm256_extract_epi32(sm, 4);
    for(; i < len; ++i) s += array[i];
    return s;
}

有趣的是，因为这个函数被调用了很多次，消耗整数直到数组对齐实际上比使用 loadu.

花费更多的时间

使用 Intel Intrinsics 快速找到整数数组的总和

Using Intel Intrinsics to quickly find sum of array of integers

c++

intrinsics

avx

avx2