提问人:elena 提问时间:2/7/2023 更新时间:2/7/2023 访问量:168
时间关键型 C++ 循环中的浮点数舍入错误,寻找有效的解决方案
Float rounding error in time-critical C++ loop, looking for an efficient solution
问:
作为一个前提,我知道这个问题已经得到解决,但从未在这种特定情况下得到解决,从我能找到的搜索中。
在一段时间关键的代码中,我有一个循环,其中浮点值 x 必须在“z”步长中从 0 线性增长到正好 1。
未优化的解决方案是:
const int z = (some number);
int c;
float x;
for(c=0; c<z; c++)
{
x = (float)c/(float)(z-1);
// do something with x here
}
显然,我可以避免浮点转换并使用两个循环变量和缓存(浮点数)(z-1):
const int z = (some number);
int c;
float xi,x;
const float fzm1 = (float)(z-1);
for(c=0,xi=0.f; c<z; c++, xi+=1.f)
{
x=xi/fzm1;
// do something with x
}
但是,谁会在每次循环传递时重复一个常数的除法呢?显然,任何人都会把它变成乘法:
const int z = (some number);
int c;
float xi,x;
const float invzm1 = 1.f/(float)(z-1);
for(c=0,xi=0.f; c<z; c++, xi+=1.f)
{
x=xi * invzm1;
// do something with x
}
在这里,明显的舍入问题可能会开始显现。 对于 z 的某些整数值,(z-1)*(1.f/(float)(z-1)) 不会给出正好 1,而是给出 0.999999...,因此 x 在最后一个循环周期中假定的值不会正好是 1。
如果改用加法器,即
const int z = (some number);
int c;
float x;
const float x_adder = 1.f/(float)(z-1);
for(c=0,x=0.f; c<z; c++, x+=x_adder)
{
// do something with x
}
情况更糟,因为x_adder中的错误会累积起来。
所以我能看到的唯一解决方案是在某处使用条件,例如:
const int z = (some number);
int c;
float xi,x;
const float invzm1 = 1.f/(float)(z-1);
for(c=0,xi=0.f; c<z; c++, xi+=1.f)
{
x = (c==z-1) ? 1.f : xi * invzm1;
// do something with x
}
但是在时间关键的循环中,如果可能的话,应该避免分支!
哦,我什至不能拆分循环并做
for(c=0,xi=0.f; c<z-1; c++, xi+=1.f) // note: loop runs now up to and including z-2
{
x=xi * invzm1;
// do something with x
}
x=1.f;
// do something with x
因为我必须复制整个代码块“用 x 做一些事情”,这也不简短也不简单,我不能把它变成一个函数调用(效率低下,太多的局部变量要传递),我也不想使用 #defines(会很差、不优雅和不切实际)。
你能想出任何有效或聪明的解决方案来解决这个问题吗?
答:
请考虑使用以下方法:
const int z = (some number > 0);
const int step = 1000000/z;
for(int c=0; c<z-1; ++c)
{
x += step; //just if you really need the conversion, divide it by 1000000 when required
// do something with x
}
x = 1.f;
//do the last step with x
如果您真的不需要它,则没有转换,第一个和最后一个值符合预期,乘法减少为累积。 通过更改 1000000,您可以手动控制精度。
评论
step
x
1000000
我建议你从你展示的最后一个替代方案开始,并使用lambda来避免传递局部变量:
auto do_something_with_x = [&](float x){/*...*/}
for(c=0,xi=0.f; c<z-1; c++, xi+=1.f) // note: loop runs now up to and including z-2
{
x=xi * invzm1;
do_something_with_x(x);
}
do_something_with_x(1.f);
首先,一般考虑:引入一个循环携带的依赖链,其中包含 CPU 浮点加法所需的周期数(可能是 3 或 4 个)。它还会扼杀任何矢量化的尝试,除非您使用 .如果您在现代超标量桌面 CPU 上运行,我建议使用整数计数器并在每次迭代中转换为浮点数。xi += 1.f
-ffast-math
在我看来,避免 int->float 转换是 x87 FPU 时代的过时建议。当然,您必须考虑整个循环才能做出最终判断,但吞吐量通常与浮点加法相当。
对于实际问题,我们可以看看其他人做了什么,例如Eigen在实现他们的LinSpaced
操作时做了什么。在他们的错误跟踪器中也有一个相当广泛的讨论。
他们的最终解决方案非常简单,我认为可以在这里解释它,并根据您的具体情况进行简化:
float step = 1.f / (n - 1);
for(int i = 0; i < n; ++i)
float x = (i + 1 == n) ? 1.f : i * step;
编译器可能会选择剥离最后一次迭代以摆脱分支,但总的来说,无论如何它都不会太糟糕。在标量代码中,分支预测将很好地工作。在矢量化代码中,它是一个打包的比较和一个混合指令。
我们还可以通过适当地重构代码来强制决定剥离最后一次迭代。Lambda 对此非常有帮助,因为它们 a) 使用方便,b) 内联性非常强。
auto loop_body = [&](int i, float x) mutable {
...;
};
for(int i = 0; i < n - 1; ++i)
loop_body(i, i * step);
if(n > 0)
loop_body(n - 1, 1.f);
使用 Godbolt 进行检查(对循环体使用简单的数组初始化),GCC 仅矢量化第二个版本。Clang 对两者都进行了矢量化,但在第二个方面做得更好。
评论
你需要的是Bresenham的线算法。
它将允许您避免乘法和除法,并仅使用加法/子。只需缩放您的范围,使其可以用整数表示,如果在数学上(或“代表性”)上无法精确拆分为部分,则在最后阶段四舍五入。
评论