Решил ответвить обсуждение сабжа от темы
Олимпиадные задачиВ ней возник вопрос в влиянии ветвлений на скорость. Я
привел пример, демонстрирующий, что если в простейшей операции, выполняемой во внутреннем цикле, заменить условный переход на пару арифметических операций, то процедура может ускориться в несколько раз.
Продолжим разговор.
Кстати о сортировке. Я так понимаю, слишком на if'ах в этом случае не поэкономишь?
Вообще-то вроде как можно. Я слышал о реализациях сортировок коротких массивов (порядка 5-6 элементов), в которых число условных переходов то ли уменьшено, то ли вообще сведено к нулю. Но сам не очень в теме и реализации не анализировал. Если кто в курсе - можете просветить.
согласно PAV'у, ветвления, использующиеся функциями минимума/максимума, есть зло.
Не следует воспринимать все так однозначно и буквально. Избавление от ветвлений все равно достигается какой-то ценой, которая может оказаться выше, чем получаемый при этом выигрыш. Это все проверять надо, потому что сильно зависит еще и от качества кода, построенного компилятором.
Приведу пример. Вот любопытная статья с хабра
Пузырьки, кэши и предсказатели переходов. Суть там в следующем. Когда процессор встречает условный переход, то он на самом деле не ждет окончания вычислений, которые позволяет ему определить дальнейший ход действий. Он использует
предсказатель переходов, пытается угадать этот переход и продолжает выполнение по предсказанной веточке (насколько возможно, конечно). Если оказывается, что предсказание было неверным, то происходит откат тех действий, которые были произведены, и переход по правильной ветке. Необходимость делать такой откат влечет соответствующие накладные расходы и замедление работы.
Предсказатель переходов работает либо статически (т.е. тупо всегда делает некоторое одно предсказание), либо динамически. Второй вариант означает, что для данного конкретного ветвления (которое за короткий срок выполнялось многократно) процессор накапливает статистику - как оно срабатывало, и начинает предсказывать переход в соответствии с ней. Таким образом, если во внутреннем цикле ветвление проверяет некоторую весьма редкую ситуацию, и в большинстве случаев срабатывает одним способом, то процессор быстро научится его предсказывать, и оно практически не будет ничего замедлять.
В статье приводится конкретный пример двух реализаций сортировки методом пузырька, алгоритмически совершенно эквивалентных, т.е. там производятся просто одинаковые действия, однако в разном порядке. Мониторинг процессорных операций показывает практически одинаковые затраты по всему, однако в одном случае предсказатель переходов "промахивается" в разы чаще, чем в другом. В статье проведен тест с сортировкой массива длины 100 000 и там получается, что различие в скорости - в 3 раза.
Я полагаю, что этот пример достаточно искусственный, поскольку массивы такого объема пузырьком, конечно же, не сортируют. Я провел более реальный эксперимент, взяв случайную числовую последовательность длиной несколько миллионов чисел, разделил ее на короткие куски, и последовательно отсортировал эти куски (т.е. имитировал сортировку короткого массива во внутреннем цикле). В таком эксперименте тоже явно наблюдалось ускорение, хотя и не такое большое. При длине сортируемого массива в 10 элементов ускорение было порядка 15-20%. При длине в 100 элементов ускорение было примерно в два раза.
Внутренний цикл данной процедуры состоит из следующей операции: даны два числа
и
, нужно расположить их в порядке возрастания. В простейшей реализации это делается так:
Код:
if( a > b )
{
int x = a;
a = b;
b = x;
}
Можно сделать ту же самую операцию без ветвлений. Я применил трюк, использующий, правда, внутреннее представление числа: а именно, что старший бит отвечает за знак. Таким образом, код
Код:
int c = a - b;
int x = ((unsigned int)d)>>31;
помещает в переменную x значение 1, если разность a-b отрицательна, и ноль в противном случае. Несложная арифметика позволяет в результате получить минимум (или максимум) этих двух чисел. У меня получилась такая процедура:
Код:
int c = a - b;
int x = ((unsigned)c)>>31;
c*= x;
int min = b + c;
b = a - c;
a = min;
(Эта реализация операции сравнения без ветвлений иллюстрирует, что в теории сортировку без ветвлений сделать можно).
Однако результат был отрицательным: в обоих реализациях сортировки подмена простейшей реализации на данную заметно ухудшила быстродействие. Понятно, что операций тут достаточно много получилось (хотя, я надеялся, что компилятор может быть сумеет их достаточно компактно реализовать). Однако я думаю, что главная причина заключается в том, что эти операции все строго последовательные и каждая использует результат предыдущей. Поэтому их просто не получается нормально выполнить конвейром, никакого внутреннего распараллеливания тут не получается.
Также я попробовал применить рекоментацию
venco по использованию библиотечных функций min и max (
http://dxdy.ru/post343593.html#p343593):
Код:
int min = std::min(a,b);
b += a - min;
a = min;
К сожалению, эта штука работала еще существенно медленнее, чем даже моя безумная реализация. Возможно, виноват компилятор (у меня Microsoft Visual Studio). Я не знаю, что он сделал из данного кода. Может быть, он не сообразил или не смог заинлайнить вызов min? Хотя я поставил в настройках инлайнить все, что только возможно.
