Поговорим об оптимизирующих компиляторах. Сказ шестой: цикловые инварианты

[Rsa97]

Примеры не самые удачные. В обоих случаях цикл вообще не нужен,

int foo(int n) {
    return (n - 1) * n / 2 + n * n * 2;
}

int foo(int n) {
    return n > 807
        ? (n - 1) * n / 2 + n * n * 2
        : (1 - n) * n / 2;
}

[xortator]

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

[aamonster]

Практический вопрос: насколько можно закладываться на эту оптимизацию и писать инвариантные выражения внутри цикла? (Разумеется, речь про случаи, где ручное вытаскивание делает исходник менее читабельным, а не про случай, когда этот инвариант имеет свой смысл и запись его в переменную заведомо оправдана)

При использовании любого компилятора на llvm?

[xortator]

Если речь не про вынос ветвлений и не про память, то практически любой LLVM-ный компилятор всё вынесет (в режиме -O2 и выше). В таких случаях я бы рекомендовал не приносить читаемость в жертву.

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

К тому же, у человека может быть знание, которого у компилятора нет в принципе. Если вы посмотрите на пример про load/store по двум разным указателям, то у компилятора нет способа доказать, что они разные. Но если вы по какой-то причине знаете, что эту функцию вызывают только таким образом, что p1 и p2 никогда не перекрываются, то вы можете соптимизировать её вручную, используя это знание.

В любой ситуации можно использовать чудо-сайт https://godbolt.org/, чтобы посмотреть, что на самом деле происходит.

[Cerberuser]

Если вы посмотрите на пример про load/store по двум разным указателям, то у компилятора нет способа доказать, что они разные.

Если, конечно, нет аналога restrict из C или &mut T из Rust.

[xortator]

Ну да, есть всякие способы сообщить что-то про алиасинг, но пока что я ограничиваюсь формулировкой "всё сложно", имея в виду, что их реально много и там хватит на отдельную статью.

[vk6677]

Для чего циклы, если их можно заменить арифметическими рядами ?

[punzik]

А если цикл с сайд-эффектами?

[Cerberuser]

Чтобы сначала повыносить из них всё, что выносится, а потом уже то, что осталось, свернуть в замкнутую формулу, по идее.

[vanxant]

Да это примеры синтетические, без внешних зависимостей. В реальности вы будете итерироваться по какому-то внешнему контейнеру, и ваши x с y - это будут поля объектов в этом контейнере

[xortator]

Дело в том, что в LLVM (да и большинстве других компиляторов) каждая оптимизация отвечает только за одну часть работы. LICM не умеет сокращать сумму прогрессий, GVN не умеет дуплицировать циклы, а векторизатор не пытается решать квадратные уравнения. Если оптимизации на вход пришёл какой-то IR, она будет пытаться с ним сделать то, что умеет она, поскольку каждая отдельная оптимизация не знает (да и не может знать) всего, что ещё можно с ним сделать.

Я намеренно привожу простые примеры, чтобы в них не было лишнего кода, который мешает понять, что происходит и как работает наша оптимизация. Да, их обычно можно оптимизировать сотней других способов. Например, превратив в сумму ряда или векторизовав. Но не надо забывать, что цель статьи -- рассказать про конкретный класс преобразований, а не про то, как заоптимизировать до максимума какой-нибудь игрушечный пример. :)