Оптимизация цикла C с помощью условных переменных в цикле

Question

Извиняюсь, если об этом спрашивают в архивах.Я нашел несколько похожих вопросов, но ни один из них не показался именно тем, что я хотел.У меня есть серия вычислений, которые будут хранить значения в 4 (очень больших) массивах: A, B, C и D. Эти вычисления взаимозависимы, например, для вычисления b [i] может потребоваться использование [i-1].Я способен выразить все в одном цикле, но это приводит к крайним случаям, когда для определенных значений i должны выполняться только некоторые вычисления.Например:

for(i=0;i<end;i++)
{
    if(i == 0)
        //calculate A[i+1] and B[i+1]
    else if (i == end-1)
        //calculate C[i-1] and D[i-1]
    else
        //calculate A[i+1], B[i+1], C[i-1], D[i-1]
}

Из-за проблем с производительностью я бы хотел, чтобы в моем цикле не было условных выражений.Оценка условия будет дешевой по сравнению с расчетами, но, возможно, не пренебрежимо мала.Мой вопрос заключается в том, может ли компилятор надежно расширить это до

//calculate A[1] and B[1]
for(i=1;i<end-1;i++)
{
    //calculate A[i+1], B[i+1], C[i-1], D[i-1]
}
//calculate C[end-2] and D[end-2]

. Я собираю из архивов, что компилятор разбил бы мой цикл, если бы условные выражения были постоянными, но здесь они зависят от i, что в принципе может быть изменено некоторыми из моих расчетов.Будет ли он обнаруживать, что я не вмешиваюсь в переменную итерации и, таким образом, разумным образом разбиваю ее на части?

Дополнительная информация, если вы решите ответить на вопрос, предложив лучший способ выполнения действий:

Первоначально код был написан с 4 циклами, чтобы вычислить элементы для каждого из массивов.Это был самый интуитивно понятный способ написания кода, но он был неэффективным.Поскольку вычисление элементов в одном массиве зависело от элементов в других массивах, это означало, что мне приходилось считывать все 4 массива из памяти во время каждого из 4 циклов.Поскольку эти массивы не помещаются в кеш, это не оптимально, и мне нужен был код, который будет циклически проходить через мои массивы только один раз.

Я также знаю, что могу разорвать свой цикл вручную, и это действительно так.как все в настоящее время делается.Однако в этих вычислениях используются нетривиальные формулы (и я не могу позволить себе потерю производительности при вызове функции во время каждой итерации этого цикла), поэтому разрыв кода привел к дублированию кода, которое не только очень трудно прочитать, но и практически невозможно поддерживать на следующем этапе.время, когда мои формулы будут изменены (что они будут ...)

Заранее спасибо!

Answer 1

Чтобы ответить на ваш вопрос в более широком смысле: когда оптимизация критична, профилировщик - ваш друг.Разработчики, как известно, плохо догадываются, где в нашем коде процессор проводит большую часть своего времени.Профилировщик точно покажет вам, где находятся «дорогие» операции, поэтому вы можете сосредоточиться на исправлении областей, которые дадут вам наиболее значительные улучшения.

Мне интересно ваше заявление о том, что вы "не можетепозволить себе снижение производительности при вызове функции во время каждой итерации этого цикла ... "Откуда вы это знаете?Многие современные процессоры оптимизированы для вызовов функций, особенно если вы можете передать указатель (на struct?) Вместо множества отдельных аргументов.Если ваши вычисления действительно "нетривиальны", тогда издержки вызова функции могут быть незначительными.

Другие вещи, о которых стоит подумать:

• В качестве эксперимента переиндексируйтеваши расчеты, чтобы они работали именно на i, а не i-1 или i+1, насколько это возможно.Так, например, используйте A[i], B[i], C[i-2] и D[i-2].Я был бы удивлен, если бы это значительно улучшило использование оптимизирующего компилятора, но вы никогда не знаете ...

• Предварительно вычисляйте все, что сможете.

• Постарайтесь разбить свои вычисления на более мелкие компоненты, которые являются либо постоянными, либо общими, как предположил Джеймс Гринхалг, чтобы их можно было повторно использовать.

• Можете ли вы переписать свои уравнения более эффективно?Анализ математики может привести вас к сокращению: возможно, вы можете переписать некоторые (или все) итерации в закрытом виде.

