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

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

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

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

E-граф разрешает эту дилемму иначе. Структура накапливает исходное выражение и найденные эквиваленты в одном месте, объединяя их общие элементы. Когда новое правило обнаруживает допустимый вариант, egg добавляет его в граф, не вытесняя существующие выражения. Таким образом происходит постепенное накопление разнообразных способов выполнить одно вычисление.

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

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

Идея насыщения равенствами появилась задолго до создания egg. Первое подробное описание метода относится к 2009 году, а рецензируемая статья вышла в 2011-м. Авторы предложили отказаться от последовательного разрушительного переписывания и накапливать информацию об эквивалентности разных элементов. После насыщения оптимизатор мог выбрать готовый вариант из всех обнаруженных возможностей.

На практике этот подход долгое время тормозили проблемы производительности и расхода памяти. По мере роста количества правил пространство возможных выражений экспоненциально расширяется. Даже компактное хранение общих частей не решало проблему обработки огромных E-графов. Когда egg была выпущена как открытый проект в 2020 году, реализация алгоритма значительно упростилась и ускорилась, благодаря чему насыщение равенствами вышло за рамки экспериментальных систем и попало в практическое применение.

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

E-графы используют при совершенствовании нейронных сетей. В некоторых реализациях получено 50-кратное ускорение оптимизации. При проектировании цифровых схем метод позволял сокращать размер схемы на 63%. Некоторые промышленные компиляторы переходят на E-графы, а инженеры Intel применяют подобные структуры при разработке микросхем.

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

Благодаря этому egg удобен для быстрого прототипирования. Разработчик может протестировать набор преобразований без создания полноценного оптимизатора со сложной системой приоритизации. Если результаты окажутся полезными, найденные правила можно оставить в egg или перенести в специализированный инструмент.

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

Подробный анализ egg опубликован в журнале Communications of the ACM. Редакция включила статью в раздел Research Highlights с избранными исследованиями в области вычислительной техники. За шесть лет с момента открытого релиза E-графы нашли применение в численных вычислениях, глубоком обучении, проектировании электроники и промышленных компиляторах, но проблема избыточного использования памяти по-прежнему ограничивает круг задач, где насыщение равенствами практически целесообразно.