为什么 Floor() 这么慢?
-
05-07-2019 - |
题
我最近编写了一些代码(ISO/ANSI C),并对它所实现的糟糕性能感到惊讶。长话短说,原来罪魁祸首是 floor()
功能。它不仅速度慢,而且没有矢量化(使用英特尔编译器,又名 ICL)。
以下是对 2D 矩阵中的所有单元执行取整的一些基准:
VC: 0.10
ICL: 0.20
将其与简单的转换进行比较:
VC: 0.04
ICL: 0.04
怎么能 floor()
比简单的演员转换慢得多吗?!它本质上做同样的事情(除了负数)。第二个问题:有人知道超快的吗 floor()
执行?
附:这是我进行基准测试的循环:
void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned)
{
float *rowA=NULL;
int *intRowA=NULL;
int row, col;
for(row=0 ; row<height ; ++row){
rowA = matA + row*width_aligned;
intRowA = intA + row*width_aligned;
#pragma ivdep
for(col=0 ; col<width; ++col){
/*intRowA[col] = floor(rowA[col]);*/
intRowA[col] = (int)(rowA[col]);
}
}
}
解决方案
有些事情比投射更慢,并阻止矢量化。
最重要的一个:
楼层可以修改全局状态。如果传递的值太大而无法以float格式表示为整数,则 errno 变量将设置为 EDOM 。还完成了对NaN的特殊处理。所有这些行为都适用于想要检测溢出情况并以某种方式处理情况的应用程序(不要问我怎么做)。
检测这些有问题的条件并不简单,占地面执行时间的90%以上。实际的舍入很便宜,可以内联/矢量化。这也是很多代码,所以内联整个函数会使你的程序运行得更慢。
某些编译器具有特殊的编译器标志,允许编译器优化一些很少使用的c标准规则。例如, GCC 可以被告知你根本不对errno感兴趣。为此,请传递 -fno-math-errno 或 -ffast-math 。 ICC和VC可能有类似的编译器标志。
顺便说一句 - 您可以使用简单的演员表来滚动自己的地板功能。你只需要以不同的方式处理消极和积极的情况。如果您不需要特殊处理溢出和NaN,那可能会快得多。
其他提示
如果要将floor()
操作的结果转换为int,并且如果您不担心溢出,则以下代码比(int)floor(x)
快得多:
inline int int_floor(double x)
{
int i = (int)x; /* truncate */
return i - ( i > x ); /* convert trunc to floor */
}
无分支地板和天花板(更好地利用管道)无错误检查
int f(double x)
{
return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor
}
int c(double x)
{
return (int) x + (x > (int) x);
}
或使用楼层
int c(double x)
{
return -(f(-x));
}
实际最快实施 为一个 大的 大批 在现代 x86 CPU 上将是
- 将 MXCSR FP 舍入模式更改为向 -Infinity 舍入(又名
floor
). 。在C中,这应该可以通过fenv
东西,或者_mm_getcsr
/_mm_setcsr
. 循环遍历数组
_mm_cvtps_epi32
在 SIMD 向量上,转换 4float
使用当前舍入模式将 s 转换为 32 位整数。(并将结果向量存储到目的地。)cvtps2dq xmm0, [rdi]
是自 K10 或 Core 2 以来任何 Intel 或 AMD CPU 上的单个微融合 uop。(https://agner.org/optimize/) 与 256 位 AVX 版本相同,带有 YMM 向量。- 使用 MXCSR 的原始值将当前舍入模式恢复为正常的 IEEE 默认模式。(四舍五入,甚至作为抢七)
这允许每个时钟周期加载 + 转换 + 存储 1 个 SIMD 结果向量,与截断一样快. 。(SSE2 有一个特殊的 FP->int 转换指令用于截断,正是因为 C 编译器非常普遍需要它。在 x87 的糟糕日子里,甚至 (int)x
需要将 x87 舍入模式更改为截断然后再更改回来。 cvttps2dq
对于带截断的压缩 float->int (注意额外的 t
在助记符中)。或者对于标量,从 XMM 到整数寄存器, cvttss2si
或者 cvttsd2si
对于标量 double
为标量整数。
通过一些循环展开和/或良好的优化,这应该是可能的,不会在前端出现瓶颈,假设没有缓存未命中瓶颈,每个时钟存储吞吐量仅为 1。(在 Skylake 之前的 Intel 上,也存在每时钟 1 个打包转换吞吐量的瓶颈。)即 每个周期 16、32 或 64 字节,使用 SSE2、AVX 或 AVX512。
在不改变当前舍入模式的情况下,需要SSE4.1 roundps
舍入 a float
到最接近的整数 float
使用您选择的舍入模式。或者,您可以使用其他答案中显示的技巧之一,该技巧适用于具有足够小大小的浮点数以适合有符号的 32 位整数,因为无论如何这都是您的最终目标格式。)
(使用正确的编译器选项,例如 -fno-math-errno
, ,以及右边的 -march
或者 -msse4
选项,编译器可以内联 floor
使用 roundps
, ,或标量和/或双精度等效值,例如 roundsd xmm1, xmm0, 1
, ,但这需要 2 uops,并且在 Haswell 上对于标量或向量具有每 2 个时钟 1 个吞吐量。实际上,gcc8.2会内联 roundsd
为了 floor
即使没有任何快速数学选项, 正如您在 Godbolt 编译器资源管理器中看到的那样. 。但那是与 -march=haswell
. 。遗憾的是,它不是 x86-64 的基准,因此如果您的计算机支持它,您需要启用它。)
是的,floor()
在所有平台上都非常慢,因为它必须实现IEEE fp规范中的许多行为。你不能在内循环中真正使用它。
我有时使用宏来估算floor():
#define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1))
它的行为与floor(-1) == -1
完全不同:例如,PSEUDO_FLOOR(-1) == -2
但是<=>,但它足够接近大多数用途。
实际上无分支版本需要在浮点和整数域之间进行单次转换,这会将值x
转换为所有正或负范围,然后转换/截断并将其移回。
long fast_floor(double x)
{
const unsigned long offset = ~(ULONG_MAX >> 1);
return (long)((unsigned long)(x + offset) - offset);
}
long fast_ceil(double x) {
const unsigned long offset = ~(ULONG_MAX >> 1);
return (long)((unsigned long)(x - offset) + offset );
}
正如评论中所指出的,这种实现依赖于临时值x +- offset
而不是溢出。
在64位平台上,使用int64_t中间值的原始代码将产生三个指令内核,同样可用于int32_t缩小范围floor / ceil,其中|x| < 0x40000000
-
inline int floor_x64(double x) {
return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL);
}
inline int floor_x86_reduced_range(double x) {
return (int)(x + 0x40000000) - 0x40000000;
}
- 他们不做同样的事情。 floor()是一个函数。因此,使用它会产生函数调用,分配堆栈帧,复制参数和检索结果。 转换不是函数调用,因此它使用更快的机制(我相信它可能使用寄存器来处理值)。
- 可能floor()已经过优化。
- 您可以从算法中获得更多性能吗?也许切换行和列可能会有所帮助?你可以缓存常见值吗?您的所有编译器都进行了优化吗?你可以切换操作系统吗?编译器? Jon Bentley的编程珍珠对可能的优化进行了很好的评估。 醇>
快速双轮
double round(double x)
{
return double((x>=0.5)?(int(x)+1):int(x));
}
终端日志
测试custom_1 8.3837
测试native_1 18.4989
测试custom_2 8.36333
测试native_2 18.5001
测试custom_3 8.37316
测试native_3 18.5012
<强>测试强>
void test(char* name, double (*f)(double))
{
int it = std::numeric_limits<int>::max();
clock_t begin = clock();
for(int i=0; i<it; i++)
{
f(double(i)/1000.0);
}
clock_t end = clock();
cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;
}
int main(int argc, char **argv)
{
test("custom_1",round);
test("native_1",std::round);
test("custom_2",round);
test("native_2",std::round);
test("custom_3",round);
test("native_3",std::round);
return 0;
}
<强>结果强>
类型转换和使用你的大脑比使用本机功能快3倍。