冒着重复的风险,也许我现在找不到类似的帖子:
我是用C写的(具体来说是C20)。我有一个带计数器的循环,它每转一圈都计数。我们称之为counter
。如果这个counter
达到了一个页面限制(我们称之为page_limit
),程序应该在下一页继续。它看起来像这样:
const size_t page_limit = 4942;
size_t counter = 0;
while (counter < foo) {
if (counter % page_limit == 0) {
// start new page
}
// some other code
counter += 1;
}
字符串
现在我想知道,因为计数器走得很高:如果我不用程序每次都计算counter % page_limit
的模,而是用另一个计数器,程序会运行得更快吗?它可能看起来像这样:
const size_t page_limit = 4942;
size_t counter = 0;
size_t page_counter = 4942;
while (counter < foo) {
if (page_counter == page_limit) {
// start new page
page_counter = 0;
}
// some other code
counter += 1;
page_counter += 1;
}
型
3条答案
按热度按时间mnowg1ta1#
(我假设你的意思是写
if(x%y==0)
而不是if(x%y)
,相当于计数器。我不认为编译器会为你做这种优化,所以它可能是值得的。它将是更小的代码大小,即使你不能测量速度差异。
x % y == 0
路仍然分支(所以仍然受到分支错误预测的影响,这些错误预测很少为真)。它唯一的优点是它不需要一个单独的计数器变量,只需要在循环中的某个点上的一些临时寄存器。但它确实需要每次迭代的除数。总的来说,这对于代码大小来说应该是更好的,而且如果您习惯了这种习惯用法,可读性也不会降低。(特别是如果您使用
if(--page_count == 0) { page_count=page_limit; ...
,因此所有逻辑片段都位于两个相邻行中。如果你的
page_limit
* 不是 * 一个编译时常量,这更有可能有所帮助。dec/jz
在多次递减中只取一次,比div
/test edx,edx
/jz
便宜得多,包括前端吞吐量。(div
在Intel CPU上被微编码为大约10个uops,因此即使它是一条指令,它仍然会占用前端多个周期,从而占用吞吐量资源,使周围的代码无法进入无序的后端)。(With a constant divisor, it's still multiply, right shift, sub to get the quotient,然后相乘和相减,得到余数。所以仍然有几个单微操作指令。虽然有一些小常数整除测试的技巧,请参阅@ CassioNeri关于快速整除测试的答案(2,3,4,5,...,16)?引用了他的期刊文章最近的GCC可能已经开始使用这些。
但是如果你的循环体不会在前端指令/uop吞吐量(在x86上)或除法器执行单元上形成瓶颈,那么乱序exec可能会隐藏甚至一条
div
指令的大部分开销。它不在关键路径上,因此如果它的延迟与其他计算并行发生,并且有空闲的吞吐量资源,则它可能是空闲的。(分支预测+推测执行允许执行继续,而无需等待分支条件已知,并且由于该工作独立于其他工作,因此它可以“提前运行”,因为编译器可以看到未来的迭代。尽管如此,使这项工作更便宜可以帮助编译器更快地看到和处理分支预测错误。但是具有快速恢复功能的现代CPU可以在恢复时继续处理分支之前的旧指令。(What exactly happens when a skylake CPU mispredicts a branch?/通过提前计算条件避免管道停滞)
当然,一些循环 * 确实 * 完全保持CPU的吞吐量资源忙碌,而不是缓存未命中或延迟链的瓶颈。每次迭代执行的uop越少,对其他超线程(或一般的SMT)越友好。
或者,如果您关心在有序CPU上运行的代码(常见于ARM和其他针对低功耗实现的非x86 ISA),则真实的工作必须等待分支条件逻辑。(只有硬件预取或缓存未命中加载等操作才能在运行额外代码以测试分支条件时做有用的工作。
使用递减计数器
实际上,您希望让编译器使用一个可以编译为
dec reg / jz .new_page
或类似值的向下计数器,而不是向上计数;所有普通的ISA都可以很便宜地做到这一点,因为它和你在普通循环的底部找到的东西是一样的。(dec
/jnz
在非零时保持循环)字符串
向下计数器在asm中更有效,在C中同样可读(与向上计数器相比),因此如果您正在进行微优化,您应该以这种方式编写它。相关:在手写asm FizzBuzz中使用该技术。也可能是3和5的倍数的asm sum的code review,但它对无匹配没有任何作用,因此优化它是不同的。
注意
page_limit
只在if体内部被访问,所以如果编译器的寄存器不足,它可以很容易地溢出,只在需要时读取它,而不是将寄存器与它或乘法器常数绑定在一起。或者,如果它是一个已知的常量,则只是一个立即移动指令。(大多数ISA也有比较即时,但不是全部。例如,MIPS和RISC-V只有比较和分支指令,这些指令将指令字中的空间用于目标地址,而不是立即数。)许多RISC ISA具有特殊支持,可以有效地将寄存器设置为比大多数采用立即数的指令更宽的常数(如具有16位立即数的ARM
movw
,因此4092
可以在mov
而不是cmp
的一条指令中完成:它不适合由偶数计数旋转的12位)。与除法(或乘法逆)相比,大多数RISC ISA没有乘法立即数,并且乘法逆通常比一个立即数更宽。(x86确实有multiple-immediate,但不是给你一个高半的形式。)Divide-immediate更罕见,甚至x86都没有,但没有编译器会使用它,除非优化空间而不是速度,如果它确实存在的话。
像x86这样的CISC ISA通常可以与内存源操作数相乘或相除,因此如果寄存器不足,编译器可以将除数保留在内存中(特别是如果它是一个运行时变量)。每次迭代加载一次(在缓存中命中)并不昂贵。但是,如果循环足够短并且没有足够的寄存器,溢出和重新加载在循环内更改的实际变量(如
page_count
)可能会引入存储/重新加载延迟瓶颈。(虽然这可能并不合理:如果你的循环体足够大,需要所有的寄存器,它可能有足够的延迟来隐藏一个store/reload。rt4zxlrg2#
如果除数是常数,大多数优化编译器会将除法或取模操作转换为乘以预生成的逆常数和移位指令。如果在循环中重复使用相同的除数值,也可能是这样。
模乘以逆得到 * 商 *,然后将 * 商 * 乘以 * 除数 * 得到 * 积 *,然后 * 原始数 * 减去 * 积 * 将是模。
乘法和移位在相当新的X86处理器上是快速指令,但是分支预测也可以减少条件分支所花费的时间,因此建议可能需要基准来确定哪个是最好的。
xlpyo6sf3#
如果有人把它放在我面前,我宁愿它是:
字符串
因为程序现在表达了处理的意图--一堆
page_limit
大小的块;而不是试图优化操作。编译器可以生成更好的代码,这只是一件幸事。