Комментарии 7
Интересно, имеется ли этот эффект в Java, надо бы проверить.
При исполнении байт кода у JVM есть два сценария: 1. интерпретировать байт код; 2. компилировать байт код. В первом случае, как мне кажется, накладные расходы на интерпретацию будут слишком высоки и прироста в скорости работы заметить не получится. Во втором же случае происходит ровно тоже, что и в случае С++, поэтому ускорение должно наблюдаться.
Где-то я читал, что начиная с какой-то версии JVM всегда компилирует байт код. Мог не так понять. В любом случае, желательно код перед бенчмарками "прогреть", то есть выполнить многократный вызов функции с кодом, чтобы вызвать срабатывание механизма компиляции.
Еще, на сколько мне известно, JVM может обнаружить, что один и тот же код выполняется в цикле и оптимзировать это. Поэтому, возможно, придется как-то аккуратно запускать бенчмарк.
а при чем тут java не java? основная причина глобального торможения любой программы это зависимость вычислений по данным, будь это необходимость загружать их из памяти или ждать результаты предыдущих вычислений. можете посмотреть давний доклад "Сергей Куксенко — Quantum Performance Effects".
Тут интересней посмотреть асемблер с if-else логикой. С большой долей вероятности c2 компилятор наиболее вероятный брач (который он считает по своей метрике) поместит в if, а маловероятный в else, но надо проверять
Тут интереснее другое, по сути компилятор обязан
увидеть, что data / array size не меняются в цикле
т.к. переполнение невозможно (UB) догадаться преобразовать это в выполнение цикла один раз и умножение на количество выполнений цикла выше (100'000)
в идеальном сценарии, если бы компилятор знал инвариант функции sort, он должен был бы найти один раз число >= 128 и от него до конца складывать числа, т.е. преобразовать цикл
Понятно почему не происходит третьего - сложно работать с циклами, плюс никто не пишет оптимизации под плохой код (а тут он именно такой)
Но интересно, что первое он тоже не делает. Я вынес в функцию и сделал её pure - и это тоже не помогло, потому что он заинлайнил раньше чем понял в чём дело. Тогда я поставил noinline и действительно, только тогда он смог преобразовать убрав внешний цикл
foo(int*, int): # @foo(int*, int)
push rax
call sum_foo(int*, int)
imul rax, rax, 100000
pop rcx
ret
.LCPI1_0:
Тут интереснее другое, по сути компилятор обязан
Всё-таки, это — вторично, хотя и весьма полезно.
А первично — то, что умножает основной посыл статьи на 0.
Не буду расшифровывать в ассемблерном коде по вашей ссылке векторизованную часть цикла с MMX-инструкциями, которая обрабатывает за один проход цикла сразу 4 элемента, а возьму вместо этого концовку цикла с обычными инструкциями, которая обрабатывает последние 1-3 элемента, если размер массива не кратен 4:
xor edx, edx
...
.LBB1_8: # =>This Inner Loop Header: Depth=1
mov r8d, dword ptr [rdi + 4*rsi]
cmp r8d, 127
cmovle r8d, edx
add rax, r8
inc rsi
cmp rcx, rsi
jne .LBB1_8Видите условный переход после сравнения r8d со 127?
Вот и я не вижу.
Векторизованная часть кода ведёт себя аналогичным образом, но с помощью других инструкций и немного другого механизма, но результат — тот же, условный переход там в аналогичном месте также отсутствует.
Таким образом, вы доказали своим кодом, что основной посыл статьи умножен на 0: нет условного перехода — нет и эффекта от предсказателя перехода.
Справедливости ради следует заметить, что компилятор от Microsoft оптимизацию, на которую я намекаю, не выполняет.
Да, в Java такой эффект тоже есть.
Benchmark Mode Cnt Score Error Units
App.sorted thrpt 25 1979,922 ± 110,953 ops/s
App.unsorted thrpt 25 269,936 ± 9,185 ops/s
вот почитал и тут и на стек оверуоу и все равно не считают что "просто потому что бранч предиктор" это ответ на вопрос. что именно дает тут бранч предиктор? у нас что огромные ветви? нет. ну угодал он заходить или нет, но дальше эти данные надо сейчас же грузить из памяти чтобы произвести сложение. или процессор считает что ничего складывать не надо, хорошо, тут он прокрутит счётчик и чуть позже проверит что пришло из памяти. большой профит? вроде нет. в общем при условии что мы имеем дело с бранчем аж в одну инструкцию и эта самая инструкция все равно требует данных из условия как минимум в половине случаев (хотя автор и тут ошибся nextInt() % 256 это не заполнение массива рандомно от 0 до 256 равномерно, я посчитал, там 25 на 75 получается) приходим к мысли, что дело не только в бранч предикторе. и процессор ничего не читает из памяти, он работает с кэш линиями - грузит в них сразу часть массива - т.е. работа вашего теоретического конвейера принципиально расходится с реальным в 99% случаев при линейном чтении. в общем фокус тут явно сложнее чем просто "бранч предиктор", но ответа я не вижу ни тут, ни на SO. прогнал локальный тест на java по всем канонам микро бенчмарков - никакой разницы, только на огромных массивах она появляется.
на SO запускали perf:
26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches
и
65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches
я тут вижу 2 вещи 1) плавает частота, т.е. не выключен буст, плохо для теста 2) главное 1.55 insns per cycle - за один такт выполняется более одной инструкции, это значит что процессор выполняет параллельные операции сложения (никакого чуда тут нет, это и называется суперскалярность). так что тут комбинация фич, а не один бранч предиктор.
почему в java я не получаю разницы - не ясно, надо смотреть ассемблер, возможно jit выпиливает бранч сам
В общем тема не раскрыта ;)
Как, блуждая по Stack Overflow, можно набрести на Branch predictor