我假设计算一个数字的模是一个有点昂贵的操作,至少与简单的算术测试(例如查看一个数字是否超过数组的长度)相比。如果确实是这样,那么替换例如以下代码是否更有效:
res = array[(i + 1) % len];
与以下?:
res = array[(i + 1 == len) ? 0 : i + 1];
第一个更容易看,但我想知道第二个是否更有效。如果是这样的话,我是否可以期望一个优化编译器在使用编译语言时用第二个代码片段替换第一个代码片段?
当然,这种“优化”(如果它确实是一种优化)并不是在所有情况下都有效(在这种情况下,它只在i+1
永远不会大于len
时有效)。
9条答案
按热度按时间nafvub8i1#
我的一般建议如下。使用您认为更美观的版本,然后分析整个系统。只优化分析器标记为瓶颈的代码部分。我敢打赌,模运算符不会在其中。
就具体的例子而言,只有基准测试才能告诉你,在你的特定架构上,使用你的特定编译器,哪一个更快。你可能会用branching代替modulo,但很明显哪一个更快。
fzsnzjdm2#
一些简单的测量:
使用gcc或clang和
-O3
编译,并运行time ./a.out 0 42 1000000000
(模版本)或time ./a.out 1 42 1000000000
(比较版本),结果如下:*6.25秒用户运行时间为模数版本,
*对比版本为1.03秒。
(使用gcc 5.2.1或clang 3.6.2;英特尔酷睿i5- 4690K@3.50GHz; 64位Linux)
这意味着使用比较版本可能是一个好主意。
ewm0tg9j3#
那么,看看2种方法来获得“模3”循环计数器的下一个值。
我使用gcc -O3选项(用于通用的x64架构)和-s来编译它,以获取汇编代码。
第一个函数的代码做了一些无法解释的魔术(*)来避免除法,无论如何都使用乘法:
并且比第二个函数长得多(我敢打赌慢得多):
因此,“(现代)编译器无论如何都比你做得更好”并不总是正确的。
有趣的是,用4代替3的相同实验导致第一个函数的与掩码
但总的来说,它仍然不如第二个版本。
更明确地说明正确的做事方法
产生更好的结果:
()好吧,没那么复杂。乘以倒数。计算整数常数K =(2^N)/3,对于N的某个足够大的值。现在,当你想要X/3的值时,而不是除以3,计算XK,并将其向右移动N个位置。
xdyibdwo4#
如果代码中的“len”足够大,那么条件语句会更快,因为分支预测器几乎总是能正确猜测。
如果不是,那么我相信这与循环队列密切相关,在循环队列中,长度通常是2的幂。这将使编译器能够用一个简单的AND代替模。
代码如下:
size=15:
size=16:
在gcc 7.3.0中编译,使用-O3优化。这台机器是i7 920。
f8rj6qna5#
这里有一些额外的基准。请注意,我还添加了一个无分支版本:
这是我的i7- 4870 HQ的输出
在这种特殊情况下,三元运算符看起来要上级得多,当分支预测器上升时,它变得更加优越。但请注意,这是一个非常特殊的情况:如果我们不通过非常量值递增索引,使用更通用的
operator%
将是简单的,而其他两种方法可能会变得非常复杂。我想强调一下这个被低估的评论:
例如,通过删除
size
变量上的循环并将其声明为const size_t size = 4;
,我得到:结论
无分支版本的执行时间在各种场景中都非常稳定。在所考虑的情况下,三进制始终优于无分支,特别是当分支预测器启动时。最后,
operator%
虽然更通用,速度也更慢,但有机会得到优化,成为最快的,就像右侧的特定常量值一样。当然,这是完全依赖于平台的,谁知道这将如何在Arduino上:)
unftdfkk6#
我读了一篇关于快速哈希Map的文章。瓶颈可以是求模运算符以找到哈希桶。他们建议把你的桶数设为2的幂。显然,用2的幂求模就像看最后n位。
dddzy1tm7#
模运算代价很高,但除法运算代价也很高。因此,将代码从使用模运算符转换为除法并不会优化代码。
优化上述代码
rta7y2nd8#
是的,如果你在循环中调用取模运算符
%
,它会慢得多。如果你只是叫它几倍最大值,我不会担心它。即使在Visual Studio 2022的发布模式下,我的分析器也会将
if (value % alignment != 0)
语句标记为约10%的CPU使用率,这是相当大的。我能够通过使用简单的按位&
来显着优化它,因为我的对齐总是2的幂:优化编译器不能确定我的对齐总是2的幂,所以编译器不允许隐式地进行优化。这是编译器不能自动帮助你的例子之一。
现在,我的分析器只显示
if
语句的CPU使用率为0.3%,这比直接使用%
时更有效。mefy6pfw9#
在大多数架构上,模运算可以用一条处理器指令来完成(例如,x86上的DIV)。然而,这可能是一个不成熟的优化,你需要什么。