Comments 144
Ответом к этому комментарию я прошу давать только таблицу времени работы.
Укажите также процессор и компилятор с опциями. Используйте тэг «pre».
Укажите также процессор и компилятор с опциями. Используйте тэг «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
UFO just landed and posted this here
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
UFO just landed and posted this here
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
Прошу простить мой косяк!
Сделал в тексте апдейт программы: я совсем забыл, что нужно подавать на вход хаотичные данные, о чём мне справедливо указали ниже. Вот правильная версия программы.
Тех, кто уже принял участие, прошу перетестировать. Далее можно, кстати, обе программы тестировать — интересно же.
Сделал в тексте апдейт программы: я совсем забыл, что нужно подавать на вход хаотичные данные, о чём мне справедливо указали ниже. Вот правильная версия программы.
Тех, кто уже принял участие, прошу перетестировать. Далее можно, кстати, обе программы тестировать — интересно же.
g++ -std=gnu++11 (gcc version 4.8.4)
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® 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
UFO just landed and posted this here
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
Intel Core 2 Duo E8400 @3.00GHz
Visual C++ 2015
Опции: /Ox
Последовательно
Хаотично
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
UFO just landed and posted this here
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
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
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
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
UFO just landed and posted this here
botanic@botfang:~$ cat /proc/cpuinfo | grep -wm1 Intel
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
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
Intel® Core(TM) i7 CPU 950 @3.07GHz 3.06GHz
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
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
Железо: Intel® Pentium® CPU N3530 @ 2.16GHz;
Компилятор: GCC 5.3.0;
Командная строка:
Линейно:
Хаотично:
Компилятор: 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
Intel® Core(TM) i3-4130 CPU @ 3.40GHz
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
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:
Но, надо отметить, определение empty в последовательной версии некорректно: что gcc, что clang успешно сворачивают цикл с empty в константу. gcc, кстати, в неправильную константу: https://godbolt.org/g/wibi2q.
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.
Intel Xeon E5620
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
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
AMD FX(tm)-4300 @ 3.80GHz
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
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
Intel Core i7 @ 2.2 GHz (Mac)
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
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
UFO just landed and posted this here
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
Никак не могу понять, почему у нескольких людей уже такие тормоза на minu с IF? Очень резко выбивается из общей картины.
Исходный вариант (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 не срабатывает; хотя скорее тут что-то посложнее).
UFO just landed and posted this here
Да, это входило в мои цели тоже — мне нужно было определить, будут ли у кого-то отрицательные значения, т. к. это свидетельствует о необходимости пересмотреть методологию расчётов.
Для AMD такое вроде нормально, по крайней мере раньше был такой баг, исправлялось настройкой таймера в системе.
Попробуйте запустить ping 127.0.0.1 или адрес другого компьютера в локальной сети и посмотрите время ответа. Если получите отрицательное, это баг процессора.
Попробуйте запустить ping 127.0.0.1 или адрес другого компьютера в локальной сети и посмотрите время ответа. Если получите отрицательное, это баг процессора.
Intel® Core(TM) i5-4670K CPU @ 3.40GHz
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
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
Я как-то раз был на лекции от Интел по поводу устройства современного процессора, в контексте оптимизаций кода. Так вот, в процессорах, выпущенных в последние несколько лет, суперскалярность ого-го, может выполнять до 100 инструкций вперёд. Спекулятивно, конечно, часть из них придётся выкинуть потом. А ещё есть предсказатель переходов, в который закапывают много сил и творят чёрную магию.
В общем, все эти блоки внутри процессора чуть ли не умнее, чем компиляторы, а они точно умнее, большинство программистов. Лезть в дебри таких оптимизаций стоит только если явно есть хотспот.
В общем, все эти блоки внутри процессора чуть ли не умнее, чем компиляторы, а они точно умнее, большинство программистов. Лезть в дебри таких оптимизаций стоит только если явно есть хотспот.
Вы правы, если говорить о настольных процессорах. Однако мне лично не очевидно, что будет на мобильных телефонах или видеокартах. Там как раз игра может стоить свеч. Суть эксперимента — проверить разные процессоры, у кого что есть. Ну и разные компиляторы между делом тоже.
Там как раз игра может стоить свеч
Ха, неплохой каламбур получился… Именно «игра» — в основном такие оптимизации нужны разве что для геймдева.
Да нет, я бы не сказал: ) В научных вычислениях, когда попадаются задачи, занимающие миллионы часов машинного времени, такое тоже может иметь смысл.
А зачем научные вычисления на мобильных телефонах делать… А, ой, и видеокартах. Не обратил внимание в начале, приношу свои извинения. Тогда да… На видеокартах, кстати, насколько я слышал, вообще все ветки исполняются одна за другой, а потом выбирается та, для которой условие прошло (подробнее, там когда про warp рассказывается говорится об этом).
Это мне известно, вот и интересно, насколько результат будет другим. Вообще по-хорошему для видеокарты нужно делать тесты иначе, запускать там 1 поток и делать по нему выводу — плохая идея. Нужна другая система тестирования, учитывающая её особенность.
Кстати, научные вычисления может быть полезно запускать на ARM процессорах с точки зрения экономии электроэнергии. Вместо 10 серверов x86 брать 100 на ARM, и это может оказаться дешевле/экономичнее с точки зрения электропотребления. Но это надо для каждой конкретной задачи рассматривать, экономии может и не получиться.
Простите, но вы измеряете производительность сферического коня. На производительность алгоритмов с ветвлением огромное влияние оказывает branch prediction. У вас созданы идеальные для него условия: первые N/2 вызовов идут по одному пути, остальные — по другому. Подайте на вход случайную последовательность, и получите совершенно другие результаты.
Для примера: rextester.com/PDBX5718. Я оставил только sign. Случайностью входа управляет макрос RANDOM.
Данный вопрос хорошо освещен на StackOverflow: stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
Для примера: rextester.com/PDBX5718. Я оставил только sign. Случайностью входа управляет макрос RANDOM.
Данный вопрос хорошо освещен на StackOverflow: stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
Спасибо за замечание. Если уж придираться полностью, то сам по себе способ — запускать подряд 232 раз функцию друг за другом — это тоже минус с точки зрения измерений, так как в реальных условиях всё может быть иначе.
Исправить ситуацию можно проще: после строки 28 добавить строку
Данные будут идти хаотично. Да, разница будет.
Исправить ситуацию можно проще: после строки 28 добавить строку
a = 17*a+1; \
Данные будут идти хаотично. Да, разница будет.
Я исправил свою ошибку (в статье теперь ссылка на вторую программу). Хорошо, что Вы быстро появились: )
Данный момент я знал и в точности так делал в статье про подсчёт битов, но почему-то сейчас он вылетел из головы совсем. Спасибо.
Данный момент я знал и в точности так делал в статье про подсчёт битов, но почему-то сейчас он вылетел из головы совсем. Спасибо.
Просто посмотрев на исходний код я могу сказать, что ваши mini, maxi, minu, maxu проиграют в скорости. Поскольку это
С его 8 операциями будет медленей чем один простой условный переход.
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
Я использовал такой генератор:
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
Да, об этом уже сказал meduzik, я исправил свою ошибку. Через некоторое время приведу статью в порядок (поправлю цифры). Новая версия программы в тексте статьи рядом со старой.
Intel® Core(TM) i5-4258U CPU @ 2.40GHz
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
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
похоже термины profiling и bottleneck после этого исследования можно отправлять в историю.
В статью были внесены изменения: добавлена вторая версия программы с хаотичной подачей данных. Такой подход несколько меняет ситуацию для sign и abs. Можно тестировать обе версии, потому что интересно теперь и то, в каких случаях разницы не будет.
Тест рандомной версии на i7-3667U (mscv 2013, дефолтные настройки release):
А теперь, внимание, снимем немного позора с min/max:
результат:
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
В последней версии min/max используются условия. Да, эта функция быстрее, и я даже об этом писал в одной своей статье, но по условиям эксперимента соревнуются именно функция с условием и функция БЕЗ него.
операторы < и > не генерят бранчинга, посмотрите генерируемый асм
Это я знаю, что в ряде случаев там будет линейный код. Но мы сейчас смотрим на код с позиции программиста, который не может знать, что сделает компилятор. Цель программиста — избавиться от условий, если он их видит (именно ТАК поступают те, кто фанатично избавляется от них — для них эта статья и написана). Более того, как я уже говорил, здесь просто пробный эксперимент, позже я, наверное, сделаю проверку всех существующих версий (они уже описаны в [4-7]).
Простите, но условия — это ключевое слово if и оператор ?, так же условия содержатся в конструкциях for и while.
А > и < — просто бинарные операторы.
Любой программист, прочитавший хотя-бы книжку K&R об этом знает.
А > и < — просто бинарные операторы.
Любой программист, прочитавший хотя-бы книжку K&R об этом знает.
P.S.:
> в ряде случаев там будет линейный код
там во всех 100% случаев будет линейный код, на любых архитектурах, даже тех, которых пока нет, почитайте стандарт
> в ряде случаев там будет линейный код
там во всех 100% случаев будет линейный код, на любых архитектурах, даже тех, которых пока нет, почитайте стандарт
Вы всё равно не о том спорите. В ряде случаев конструкции < и > могут порождать ветвление (работать как условие). Я говорю о ситуации, когда программист, видя подобную конструкцию, считает, что здесь именно условие (он не знает, что именно сгенерирует компилятор). Бинарный оператор — это не гарантия отсутствия условного перехода, об этом знает любой, кто хоть раз оптимизировал программы. Верно?
Нет, не верно, операторы < и > никогда не сгенерят бранч на x86, x86_64, IA64, ARM (включая thumb), ARM64.
Вообще, в погорячился про никогда. Например, на PIC micro этот оператор сгенерит бранч. Но там и операторы + и − тоже нагенерят бранчей мама не балуй.
Если программист видит оператор < или > и думает про бранч, то он, простите, дебил.
Вообще, в погорячился про никогда. Например, на PIC micro этот оператор сгенерит бранч. Но там и операторы + и − тоже нагенерят бранчей мама не балуй.
Если программист видит оператор < или > и думает про бранч, то он, простите, дебил.
Так лучше. И не надо считать подобных программистов дебилами, потому что в отличие от перечисленных архитектур, существует масса других.
Ещё дополню: когда говорите «никогда», то следует подчеркнуть, что речь идёт о типах данных вроде int, что не превышают по разрядности разрядность кода и для которых существуют нужные инструкции в процессоре. Например, если взять Ваш код для min/max и подставить туда long long, вы увидите в листинге несколько условных переходов, хотя только что говорили, что их НИКОГДА не будет для архитектуры x86. Поэтому предлагаю не тыкать друг друга носом в Стандарт и в опыт реальной работы, а смотреть на вещи как есть. Есть не мало случаев, когда «бинарный оператор» даёт условный переход, и это не только у дебилов, у нормальных программистов тоже бывает.
Если тип данных шире машинного, то и все ваши остальные конструкции будут усыпаны бранчами.
Что, операторов + − и * тоже будем бояться как огня?
Вы придумали себе мнимого врага — компараторы, и с ним фанатично боретесь. Смешно же
Что, операторов + − и * тоже будем бояться как огня?
Вы придумали себе мнимого врага — компараторы, и с ним фанатично боретесь. Смешно же
Во-первых, Вы не правы, в этом нетрудно убедиться самостоятельно, просто скомпилировав мою версию min и max для long long — там не будет ни одного условного перехода. И не должно быть. Во-вторых, при чём тут умножение, сложение и вычитание? И там тоже не будет условных переходов, если тип данных шире регистра, в этом тоже можно легко убедиться. В-третьих, Вы считаете, что я придумал себе врага и с ним борюсь. Ошибаетесь, я как раз ни с кем не борюсь, а всего лишь предложил пробный эксперимент, по результатам которого сделаю другой. Моё мнение по поводу компараторов вы вообще нигде здесь не увидите. Вот видите, Вы уже начинаете сыпать домыслами, когда выяснилось, что Вы подходите к дискуссии по вопросу не с того краю.
.
Кстати, раз уже тема поднялась, задам вопрос — немного оффтоп… Вот часто когда говорят про компилятор, называют его clang — видел в постах. Но clang — это ведь только frontend, а backend у него llvm. Или я ошибаюсь?.. Ещё раз приношу свои извинения за оффтоп.
Просто традиция. Если подходить формально, то не clang, а clang++(также как не gcc а g++), но в большинстве случаев clang построен на базе llvm-backend, так что это просто опускают. Фактически llvm объединяет группу компиляторов с общим backend, а для обозначения конкретного используется имя frontend. И, ко всему прочему, есть llvm-gcc…
Все кто постит тут результаты — не забывайте включать оптимизации (-O3), иначе ваши результаты полностью бесполезны!
С удовольствием бы проверил код интеловским компилятором, но вот незадача: MS в последнем апдейте VS его поломало. В любом случае, ветвление в современных процессорах — совсем не тот ужас, который был лет 25 назад.
До сих пор приходится это объяснять студентам, которые считают ветвление дорогой операцией, ломающей конвейер. При этом эти же студенты используют pow для возведения в квадрат и злоупотребляют делением.
До сих пор приходится это объяснять студентам, которые считают ветвление дорогой операцией, ломающей конвейер. При этом эти же студенты используют pow для возведения в квадрат и злоупотребляют делением.
Ветвление — это дорогая операция, ломающая конвейр в случае ошибки предсказания. Собственно, представленные в комментариях результаты тестов это наглядно демонстрируют. Однако, стоит понимать, что все современные процессоры имеют инструкцию условного копирования (cmove), поэтому в простых случаях использование оператора ?: к ветвлению не приводит.
А возведение в константную целочисленную степень, типа pow(x, 2), на современных компиляторах инлайнится в несколько умножений, поэтому ничего страшного в нем нет.
А возведение в константную целочисленную степень, типа pow(x, 2), на современных компиляторах инлайнится в несколько умножений, поэтому ничего страшного в нем нет.
Ага, вот прямо сейчас посмотрел: компилятором VS инлайнится только возведение в степень 2.
Остальные варианты — pow(x, 1), pow(x, 3), pow(x, 2.0f) — через медленные вызовы возведения в степень.
В C# и того хуже: там всегда вызывается pow (проверял по времени выполнения, т.к. ассемблерный код при подключении отладчика становится другим).
Остальные варианты — pow(x, 1), pow(x, 3), pow(x, 2.0f) — через медленные вызовы возведения в степень.
В C# и того хуже: там всегда вызывается pow (проверял по времени выполнения, т.к. ассемблерный код при подключении отладчика становится другим).
Intel® Core(TM) i5-3570 CPU @ 3.40GHz
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 `, чтобы получать неотрицательные значения времени
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 `, чтобы получать неотрицательные значения времени
В первую очередь нужно смотреть в дизассемблер. На x86 есть инструкция cmov (условное присваивание), предназначенная для избавления от простых ветвлений. Плюс есть SSE инструкции вычисляющие max/min для тех случаев, где цикл может быть векторизован. На ARM практически все инструкции могут быть условными, NEON (векторные инструкции на ARM) тоже поддерживает max и min. Так что у хорошего компилятора даже в коде с if'ами не будет полноценных ветвлений.
PS Для предотвращения оптимизации циклов, нужно использовать volatile. Так же советую посмотреть это видео про микробенчмарки: CppCon 2015: Chandler Carruth «Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!»
PS Для предотвращения оптимизации циклов, нужно использовать volatile. Так же советую посмотреть это видео про микробенчмарки: CppCon 2015: Chandler Carruth «Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!»
Я вообще-то написал про cmovXX, и сообщил, что компилятор может использовать данную конструкцию при необходимости. Да, у хорошего компилятора не будет ветвлений, но я веду речь про тех программистов, кто до сих пор этого не знает. С другой стороны, как выяснилось, при хаотичном потоке данных функции без ветвлений (sign, abs) на x86 чаще выигрывают.
volatile не вариант, он может в некоторых компиляторах заставить переменную оказаться в памяти и не применять к ней оптимизаций вообще, что порождает некоторые косвенные эффекты, которые нам не нужны.
volatile не вариант, он может в некоторых компиляторах заставить переменную оказаться в памяти и не применять к ней оптимизаций вообще, что порождает некоторые косвенные эффекты, которые нам не нужны.
Видео, конечно, полезное для многих, спасибо за ссылку, но касательно моих интересов там нет ничего.
Вот представьте: мне нужна программа, которую любой пользователь может скомпилировать и запустить у себя, она выдаст время работы функций и всё. Не нужно, чтобы пользователь устанавливал бы себе дополнительные пакеты или делал какие-то дополнительные действия.
Далее, если говорить о честном тестировании функций, то тут вообще беда — даже хаотичное тестирование в цикле не сильно полезно (в малых циклах процессор может кэшировать сразу уже раскодированные команды при первом проходе, не раскодируя их затем при остальных), так как в реальных условиях, особенно когда нужная нам функция окружена некими другими командами, всё может быть совершенно иначе. Я ищу разные варианты решения этой проблемы, но пока не нахожу. Пока прихожу к выводу, что оптимизация программ в современных процессорах — это IT-аналог гадания на кофейной гуще. Хоть что делай — мы не знаем, что с этим сделает процессор, особенно если учесть, что ряд команд он преобразует во внутренние RISC команды которые (кстати) могут оказаться с ветвлениями (хотя исходные команды были без них). И вот об этих тонкостях работы микрокоманд хотелось бы узнавать из подобных видео. О том, насколько вообще честно мы можем измерить время работы функции, чтобы это было близко к реальным условиям.
Вот представьте: мне нужна программа, которую любой пользователь может скомпилировать и запустить у себя, она выдаст время работы функций и всё. Не нужно, чтобы пользователь устанавливал бы себе дополнительные пакеты или делал какие-то дополнительные действия.
Далее, если говорить о честном тестировании функций, то тут вообще беда — даже хаотичное тестирование в цикле не сильно полезно (в малых циклах процессор может кэшировать сразу уже раскодированные команды при первом проходе, не раскодируя их затем при остальных), так как в реальных условиях, особенно когда нужная нам функция окружена некими другими командами, всё может быть совершенно иначе. Я ищу разные варианты решения этой проблемы, но пока не нахожу. Пока прихожу к выводу, что оптимизация программ в современных процессорах — это 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 не содержит условных переходов.
Со всеми этими оптимизациями ветвлений надо иметь ввиду, что во многих случаях эта оптимизация не бесплатна и процессор как-бы вычисляет обе веткие ветки одновременно, т.е. иногда вычислений становится больше. А когда вычислений больше надо учитывать наличие свободных исполнительных устройств, instruction latency, зависимости по данным и т.п.
Всё сводится к обычному The Third Rule of Code Optimization: Profile first
Всё сводится к обычному The Third Rule of Code Optimization: Profile first
Ветвление на современном процессоре стоит 0 тактов. В оптимистичном сценарии. Причём ничего не стоит не только сам if, но и условие внутри него. Это возможно благодаря так называемому предсказанию переходов. Но это название не более, чем маркетинговый трюк. Никакого предсказания в строгом смысле этого слова в процессоре не делается. Просто одновременно с вычислением условия на соседнем конвейере начинается выполнение той ветки, которая будет выполнена в случае true. Таким образом, к тому моменту, когда условие будет реально просчитано, первая ветка уже будет выполнена ровно на столько тактов, сколько потребовалось на вычисление условия. Конечно, если окажется, что условие равно false, то результаты выполнения первой ветки придётся отбросить и начать выполнять вторую ветку с самого начала. Но, во-первых, в компиляторе есть специальная оптимизация. Когда компилятор уверен в том, что наиболее вероятной веткой является else, он тупо переставляет ветки местами и инвертирует условие внутри if. Во-вторых, есть программист, который иногда лучше компилятора знает, какая ветка является более вероятной. Хороший программист всегда ставит наиболее вероятную ветку первой. На тот случай, если оптимизатор в компиляторе не сможет придти к однозначному выводу о необходимости оптимизации. В этом случае оптимизатор просто ничего не меняет и оставляет так, как было у программиста.
На самом деле это неправда. Если бы стоимость была 0 тактов, то не было бы разницы между последовательным и хаотичным потоком данных.
Эта разница объясняется иначе. Ветвление тут ни при чём. Это другая оптимизация, которая относится к циклам. Когда оптимизатор видит, что в коде есть цикл, в котором переменная монотонно возрастает/убывает, он переделывает код таким образом, чтобы эта переменная всегда была в регистре. И прямо в регистре он её инкрементит/декрементит, не перекладывая постоянно из регистра в память/кэш и обратно.
Нет, дело не в этом. Когда данные подаются хаотично (по формуле), переменная также находится в регистре, я проверял (там же она пересчитывается). Более того, я всегда вычитаю время работы самого вычисления этих данных, оставляя чистое время работы самой функции.
Не вижу, чтобы в программе измерялось время вычисления нового значения по формуле. Там измеряется только общее время работы всего цикла. Да это и невозможно сделать. На сам замер уйдёт несравнимо больше времени, чем на вычисление формулы.
Я измеряю время работы пустого цикла, который генерирует входные данные, затем полного цикла, который вместе с генерацией данных вызывает функцию. В ассемблерном листинге я убедился, что генерация происходит в регистре. Затем я вычитаю время работы полного цикла и пустого — получаю почти чисто время работы функции. А мы наблюдаем, что разница между одной и другой версией колоссальна. Версия с ветвлением может работать в несколько десятков раз медленнее, чем без ветвлений при хаотичной подаче, когда как при последовательной подаче версия с ветвлением выигрывает. Это можно объяснить только тем, что ветвление играет роль в вычислениях, особенно когда предсказатель не может надёжно предсказывать.
Это некорректно. Когда вы убираете из цикла вызов тестируемой функции, выполнение кода распределяется по конвейерам процессора совсем по-другому. Условие продолжения цикла (while (a != 0)) — это тоже ветвление. Процессор начинает выполнять следующую итерацию цикла ещё до того, как вычислит формулу, в надежде на то, что a действительно не будет равно нулю. В случае пустого цикла каждая следующая итерация цикла использует один дополнительный конвейер. Пока предыдущее значение a ещё не готово, на этом конвейере уже можно делать всё, что не зависит от a: 1) выбрать какие именно из блоков умножения и сложения будут использованы (и тех и других много); 2) загрузить в них обе константы (19993 и 1); 3) подготовить два временных места для размещения результатов умножения и сложения (внутренних для конвейера); 4) хрен знает что ещё (конвейер делает много такого, что не сразу приходит в голову). А когда в цикле есть ещё и функция, которая тоже зависит от a, то каждая следующая итерация задействует два дополнительных конвейера. Один делает всё то же самое, что и в случае пустого цикла, а второй параллельно начинает выполнять тестируемую функцию и делает всю возможную работу, которую можно сделать до того, как реально упрётся в отсутствие значения a, вычисленного на предыдущей итерации. Короче говоря, я хочу сказать, что замер на пустом цикле вообще никак не соотносится с замером на цикле с тестовой функцией.
Мы сейчас разговариваем не о способе измерения времени, а о том, что по Вашим словам стоимость ветвления равна нулю. Это не так и это нетрудно показать. Тот факт, что я не вполне корректно измеряю время работы функции мне и так хорошо известен. Но других вариантов, увы, не вижу. Этот способ хотя бы как-то коррелирует со сложностью функции.
Пока вам удалось показать это лишь с опорой на предположение о том, что будто бы вам удаётся измерять время работы функции в цикле отдельно от времени работы самой циклической конструкции. Это не так. Именно поэтому я и начал говорить о способе измерения времени. Я считаю, что измерить время работы настолько крохотных функций путём многократного их повторения в цикле на современном процессоре вообще невозможно. Тем более при использовании ключа -O3.
Да сколько можно… я не говорю нигде про отдельное измерение. Я сказал, что получаю почти чистое время работы функции в этих конкретных условиях. Это время не является точным, но оно коррелирует с реальностью. С тем, как функция будет вести себя в практических приложениях. Вы же, невнимательно прочитав мой ответ, считаете, что я делаю абсолютно точные вычисления и спорите с этой выдумкой. Не надо так.
Нигде не говорил подобного. Я отрицаю именно то, что вы на самом деле утверждаете. То, что замер не является точным, — понятно. Это само собой. Речь идёт о том, что он также не является ни чистым, ни почти чистым. Условия замера в случае «пустого» цикла и в случае цикла с функцией совершенно разные.
Попробую на пальцах объяснить.
Есть функция f, а есть функция g. Есть цикл, внутрь которого мы встраиваем эти функции. С функцией f получаем время A, с функцией g получаем время B. Есть ещё время C, когда цикл почти пустой (там только генерация данных). Я вычисляю (A-C) и (B-C), называя это практически чистым временем работы функции. Я называют это этим словом, то есть даю название этим значениям (Вы можете называть их «грязным временем», суть это не поменяет). Эти значения разные, они показывают то, насколько одна функция быстрее или медленнее другой (можно даже не вычитать C, если угодно, но я хочу вычитать).
Вы понимаете? Я получаю два разных числа и на основе их соотношения делаю приблизительный вывод о скорости работы функций. Этот вывод коррелирует с реальностью. Я не говорю, что данные числа отражают реальность, я говорю, что если в этом эксперименте одна функция сильно быстрее другой, то в реальности будет ТО ЖЕ САМОЕ. Это понятно? Если нет, то что именно не так?
Есть функция f, а есть функция g. Есть цикл, внутрь которого мы встраиваем эти функции. С функцией f получаем время A, с функцией g получаем время B. Есть ещё время C, когда цикл почти пустой (там только генерация данных). Я вычисляю (A-C) и (B-C), называя это практически чистым временем работы функции. Я называют это этим словом, то есть даю название этим значениям (Вы можете называть их «грязным временем», суть это не поменяет). Эти значения разные, они показывают то, насколько одна функция быстрее или медленнее другой (можно даже не вычитать C, если угодно, но я хочу вычитать).
Вы понимаете? Я получаю два разных числа и на основе их соотношения делаю приблизительный вывод о скорости работы функций. Этот вывод коррелирует с реальностью. Я не говорю, что данные числа отражают реальность, я говорю, что если в этом эксперименте одна функция сильно быстрее другой, то в реальности будет ТО ЖЕ САМОЕ. Это понятно? Если нет, то что именно не так?
Зачем вы всё это мне объясняете? Это всё понятно из текста программы. Проблема в другом. Не в том, что я не понимаю, что вы хотите измерить, а в том, что вы реально измеряете не то, что хотите. Понимаете? Мысленная модель вашего эксперимента не соответствует тому, как это на самом деле выполняется в процессоре с предсказанием условных переходов. В вашей модели сама циклическая конструкция никак не влияет на вызываемую внутри функцию. Вы просто вычитаете время, затраченное на цикл, из общего времени. В действительности же при выполнении в цикле таких простейших функций конструкция цикла оказывается неразделимо переплетена с самой функцией. Когда вы убираете из цикла вызов функции, процесс выполнения самой циклической конструкции меняется очень существенно. Проще говоря, вы не можете вычислить (А-С). Когда вы измеряете A, в него в качестве составляющей входит время, которое вы обозначаете как С. А когда вы пытаетесь измерить это С отдельно (чтобы вычесть его из A), у вас реально измеряется время, которое даже не С-штрих… это просто другое время — D… оно никак не связано с тем С, которое входит в А. Возможно, какая-то связь между C и D есть, но скорее всего даже разработчики процессоров не сразу скажут, какая именно и есть ли связь вообще.
Нет, Вы по-прежнему меня не понимаете, приписывая мне своё видение эксперимента. Будет ли Вам лучше, если я скажу, что мне нужны числа A и B? А зачем они нужны — я в тексте статьи не говорил. Число C я вычитаю для более удобного определения соотношения (считайте это погрешностью). По поводу наличия или отсутствия связи между этими величинами и реальностью я имею своё мнение, основанное на моём опыте. При этом заметьте, я не спорю, что эти числа никакого отношения к реальному времени работы функции не имеют, я утверждаю лишь, что есть чёткая корреляция.
А я, основываясь на своём опыте, считаю, что такая корреляция могла бы быть лишь в том случае, если бы в процессоре не было бы оптимизации ветвлений через предсказание переходов. При этом мой опыт больше и лучше вашего. Я занимаюсь программированием только на С++ более 15 лет. А до этого писал на чистом С и ассемблере. Так что вы совершенно напрасно придаёте такое значение своему опыту в нашем с вами разговоре. По сравнению с моим он незначителен (считайте его погрешностью).
Ну началось: ) Сейчас будем выяснять, кто круче по числу лет. Наверное, Вы из тех людей, кто путает количество и качество.
Внимательно слушаю ответ на мой вопрос ниже.
Внимательно слушаю ответ на мой вопрос ниже.
Выяснять ничего не будем. Понятно, что я круче и по числу лет и по качеству опыта. Но заметьте, не я начал делать упор на свой опыт, пытаясь что-то обосновать. Это вы начали. Я про опыт заговорил лишь для того, чтобы напомнить вам, что опыт есть не только у вас.
Вы не правы. Я сказал про свой опыт ТОЛЬКО для того чтобы показать, что в нём (в моём опыте) присутствует корреляция между моими сферическими в вакууме экспериментами и тем, как результаты опыта ложатся на реальные задачи. А Вы приняли это на свой счёт, будто бы я пытаюсь соревноваться. Нет, этого, увы, не будет: )
Возможно, я что-то неправильно понял. Мне показалось, что вы каким-то образом обосновываете свою правоту ссылкой на опыт. Это выглядело как заход с козырей. Естественно, я был вынужден ответить тоже козырем. Любой подобный разговор чем-то похож на преферанс, где отвечать нужно той же мастью. А из козырей у меня, к сожалению, есть только старшие карты — туз и король.
Нет, простите, если я, быть может, выбрал не тот оборот речи, однако когда я сказал «опыт», то это было (и мне показалось, я написал ясно), в контексте того, что мой опыт таких экспериментов даёт нужный результат в реальных расчётах. Обычно в научных, потому как оптимизацией бытовых программ я не занимаюсь. Это было сказано против Вашего тезиса о том, что будто бы мои эксперименты не имеют смысла. Хотя я-то знаю, что имеют.
На всякий случай, вынужден пояснить один философский момент из нашей жизни. В нашей жизни многие вещи определяются косвенно, так как напрямую их определить нельзя вообще никак. Так, например, учёные не могут разглядеть и замерить свойства квантовых частиц, но определяют их физику по косвенным признакам, в результате соударения их друг об друга. Получаемая физиками модель отвечает на ряд вопросов, важных для физиков. Далее, в реальных условиях человек не бегает по беговой дорожке в соответствующей одежде, однако если взять двух людей на беговой дорожке и двух людей, бегущих за троллейбусом, то и там, и там оба покажут качественно одинаковый результат (тот прибежит первым, кто лучше к этому подготовлен). В мире всё так, эксперимент есть эксперимент, и если я говорю, что мне нужны эти данные и я знаю, что с ними делать, значит на то у меня есть основания, диктуемые опытом. А кому кажется, что тут нет ВООБЩЕ никакой связи — ну значит это его мнение, пусть кажется дальше. Любой факт может иметь значение для того, кто в теме. Кто не в теме, тому это может ничего не говорить. Вот на этом можно и остановить разговор.
Он вас не слушает. Я хотел большой коммент написать про измерение сферического коня в вакууме. Но вы уже это разжевали так, что по-моему больше даже вопросов быть не может.
Ещё Вы неверно поняли смысл пустого цикла (посмотрите всё-таки программу и мой комментарий выше внимательнее). Пустым я назвал цикл, в котором есть вычисление потока данных. То есть формула там тоже присутствует.
Там есть предсказание. Читайте документацию. Есть специальные таблицы, которые сохраняют историю переходов в зависимости от адреса, и на основе истории делают предсказание.
Тогда измерять тем более бессмысленно. Чтобы измерения имели смысл, нужно знать логику работы с этими таблицами и учитывать её.
Смысл есть всегда. В данном случае мы пытаемся отыскать разницу по времени работы функций по отношению друг к другу. Наши измерения показывают эту разницу и в ней есть смысл. Или Вы хотите утверждать, что если, скажем, в наших экспериментах одна функция быстрее другой в 10 раз, то в реальных программах со случайным потоком данных может статься наоборот?
Нет, они показывают не эту разницу, а какие-то неслучайные числа, которые не имеют отношения к умозрительной модели вашего эксперимента.
Это ещё нужно доказать, что не имеют отношения. Подобные голословные заключения здесь мало полезны.
К сожалению, всё ровно наоборот. Традиционно доказывать нужно именно соответствие модели эксперименту. Не наоборот.
Ничего подобного, я же не приводил никакой модели и не называл целей эксперимента. Цель и модель приписали мне Вы, и с ней же спорите. Если я даже попрошу Вас назвать мою умозрительную модель — Вы не сможете этого сделать. Попробуйте, если не верите.
То, что вы не привели никакой модели эксперимента, — это не оправдание, а скорее отягчающее обстоятельство. Должны были привести, если считаете, что эта модель не следует однозначно из текста программы. Эксперимент, который не имеет никакой модели, не имеет и смысла.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.
Ответьте, пожалуйста, на простой вопрос.
Вот цикл, который выполняется 20 секунд:
Вот цикл, который выполняется 10 секунд:
(Функции в цикле одинаковые — которые с IF из статьи).
Вопрос такой: почему время работы разное, если принять во внимание Ваше утверждение о том, что ветвление работает 0 тактов? Мой компилятор выдаёт абсолютно идентичные листинги программ, разница только в константе, которая кладётся в регистр. В первом случае 19993, во втором — 11.
По поводу эксперимента… Вы продолжаете заниматься приписыванием мне какой-то своей модели поведения. У меня есть цели и задачи эксперимента (а Вы сказали, что нет), я знаю, чего я хочу добиться, но я не обязан об этом сообщать. Если Вы не понимаете моих целей, то это НЕ значит, что моя методика обязана совпадать с Вашим представлением о таковой. Верно?
Далее, по поводу ветвления цикла. Мне не нужно учитывать предсказание выхода из него, оно не влияет на то, что мне нужно. Подставляя разные функции в программу, предсказание выхода из цикла я существенно не меняю.
Я внимательно слушаю Ваш ответ на простой вопрос.
Вот цикл, который выполняется 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 не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
Обождите. Я никак в толк не возьму: что именно я не понимаю? Вы можете сформулировать конкретный тезис? Чётко и одним предложением.
Можно ли узнать, как размер константы связан со скоростью вычисления? Константы какого размера будут давать одинаковое время умножения, если второй операнд всегда 32 бита?
Можно ли узнать, как размер константы связан со скоростью вычисления? Константы какого размера будут давать одинаковое время умножения, если второй операнд всегда 32 бита?
Одним предложением это вряд ли можно сформулировать. Важен не размер константы, а количество значащих разрядов, а иногда и конкретное значение. Например, умножение на 11 можно сделать вообще без умножения. В десятичной системе это часто можно сделать в уме: добавить справа ноль, умножив таким образом на 10, и прибавить к результату операнд. Для двоичной системы тоже несложно придумать алгоритм без умножения: добавить к операнду три нуля, прибавить операнд с двумя добавленными нулями и вычесть операнд. Если я смог придумать такой алгоритм за 10 секунд, то разработчики процессора скорее всего тоже додумались до такой оптимизации за много лет работы и встроили её в блок, выполняющий умножение.
Я продолжил свой эксперимент: загнал в массив упорядоченный набор чисел и запустил цикл с функцией sign0 (которая с IF), получил почти 16 секунд. Затем взял массив из тех же, но неупорядоченых чисел, получил 20 секунд. Затем повторил эксперимент с функцией sing1 (без IF), время работы в обоих случаях одинаково (16,8 сек). Вывод: ветвление вносит дополнительные затраты на работу программы, когда предсказатель не может надёжно предсказывать, то есть ветвление — это не 0 тактов.
Но я и не говорил, что оно всегда 0 тактов. Мой первый коммент состоял не только из первого предложения. Фактически, уже со второго предложения начинается объяснение, почему иногда может быть не 0. Естественно, если вы будете специально запутывать предсказатель, то не 0 тактов будет чаще. Но в реальных программах входные данные, как правило, не запутаны. И значит стоимость ветвления в среднем близка к нулю. И обычно можно не беспокоиться о том, что у тебя в программе есть лишний IF, который можно было бы убрать, придумав какой-нибудь изощрённый алгоритм.
К сожалению, в моей реальности это не так, иначе я вряд ли бы занимался подобными экспериментами. В одних случаях ветвление работает быстрее, в других без него быстрее. На видеокартах так вообще часто приходится делать уйму работы, чтобы вместо одно IF была сотня строк, но зато более быстрых. В таком случае, я не понял суть вашей претензии. Из двух алгоритмов я выбираю тот, который на моих сферических в вакууме тестах работает быстрее — и этот выбор я делаю на разных компьютерах с помощью сообщества, которое эти тесты запускает.
Суть в том, что а) эксперимент здесь не нужен; б) эксперимент смоделирован неверно.
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
Так… ну вот, как я и говорил, Вы совершенно неверно понимаете мою мотивацию. Чтобы говорить о верности или неверности эксперимента, нужно знать мои цели. Вы их не знаете (а я их и не говорил). Далее, Вы серьезно думаете, что в какой-то программе sign, abs или минимум с максимумом будут узким местом, чтобы с ними так возиться? Вряд ли. Вообще эти функции — это последнее, что меня интересовало бы в сложной программе, где они как капля в море. Меня интересует в этом эксперименте другое, совсем другое… и я ещё даже не решил, писать статью с объяснением или нет.
Ну, на это я даже не знаю, что сказать. Эксперимент совершенно точно выглядит как эксперимент по исследованию ветвлений. Понятно, что на примере каких-то конкретных функций, и что сами эти функции не имеют значения. Но предметом исследование определённо является само ветвление и его влияние на тайминг. Если это на самом деле не так, и реальная цель вашего эксперимента состоит, например, в исследовании того, сколько человек поведутся на призыв и начнут запускать бессмысленный и некорректный бенчмарк на своих машинах, то тогда у меня нет возражений по существу. Если эксперимент был социальным, то он действительно удался.
Чушь несёте. Одна из косвенных целей — сравнить два алгоритма. В одном из них есть IF (в программе), в другом — нет. При этом меня совершенно не интересует, как именно будет работать (и будет ли он вообще после компиляции) условный переход. Теперь ясно? Суть: есть сферический в вакууме цикл проверки двух РАЗНЫХ (абсолютно разных) функций, мне нужно узнать время работы этих циклов минус время работы цикла, который я назвал пустым (даже если разность будет отрицательной). Зачем мне это нужно — этого я нигде не говорил. Далее, не нужно пытаться делать выводы только на основе того, как с Ваших позиций выглядит эксперимент. Очень может оказаться, что Вы многого не знаете, чтобы залезать в чужую голову и делать вид, что Вы там что-то понимаете. Я так и не понял, вашу претензию. Видимо, её нет, а Вы хотели просто что-то сказать, но не знали, что. Ещё раз: условные переходы в скомпилированном коде меня НЕ интересуют. Не интересует меня и то, как долго или быстро работает IF, где бы он ни был.
Ну, тогда просто согласимся на том, что обычно условный переход ничего не стоит и париться на счёт него не нужно.
А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.
А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.
Далее, если продолжить указывать Вам на логические ошибки, то можно это сделать со многих сторон. Вот одна из них: я сказал Вам, что меня интересует время работы моего цикла при вызове одной и другой функции. Вы же мне говорите, что я исследую работу IF, хотя эти два момента не связаны напрямую. Сколько уже можно приписывать мне СВОИ представления о том, что Я делаю, а не Вы?
Добро пожаловать в реальность! В будущем все люди, с которыми вы будете иметь дело, только тем и будут заниматься, что приписывать вам те мысли и цели, которые, как они думают, у вас есть. Телепатов, к сожалению, нет. Но это не мешает людям думать, что они точно знают мысли других. Вам придётся как-то научиться жить с этим. И не факт, что сможете. У многих гиков это не получается и со временем они начинают не любить окружающих за то, что их никто не понимает.
С чего Вы решили, что знаете, с какими людьми я буду иметь дело в будущем? Более того, класс людей, которые любят соваться в том, в чём не разобрались достаточно хорошо, очень велик и меня это не удивляет. Меня удивляет Ваша упорная настойчивость повторять мне одну и ту же мысль, которую я понял с первого раза и против которой чётко и ясно указал контраргумент, а затем повторил его 10 раз. Вот здесь в комментарии это последний раз. И то, я сделал одолжение, что так настойчиво объяснял свою позицию. Если и сейчас не понятно, то мне теперь это безразлично. Разговор окончен: )
Касательно операции умножения — есть такой документик:
http://www.agner.org/optimize/instruction_tables.pdf
В современных процессорах операция умножения выполняется за константное количество тактов. А вот время выполнения деления пока что довольно долгое и зависит от значений операндов.
http://www.agner.org/optimize/instruction_tables.pdf
В современных процессорах операция умножения выполняется за константное количество тактов. А вот время выполнения деления пока что довольно долгое и зависит от значений операндов.
Время работы этих циклов отличается ровно в 2 раза, потому что тело цикла с константой 19993 исполнится 4294967296 раз, а с константой 11 — 2147483648 раз.
Нужно понимать что вот под капотом глубоко где-то так (вариант 2) и будет, по крайней нормальный Math-compiler именно так и сделает, но это будет работать быстрее, потому что там решили общую задачу и написали 100.000 тестов. В принципе, поэтому либы и пишутся.
Классический вариант реализуется несложной схемой из условий:
Вот такие штуки превращаются
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);
}
Классический вариант реализуется несложной схемой из условий:
Вот такие штуки превращаются
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
Линейно:
g++ -std=gnu++11 -O0
sign: 6.23 vs 5.54
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: 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
g++ -std=gnu++11 -O1
sign: 3.55 vs 3.47
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: 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
g++ -std=gnu++11 -O2
sign: 5.47 vs 5.35
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.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
g++ -std=gnu++11 -O3
sign: 7.39 vs 5.23
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.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
g++ -std=gnu++11 -Os
sign: 5.75 vs 5.24
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: 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
Хаотично:
g++ -std=gnu++11 -O0
sign: 33.41 vs 3.77
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: 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
g++ -std=gnu++11 -O1
sign: 2.06 vs 2.03
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: 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
g++ -std=gnu++11 -O2
sign: 15.51 vs 2.05
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.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
g++ -std=gnu++11 -O3
sign: 15.17 vs 2.02
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: 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
g++ -std=gnu++11 -Os
sign: 15.55 vs 1.81
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
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 up to leave a comment.
Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max