hyn*_*ner 12 c++ performance benchmarking x86 32bit-64bit
我有一段代码,在Windows上运行速度比在linux上快2倍.这是我测量的时间:
g++ -Ofast -march=native -m64
29.1123
g++ -Ofast -march=native
29.0497
clang++ -Ofast -march=native
28.9192
visual studio 2013 Debug 32b
13.8802
visual studio 2013 Release 32b
12.5569
这似乎是一个太大的差异.
这是代码:
#include <iostream>
#include <map>
#include <chrono>
static std::size_t Count = 1000;
static std::size_t MaxNum = 50000000;
bool IsPrime(std::size_t num)
{
for (std::size_t i = 2; i < num; i++)
{
if (num % i == 0)
return false;
}
return true;
}
int main()
{
auto start = std::chrono::steady_clock::now();
std::map<std::size_t, bool> value;
for (std::size_t i = 0; i < Count; i++)
{
value[i] = IsPrime(i);
value[MaxNum - i] = IsPrime(MaxNum - i);
}
std::chrono::duration<double> serialTime = std::chrono::steady_clock::now() - start;
std::cout << "Serial time = " << serialTime.count() << std::endl;
system("pause");
return 0;
}
所有这些都是在Windows 8与Linux 3.19.5(gcc 4.9.2,clang 3.5.0)的同一台机器上测得的.linux和windows都是64位.
这可能是什么原因？一些调度问题？
你没有说windows/linux操作系统是32位还是64位.
在64位Linux机器上,如果将size_t更改为int,您会发现linux上的执行时间会降低到与Windows相同的值.
size_t是win32上的int32,win64上的int64.
编辑:刚刚看到你的窗户拆卸.
你的Windows操作系统是32位的(或至少你编译为32位).
size_t是 Linux 上 x86-64 System V ABI 中的 64 位无符号类型，您在其中编译 64 位二进制文件。但在 32 位二进制文件中（就像您在 Windows 上制作的那样），它只是 32 位，因此试除循环仅执行 32 位除法。（size_t适用于 C++ 对象的大小，而不是文件的大小，因此它只需要是指针宽度。）
在 x86-64 Linux 上，-m64是默认值，因为 32 位基本上被认为是过时的。要制作 32 位可执行文件，请使用g++ -m32.
与大多数整数运算不同，Ice Lake 之前的 Intel CPU 上的除法吞吐量（和延迟）取决于操作数大小：64 位除法比 32 位除法慢。 （https://agner.org/optimize/和https://uops.info/查看端口的指令吞吐量/延迟/uops 表）。\n相关：codereview 问答：检查 NASM Win64 程序集中的数字是否为素数。AMD 没有这个问题（或者说 64 位 div/idiv 速度慢得不合理），并且 Intel Ice Lake 使 64 位 div/idiv 的微指令数量与 32 位类似。
\n与乘法或加法等其他操作相比，它非常慢：您的程序完全在整数除法吞吐量上遇到瓶颈，而不是在操作上map。（使用 Skylake 上 32 位二进制的性能计数器，arith.divider_active可以计算除法24.03执行单元处于活动状态的十亿个周期，其中24.84。是的，没错，除法是如此之慢，以至于有一个性能计数器只是对于那个执行单元。这也是一种特殊情况，因为它不是完全流水线的，所以即使在这样的情况下，你有独立的部门，它也不能像这样在每个时钟周期启动一个新的部门可以用于其他多周期运算，例如 FP 或整数乘法。）
不幸的是，g++ 无法基于数字是编译时常量并因此具有有限范围这一事实进行优化。g++ -m64优化div ecx为而不是. 是合法的（并且会大大加速）div rcx。这一更改使得 64 位二进制文件的运行速度与 32 位二进制文件一样快。（它计算完全相同的东西，只是没有那么多高零位。结果被隐式地零扩展以填充 64 位寄存器，而不是由除法器显式计算为零，这就足够了在这种情况下速度更快。）
我在 Skylake 上验证了这一点，方法是编辑二进制文件，将0x48REX.W 前缀替换为0x40，更改div rcx为div ecx不执行任何操作的 REX 前缀。所用的总周期在 32 位二进制的 1% 以内g++ -O3 -m32 -march=native。（还有时间，因为两次运行时 CPU 碰巧以相同的时钟速度运行。）（Godbolt 编译器资源管理器上的 g++7.3 asm 输出。）
32 位代码，运行 Linux 的 3.9GHz Skylake i7-6700k 上的 gcc7.3 -O3
\n$ cat > primes.cpp # and paste your code, then edit to remove the silly system("pause")\n$ g++ -Ofast -march=native -m32 primes.cpp -o prime32\n\n$ taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,instructions,uops_issued.any,uops_executed.thread,arith.divider_active ./prime32 \nSerial time = 6.37695\n\n\n Performance counter stats for \'./prime32\':\n 6377.915381 task-clock (msec) # 1.000 CPUs utilized \n 66 context-switches # 0.010 K/sec \n 0 cpu-migrations # 0.000 K/sec \n 111 page-faults # 0.017 K/sec \n 24,843,147,246 cycles # 3.895 GHz \n 6,209,323,281 branches # 973.566 M/sec \n 24,846,631,255 instructions # 1.00 insn per cycle \n 49,663,976,413 uops_issued.any # 7786.867 M/sec \n 40,368,420,246 uops_executed.thread # 6329.407 M/sec \n 24,026,890,696 arith.divider_active # 3767.201 M/sec \n \n 6.378365398 seconds time elapsed\n与 REX.W=0 的 64 位（手工编辑的二进制文件）相比
\n Performance counter stats for \'./prime64.div32\':\n\n 6399.385863 task-clock (msec) # 1.000 CPUs utilized \n 69 context-switches # 0.011 K/sec \n 0 cpu-migrations # 0.000 K/sec \n 146 page-faults # 0.023 K/sec \n 24,938,804,081 cycles # 3.897 GHz \n 6,209,114,782 branches # 970.267 M/sec \n 24,845,723,992 instructions # 1.00 insn per cycle \n 49,662,777,865 uops_issued.any # 7760.554 M/sec \n 40,366,734,518 uops_executed.thread # 6307.908 M/sec \n 24,045,288,378 arith.divider_active # 3757.437 M/sec \n\n 6.399836443 seconds time elapsed\n与原始 64 位二进制文件相比：
\n$ g++ -Ofast -march=native primes.cpp -o prime64\n$ taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,instructions,uops_issued.any,uops_executed.thread,arith.divider_active ./prime64\nSerial time = 20.1916\n\n Performance counter stats for \'./prime64\':\n\n 20193.891072 task-clock (msec) # 1.000 CPUs utilized \n 48 context-switches # 0.002 K/sec \n 0 cpu-migrations # 0.000 K/sec \n 148 page-faults # 0.007 K/sec \n 78,733,701,858 cycles # 3.899 GHz \n 6,225,969,960 branches # 308.310 M/sec \n 24,930,415,081 instructions # 0.32 insn per cycle \n 127,285,602,089 uops_issued.any # 6303.174 M/sec \n 111,797,662,287 uops_executed.thread # 5536.212 M/sec \n 27,904,367,637 arith.divider_active # 1381.822 M/sec \n\n 20.193208642 seconds time elapsed\n我不知道为什么性能计数器arith.divider_active没有增加更多。 div 64的 uop 明显多于div r32，因此可能会损害乱序执行并减少周围代码的重叠。div但我们知道，没有其他指令的背靠背也有类似的性能差异。
无论如何，这段代码大部分时间都花在那个可怕的试除循环中（它检查每个奇数和偶数除数，即使我们在检查低位后已经可以排除所有偶数除数...... 并且它检查所有一直到num而不是，所以对于非常大的素数来说sqrt(num)它的速度非常慢。）
根据perf record， 99.98% 的 cpu 周期事件在第二个试除循环（第一个）中触发MaxNum - i，因此div仍然是整个瓶颈，这只是性能计数器的一个怪癖，并非所有时间都记录为arith.divider_active
3.92 \xe2\x94\x821e8: mov rax,rbp\n 0.02 \xe2\x94\x82 xor edx,edx\n 95.99 \xe2\x94\x82 div rcx\n 0.05 \xe2\x94\x82 test rdx,rdx \n \xe2\x94\x82 \xe2\x86\x93 je 238 \n ... loop counter logic to increment rcx\n来自 Agner Fog 的 Skylake 说明表：
\n uops uops ports latency recip tput\n fused unfused\nDIV r32 10 10 p0 p1 p5 p6 26 6\nDIV r64 36 36 p0 p1 p5 p6 35-88 21-83\n（div r64本身实际上取决于其输入的实际大小，输入越小，速度越快。真正慢的情况是商非常大，IIRC。当 RDX 中 128 位被除数的上半部分时，速度可能也会更慢： RAX 不为零。C 编译器通常只div与 一起使用rdx=0。）
周期计数的比率 ( 78733701858 / 24938804081 = ~3.15) 实际上小于最佳情况吞吐量的比率 ( 21/6 = 3.5)。它应该是一个纯粹的吞吐量瓶颈，而不是延迟，因为下一个循环迭代可以开始，而无需等待最后的除法结果。（感谢分支预测+推测执行。）也许该除法循环中存在一些分支未命中。
如果您只发现 2 倍的性能比，那么您拥有不同的 CPU。可能是 Haswell，其中 32 位div吞吐量为 9-11 个周期，64 位div吞吐量为 21-74 个周期。
可能不是 AMD：即使对于div r64. 例如，压路机的div r32吞吐量 = 1 每 13-39 个循环，并且div r64= 13-70。我猜想，与英特尔不同，即使您将它们提供给更宽的寄存器中的除法器，使用相同的实际数字，您也可能会获得相同的性能。（最坏的情况会增加，因为输入和结果的可能大小更大。）AMD 整数除法只有 2 uops，与 Skylake 上微编码为 10 或 36 uops 的 Intel 不同。（对于以 57 微指令进行签名的情况，甚至更多idiv r64。）这可能与 AMD 对于宽寄存器中的小数字的效率有关。
顺便说一句，FP 除法始终是单微指令，因为它在正常代码中对性能更为关键。（提示：如果他们关心性能的话，在现实生活中没有人会使用完全幼稚的试除法来检查多个素数。筛子或其他东西。）
\n有序的关键map是 a size_t，并且指针在 64 位代码中更大，使得每个红黑树节点明显更大，但这不是瓶颈。
顺便说一句，与两个数组相比，这map<>是一个糟糕的bool prime_low[Count], prime_high[Count]选择：一个用于低Count元素，一个用于高元素Count。您有 2 个连续的范围，键可以按位置隐式。或者至少使用std::unordered_map哈希表。我觉得有序版本应该被称为ordered_map, and map = unordered_map，因为您经常看到代码map在不利用排序的情况下使用。
您甚至可以std::vector<bool>使用 1/8 的缓存占用量来获取位图。
有一个“x32”ABI（长模式下的 32 位指针），对于不需要超过 4G 虚拟地址空间的进程来说，它具有两全其美的优点：小指针可实现更高的数据密度/更小的缓存占用空间指针密集型数据结构，但具有现代调用约定、更多寄存器、基线 SSE2 和 64 位整数寄存器（当您确实需要 64 位数学时）的优势。但不幸的是它不是很受欢迎。它只是快一点，所以大多数人不想要每个库的第三个版本。
\n在这种情况下，您可以修复要使用的源unsigned int（或者uint32_t如果您想移植到int只有 16 位的系统）。或者uint_least32_t避免需要固定宽度的类型。您可以仅对 arg to 执行此操作IsPrime，也可以对数据结构执行此操作。（但是如果您正在优化，则键是按数组中的位置隐式显示的，而不是显式的。）
您甚至可以制作一个具有 64 位循环和 32 位循环的版本IsPrime，它根据输入的大小进行选择。