У меня есть кусок кода, который работает в 2 раза быстрее в Windows, чем в Linux. Вот времена, которые я измерял:
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 до значения, аналогичного тому, которое у вас есть для окон.
size_t является int32 на win32, int64 на win64.
РЕДАКТИРОВАТЬ: только что увидела вашу разборку окон.
Ваша ОС Windows - это 32-битная разновидность (или, по крайней мере, вы скомпилированы для 32-разрядной версии).
size_t - это 64-разрядный тип без знака в x86-64 System V ABI в Linux, где вы компилируете 64-разрядный двоичный файл. Но в 32-разрядном двоичном коде (как вы делаете в Windows) он только 32-разрядный, и, таким образом, цикл пробного деления выполняет только 32-разрядное деление. (size_t предназначен для размеров объектов C++, а не файлов, поэтому он должен быть только шириной указателя.)
В x86-64 Linux по умолчанию используется -m64, потому что 32-битная -m64 считается устаревшей. Чтобы сделать 32-битный исполняемый файл, используйте g++ -m32.
В отличие от большинства целочисленных операций, пропускная способность деления (и задержка) на современных процессорах x86 зависит от размера операнда: 64-битное деление медленнее, чем 32-битное. (https://agner.org/optimize/ для таблиц пропускной способности команд/латентности /uops для каких портов).
И это очень медленно по сравнению с другими операциями, такими как умножение или особенно сложение: ваша программа полностью ограничивает пропускную способность целочисленного деления, а не операции на map. (С счетчиками perf для 32-разрядного двоичного arith.divider_active Skylake arith.divider_active подсчитывает 24.03 миллиарда циклов, в которых была активна единица выполнения деления, из 24.84 числа 24.84 миллиарда тактовых циклов ядра. Да, верно, деление настолько медленное, что существует счетчик производительности только для этого исполнительного блока. Это также особый случай, потому что он не полностью конвейеризован, поэтому даже в таком случае, когда у вас есть независимые деления, он не может запускать новое каждый тактовый цикл, как для других многоцикловых операций. как FP или целочисленное умножение.)
g++, к сожалению, не удается оптимизировать на основании того факта, что числа являются константами времени компиляции и поэтому имеют ограниченные диапазоны. Для g++ -m64 было бы законным (и огромным ускорением) оптимизировать для div ecx вместо div rcx. Это изменение заставляет 64-разрядный двоичный файл работать так же быстро, как и 32-разрядный двоичный. (Он вычисляет одно и то же, просто без большого количества битов с большим нулем. Результат неявно расширяется до нуля, чтобы заполнить 64-битный регистр, вместо того, чтобы делитель явно вычислял его как ноль, и это намного быстрее в этом случае.)
Я подтвердил это на Skylake, отредактировав двоичный 0x48 заменив префикс 0x48 REX.W на 0x40, заменив div rcx на div ecx с префиксом REX бездействия. Общее количество выполненных циклов было в пределах 1% от 32-битного двоичного g++ -O3 -m32 -march=native из g++ -O3 -m32 -march=native. (И время, поскольку ЦП работал на одной и той же тактовой частоте для обоих запусков.) (Вывод asm g++ 7.3 в проводнике компилятора Godbolt.)
32-битный код, gcc7.3 -O3 на 3,9 ГГц Skylake i7-6700k под управлением 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 больше не arith.divider_active. div 64 значительно больше div r32, чем div r32, поэтому, возможно, он div r32 выполнению не по порядку и уменьшает перекрытие окружающего кода. Но мы знаем, что div без других инструкций имеет похожую разницу в производительности.
И в любом случае, этот код проводит большую часть своего времени в этом ужасном цикле пробного деления (который проверяет каждый нечетный и четный делитель, даже если мы уже можем исключить все четные делители после проверки младшего бита... И который проверяет все вплоть до num вместо sqrt(num), так что это очень медленно для очень больших простых чисел.)
Согласно perf record о perf record, 99,98% событий цикла процессора MaxNum - i во 2-м цикле пробного деления, то есть 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:
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 себе div r64 зависит от фактического размера его входов, причем небольшие входы быстрее. Очень медленные случаи с очень большими частями, IIRC. И, вероятно, также медленнее, когда верхняя половина 128-битного дивиденда в RDX: RAX отличен от нуля. Компиляторы C обычно используют только div с rdx=0)
Отношение количества циклов (78733701858/24938804081 = ~3.15) на самом деле меньше, чем отношение пропускной способности для лучшего случая (21/6 = 3.5). Это должно быть чисто узкое место в пропускной способности, а не задержка, потому что следующая итерация цикла может начаться без ожидания последнего результата деления. (Благодаря предсказанию ветвлений + спекулятивному выполнению.) Возможно, в этом цикле деления есть некоторые ошибки ветвления.
Если вы нашли только 2-кратное соотношение производительности, значит, у вас другой процессор. Возможно, Хасуэллы, где 32-битный div пропускная способности составляют 9-11 циклов, а также 64-битный div пропускной способности составляет 21-74.
Вероятно, не AMD: пропускная способность в лучшем случае все еще мала даже для div r64. Например, Steamroller имеет пропускную способность div r32= 1 на 13-39 циклов, а div r64= div r64. Я предполагаю, что с теми же фактическими числами вы, вероятно, получите ту же производительность, даже если вы отдадите их разделителю в более широких регистрах, в отличие от Intel. (Наихудший случай возрастает, потому что возможный размер ввода и результата больше.) Целочисленное деление AMD составляет всего 2 моп, в отличие от Intel, который на Skylake микрокодируется как 10 или 36 моп. (И даже больше для подписанного idiv r64 на 57 моп.) Это, вероятно, связано с эффективностью AMD для небольших чисел в широких регистрах.
Кстати, деление FP всегда однопроцессное, потому что оно более критично для производительности в обычном коде. (Подсказка: никто не использует абсолютно наивное пробное деление в реальной жизни для проверки нескольких простых чисел, если они вообще заботятся о производительности. Сито или что-то в этом роде.)
Ключом для упорядоченной map является size_t, а указатели больше в 64-битном коде, что делает каждый узел красно-черного дерева значительно больше, но это не узкое место.
Кстати, map<> это ужасный выбор здесь против двух массивов bool prime_low[Count], prime_high[Count]: один для низких Count элементов и один для высокого Count. У вас есть 2 смежных диапазона, ключ может быть неявным по положению. Или, по крайней мере, используйте хеш-таблицу std::unordered_map. Я чувствую, что заказанная версия должна была называться ordered_map и map = unordered_map, потому что вы часто видите код, использующий map не используя упорядоченность.
Вы даже можете использовать std::vector<bool> чтобы получить растровое изображение, используя 1/8 занимаемой площади кэша.
Существует "x32" ABI (32-битные указатели в длинном режиме), который обладает лучшим из двух миров для процессов, которым не требуется более 4 ГБ виртуального адресного пространства: маленькие указатели для более высокой плотности данных/меньшего объема кэша в указателе -тяжелые структуры данных, но преимущества современного соглашения о вызовах, больше регистров, базовый SSE2 и 64-битные целочисленные регистры для случаев, когда вам нужна 64-битная математика. Но, к сожалению, это не очень популярно. Это только немного быстрее, поэтому большинству людей не нужна третья версия каждой библиотеки.
В этом случае вы могли бы исправить источник, чтобы использовать unsigned int (или uint32_t если вы хотите быть переносимым на системы, где int только 16-битный). Или uint_least32_t чтобы избежать требования типа фиксированной ширины. Вы можете сделать это только для arg to IsPrime или для структуры данных. (Но если вы оптимизируете, ключ неявно определяется положением в массиве, а не явно.)
Вы могли бы даже сделать версию IsPrime с 64-битным циклом и 32-битным циклом, который выбирается в зависимости от размера ввода.
Извлеченный ответ из отредактированного вопроса:
Это было вызвано сборкой 32-битных двоичных файлов в Windows, в отличие от 64-битных двоичных файлов в Linux, вот 64-разрядные числа для Windows
Visual studio 2013 Debug 64b
29.1985
Visual studio 2013 Release 64b
29.7469