在 C 中有效地取整数向量的绝对值
Efficiently taking the absolute value of an integer vector in C
任务是将 C 整数数组的每个元素设置为其绝对值。我正在尝试尽可能高效地做到这一点。以下是我所做的一系列优化。请告诉我这些是否真的是优化，以及是否可以进行更多优化！
函数的第一个参数将是一个整数数组，第二个参数将是该数组的整数大小。
这是标准实现：
void absolute (int array[], int n){
for(int i = 0; i < n; i++)
if(array[i] < 0)
array[i] = - array[i];
}
这足以满足任何介绍性编程课程教授的需求，但我想多尝试一下，并可能在此过程中学习一些有关优化的知识。
基于，一个无分支的绝对值：
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;
}
}
（不过这个向量化了吗？）
就我所知。可以做更多的工作来优化这个功能吗？
我个人比较喜欢这个问题。正是这些问题让您想知道是否有办法让我自己的代码变得更好。
你最后的优化是不正确的，因为它初始化了 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 的实施结果。这段代码非常快，并证明您拥有的指令越少，执行时间就越快。干得好 Rotem！
更新 2
我今天进行了一些广泛的测试，发现当 gcc -O3 等编译器优化打开时，微优化（如更改 for 循环计数的方式）完全没有效果。编译器最终生成程序集，该程序集对数组指针进行指针比较以测试我们是否已到达终点。
当编译器是 运行 和 gcc -O3 时，优化 Rotem 提供的 SSE 代码也没有任何区别，因为它正确地将内存对齐到 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() 我们可以通过调用 C 库函数的简单性实现与 SIMD 几乎完全相同的速度。不使用 -march=native 的 abs() 循环只增加了 4 条指令，它没有使用 PABSD，而是使用 PSRAD、PXOR 和 PSUBD说明。
为什么可移植 abs() 比 XOR 实施更快？
事实证明，可移植（或非本地）abs() 程序集几乎与 XOR 实现完全相同。
这是 abs():
psrad , %xmm0
pxor %xmm0, %xmm1
psubd %xmm0, %xmm1
这是异或运算：
psrad , %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 实现中有一个额外的按位 AND 运算。
最终结论
使用abs()！ :D
为了获得最佳性能，我建议您使用 SIMD 说明。
不同的处理器支持不同的 SIMD 指令集。
使用手动 SIMD 指令优化的常用方法是通过 C intrinsic 函数。
以下示例使用 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 测量我的代码示例。
任务是将 C 整数数组的每个元素设置为其绝对值。我正在尝试尽可能高效地做到这一点。以下是我所做的一系列优化。请告诉我这些是否真的是优化，以及是否可以进行更多优化！
函数的第一个参数将是一个整数数组，第二个参数将是该数组的整数大小。
这是标准实现：
void absolute (int array[], int n){
for(int i = 0; i < n; i++)
if(array[i] < 0)
array[i] = - array[i];
}
这足以满足任何介绍性编程课程教授的需求，但我想多尝试一下，并可能在此过程中学习一些有关优化的知识。
基于，一个无分支的绝对值：
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;
}
}
（不过这个向量化了吗？）
就我所知。可以做更多的工作来优化这个功能吗？
我个人比较喜欢这个问题。正是这些问题让您想知道是否有办法让我自己的代码变得更好。
你最后的优化是不正确的，因为它初始化了 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 的实施结果。这段代码非常快，并证明您拥有的指令越少，执行时间就越快。干得好 Rotem！
更新 2
我今天进行了一些广泛的测试，发现当 gcc -O3 等编译器优化打开时，微优化（如更改 for 循环计数的方式）完全没有效果。编译器最终生成程序集，该程序集对数组指针进行指针比较以测试我们是否已到达终点。
当编译器是 运行 和 gcc -O3 时，优化 Rotem 提供的 SSE 代码也没有任何区别，因为它正确地将内存对齐到 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() 我们可以通过调用 C 库函数的简单性实现与 SIMD 几乎完全相同的速度。不使用 -march=native 的 abs() 循环只增加了 4 条指令，它没有使用 PABSD，而是使用 PSRAD、PXOR 和 PSUBD说明。
为什么可移植 abs() 比 XOR 实施更快？
事实证明，可移植（或非本地）abs() 程序集几乎与 XOR 实现完全相同。
这是 abs():
psrad , %xmm0
pxor %xmm0, %xmm1
psubd %xmm0, %xmm1
这是异或运算：
psrad , %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 实现中有一个额外的按位 AND 运算。
最终结论
使用abs()！ :D
为了获得最佳性能，我建议您使用 SIMD 说明。
不同的处理器支持不同的 SIMD 指令集。
使用手动 SIMD 指令优化的常用方法是通过 C intrinsic 函数。
以下示例使用 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 测量我的代码示例。