Блог*

#prog #rust хайлайты:

Переписали реализацию двоичного поиска. Эти изменения связаны с тем, что ветвление по результату сравнения в двоичном поиске плохо сочетаются с предсказателем ветвлений — они, за вычетом вырожденных случаев, плохо предсказываются, и потому приводят к снижению производительности из-за регулярных сбросов пайплайнов процессора. В данном PR количество непредсказываемых ветвлений снизили.

Именно, во-первых, для ветвления по результату сравнению используют специально добавленный для этого интринсик, который заставляет кодген использовать условные перемещения (cmov) вместо условных прыжков. Во-вторых, в теле цикла теперь нет раннего возврата в случае, если элемент считается искомым согласно предъявленному предикату. Да, это увеличивает число итераций, но взамен убирает ещё одно плохо предсказываемое ветвление и делает число итераций зависимым только от длины слайса, т. е. хорошо предсказываемым. В качестве бонуса LLVM теперь в состоянии полностью развернуть цикл для поиска по слайсам со статически известной длиной.

Бенчмарки консистентно в разных тестах и на разных процессорах подтверждают, что поиск ускорился.

GitHub

Rewrite binary search implementation by Amanieu · Pull Request #128254 · rust-lang/rust

This PR builds on top of #128250, which should be merged first.
This restores the original binary search implementation from #45333 which has the nice property of having a loop count that only depe...

🔥20👍4🥰1

www.tgoop.com/dereference_pointer_there/8430

886 viewsedited  Aug 8, 2024 at 20:55

#prog #rust хайлайты:

Переписали реализацию двоичного поиска. Эти изменения связаны с тем, что ветвление по результату сравнения в двоичном поиске плохо сочетаются с предсказателем ветвлений — они, за вычетом вырожденных случаев, плохо предсказываются, и потому приводят к снижению производительности из-за регулярных сбросов пайплайнов процессора. В данном PR количество непредсказываемых ветвлений снизили.

Именно, во-первых, для ветвления по результату сравнению используют специально добавленный для этого интринсик, который заставляет кодген использовать условные перемещения (cmov) вместо условных прыжков. Во-вторых, в теле цикла теперь нет раннего возврата в случае, если элемент считается искомым согласно предъявленному предикату. Да, это увеличивает число итераций, но взамен убирает ещё одно плохо предсказываемое ветвление и делает число итераций зависимым только от длины слайса, т. е. хорошо предсказываемым. В качестве бонуса LLVM теперь в состоянии полностью развернуть цикл для поиска по слайсам со статически известной длиной.

Бенчмарки консистентно в разных тестах и на разных процессорах подтверждают, что поиск ускорился.

BY Блог*