2

任务是将 C 整数数组的每个元素设置为其绝对值。我正在尝试尽可能有效地做到这一点。以下是我所做的一系列优化。请告诉我这些是否真的是优化，是否可以做更多！

该函数的第一个参数将是一个整数数组，第二个参数将是该数组的整数大小。

这是标准实现：

void absolute (int array[], int n){
  for(int i = 0; i < n; i++)
    if(array[i] < 0)
      array[i] = - array[i];
}

这足以满足任何介绍性编程课程的教授，但我想多玩一点，也许还能学到一些关于优化的东西。

基于https://stackoverflow.com/a/2074403，无分支绝对值：

void absolute (int array[], int n){
  for(int i = 0; i < n; i++){
    uint32_t temp = array[i] >> 31;     // make a mask of the sign bit
    array[i] ^= temp;                   // toggle the bits if value is negative
    array[i] += temp & 1;               // add one if value was negative
  }
}

基于与零的比较更有效，并且不需要额外的变量：

void absolute (int array[], int n){
  for(n--; n >= 0;){
    uint32_t temp = array[n] >> 31;
    array[n] ^= temp;
    array[n] += temp & 1;
  }
}

（这个矢量化了吗？）

这就是我所得到的。可以做更多的工作来优化这个功能吗？

4

2 回答 2

4

我个人比较喜欢这个问题。正是这些问题让你想知道是否有办法让我自己的代码变得更好。

您的最终优化是不正确的，因为它初始化了 n--，但 n 永远不会再次递减。要纠正这一点，您需要for(n--; n >= 0; n--). 虽然我发现减少或增加 for 循环的结果没有明显的优势。

如果数组的值不是真正随机分布的，我发现if(array[i] < 0)第一个实现中使用的简单实际上要快得多。

这是我用来基准测试的代码：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdint.h>
#ifdef _OPT3
#include <emmintrin.h>
#include <tmmintrin.h>
#endif

int main(int argc, char **argv)
{
        int *array;
        struct timespec tsstart, tsend;
        int ncount = 500000000;
        int i;

        array = malloc(sizeof(int) * ncount);

        for(i = 0; i < ncount; i++)
        {
                array[i] = rand();
#ifdef _DIST
                if(rand() % 100 == 0) // make the values less likely to be negative.
#else
                if(rand() % 2 == 0) // the values are equeally likely to be negaitve as positive.
#endif
                        array[i] = -rand();
        }

        clock_gettime(CLOCK_MONOTONIC, &tsstart);

#ifdef _OPT1
        for(i = 0; i < ncount; i++)
        {
                uint32_t ntemp = array[i] >> 31;
                array[i] ^= ntemp;
                array[i] += ntemp & 1;
        }
#elif _OPT2
        for(ncount--; ncount >= 0; ncount--)
        {
                uint32_t ntemp = array[ncount] >> 31;
                array[ncount] ^= ntemp;
                array[ncount] += ntemp & 1;
        }
#elif _OPT3
        for(i = 0; i < ncount; i+=4)
        {
                __m128i a3_a2_a1_a0 = _mm_loadu_si128((__m128i*)&array[i]);         //Load 4 int32 elements from array.
                a3_a2_a1_a0 = _mm_abs_epi32(a3_a2_a1_a0);                           //Set absolute of 4 int32 elements in single instruction.
                _mm_storeu_si128((__m128i*)(&array[i]), a3_a2_a1_a0);               //Store 4 int32 elements of array.
        }
#elif _OPT4
        for(i = 0; i < ncount; i++)
        {
                array[i] = abs(array[i]); // abs() is actually an intrinsic on gcc and msvc
        }
#else
        for(i = 0; i < ncount; i++)
        {
                if(array[i] < 0)
                {
                        array[i] = -array[i];
                }
        }
#endif

        clock_gettime(CLOCK_MONOTONIC, &tsend);

        printf("start: %ld.%09ld\n", tsstart.tv_sec, tsstart.tv_nsec);
        printf("end: %ld.%09ld\n", tsend.tv_sec, tsend.tv_nsec);

        tsend.tv_sec -= tsstart.tv_sec;
        tsend.tv_nsec -= tsstart.tv_nsec;
        if(tsend.tv_nsec < 0)
        {
                tsend.tv_sec--;
                tsend.tv_nsec = 1000000000 + tsend.tv_nsec;
        }
        printf("diff: %ld.%09ld\n", tsend.tv_sec, tsend.tv_nsec);

        free(array);

        return 0;
}

试验结果

这是我的结果（时间以秒为单位）。这些测试在 Intel(R) Xeon(R) CPU W3580 @ 3.33GHz 上运行。gcc (Debian 4.9.2-10) 4.9.2

// Implimentation One (No Optimizations)
$ gcc -O3 -march=native test.c
$ ./a.out
start: 9221396.418007954
end: 9221398.103490309
diff: 1.685482355

// Implimentation One Non Random Distrubution
$ gcc -D_DIST -O3 -march=native test.c
$ ./a.out
start: 9221515.889463124
end: 9221516.255742919
diff: 0.366279795

// Implementation Two (Branchless)
$ gcc -D_OPT1 -O3 -march=native test.c
$ ./a.out
start: 9221472.539690988
end: 9221472.787347636
diff: 0.247656648

