c - 有效地获取C中整数 vector 的绝对值

Question

任务是将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;
  }
}

（这会向量化吗？）

就我所知。可以做更多的事情来优化此功能吗？

Answer 1

我个人比较喜欢这个问题。像这样的问题使您想知道是否有办法使自己的代码更好。

您的最终优化不正确，因为它会初始化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;
}

检测结果

这是我的结果（时间以秒为单位）。这些测试是在3.33GHz的Intel®Xeon®CPU W3580上运行的。 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实现的结果。该代码非常快，并且证明您拥有的指令越少，执行时间就越快。 Rotem做得好！

更新2

我今天进行了一些广泛的测试，发现当打开诸如 gcc -O3之类的编译器优化时，诸如更改for循环计数方式之类的微优化绝对无效。编译器最终生成程序集，该程序集对数组指针进行指针比较以测试我们是否到达末尾。

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

最终更新

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

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

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

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

令人惊讶的是，只需使用 abs()，就可以通过调用C库函数的简单性实现几乎与SIMD相同的速度。不使用 abs()的 -march=native循环仅延长4条指令，而不使用 PABSD，而是使用 PSRAD， PXOR和 PSUBD指令。

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

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

这是 abs()：

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

这是XOR：

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;

这是XOR：

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

区别在于，在原始XOR实现中我们还有一个额外的按位AND运算。

定论

使用 abs()！ ：D