时间关键型 C++ 循环中的浮点数舍入错误,寻找有效的解决方案

Float rounding error in time-critical C++ loop, looking for an efficient solution

提问人:elena 提问时间:2/7/2023 更新时间:2/7/2023 访问量:168

问:

作为一个前提,我知道这个问题已经得到解决,但从未在这种特定情况下得到解决,从我能找到的搜索中。

在一段时间关键的代码中,我有一个循环,其中浮点值 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(会很差、不优雅和不切实际)。

你能想出任何有效或聪明的解决方案来解决这个问题吗?

C++ 浮点精度 舍入误差

评论

4赞 Scott Hunter 2/7/2023
使用循环获取除最终值之外的所有值(因为您已经知道最终值)。
0赞 B Remmelzwaal 2/7/2023
分子或分母不是必须是浮点数才能除法也产生浮点数吗?这样一来,每次计算至少可以节省一次强制转换。
1赞 Vincent Fourmond 2/7/2023
您是否实际上对所有选项进行了基准测试?我不知何故怀疑分支(最后一个命题)的成本太糟糕了,编译器实际上可能会展开最后一次迭代。
0赞 elena 2/8/2023
@Scott Hunter,如果你仔细阅读了我的问题,我指定我不能这样做,因为这意味着重复必须处理“x”的代码
0赞 elena 2/8/2023
@B Remmelzwaal,显然您没有阅读我的问题,因为我在第二个优化步骤中确实这样做了

答:

0赞 Arkady 2/7/2023 #1

请考虑使用以下方法:

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,您可以手动控制精度。

评论

0赞 Peter 2/7/2023
这样做的问题是,计算中的舍入误差会传播,并且误差会随着迭代次数的增加而增加。stepx
0赞 Arkady 2/7/2023
@Peter 我同意,但合理的精度可以通过增加 来实现,一般来说,精度无论如何都是一个可以接受的问题1000000
0赞 Eugene 2/7/2023 #2

我建议你从你展示的最后一个替代方案开始,并使用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);
4赞 Homer512 2/7/2023 #3

首先,一般考虑:引入一个循环携带的依赖链,其中包含 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 对两者都进行了矢量化,但在第二个方面做得更好。

评论

0赞 elena 2/8/2023
感谢您的有趣阐述。因此,看起来不存在“通用”解决方案......我的软件不是针对一个特定的 CPU,而是主要针对平均最近的 64 位 Intel CPU。可悲的是,我无法对程序的每个功能进行基准测试,因为它太长太复杂了。回复:你不避免 int->float 转换的观点,我总是试图避免类型转换,除非真的不可避免。我一定会深化这个话题,谢谢你指出
0赞 elena 2/8/2023
实际上,通过快速浏览 asm,看起来 GCC 实际上正在剥离最后一次迭代(使用最高的优化设置和 -ffast-math)
0赞 Homer512 2/8/2023
@elena很高兴知道它对你有用。关于CPU:基本上,任何不是真正古老的台式机或智能手机CPU都应该可以正常工作。只有没有 SSE2 的 32 位可能会受到影响。Pentium M 或更高版本都可以。按照 Agner 的指令表
1赞 Damir Tenishev 2/7/2023 #4

你需要的是Bresenham的线算法

它将允许您避免乘法和除法,并仅使用加法/子。只需缩放您的范围,使其可以用整数表示,如果在数学上(或“代表性”)上无法精确拆分为部分,则在最后阶段四舍五入。