Windows 上的 32 位试用代码比 Linux 上的 64 位代码运行速度快 2 倍
Trial-division code runs 2x faster as 32-bit on Windows than 64-bit on Linux
我有一段代码在 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 反汇编。
您的 windows OS 是 32 位版本（或者至少您已经针对 32 位编译）。
从已编辑的问题中提取的答案：
这是由于在 windows 上构建 32b 二进制文件而不是在 linux 上构建 64b 二进制文件造成的，这里是 windows 的 64b 数字：
Visual studio 2013 Debug 64b
29.1985
Visual studio 2013 Release 64b
29.7469
size_t 是 Linux 上的 x86-64 System V ABI 中的 64 位无符号类型，您正在其中编译 64 位二进制文件。但是在 32 位二进制文件中（就像你在 Windows 上做的那样），它只是 32 位的，因此试除循环只进行 32 位除法。 （size_t 是针对 C++ 对象的大小，而不是文件的大小，所以它只需要是指针宽度。）
在 x86-64 Linux 上，-m64 是默认值，因为 32 位基本上被认为已过时。要生成 32 位 executable，请使用 g++ -m32.
与大多数整数运算不同，现代 x86 CPUs 上的除法吞吐量（和延迟）取决于操作数大小：64 位除法比 32 位除法慢。（https://agner.org/optimize/ tables 的指令吞吐量/延迟/微指令对于哪些端口）。
与乘法或特别是加法等其他操作相比，它非常慢：您的程序在整数除法吞吐量上完全成为瓶颈，而不是 map 操作。 （使用 Skylake 上 32 位二进制文件的性能计数器，arith.divider_active 计数 24.03 十亿个除法执行单元处于活动状态的周期，总计 24.84 十亿个核心时钟周期。是的，没错，除法太慢了，以至于只有那个执行单元有一个性能计数器。这也是一种特殊情况，因为它没有完全流水线化，所以即使在这种情况下你有独立的除法，它也不能每个时钟都开始一个新的像其他多循环操作（如 FP 或整数乘法）一样循环。）
不幸的是，g++ 未能根据数字是编译时常量的事实进行优化，因此范围有限。将 g++ -m64 优化为 div ecx 而不是 div rcx 是合法的（并且会大大加快速度）。该更改使 64 位二进制 运行 与 32 位二进制一样快。 （它计算完全相同的东西，只是没有那么多高零位。结果隐式零扩展以填充 64 位寄存器，而不是通过除法器显式计算为零，在这种情况下要快得多。）
我通过编辑二进制文件在 Skylake 上验证了这一点，将 0x48 REX.W 前缀替换为 0x40，更改 div rcx 变成 div ecx 带有一个什么都不做的 REX 前缀。所用的总周期在 g++ -O3 -m32 -march=native 的 32 位二进制文件的 1% 以内。 （还有时间，因为 CPU 碰巧是 运行ning，两个 运行s 的时钟速度相同。）（g++7.3 asm output on the Godbolt compiler explorer。）
32 位代码，3.9GHz Skylake i7-6700k 上的 gcc7.3 -O3 运行ning Linux
$ cat > primes.cpp # and paste your code, then edit to remove the silly system("pause")
$ g++ -Ofast -march=native -m32 primes.cpp -o prime32
$ 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
Serial time = 6.37695
Performance counter stats for './prime32':
6377.915381 task-clock (msec) # 1.000 CPUs utilized
66 context-switches # 0.010 K/sec
0 cpu-migrations # 0.000 K/sec
111 page-faults # 0.017 K/sec
24,843,147,246 cycles # 3.895 GHz
6,209,323,281 branches # 973.566 M/sec
24,846,631,255 instructions # 1.00 insn per cycle
49,663,976,413 uops_issued.any # 7786.867 M/sec
40,368,420,246 uops_executed.thread # 6329.407 M/sec
24,026,890,696 arith.divider_active # 3767.201 M/sec
6.378365398 seconds time elapsed
对比64 位 REX.W=0（手动编辑的二进制文件）
Performance counter stats for './prime64.div32':
6399.385863 task-clock (msec) # 1.000 CPUs utilized
69 context-switches # 0.011 K/sec
0 cpu-migrations # 0.000 K/sec
146 page-faults # 0.023 K/sec
24,938,804,081 cycles # 3.897 GHz
6,209,114,782 branches # 970.267 M/sec
24,845,723,992 instructions # 1.00 insn per cycle
49,662,777,865 uops_issued.any # 7760.554 M/sec
40,366,734,518 uops_executed.thread # 6307.908 M/sec
24,045,288,378 arith.divider_active # 3757.437 M/sec
6.399836443 seconds time elapsed
对比原来的64位二进制:
$ g++ -Ofast -march=native primes.cpp -o prime64
$ 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
Serial time = 20.1916
Performance counter stats for './prime64':
20193.891072 task-clock (msec) # 1.000 CPUs utilized
48 context-switches # 0.002 K/sec
0 cpu-migrations # 0.000 K/sec
148 page-faults # 0.007 K/sec
78,733,701,858 cycles # 3.899 GHz
6,225,969,960 branches # 308.310 M/sec
24,930,415,081 instructions # 0.32 insn per cycle
127,285,602,089 uops_issued.any # 6303.174 M/sec
111,797,662,287 uops_executed.thread # 5536.212 M/sec
27,904,367,637 arith.divider_active # 1381.822 M/sec
20.193208642 seconds time elapsed
IDK 为什么 arith.divider_active 的性能计数器没有增加更多。 div 64 比 div r32 多得多，所以 可能 它会影响乱序执行并减少周围代码的重叠。但我们知道，没有其他指令的背靠背 div 具有类似的性能差异。
无论如何，这段代码大部分时间都花在那个糟糕的试除循环中（它检查每个奇数和偶数除数，即使我们已经可以在检查低位后排除所有偶数除数...... 并且一直检查到 num 而不是 sqrt(num)，所以对于非常大的素数 来说 非常慢 。 )
根据 perf record，99.98% 的 cpu 循环事件在 2nd 试炼循环中触发，第一个 MaxNum - i ，所以 div 仍然是整个瓶颈，这只是性能计数器的一个怪癖，并非所有时间都记录为 arith.divider_active
3.92 │1e8: mov rax,rbp
0.02 │ xor edx,edx
95.99 │ div rcx
0.05 │ test rdx,rdx
│ ↓ je 238
... loop counter logic to increment rcx
来自 Agner Fog 对 Skylake 的说明 tables：
uops uops ports latency recip tput
fused unfused
DIV r32 10 10 p0 p1 p5 p6 26 6
DIV r64 36 36 p0 p1 p5 p6 35-88 21-83
(div r64 本身实际上是数据依赖于其输入的实际大小，小输入更快。really 慢的情况具有非常大的商, IIRC。当 RDX:RAX 中 128 位被除数的上半部分不为零时，可能也会变慢。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，最佳情况下的吞吐量仍然很小。例如Steamroller 的吞吐量为 div r32 每 13-39 个周期 1 个，div r64 = 13-70 个。我猜想，使用相同的实际数字，即使将它们提供给更宽寄存器中的除法器，您也可能获得相同的性能，这与英特尔不同。 （最坏的情况会上升，因为输入和结果的可能大小更大。）AMD 整数除法只有 2 微指令，不像英特尔在 Skylake 上被微编码为 10 或 36 微指令。 （对于 57 uops 的有符号 idiv r64 甚至更多。）这可能与 AMD 对宽寄存器中的小数字有效有关。
顺便说一句，FP 划分始终是单 uop，因为它在普通代码中对性能更为关键。 （提示：如果他们关心性能根本，没有人会在现实生活中使用完全天真的试分来检查多个素数。筛选或其他东西。）
有序的map的key是一个size_t，在64位代码中指针更大，使得每个红黑树节点显着变大，但那是不是瓶颈.
顺便说一句，map<> 是一个 糟糕的 选择，对比两个 bool prime_low[Count], prime_high[Count] 数组：一个用于低 Count 元素，另一个对于高Count。您有 2 个连续的范围，键可以按位置隐含。或者至少使用 std::unordered_map 散列 table。我觉得有序版本应该被称为 ordered_map 和 map = unordered_map，因为您经常看到代码使用 map 而没有利用排序。
您甚至可以使用 std::vector<bool> 获取位图，使用缓存占用空间的 1/8。
有一个 "x32" ABI（长模式下的 32 位指针）对于不需要超过 4G 虚拟地址的进程具有两全其美的优势 space：小指针用于在指针密集型数据结构中获得更高的数据密度/更小的缓存占用空间，但现代调用约定的优势、更多的寄存器、基线 SSE2 和 64 位整数寄存器在您确实需要 64 位数学时。但不幸的是它不是很受欢迎。它只是快了一点，所以大多数人不想要每个库的第三个版本。
在这种情况下，您可以修复源代码以使用 unsigned int（或 uint32_t，如果您想成为 portable int 只有 16 位的系统）。或者 uint_least32_t 以避免需要固定宽度的类型。您只能对 IsPrime 的 arg 或数据结构执行此操作。 （但是，如果您正在优化，则键在数组中的位置是隐式的，而不是显式的。）
您甚至可以制作一个带有 64 位循环和 32 位循环的 IsPrime 版本，它根据输入的大小进行选择。
我有一段代码在 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 反汇编。
您的 windows OS 是 32 位版本（或者至少您已经针对 32 位编译）。
从已编辑的问题中提取的答案：
这是由于在 windows 上构建 32b 二进制文件而不是在 linux 上构建 64b 二进制文件造成的，这里是 windows 的 64b 数字：
Visual studio 2013 Debug 64b
29.1985
Visual studio 2013 Release 64b
29.7469
size_t 是 Linux 上的 x86-64 System V ABI 中的 64 位无符号类型，您正在其中编译 64 位二进制文件。但是在 32 位二进制文件中（就像你在 Windows 上做的那样），它只是 32 位的，因此试除循环只进行 32 位除法。 （size_t 是针对 C++ 对象的大小，而不是文件的大小，所以它只需要是指针宽度。）
在 x86-64 Linux 上，-m64 是默认值，因为 32 位基本上被认为已过时。要生成 32 位 executable，请使用 g++ -m32.
与大多数整数运算不同，现代 x86 CPUs 上的除法吞吐量（和延迟）取决于操作数大小：64 位除法比 32 位除法慢。（https://agner.org/optimize/ tables 的指令吞吐量/延迟/微指令对于哪些端口）。
与乘法或特别是加法等其他操作相比，它非常慢：您的程序在整数除法吞吐量上完全成为瓶颈，而不是 map 操作。 （使用 Skylake 上 32 位二进制文件的性能计数器，arith.divider_active 计数 24.03 十亿个除法执行单元处于活动状态的周期，总计 24.84 十亿个核心时钟周期。是的，没错，除法太慢了，以至于只有那个执行单元有一个性能计数器。这也是一种特殊情况，因为它没有完全流水线化，所以即使在这种情况下你有独立的除法，它也不能每个时钟都开始一个新的像其他多循环操作（如 FP 或整数乘法）一样循环。）
g++ 未能根据数字是编译时常量的事实进行优化，因此范围有限。将 g++ -m64 优化为 div ecx 而不是 div rcx 是合法的（并且会大大加快速度）。该更改使 64 位二进制 运行 与 32 位二进制一样快。 （它计算完全相同的东西，只是没有那么多高零位。结果隐式零扩展以填充 64 位寄存器，而不是通过除法器显式计算为零，在这种情况下要快得多。）
我通过编辑二进制文件在 Skylake 上验证了这一点，将 0x48 REX.W 前缀替换为 0x40，更改 div rcx 变成 div ecx 带有一个什么都不做的 REX 前缀。所用的总周期在 g++ -O3 -m32 -march=native 的 32 位二进制文件的 1% 以内。 （还有时间，因为 CPU 碰巧是 运行ning，两个 运行s 的时钟速度相同。）（g++7.3 asm output on the Godbolt compiler explorer。）
32 位代码，3.9GHz Skylake i7-6700k 上的 gcc7.3 -O3 运行ning Linux
$ cat > primes.cpp # and paste your code, then edit to remove the silly system("pause")
$ g++ -Ofast -march=native -m32 primes.cpp -o prime32
$ 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
Serial time = 6.37695
Performance counter stats for './prime32':
6377.915381 task-clock (msec) # 1.000 CPUs utilized
66 context-switches # 0.010 K/sec
0 cpu-migrations # 0.000 K/sec
111 page-faults # 0.017 K/sec
24,843,147,246 cycles # 3.895 GHz
6,209,323,281 branches # 973.566 M/sec
24,846,631,255 instructions # 1.00 insn per cycle
49,663,976,413 uops_issued.any # 7786.867 M/sec
40,368,420,246 uops_executed.thread # 6329.407 M/sec
24,026,890,696 arith.divider_active # 3767.201 M/sec
6.378365398 seconds time elapsed
对比64 位 REX.W=0（手动编辑的二进制文件）
Performance counter stats for './prime64.div32':
6399.385863 task-clock (msec) # 1.000 CPUs utilized
69 context-switches # 0.011 K/sec
0 cpu-migrations # 0.000 K/sec
146 page-faults # 0.023 K/sec
24,938,804,081 cycles # 3.897 GHz
6,209,114,782 branches # 970.267 M/sec
24,845,723,992 instructions # 1.00 insn per cycle
49,662,777,865 uops_issued.any # 7760.554 M/sec
40,366,734,518 uops_executed.thread # 6307.908 M/sec
24,045,288,378 arith.divider_active # 3757.437 M/sec
6.399836443 seconds time elapsed
对比原来的64位二进制:
$ g++ -Ofast -march=native primes.cpp -o prime64
$ 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
Serial time = 20.1916
Performance counter stats for './prime64':
20193.891072 task-clock (msec) # 1.000 CPUs utilized
48 context-switches # 0.002 K/sec
0 cpu-migrations # 0.000 K/sec
148 page-faults # 0.007 K/sec
78,733,701,858 cycles # 3.899 GHz
6,225,969,960 branches # 308.310 M/sec
24,930,415,081 instructions # 0.32 insn per cycle
127,285,602,089 uops_issued.any # 6303.174 M/sec
111,797,662,287 uops_executed.thread # 5536.212 M/sec
27,904,367,637 arith.divider_active # 1381.822 M/sec
20.193208642 seconds time elapsed
IDK 为什么 arith.divider_active 的性能计数器没有增加更多。 div 64 比 div r32 多得多，所以 可能 它会影响乱序执行并减少周围代码的重叠。但我们知道，没有其他指令的背靠背 div 具有类似的性能差异。
无论如何，这段代码大部分时间都花在那个糟糕的试除循环中（它检查每个奇数和偶数除数，即使我们已经可以在检查低位后排除所有偶数除数...... 并且一直检查到 num 而不是 sqrt(num)，所以对于非常大的素数 来说 非常慢 。 )
根据 perf record，99.98% 的 cpu 循环事件在 2nd 试炼循环中触发，第一个 MaxNum - i ，所以 div 仍然是整个瓶颈，这只是性能计数器的一个怪癖，并非所有时间都记录为 arith.divider_active
3.92 │1e8: mov rax,rbp
0.02 │ xor edx,edx
95.99 │ div rcx
0.05 │ test rdx,rdx
│ ↓ je 238
... loop counter logic to increment rcx
来自 Agner Fog 对 Skylake 的说明 tables：
uops uops ports latency recip tput
fused unfused
DIV r32 10 10 p0 p1 p5 p6 26 6
DIV r64 36 36 p0 p1 p5 p6 35-88 21-83
(div r64 本身实际上是数据依赖于其输入的实际大小，小输入更快。really 慢的情况具有非常大的商, IIRC。当 RDX:RAX 中 128 位被除数的上半部分不为零时，可能也会变慢。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，最佳情况下的吞吐量仍然很小。例如Steamroller 的吞吐量为 div r32 每 13-39 个周期 1 个，div r64 = 13-70 个。我猜想，使用相同的实际数字，即使将它们提供给更宽寄存器中的除法器，您也可能获得相同的性能，这与英特尔不同。 （最坏的情况会上升，因为输入和结果的可能大小更大。）AMD 整数除法只有 2 微指令，不像英特尔在 Skylake 上被微编码为 10 或 36 微指令。 （对于 57 uops 的有符号 idiv r64 甚至更多。）这可能与 AMD 对宽寄存器中的小数字有效有关。
顺便说一句，FP 划分始终是单 uop，因为它在普通代码中对性能更为关键。 （提示：如果他们关心性能根本，没有人会在现实生活中使用完全天真的试分来检查多个素数。筛选或其他东西。）
有序的map的key是一个size_t，在64位代码中指针更大，使得每个红黑树节点显着变大，但那是不是瓶颈.
顺便说一句，map<> 是一个 糟糕的 选择，对比两个 bool prime_low[Count], prime_high[Count] 数组：一个用于低 Count 元素，另一个对于高Count。您有 2 个连续的范围，键可以按位置隐含。或者至少使用 std::unordered_map 散列 table。我觉得有序版本应该被称为 ordered_map 和 map = unordered_map，因为您经常看到代码使用 map 而没有利用排序。
您甚至可以使用 std::vector<bool> 获取位图，使用缓存占用空间的 1/8。
有一个 "x32" ABI（长模式下的 32 位指针）对于不需要超过 4G 虚拟地址的进程具有两全其美的优势 space：小指针用于在指针密集型数据结构中获得更高的数据密度/更小的缓存占用空间，但现代调用约定的优势、更多的寄存器、基线 SSE2 和 64 位整数寄存器在您确实需要 64 位数学时。但不幸的是它不是很受欢迎。它只是快了一点，所以大多数人不想要每个库的第三个版本。
在这种情况下，您可以修复源代码以使用 unsigned int（或 uint32_t，如果您想成为 portable int 只有 16 位的系统）。或者 uint_least32_t 以避免需要固定宽度的类型。您只能对 IsPrime 的 arg 或数据结构执行此操作。 （但是，如果您正在优化，则键在数组中的位置是隐式的，而不是显式的。）
您甚至可以制作一个带有 64 位循环和 32 位循环的 IsPrime 版本，它根据输入的大小进行选择。