为什么使用带有int64_t操作数的mod使这个函数慢150％？
max_rem函数计算(a+1)^n + (a-1)^n在除以a²时离开的最大余数， n = 1, 2, 3... main调用max_rem每个从3到999 。 完整代码：
#include #include int max_rem(int a) { int max_r = 0; int m = a * a; // <-------- offending line int r1 = a+1, r2 = a-1; for(int n = 1; n <= a*a; n++) { r1 = (r1 * (a + 1)) % m; r2 = (r2 * (a - 1)) % m; int r = (r1 + r2) % m; if(max_r < r) max_r = r; } return max_r; } int main() { int64_t sum = 0; for(int a = 3; a < 1000; a++) sum += max_rem(a); printf("%ld\n", sum); }
如果我改变第6行：
int m = a * a;
至
int64_t m = a * a;
整个计算速度慢了约150％ 。 我尝试了gcc 5.3和clang 3.6 。
使用int ：
$ gcc -std=c99 -O3 -Wall -o 120 120.c $ time(./120) real 0m3.823s user 0m3.816s sys 0m0.000s
使用int64_t ：
$ time(./120) real 0m9.861s user 0m9.836s sys 0m0.000s
是的，我在64位系统上 。 为什么会这样？
我一直认为使用int64_t更安全，更便携，并且是“现代编写C”®的方式，并且不会损害64位系统上的数字代码性能。 这个假设是错误的吗？
编辑 ：只是要清楚： 即使你将每个变量更改为int64_t ，减速仍然存在 。 所以这不是混合int和int64_t的问题。
我一直认为使用int64_t更安全，更便携，并且是“现代编写C”®的方式，并且不会损害64位系统上的数字代码性能。 这个假设是错误的吗？
对我来说似乎如此。 您可以在英特尔软件优化参考手册 （附录C，表C-17通用指令，第645页）中找到指令时序：
IDIV r64每条指令吞吐量为85-100个周期
IDIV r32每条指令的吞吐量为20-26个周期
TL; DR：您会看到不同类型更改的性能，因为您正在测量不同的计算 – 一个包含所有32位数据，另一个包含部分或全部64位数据。
我一直认为使用int64_t更安全，更便携，并且是“编写C”®的现代方式
int64_t是最安全和最便携的（在符合C99和C11编译器之间）引用64位有符号整数类型的方式，没有填充位和二进制补码表示，如果实现实际上提供了这种类型。 是否使用此类型实际上使您的代码更具可移植性取决于代码是否依赖于整数表示的任何特定特征，以及您是否关心到不提供此类型的环境的可移植性。
并且不会损害64位系统上的数字代码性能。 这个假设是错误的吗？
int64_t被指定为typedef 。 在任何给定的系统上，使用int64_t在语义上与直接使用该系统上typedef基础的类型相同。 您将看到这些替代方案之间没有性能差异。
但是，你的推理和问题似乎相信一个假设：要么在你执行测试的系统上， int64_t的基本类型是int ，要么64位算术将在该系统上与32位算术完全相同。 这些假设都不合理。 绝不保证64位系统的C实现会使int成为64位类型，特别是对于x86_64而言，GCC和Clang都不会这样做。 此外，C对于算法在不同类型上的相对性能没有任何说法，正如其他人所指出的，对于64位操作数，本机x86_64整数除法指令实际上比32位操作数更慢。 其他平台可能会出现其他差异。
与任何其他操作相比，整数除法/模数非常慢。 （并且取决于数据大小，与现代硬件上的大多数操作不同，请参阅此答案的结尾）
对于重复使用相同的模数，通过查找整数除数的乘法逆，可以获得更好的性能 。 编译器会为您编写这样的编译时常量，但是在运行时执行它的时间和代码大小相当昂贵，所以对于当前的编译器，您必须自己决定它何时值得做。
它预先需要一些CPU周期，但每次迭代它们分摊3个分区。
这个想法的参考文件是Granlund和蒙哥马利1994年的论文 ，当时鸿沟仅为P5奔腾硬件的4倍。 那篇论文讨论了在gcc 2.6中实现这个想法，以及它运作的数学certificate。
编译器输出显示由一个小常量除以的代码类型：
## clang 3.8 -O3 -mtune=haswell for x86-64 SysV ABI: first arg in rdi int mod13 (int a) { return a%13; } movsxd rax, edi # sign-extend 32bit a into 64bit rax imul rcx, rax, 1321528399 # gcc uses one-operand 32bit imul (32x32 => 64b), which is faster on Atom but slower on almost everything else. I'm showing clang's output because it's simpler mov rdx, rcx shr rdx, 63 # 0 or 1: extract the sign bit with a logical right shift sar rcx, 34 # only use the high half of the 32x32 => 64b multiply add ecx, edx # ecx = a/13. # adding the sign bit accounts for the rounding semantics of C integer division with negative numbers imul ecx, ecx, 13 # do the remainder as a - (a/13)*13 sub eax, ecx ret
是的，所有这些都比div指令便宜，因为吞吐量和延迟。
我试图谷歌更简单的描述或计算器，并找到像这个页面的东西。
在现代Intel CPU上，32和64b乘法每个周期吞吐量为1，周期延迟为3。 （即它是完全流水线的）。
除法仅部分流水线化（div单元每个时钟不能接受一个输入），与大多数指令不同，它具有数据相关的性能：
来自Agner Fog的insn表 （另请参阅x86标签wiki）：
- Intel Core2：
idiv r32：每12-36c吞吐量一个（18-42c延迟，4 uop）。
idiv r64：每28-40c吞吐量一次（39-72c延迟，56 uops）。 （unsigneddiv显着更快：32 uops，每18-37c吞吐量一个） - Intel Haswell：
div/idiv r32：每8-11c吞吐量一个（22-29c延迟，9 uop）。
idiv r64：每24-81c吞吐量一个（39-103c延迟，59 uops）。 （无符号div：每21-74c吞吐量一个，36 uops） - Skylake：
div/idiv r32：每6c吞吐量一次（26c延迟，10 uop）。
64b：每24-90c吞吐量一个（42-95c延迟，57 uop）。 （无符号div：每21-83c吞吐量一个，36 uops）
因此在英特尔硬件上，无符号分区对于64位操作数来说更便宜，对于32b操作数则相同。
32b和64b idiv之间的吞吐量差异很容易占150％的性能。 您的代码完全受吞吐量限制，因为您有大量独立操作，尤其是循环迭代之间。 循环携带的依赖关系只是max操作的cmov 。
这个问题的答案只能来看看大会。 为了我的好奇心，我会在我的盒子上运行它，但它距离3000英里:(所以我必须猜测，你在这里查看并发布你的发现……只需在编译器命令行中添加-S即可。
我相信使用int64编译器正在做与int32不同的事情。 也就是说，他们不能使用int32可用的一些优化。
也许gcc只用int32替换乘法？ 应该有一个’if（x <0）'分支。 也许gcc可以用int32消除它？
我不知道如果他们都表现出“偶像”，那么表现就不会如此不同