如何使用右移操作符避免除法运算

3

我有一个cpp项目,虽然能运行但性能很差。

int currentPos = getPos();
int length = getLength();
if (1.0 * currentPos / length < 0.5)
{
    // do something
}
else
{
    // do something
}

问题是:1.0 * currentPos / length花费的时间太长了。
谷歌告诉我,除法总是需要很多时间,我们可以借助右移来避免它。
例如,a=a/4可以替换为b=b>>2
我可以理解这个例子,但我不知道如何使用右移来优化我的代码。
如果不可能,是否有其他方法可以避免除法?
编辑: 1)if中的条件并不总是0.5,它可以是任何介于(0,1)之间的有理数。 2)上面的代码每秒执行10 * 56 * 181 * 56 * 181次。

你可以使用 currentPos << 1 < length 或者 currentPos < length >> 1 - Eli Sadoff
1
@Thomas 那这样就行不通了。 - Eli Sadoff
1
方程式 current / length < 0.5 等同于 2 * current < length。如果方程式是 current / length < 0.7,那么它将变成 10 * current < 7 * length。没有除法,只有乘法。任何乘以2的操作都可以替换为 << 1 - alvits
4
我非常怀疑一个简单的除法会导致太多的时间被浪费。你是否进行了全面优化的编译,并实际使用性能分析工具来告诉你代码中实际花费了最多的时间? - Michael Dorgan
1
您IP地址为143.198.54.68,由于运营成本限制,当前对于免费用户的使用频率限制为每个IP每72小时10次对话,如需解除限制,请点击左下角设置图标按钮(手机用户先点击左上角菜单按钮)。 - harold
显示剩余3条评论
4个回答

2

避免除以零是很简单的。

if (length > 2 * currentPos)

使用移位运算代替除法是一种微小的优化,任何一个好的编译器都会自动为您执行,而不会让您弄乱代码并使其难以阅读。


1
而且最重要的是,无用的整数转FP转换(以及无用的FP操作)。 - Matteo Italia
1
@Thomas:我严重怀疑,按照现在的写法,这不是你的性能瓶颈。使用分析工具,你几乎肯定会发现你的性能问题在其他地方。 - Matteo Italia
@MatteoItalia,我不确定Thomas使用的平台是什么,但我之前用过一种微控制器(来自MSP430系列),每个分区使用了大约4毫秒。话虽如此,我同意对代码进行分析可能会指出问题的根本原因在其他地方。 - Catsunami
2
@Thomas - 以上代码每秒被调用多少次?目标系统是什么?这些信息真的有助于我们更好地回答问题。 - Michael Dorgan
1
@Thomas 你确实处于边缘位置。在快速的CPU上,你可以希望每次迭代执行大约15条指令,并且仍然保持这个速率,但前提是它们必须是正确的组合,而且没有任何东西会减慢它们的速度。你真的必须让它们有用。我建议你在一个新问题中发布更完整的代码,并提供足够的上下文,以便可以建议SIMD解决方案。 - harold
显示剩余8条评论

1
让我们坦诚一点。在任何现代CPU上,浮点数除法将被流水线化处理,并且需要的时间与大多数其他FPU或甚至整数操作一样长。
相反,您应该在代码中使用分析工具来确定实际出现瓶颈的位置。只要您的代码没有处于1,000,000,000,000次循环中,这并不会产生什么影响。
如果您的代码确实处于这样的循环中,请告诉我们,因为除了简单除法截断这种方式已近十年无用之外,还有其他方式可以帮助您进行强化缩减、预计算等。
更新事实,这确实坐落在一个10亿次循环中。
现在,让我们从您的两个函数GetPos()GetLength()开始。如果您可以以这样的方式组织数据,使这些值对于循环的某些部分保持恒定,您就可以完全消除许多内存访问。您还可以在循环外进行乘法运算。
接下来,如果您可以在循环运行之前按长度或位置对数据进行排序,则可以通过数据二进制搜索将比较减少到最多20次左右,而不是数十亿次(O(log n)与O(n)的力量),然后您的代码运行非常快。
如果不可能,但数据每个循环都是恒定的,并且“做某事”的条件没有改变,那么这将变得非常并行化,可能可以跨多个CPU线程-尽管这不像听起来那么容易,所以要小心。
这只是一个开始,但我想让您知道更多信息可以提供更好的解决方案。

不过,让我们不要鼓励使用除法,对吧?相比乘法,除法的吞吐量仍然差一个数量级。 - harold
是的,它正处于一个繁重的循环中。请参考问题中的“编辑”部分。 - Yves
@harold,我同意尽可能避免不必要的除法总是明智的做法。 - Michael Dorgan

0

有一种通过常数进行快速除法的方法,但这仅适用于您在编译时知道该值的情况。通用算法在书籍Hacker's Delight中有描述。互联网上也有很多示例。不过你的情况有所不同。您从函数中检索长度

getLength();

然而,如果长度不是常数,但对于几个计算仍然是相同的数字,则可以通过计算倒数乘以它来提高性能。

这与乘法本身是通过二进制移位和加法完成的事实有关-比除法少得多。不过这可能有点棘手,因为我假设代码片段来自函数内部,因此您可能需要一个全局变量(或至少是函数外部的变量,即类成员)。


顺便说一下,对于常量,这些技巧通常直接实现在编译器中 - 没有必要混淆您的代码。 - Matteo Italia

0

注意:要将整数除以2,只需向右移动1位... (4>> 1)== 2。 (而4>> 2 == 1)


我最近(通过艰难的方式)学到,完全优化(-O3)并不总是做你想要的事情。(g++ v5.2.1,ubuntu 64)

在一个5x10^9的循环中,我手动更改了代码:

if (ZERO == (n & B00) // n-even
{
    ...even actions
}
else // n-odd
{
    ...odd actions
}

to:

if (n & B00) // n-odd
{
    ...odd actions
}
else // n-even
{
    ...even actions
}

并在该循环中节省了8秒钟。 (从58到50)

在尝试这个测试之前,我认为编译器a)可以(并且会)重新排列代码,并且b)明确测试零会更快。 我错了。

我提到这一点,即使您的问题似乎不同,因为它是一个非常简单的测试...几秒钟的编辑,然后进行编译和运行。


==0 应该是无关紧要的,重点在于您切换了分支,这应该会影响分支预测器的初始启发式。如果您知道一个分支的结果比另一个更有可能,您可以使用类似__builtin_expect(也许打包在像通常的“likely”和“unlikely”宏中)的东西来帮助编译器,或者使用 PGO 让它根据真实世界数据自己解决问题。 - Matteo Italia

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接