// Implementation Three (Branchless Decrement)
$ gcc -D_OPT2 -O3 -march=native test.c
$ ./a.out
start: 9221930.068693139
end: 9221930.334575475
diff: 0.265882336

// Rotem's Implementation (SIMD)
$ gcc -D_OPT3 -O3 -march=native test.c
$ ./a.out
start: 9222076.001094679
end: 9222076.230432423
diff: 0.229337744

// Inuitive abs() Implementation
$ gcc -D_OPT4 -O3 -march=native test.c
$ ./a.out
start: 9222112.523690484
end: 9222112.754820240
diff: 0.231129756
// Inuitive abs() Implementation Without native
$ gcc -D_OPT4 -O3 test.c
$ ./a.out
start: 9223301.744006196
end: 9223301.974097927
diff: 0.230091731

结论

我从中得出的结论是，处理分支预测的硬件优化可能会显着加快代码执行速度并比任何基于软件的优化更好地提高速度。通过尝试优化分支，您创建了执行相同步骤的代码，无论处理的数据如何。因此，虽然它在恒定时间内执行，但如果数据不是完美的随机分布，您实际上可能会使执行速度变慢。

更新：我在打开编译器优化的情况下做了一些测试，发现不同的结果并不完全支持我之前得出的结论。

根据我的经验，我发现如果你可以简单地编写更少的代码，那通常是最好的优化方式。似乎指令越少，无论硬件功能如何，它执行的速度就越快。

我期待阅读有关此练习的任何评论。

更新

我已经添加了 Rotem 的实施结果。这段代码非常快，证明你拥有的指令越少，执行时间就越快。干得好罗特姆！

更新 2

我今天做了一些广泛的测试，发现像改变 for 循环计数的方式这样的微优化在gcc -O3打开编译器优化时完全没有效果。编译器最终生成了对数组指针进行指针比较的程序集，以测试我们是否已经到达终点。

优化 Rotem 提供的 SSE 代码在运行编译器时也没有什么区别，gcc -O3因为它在 16 字节边界上正确对齐内存，从而消除了_mm_loadu_si128()/的_mm_storeu_si128()必要性。

最终更新

我添加了另一个使用简单直观的abs()功能的实现。事实证明abs()，gcc 和 MSVC 实际上是一个编译器内在函数。gcc -O3我简单地使用优化重做了所有的测试结果。

如您所见，Rotem 的 SIMD 实现和abs()实现是最快的，其次是两个 XOR 实现，最后是分支实现。

在两个 XOR 实现中，递减 for 循环的一个实际上稍微慢一些，因为它的循环包含 14 条指令，而递增循环仅包含 13 条指令。

Rotem 的 SIMD 实现和abs()实现实际上都依赖于PABSD指令，并且都有包含 7 条指令的循环。然而，速度上的微小差异（SIMD 稍快）来自于这样一个事实，即优化的 SIMD 实现假定内存将始终包含 4 个整数的倍数（128 位），而abs()实现需要额外的指令来测试内存不包含的情况4个整数的倍数。

这里令人惊奇的是，通过简单地使用abs()我们可以实现与 SIMD 几乎完全相同的速度，并且调用 C 库函数的简单性。没有 using的abs()循环-march=native只有 4 条指令，而不是using PABSD，它使用PSRAD,PXOR和PSUBD指令。

为什么可移植性abs()比 XOR 实现更快？

事实证明，可移植（或非本地）abs()程序集几乎与 XOR 实现完全相同。

这是abs()：

psrad   $31, %xmm0
pxor    %xmm0, %xmm1
psubd   %xmm0, %xmm1

这是异或：

psrad   $31, %xmm1
movdqa  %xmm1, %xmm2
pxor    %xmm1, %xmm0
pand    %xmm3, %xmm2
paddd   %xmm2, %xmm0

现在让我们将它们转换回 C 代码：

这是abs()：

int ntemp = array[i] >> 31;
array[i] ^= ntemp;
array[i] -= ntemp;

这是异或：

uint32_t ntemp = array[i] >> 31;
array[i] ^= ntemp;
array[i] += ntemp & 1;

不同之处在于我们在原始 XOR 实现中有一个额外的按位与运算。

定论

使用abs()！:D

于 2016-07-15T08:03:48.073 回答
3

为了获得最佳性能，我建议您使用SIMD指令。
不同的处理器支持不同的 SIMD 指令集。

使用手动 SIMD 指令优化的常用方法是使用 C内部函数。

以下示例使用 SSE 内在函数：

#include <intrin.h>

//Limitations:
//1. n must be a multiple of 4.
void absolute(const int array[], int n)
{
    int x;

    //Process 4 elements per iteration.
    for (x = 0; x < n; x += 4)
    {  
        __m128i a3_a2_a1_a0 = _mm_loadu_si128((__m128i*)&array[x]);     //Load 4 int32 elements from array.

        a3_a2_a1_a0 = _mm_abs_epi32(a3_a2_a1_a0);                       //Set absolute of 4 int32 elements in single instruction.

        _mm_storeu_si128((__m128i*)(&array[x]), a3_a2_a1_a0);           //Store 4 int32 elements of array.
    }
}

考虑一下：这只是一个例子（不是最好的性能）。

感谢Brandon测量我的代码示例。

于 2016-07-15T08:43:15.227 回答