Комментарии 11
То, насколько изящно вы это сделали, замечательно говорит, что теория компиляторов (элементы которой вы тут показали) не зря называется "математикой, застывшей в ассемблере".
Для полноты рассказа (для тех, кто на "вы" с компиляторами) можно сказать, что язык Rust имеет к теме статьи очень посредственное отношение (это может быть важно знать).
В тулчейне LLVM есть название "фронтенд" для программы, которая переводит исходный код в LLVM IR, и "бэкенд" для программы, которая оптимизирует LLVM IR и переводит его в ассемблер.
Для нового языка программирования достаточно написать только "фронтенд", то есть переводчик исходника в LLVM IR. Сначала "фронтенд" был только один - Clang (для языков C/C++/Objective-C), затем появились другие для новых языков, в том числе для Rust.
Другими словами, примерные программы в статье могли бы быть написаны вместо Rust на C, C++ или куче других языков, а смысл остался бы тем же.
Да, большое спасибо за уточнение! Я забыл об этом написать, но я пробовал компилировать подобный код на C и C++, и везде оптимизация срабатывала.
Однако у rust есть другая особенность: если написать цикл от 0 до n включительно (через for i in 0..=n), то оптимизация не срабатывает, хотя если написать код "по-простому" (без range based for), то оптимизация работает.
В заключение, хочу выразить мысль, что такая оптимизация в очередной раз подчёркивает, что код, который вы написали, не обязательно будет совпадать в точности с тем, что будет исполнять процессор.
Хочу выразить другую мысль: мы видим движение куда-то не туда. Мы написали императивный код который описывает что надо сделать, а оптимизатор делает это по своему. Может пора уже переходить на декларативный уровень? Где вы описываете что надо и какие преобразования, предположения и инварианты есть что бы компилятор генерировал код на основе явных инструкций. Не применительно к данной оптимизации в C++ есть довольно большой зоопарк предположений (не всегда верных, даже в большинстве случаев не верных) на которых он строит свои оптимизации. В результате иногда бывает очень весело.
Мы написали императивный код который описывает что надо сделать, а оптимизатор делает это по своему
Оптимизатор сделал ровно то, что требуется. Проанализировал граф зависимостей между переменными и выяснил, как его можно переупорядочить и упростить, не нарушая инварианты по side effects, которые были в исходном коде. Код от этого не перестал быть императивным.
Может пора уже переходить на декларативный уровень?
Тогда C++ это уже супер декларативный уровень, потому что в ассемблере нет никаких классов, лямбд, исключений. Инварианты для компилятора тоже можно наставить [[assume]].
в C++ есть довольно большой зоопарк предположений (не всегда верных, даже в большинстве случаев не верных) на которых он строит свои оптимизации
C++ это достаточно зрелый язык, что у него есть модель памяти (у модного Rust ее нет...) Большинство предположений соответствуют ей и строги математически.
Например, если читать из одного и того же адреса в цикле, то C++ соптимизирует это в одно чтение, предполагая, что незачем читать больше одного раза одно и то же - нет side effect. Чтобы указать, что это не так (например, на железке в этот адрес какой-то другой процесс может записывать числа) и каждое чтение это наличие side effect, нужен модификатор volatile.
C++ это достаточно зрелый язык, что у него есть модель памяти
Не то слово, даже перезрелый. Вот какие грибы надо было есть что бы такое стандартизировать? https://youtu.be/ZgZ4_2YwtDQ?t=533
А какие альтернативы? Это уже по факту было и компиляторами использовалось. Strict aliasing rule и оптимизации вроде "указатели из разных массивов не могут указывать на один и тот же элемент" берутся отсюда же. А дальше либо мы как-то убеждаем компиляторы не делать какие-то оптимизации, либо легализуем такое поведение в стандарте и попутно пытаемся придать ему смысл. Второе кажется вероятнее.
double avg = 0;
for(int k=1;i<=n;i++)
{
avg+=pow(2*cos(2*k*pi/n),2);
}К сожалению (или к счастью), нет, такое не сработает. Дело в том, что IndVarSimplification оптимизирует только весьма ограниченный ряд последовательностей. Это арифметические прогрессии, ряды, где разницы между соседними элементами образуют арифметическую прогрессию и т.д. А функции cos и pow кажется могут вообще не заинлайниться, и оптимизации точно не произойдет
Хороший разбор и примеры. Интересно, что материал неявно затрагивает ещё одну важную тему: SCEV Evaluation является прекрасным примером оптимизации, честно полагающейся на отсутствие UB (undefined behavior) в исходном коде. Мы применяем матаппарат на множестве целых чисел, чтобы вывести некоторые результирующие формулы, но они с большой вероятностью перестают работать, если допустить целочисленное переполнение на итерациях суммирования (однако, не исключено, что формулы справедливы в арифметике по модулю 2⁶⁴, например).
Как IndVarSimplification применяет математику в вашем коде