Comments 144
Укажите также процессор и компилятор с опциями. Используйте тэг «pre».
Intel Core 2 Duo E8400 @3.00GHz Visual C++ 2015 Опции: /Ox sign: 2.87 vs 3.97 abs: 2.29 vs 2.33 mini: 3.46 vs 8.93 maxi: 3.45 vs 9.10 minu: 3.45 vs 9.46 maxu: 3.45 vs 9.81
Intel(R) Core(TM) i5-3450 CPU @ 3.10GHz
g++ -std=gnu++11 BranchFreeTimeout.cpp
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
sign: 4.64 vs 3.84
abs: 2.88 vs 5.78
mini: 5.01 vs 14.40
maxi: 5.08 vs 14.55
minu: 5.07 vs 14.10
maxu: 5.09 vs 13.63
Intel Core i5-4690 CPU @ 3.50GHz gcc version 5.2.1 g++ -std=c++11 BranchFreeTimeout.cpp sign: 2.45 vs 2.69 abs: 2.44 vs 4.92 mini: 4.06 vs 11.19 maxi: 3.86 vs 11.04 minu: 4.15 vs 11.08 maxu: 4.07 vs 11.10 2147483646
Сделал в тексте апдейт программы: я совсем забыл, что нужно подавать на вход хаотичные данные, о чём мне справедливо указали ниже. Вот правильная версия программы.
Тех, кто уже принял участие, прошу перетестировать. Далее можно, кстати, обе программы тестировать — интересно же.
Intel® Core(TM) i7-2600 CPU @ 3.40GHz
sign: 4.49 vs 5.82
abs: 5.12 vs 6.15
mini: 6.30 vs 15.02
maxi: 5.92 vs 14.99
minu: 6.13 vs 14.88
maxu: 6.38 vs 15.30
Intel® Xeon® CPU E5-2620 0 @ 2.00GHz
sign: 7.08 vs 9.13
abs: 6.32 vs 9.53
mini: 9.59 vs 22.66
maxi: 9.25 vs 22.94
minu: 9.76 vs 22.87
maxu: 9.94 vs 23.15
clang++ -std=gnu++11 (clang version 3.4)
Intel® Core(TM) i7-2600 CPU @ 3.40GHz
sign: 3.42 vs 4.11
abs: 3.26 vs 4.90
mini: 5.55 vs 11.98
maxi: 6.27 vs 12.00
minu: 5.65 vs 12.46
maxu: 5.55 vs 12.38
Intel® Xeon® CPU E5-2620 0 @ 2.00GHz
sign: 5.64 vs 6.74
abs: 5.57 vs 8.05
mini: 8.39 vs 18.64
maxi: 9.48 vs 18.66
minu: 8.92 vs 19.50
maxu: 8.92 vs 19.33
Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz GCC 4.9.3-r3 Опции: -std=gnu++11 -O3 sign: 11.25 vs 2.25 abs: 11.93 vs 1.30 mini: 1.22 vs 2.59 maxi: 1.19 vs 2.71 minu: 13.64 vs 3.01 maxu: 1.21 vs 2.54
Visual C++ 2015
Опции: /Ox
Последовательно
sign: 2.87 vs 3.97 abs: 2.29 vs 2.33 mini: 3.46 vs 8.93 maxi: 3.45 vs 9.10 minu: 3.45 vs 9.46 maxu: 3.45 vs 9.81
Хаотично
sign: 13.02 vs 1.26 abs: 12.01 vs 0.81 mini: 1.89 vs 5.97 maxi: 1.93 vs 6.31 minu: 1.89 vs 6.44 maxu: 1.92 vs 6.70
Intel® Core™ i7-6700K CPU @ 4.00GHz GCC 5.2.1 Опции: -O3 -std=gnu++11 Старая версия: sign: 4.31 vs 2.76 abs: 2.07 vs 2.22 mini: 2.07 vs 4.66 maxi: 2.08 vs 4.23 minu: 2.08 vs 4.19 maxu: 2.14 vs 4.12 Новая версия: sign: 9.87 vs 0.72 abs: 9.57 vs 0.39 mini: 0.49 vs 0.83 maxi: 0.48 vs 0.82 minu: 10.20 vs 0.74 maxu: 0.49 vs 0.91
x86_64 Intel(R) Core(TM) i7 CPU X 980 @ 3.33GHz
g++-5.3.0 test.cpp -std=c++11 -O3 -pipe -march=native
sign: 11.36 vs 3.64
abs: 10.53 vs 0.91
mini: 1.25 vs 2.83
maxi: 1.19 vs 2.87
minu: 12.99 vs 3.37
maxu: 1.19 vs 2.77
2147483646
gcc version 4.9.2 (Raspbian 4.9.2-10)
options: -std=gnu++11
BranchFreeTimeout.cpp
sign: 66.21 vs 89.49
abs: 62.63 vs 78.74
mini: 71.58 vs 125.39
maxi: 71.58 vs 125.32
minu: 68.00 vs 128.90
maxu: 68.00 vs 128.90
2147483646
BranchFreeTimeoutNew.cpp
sign: 85.91 vs 93.07
abs: 81.43 vs 82.33
mini: 91.29 vs 128.90
maxi: 91.29 vs 128.90
minu: 87.70 vs 132.48
maxu: 87.70 vs 132.49
2147483646
Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz gcc version 4.9.2 (Raspbian 4.9.2-10) options: -std=gnu++11 -O3 BranchFreeTimeout.cpp sign: 7.11 vs 7.11 abs: 7.11 vs 3.52 mini: 7.11 vs 10.69 maxi: 3.52 vs 7.11 minu: 3.52 vs 7.11 maxu: 7.11 vs 7.11 2147483646 BranchFreeTimeoutNew.cpp sign: 22.01 vs 10.74 abs: 18.80 vs 10.73 mini: 10.74 vs 17.93 maxi: 10.74 vs 14.33 minu: 24.63 vs 7.16 maxu: 10.74 vs 7.16 2147483646
model name: Intel® Core(TM) i7-4810MQ CPU @ 2.80GHz
опции везде -std=c++11 -O3 -lstdc++
botanic@botfang:~/source/other/fastest_algorithm$ clang -v
Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)
…
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: -0.00 vs -0.00
abs: -0.00 vs -0.00
mini: -0.00 vs -0.00
maxi: -0.00 vs -0.00
minu: -0.00 vs -0.00
maxu: -0.00 vs -0.00
2147483648
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
sign: 9.63 vs 0.69
abs: 0.50 vs 0.25
mini: 1.03 vs 2.10
maxi: 0.98 vs 2.27
minu: 1.14 vs 2.16
maxu: 0.87 vs 2.25
2147483646
botanic@botfang:~/source/other/fastest_algorithm$ gcc -v
…
gcc version 4.9.2 (Debian 4.9.2-10)
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: 3.61 vs 1.90
abs: 1.16 vs 1.23
mini: 1.64 vs 2.91
maxi: 1.64 vs 2.32
minu: 1.86 vs 1.14
maxu: 1.62 vs 1.94
2147483646
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
sign: 9.85 vs 0.72
abs: 9.77 vs 0.37
mini: 0.60 vs 0.98
maxi: 0.60 vs 0.99
minu: 11.09 vs 1.02
maxu: 0.62 vs 1.03
2147483646
вне программы кланг с -O1 (-O2 тоже был неверно понят):
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: 7.38 vs 5.86
abs: 4.74 vs 5.82
mini: 5.83 vs 7.06
maxi: 5.84 vs 6.41
minu: 5.82 vs 8.18
maxu: 5.89 vs 6.99
2147483646
Windows 7 32
g++ -std=c++11
sign: 6.18 vs 8.08
abs: 7.43 vs 12.77
mini: 11.19 vs 26.56
maxi: 11.30 vs 26.67
minu: 13.91 vs 23.85
maxu: 13.91 vs 24.64
Компилятор: GCC 5.3.0;
Командная строка:
g++ -o3 -std=gnu++11
.Линейно:
sign: 11.07 vs 12.50 abs: 12.29 vs 18.13 mini: 19.70 vs 38.46 maxi: 19.57 vs 39.13 minu: 19.79 vs 33.52 maxu: 19.21 vs 33.88
Хаотично:
sign: 15.62 vs 5.06 abs: 13.80 vs 2.50 mini: 4.13 vs 5.95 maxi: 3.89 vs 6.12 minu: 17.45 vs 7.50 maxu: 3.89 vs 6.50
Intel(R) Core(TM) i5-2410M CPU @2.30GHz:
Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
Full optimization (-O3)
BranchFreeTimeoutNew.exe
sign: 14.49 vs 2.41
abs: 13.55 vs 1.49
mini: 2.05 vs 5.99
maxi: 2.07 vs 9.88
minu: 2.43 vs 6.46
maxu: 2.06 vs 10.52
BranchFreeTimeout.exe
sign: 3.28 vs 3.66
abs: 2.36 vs 1.58
mini: 3.04 vs 7.53
maxi: 3.16 vs 10.84
minu: 3.53 vs 7.81
maxu: 3.05 vs 10.65
Visual Studio 2015 (v140):
Full Optimization (/Ox)
BranchFreeTimeoutNew.exe
sign: 15.64 vs 2.45
abs: 12.61 vs 1.49
mini: 2.09 vs 6.14
maxi: 2.13 vs 5.88
minu: 2.41 vs 6.34
maxu: 2.07 vs 6.48
BranchFreeTimeout.exe
sign: 3.08 vs 3.75
abs: 1.51 vs 1.50
mini: 2.97 vs 7.30
maxi: 2.96 vs 7.34
minu: 3.52 vs 7.83
maxu: 2.97 vs 8.02
То же самое для чуть более нового интела:
Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz:
Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
Full optimization (-O3)
BranchFreeTimeoutNew.exe
sign: 17.58 vs 0.61
abs: 14.51 vs 0.24
mini: 0.41 vs 2.61
maxi: 0.35 vs 9.28
minu: 0.69 vs 2.96
maxu: 0.44 vs 8.83
BranchFreeTimeout.exe
sign: 2.94 vs 2.25
abs: 1.46 vs 1.01
mini: 1.66 vs 5.06
maxi: 2.48 vs 9.21
minu: 2.33 vs 6.16
maxu: 1.75 vs 9.43
Visual Studio 2015 (v140):
Full Optimization (/Ox)
BranchFreeTimeoutNew.exe
sign: 15.54 vs 0.70
abs: 13.58 vs 0.17
mini: 0.37 vs 2.52
maxi: 0.37 vs 3.25
minu: 0.62 vs 5.21
maxu: 0.51 vs 4.88
BranchFreeTimeout.exe
sign: 3.72 vs 1.92
abs: 0.96 vs 0.86
mini: 1.65 vs 5.05
maxi: 1.49 vs 4.84
minu: 1.91 vs 6.15
maxu: 1.50 vs 5.66
g++ -std=gnu++11 BranchFreeTimeoutNew.cpp
sign: 23.61 vs 1.75
abs: 22.11 vs 3.52
mini: 24.28 vs 10.84
maxi: 24.51 vs 10.83
minu: 23.90 vs 10.87
maxu: 23.80 vs 10.79
2147483646
AMD Phenom II P820 @1.80GHz Visual C++ 2015, /Ox Последовательная версия: sign: 4.81 vs 5.14 abs: 3.61 vs 2.40 mini: 2.40 vs 12.01 maxi: 2.40 vs 12.00 minu: 2.40 vs 12.14 maxu: 2.53 vs 12.73 Хаотическая версия: sign: 20.19 vs -0.00 abs: 18.07 vs 0.00 mini: 0.00 vs 9.60 maxi: -0.00 vs 12.01 minu: 0.00 vs 12.01 maxu: 0.04 vs 12.01 g++ 5.2.0, -std=c++11 -O3 Последовательная версия: sign: 9.72 vs 9.59 abs: 7.20 vs 7.20 mini: 7.20 vs 14.50 maxi: 7.19 vs 9.88 minu: 7.20 vs 7.20 maxu: 7.20 vs 9.59 Хаотическая версия: sign: 17.34 vs 2.56 abs: 16.28 vs 0.02 mini: -0.00 vs 0.00 maxi: 0.00 vs 3.61 minu: 20.99 vs 8.91 maxu: -0.00 vs 3.61
Но, надо отметить, определение empty в последовательной версии некорректно: что gcc, что clang успешно сворачивают цикл с empty в константу. gcc, кстати, в неправильную константу: https://godbolt.org/g/wibi2q.
Visual C++ 2015
Опции: /Ox /arch:SSE2
Release Win32:
sign: 18.47 vs 4.68
abs: 15.53 vs 1.47
mini: 2.96 vs 8.32
maxi: 2.99 vs 7.92
minu: 3.06 vs 8.35
maxu: 2.94 vs 8.41
2147483646
Release x64:
sign: 18.56 vs 4.71
abs: 15.83 vs 1.68
mini: 3.08 vs 7.81
maxi: 3.02 vs 7.78
minu: 3.03 vs 8.32
maxu: 3.31 vs 7.61
2147483646
gcc version 4.8.4
g++ -std=c++11 -O2 BranchFreeTimeoutNew.cpp
sign: 11.89 vs 2.16
abs: 12.05 vs 0.00
mini: -0.05 vs 2.15
maxi: -0.08 vs 1.66
minu: 12.77 vs 2.23
maxu: 0.00 vs 1.74
2147483646
g++ -std=c++11 BranchFreeTimeoutNew.cpp
sign: 27.91 vs 2.95
abs: 28.03 vs 4.16
mini: 32.46 vs 12.13
maxi: 32.33 vs 12.04
minu: 31.42 vs 12.93
maxu: 30.78 vs 12.90
2147483646
Intel® Core(TM) i7-4790 CPU @ 3.60GHz
gcc version 5.3.0 (GCC)
-std=c++11 -O3 -march=native
последовательно:
sign: 4.40 vs 2.87 abs: 2.16 vs 2.24 mini: 2.22 vs 4.85 maxi: 2.22 vs 4.43 minu: 2.22 vs 3.78 maxu: 2.58 vs 3.93
хаотично:
sign: 9.70 vs 0.62 abs: 8.92 vs 0.27 mini: 0.46 vs 0.76 maxi: 0.46 vs 0.73 minu: 9.52 vs 0.61 maxu: 0.47 vs 0.82
Исходный вариант (return a>b ? b:a;
):
minu: 9.52 vs 0.61
cmpl %eax, %r13d
ja .L18
addl %r13d, %r12d
Модифицированный вариант (return b>a ? a:b;
):
minu: 0.78 vs 0.64
cmpl %r13d, %eax
cmova %r13d, %eax
addl %eax, %r12d
Причуда компилятора (может если %eax
является операндом не с той стороны, то шаблон для генерации cmov
не срабатывает; хотя скорее тут что-то посложнее).
Попробуйте запустить ping 127.0.0.1 или адрес другого компьютера в локальной сети и посмотрите время ответа. Если получите отрицательное, это баг процессора.
gcc (GCC) 5.3.0
Опции: -std=c++11 -O3 -DNDEBUG
Последовательно
sign: 4.64 vs 3.02
abs: 2.27 vs 2.35
mini: 2.34 vs 5.10
maxi: 2.34 vs 4.64
minu: 2.33 vs 4.54
maxu: 2.72 vs 4.47
Хаотично
sign: 10.26 vs 0.68
abs: 9.34 vs 0.33
mini: 0.55 vs 0.88
maxi: 0.55 vs 0.85
minu: 10.08 vs 0.72
maxu: 0.55 vs 0.93
Новая версия
Intel Core i7 5500U @ 2.4GHz
mingw-w64 x86_64-5.3.0-posix-seh-rt_v4-rev0
Без оптимизаций:
sign: 30.69 vs 2.04 2147483646 abs: 30.14 vs 5.40 mini: 29.88 vs 13.06 maxi: 30.49 vs 13.51 minu: 29.89 vs 14.17 maxu: 30.21 vs 14.58
С оптимизациями (-fno-exceptions -fno-rtti -std=c++14 -O3 -fstrict-aliasing -flto -fomit-frame-pointer -march=native -floop-interchange -ftree-loop-distribution -floop-strip-mine -floop-block -ftree-vectorize):
sign: 13.38 vs 1.40 abs: 14.61 vs 0.50 2147483646 mini: 0.84 vs 1.44 maxi: 1.14 vs 1.47 minu: 15.34 vs 1.79 maxu: 0.84 vs 1.80
А если включить еще и -ffast-math -funroll-loops, то получается фигня
2147483646 sign: 14.54 vs -0.11 abs: 12.93 vs -0.44 mini: -0.39 vs 0.21 maxi: -0.36 vs 0.53 minu: 13.88 vs 0.61 maxu: -0.10 vs 0.56
В общем, все эти блоки внутри процессора чуть ли не умнее, чем компиляторы, а они точно умнее, большинство программистов. Лезть в дебри таких оптимизаций стоит только если явно есть хотспот.
Там как раз игра может стоить свеч
Ха, неплохой каламбур получился… Именно «игра» — в основном такие оптимизации нужны разве что для геймдева.
Для примера: rextester.com/PDBX5718. Я оставил только sign. Случайностью входа управляет макрос RANDOM.
Данный вопрос хорошо освещен на StackOverflow: stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
Исправить ситуацию можно проще: после строки 28 добавить строку
a = 17*a+1; \
Данные будут идти хаотично. Да, разница будет.
Данный момент я знал и в точности так делал в статье про подсчёт битов, но почему-то сейчас он вылетел из головы совсем. Спасибо.
i32 d = a - b;
return a - (d&(~(d ^ ((a^b)&(d^a))) >> SHIFT));
С его 8 операциями будет медленей чем один простой условный переход.
Я использовал такой генератор:
inline unsigned int fastrand() {
return g_seed = (214013 * g_seed + 2531011);
}
Табличка:
Intel Core i7-3632QM @2.20GHz
Visual C++ 2015
Опции: /Ox
sign: 19.09 vs 5.79
abs: 16.64 vs 4.72
mini: 11.05 vs 12.95
maxi: 11.06 vs 13.18
minu: 10.97 vs 13.75
maxu: 11.07 vs 13.62
Apple LLVM version 7.3.0 (clang-703.0.29)
Опции: -std=gnu++11
Старая версия программы:
sign: 2.78 vs 3.21
abs: 3.79 vs 5.34
mini: 6.04 vs 14.08
maxi: 6.16 vs 13.99
minu: 6.26 vs 13.38
maxu: 5.87 vs 13.40
Новая версия программы:
sign: 33.67 vs 3.23
abs: 30.61 vs 3.75
mini: 31.84 vs 15.64
maxi: 32.54 vs 13.54
minu: 33.01 vs 13.91
maxu: 33.41 vs 14.28
sign: 13.71 vs 1.68
abs: 12.81 vs 0.29
mini: 1.11 vs 4.45
maxi: 1.06 vs 3.59
minu: 1.57 vs 4.16
maxu: 1.07 vs 4.28
2147483646
А теперь, внимание, снимем немного позора с min/max:
static i32 mini1(i32 x, i32 y) {
return y ^ ((x ^ y) & -(x < y));
}
static i32 maxi1(i32 x, i32 y) {
return x ^ ((x ^ y) & -(x < y));
}
результат:
sign: 13.67 vs 1.66
abs: 13.15 vs 0.41
mini: 1.09 vs 2.90
maxi: 1.08 vs 1.89
А > и < — просто бинарные операторы.
Любой программист, прочитавший хотя-бы книжку K&R об этом знает.
> в ряде случаев там будет линейный код
там во всех 100% случаев будет линейный код, на любых архитектурах, даже тех, которых пока нет, почитайте стандарт
Вообще, в погорячился про никогда. Например, на PIC micro этот оператор сгенерит бранч. Но там и операторы + и − тоже нагенерят бранчей мама не балуй.
Если программист видит оператор < или > и думает про бранч, то он, простите, дебил.
Что, операторов + − и * тоже будем бояться как огня?
Вы придумали себе мнимого врага — компараторы, и с ним фанатично боретесь. Смешно же
Все кто постит тут результаты — не забывайте включать оптимизации (-O3
), иначе ваши результаты полностью бесполезны!
До сих пор приходится это объяснять студентам, которые считают ветвление дорогой операцией, ломающей конвейер. При этом эти же студенты используют pow для возведения в квадрат и злоупотребляют делением.
А возведение в константную целочисленную степень, типа pow(x, 2), на современных компиляторах инлайнится в несколько умножений, поэтому ничего страшного в нем нет.
Остальные варианты — pow(x, 1), pow(x, 3), pow(x, 2.0f) — через медленные вызовы возведения в степень.
В C# и того хуже: там всегда вызывается pow (проверял по времени выполнения, т.к. ассемблерный код при подключении отладчика становится другим).
Linux 3.19.0-56-generic x86_64 GNU/Linux
Ubuntu 15.10
gcc 5.2.1
g++ -O3 -std=c++14
Old:
sign: 4.84 vs 5.40
abs: 2.32 vs 2.44
mini: 3.17 vs 5.83
maxi: 3.07 vs 5.40
minu: 2.98 vs 5.40
maxu: 3.55 vs 5.30
New:
sign: 9.92 vs 3.03
abs: 9.56 vs 0.17
mini: 1.18 vs 1.09
maxi: 1.18 vs 1.38
minu: 10.31 vs 1.66
maxu: 1.28 vs 1.45
g++ -std=c++14
Old:
sign: 2.45 vs 2.28
abs: 1.43 vs 3.94
mini: 3.22 vs 11.44
maxi: 3.23 vs 11.20
minu: 3.26 vs 11.25
maxu: 3.36 vs 11.24
New:
sign: 21.10 vs 0.76
abs: 20.00 vs 2.12
mini: 22.27 vs 9.19
maxi: 22.19 vs 9.33
minu: 22.75 vs 9.38
maxu: 22.82 vs 9.46
P.S.: Мне пришлось заменить `chrono::duration_cast ` на `chrono::duration_cast `, чтобы получать неотрицательные значения времени
PS Для предотвращения оптимизации циклов, нужно использовать volatile. Так же советую посмотреть это видео про микробенчмарки: CppCon 2015: Chandler Carruth «Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!»
volatile не вариант, он может в некоторых компиляторах заставить переменную оказаться в памяти и не применять к ней оптимизаций вообще, что порождает некоторые косвенные эффекты, которые нам не нужны.
Вот представьте: мне нужна программа, которую любой пользователь может скомпилировать и запустить у себя, она выдаст время работы функций и всё. Не нужно, чтобы пользователь устанавливал бы себе дополнительные пакеты или делал какие-то дополнительные действия.
Далее, если говорить о честном тестировании функций, то тут вообще беда — даже хаотичное тестирование в цикле не сильно полезно (в малых циклах процессор может кэшировать сразу уже раскодированные команды при первом проходе, не раскодируя их затем при остальных), так как в реальных условиях, особенно когда нужная нам функция окружена некими другими командами, всё может быть совершенно иначе. Я ищу разные варианты решения этой проблемы, но пока не нахожу. Пока прихожу к выводу, что оптимизация программ в современных процессорах — это IT-аналог гадания на кофейной гуще. Хоть что делай — мы не знаем, что с этим сделает процессор, особенно если учесть, что ряд команд он преобразует во внутренние RISC команды которые (кстати) могут оказаться с ветвлениями (хотя исходные команды были без них). И вот об этих тонкостях работы микрокоманд хотелось бы узнавать из подобных видео. О том, насколько вообще честно мы можем измерить время работы функции, чтобы это было близко к реальным условиям.
Kubuntu 15.10 x64
i7-4700MQ CPU @ 2.40GHz
gcc 5.2.1
# g++ -std=c++11 BranchFreeTimeoutNew.cpp -o test.elf
# ./test.elf
sign: 24.26 vs 2.54
abs: 24.49 vs 4.54
mini: 26.85 vs 12.34
maxi: 26.27 vs 12.45
minu: 32.05 vs 12.84
maxu: 31.15 vs 14.50
2147483646
# g++ -std=c++14 -O3 BranchFreeTimeoutNew.cpp -o test.elf
# ./test.elf
sign: 12.25 vs 1.09
abs: 11.18 vs 0.58
mini: 0.86 vs 1.21
maxi: 0.85 vs 1.11
minu: 11.87 vs 0.95
maxu: 0.89 vs 1.20
2147483646
И ещё, для всех, если ещё не знаете — есть великолепный сервис gcc.godbolt.org, который позволяет быстро посмотреть на ассемлерный кот сгененированный разными компиляторами. Поддерживаются GCC, Clang и ICC разных версий и для разных архитектур.
mini0(int, int):
cmpl %esi, %edi
movl %esi, %eax
cmovle %edi, %eax
ret
maxi0(int, int):
cmpl %esi, %edi
movl %esi, %eax
cmovge %edi, %eax
ret
mini1(int, int):
movl %edi, %eax
movl %edi, %edx
subl %esi, %eax
xorl %edi, %esi
xorl %eax, %edx
andl %edx, %esi
xorl %eax, %esi
notl %esi
sarl $31, %esi
andl %eax, %esi
movl %edi, %eax
subl %esi, %eax
ret
maxi1(int, int):
movl %edi, %edx
movl %edi, %eax
subl %esi, %edx
xorl %esi, %eax
xorl %edx, %edi
andl %edi, %eax
xorl %edx, %eax
notl %eax
sarl $31, %eax
andl %edx, %eax
addl %esi, %eax
ret
Видно, что GCC сгенерировал cmov интсрукции, и в результате варинт с if не содержит условных переходов.
Всё сводится к обычному The Third Rule of Code Optimization: Profile first
Есть функция f, а есть функция g. Есть цикл, внутрь которого мы встраиваем эти функции. С функцией f получаем время A, с функцией g получаем время B. Есть ещё время C, когда цикл почти пустой (там только генерация данных). Я вычисляю (A-C) и (B-C), называя это практически чистым временем работы функции. Я называют это этим словом, то есть даю название этим значениям (Вы можете называть их «грязным временем», суть это не поменяет). Эти значения разные, они показывают то, насколько одна функция быстрее или медленнее другой (можно даже не вычитать C, если угодно, но я хочу вычитать).
Вы понимаете? Я получаю два разных числа и на основе их соотношения делаю приблизительный вывод о скорости работы функций. Этот вывод коррелирует с реальностью. Я не говорю, что данные числа отражают реальность, я говорю, что если в этом эксперименте одна функция сильно быстрее другой, то в реальности будет ТО ЖЕ САМОЕ. Это понятно? Если нет, то что именно не так?
Внимательно слушаю ответ на мой вопрос ниже.
Там есть предсказание. Читайте документацию. Есть специальные таблицы, которые сохраняют историю переходов в зависимости от адреса, и на основе истории делают предсказание.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.
Вот цикл, который выполняется 20 секунд:
u32 i = 0, s = 0;
do {
i = 19993*i + 1;
s += sign0 ((i32)i);
} while (i!=0);
Вот цикл, который выполняется 10 секунд:
u32 i = 0, s = 0;
do {
i = 11*i + 1;
s += sign0 ((i32)i);
} while (i!=0);
(Функции в цикле одинаковые — которые с IF из статьи).
Вопрос такой: почему время работы разное, если принять во внимание Ваше утверждение о том, что ветвление работает 0 тактов? Мой компилятор выдаёт абсолютно идентичные листинги программ, разница только в константе, которая кладётся в регистр. В первом случае 19993, во втором — 11.
По поводу эксперимента… Вы продолжаете заниматься приписыванием мне какой-то своей модели поведения. У меня есть цели и задачи эксперимента (а Вы сказали, что нет), я знаю, чего я хочу добиться, но я не обязан об этом сообщать. Если Вы не понимаете моих целей, то это НЕ значит, что моя методика обязана совпадать с Вашим представлением о таковой. Верно?
Далее, по поводу ветвления цикла. Мне не нужно учитывать предсказание выхода из него, оно не влияет на то, что мне нужно. Подставляя разные функции в программу, предсказание выхода из цикла я существенно не меняю.
Я внимательно слушаю Ваш ответ на простой вопрос.
К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
Можно ли узнать, как размер константы связан со скоростью вычисления? Константы какого размера будут давать одинаковое время умножения, если второй операнд всегда 32 бита?
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.
http://www.agner.org/optimize/instruction_tables.pdf
В современных процессорах операция умножения выполняется за константное количество тактов. А вот время выполнения деления пока что довольно долгое и зависит от значений операндов.
Классический вариант реализуется несложной схемой из условий:
Вот такие штуки превращаются
sign_t sign0 (i32 a) {
if (a>0) return +1;
if (a<0) return -1;
return 0;
}
В вот такие штуки:
sign_t sign1 (i32 a) {
return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
}
Intel(R) Core(TM) i3-3120M CPU @ 2.50GHz
Ubuntu 16.10 x64
GCC 5.3.1
Linux xx 4.4.0-18-generic #34-Ubuntu SMP Wed Apr 6 14:01:02 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
Линейно:
abs: 4.52 vs 8.28
mini: 7.12 vs 19.71
maxi: 7.28 vs 19.04
minu: 7.12 vs 18.99
maxu: 7.12 vs 18.93
2147483646
abs: 1.74 vs 2.69
mini: 3.02 vs 6.20
maxi: 3.02 vs 6.34
minu: 3.04 vs 6.94
maxu: 3.77 vs 5.98
4294967294
abs: 3.52 vs 3.60
mini: 4.52 vs 8.93
maxi: 4.54 vs 8.19
minu: 4.51 vs 8.02
maxu: 5.25 vs 8.22
4294967294
abs: 3.47 vs 3.52
mini: 4.58 vs 9.00
maxi: 4.53 vs 8.17
minu: 4.52 vs 7.95
maxu: 5.30 vs 8.01
4294967294
abs: 3.50 vs 3.59
mini: 4.02 vs 5.30
maxi: 4.09 vs 5.32
minu: 4.58 vs 3.57
maxu: 4.05 vs 5.31
4294967294
Хаотично:
abs: 32.11 vs 5.66
mini: 35.58 vs 16.71
maxi: 36.27 vs 16.96
minu: 37.68 vs 18.20
maxu: 37.08 vs 18.38
2147483646
abs: 0.67 vs 0.31
mini: 1.79 vs 1.99
maxi: 1.80 vs 2.68
minu: 1.82 vs 2.23
maxu: 1.81 vs 2.21
2147483646
abs: 14.38 vs 0.37
mini: 1.86 vs 1.72
maxi: 1.85 vs 2.15
minu: 15.45 vs 2.68
maxu: 1.92 vs 2.21
2147483646
abs: 14.41 vs 0.36
mini: 1.86 vs 1.73
maxi: 1.86 vs 2.16
minu: 15.57 vs 2.68
maxu: 1.95 vs 2.22
2147483646
abs: 0.40 vs 0.35
mini: 1.41 vs 1.49
maxi: 1.37 vs 2.14
minu: 1.71 vs 2.50
maxu: 1.47 vs 2.14
2147483646
Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max