Является ли Loop Lift еще правильной ручной оптимизацией для кода C?

Ответ 1

Если ваш профилировщик говорит вам, что существует проблема с циклом, и только тогда вещь, на которую следует обратить внимание, является ссылкой на память в цикле, который, как вы знаете, является инвариантным по циклу, но компилятор этого не делает. Здесь надуманный пример, пузырящий элемент до конца массива:

for ( ; i < a->length - 1; i++)
    swap_elements(a, i, i+1);

Вы можете знать, что вызов swap_elements не меняет значение a->length, но если определение swap_elements находится в другом исходном файле, вполне вероятно, что компилятор этого не делает. Следовательно, может оказаться целесообразным вывести вычисление a->length из цикла:

int n = a->length;
for ( ; i < n - 1; i++)
    swap_elements(a, i, i+1);

В критических внутренних циклах мои ученики получают измеримые ускорения с такими преобразованиями, как этот.

Обратите внимание, что нет необходимости поднимать вычисления n-1; любой оптимизирующий компилятор отлично способен обнаруживать петлевые инвариантные вычисления среди локальных переменных. Это ссылки на память и вызовы функций, которые могут быть более сложными. И код с n-1 более явно правильный.

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

Ответ 2

Запишите код, просмотрите его и подумайте только об оптимизации, когда найдете что-то, что недостаточно быстро, и вы не можете придумать альтернативный алгоритм, который в первую очередь уменьшит/устранит узкое место.

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

Ответ 3

Проверьте сгенерированную сборку и убедитесь сами. Посмотрите, выполняется ли вычисление для цикла-инвариантного кода внутри цикла или вне цикла в коде сборки, который генерирует ваш компилятор. Если он не выполняет подъем петли, сделайте сам подъем.

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

Ответ 4

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

Ответ 5

Если они, вероятно, будут важны для производительности, вам все равно придется думать о них.

Подъем для петли наиболее выгоден, когда для поднятия значения требуется много работы для расчета. Если для вычисления требуется много работы, это, вероятно, вызов из строя. Если это вызов из строя, последняя версия gcc гораздо менее вероятна, чем вы должны понять, что он будет возвращать одинаковое значение каждый раз.

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

#include <iostream>

bool isPrime(int p) {
    for (int i = 2; i*i <= p; ++i) {
        if ((p % i) == 0) return false;
    }
    return true;
}

int countPrimesLessThan(int max) {
    int count = 0;
    for (int i = 2; i < max; ++i) {
        if (isPrime(i)) ++count;
    }
    return count;
}

int main() {
    for (int i = 0; i < 10; ++i) {
        std::cout << "The number of primes less than 1 million is: ";
        std::cout << countPrimesLessThan(1000*1000);
        std::cout << std::endl;
    }
}

Для разработки программного обеспечения требуется "специальный" подход, чтобы не вручную поднимать этот вызов countPrimesLessThan из цикла, независимо от того, был ли вы профилирован или нет.

Ответ 6

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

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

Как правило, я не стал бы поднимать итератор count/end для std::vector, потому что это простой сценарий, который легко оптимизирован. Я бы не стал поднимать что-либо, что я могу доверять моему оптимизатору для подъема, и я бы не стал поднимать все, что было известно, что это не критично. при просмотре списка из дюжины окон, чтобы ответить на нажатие кнопки. Даже если он занимает 50 мс, он все равно будет выглядеть "мгновенно" для пользователя. (Но даже это опасное предположение: если новая функция требует 20 циклов по этому же коду, она внезапно замедляется). Вы должны по-прежнему выполнять операции, такие как открытие дескриптора файла для добавления и т.д.

Во многих случаях - очень хорошо в подъеме петли - это помогает много рассмотреть относительную стоимость: какова стоимость поднятого расчета по сравнению со стоимостью пробега по телу?

Что касается оптимизаций вообще, то есть довольно много случаев, когда профилировщик не помогает. Код может иметь совсем другое поведение в зависимости от пути вызова. Авторы библиотек часто не знают частоту их вызова. Изоляция фрагмента кода для сопоставления вещей уже может значительно изменить поведение. Профилировщик может сказать вам, что "Loop X is slow", но он не скажет вам: "Loop X медленный, потому что вызов Y разбивает кеш для всех остальных". Профайлер не мог сказать вам, что "этот код быстро из-за вашего snarky CPU, но он будет медленным на компьютере Стива".

Ответ 7

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

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

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

В качестве примера возьмем фрагмент, опубликованный Стивом Джессопом:

for (int i = 0; i < 10; ++i) {
    std::cout << "The number of primes less than 1 billion is: ";
    std::cout << countPrimesLessThan(1000*1000*1000);
    std::cout << std::endl;
}

Безопасно ли вызывать вызов countPrimesLessThan? Это зависит от того, как и где определена функция. Что делать, если он имеет побочные эффекты? Это может иметь важное значение, независимо от того, вызывается ли он один или десять раз, а также когда он вызывается. Если мы не знаем, как определена функция, мы не можем переместить ее за пределы цикла. И то же самое верно, если компилятор должен выполнить оптимизацию.

Является ли определение функции видимым для компилятора? И функция достаточно коротка, чтобы мы могли доверять компилятору встроить ее или хотя бы проанализировать функцию для побочных эффектов? Если да, то да, он будет поднимать его за пределы цикла.

Если определение не видно, или если функция очень большая и сложная, то компилятор, вероятно, предположит, что вызов функции нельзя перемещать безопасно, а затем он не будет автоматически поднимать ее.

Ответ 8

Помните правило 80-20 (80% времени выполнения тратится на 20% -ный критический код в программе) Нет смысла оптимизировать код, который не оказывает существенного влияния на общую эффективность программы.

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