• Можете ли вы заменить свои уравнения в целом более простым?Например, предположим, вам нужно отсортировать набор мест по их расстоянию от вашего дома.Расчет расстояния требует вычитания, возведения в квадрат, сложения и квадратного корня.Вообще квадратный корень - безусловно самая дорогая операция.Но если вам нужны только относительные расстояния, вы можете вообще пропустить квадратный корень: сортировка по квадрату расстояния создает такой же порядок сортировки!

• Если встраивание невозможно, можете ли вы определить свои функции (или их компоненты) как эффективные макросы, поэтому, по крайней мере, вы можете избежать повторения кода?Как вы упомянули, наследование буфера обмена является смертельным врагом ремонтопригодности.

Если больше ничего, выполнение этого упражнения не даст вам уловок о том, как работает ваш компилятор и язык Си.Удачи!

Answer 2

У меня вопрос, может ли компилятор надежно расширить это до ...

Ответ, который вы ищете, - нет. Оптимизация компилятора сильно переоценена, особенно если вы не используете MSVC и не ориентируетесь на Wintel.

Как уже предлагалось, проверьте выходные данные ассемблера, чтобы проверить сами. Лично я бы проигнорировал это и просто написал бы код, чтобы компилятору не приходилось выполнять всю работу за вас - и на самом деле я думаю, что это более читабельно, если вам нужно сделать что-то особенное для первой и последней итераций для циклов рефакторинга, таких как в любом случае ... вместо того, чтобы думать об условных выражениях и их значении, порядок выполнения следует порядку написания кода, что намного более естественно (и подобно написанному языку).

Теперь вы, похоже, предполагаете, что это было нечитабельно - правильное решение imo - не вставлять весь код в цикл, а вместо этого перемещать нечитаемые блоки кода в хорошо именованные функции с сильными встраивающимися подсказками (__forceinline и т. Д.) то итерация может выглядеть так:

prepareForIteration( A, B );
for( int i = 1; i < ( end - 1 ); ++i )
{
    iterationStep( i, A, B, C, D );
}
finaliseIteration( end, C, D );

Конечно, поскольку вы знаете, что на самом деле делает код, я уверен, что вы можете найти более подходящие имена ...

Answer 3

Лучшее, что вы можете сделать, это то, что вы уже сделали: проходите по всем четырем массивам одновременно, а не по каждому в отдельности. Удобные для кеширования шаблоны доступа являются наиболее важной микрооптимизацией при работе с большими массивами.

Для приведенного вами примера я бы попробовал следующее, если вы используете gcc или clang-llvm:

for(i=0;i<end;i++)
{
    if(__builtin_expect((i == 0), 0))
        //calculate A[i+1] and B[i+1]
    else if (__builtin_expect((i == end-1), 0))
        //calculate C[i-1] and D[i-1]
    else
        //calculate A[i+1], B[i+1], C[i-1], D[i-1]
}

Это «подсказка» компилятору, который он передает процессору, чтобы помочь с предсказанием ветвлений. На современном CPU ошибочно предсказанная ветвь может стоить сотни циклов. (С другой стороны, на современном процессоре логика для прогнозирования каждой ветви на основе того, как часто она использовалась в прошлом, довольно сложна. Таким образом, ваш пробег может варьироваться.) Правильно спрогнозированная ветвь стоит 1 цикл или даже меньше, поэтому это следующая вещь, о которой я бы беспокоился.

Обратите внимание, что классические методы "оптимизации", такие как развертывание цикла, почти наверняка бесполезны и, вероятно, даже контрпродуктивны.

Наконец, если ваш алгоритм может быть векторизован, то это ваш следующий шаг. Преимущество полного исключения условных выражений из цикла состоит в том, что компилятору может быть проще автоматически его векторизовать. Но если цикл нетривиален, вам, возможно, придется написать векторизованный код вручную; попробуйте поискать "SSE intrinsics".

Как и другие предлагали, начните с использования профилировщика и опции -S (или эквивалентной) для вашего ассемблера. Удачи.

Answer 4

В дополнение к профилированию, я бы посоветовал просмотреть код, который фактически генерирует компилятор (cc -S *.c для многих компиляторов). Это должно сказать вам, как (или если) цикл разворачивается, а также показать, какие инварианты цикла перемещаются. Не забудьте указать те же настройки оптимизации, что и для обычных компиляций.