Оптимизация компиляции: как мы приближали производительность кода на PL/I к C

Можно ли написать программу на PL/I и получить скорость выполнения, сравнимую со скоростью аналогичной программы на C или быстрее? Именно это мы попытались реализовать в нашем компиляторе pli-llvm.

Мы сравнивали 21 небольшую программу - от сортировки и математических вычислений до работы со строками и файлами. Для каждой задачи были реализации на PL/I и C. Итоговая оценка была посчитана как геометрическое среднее отношений времени выполнения PL/I к C на -O2: 1,0x означает паритет, меньше 1,0x - PL/I выполнился быстрее. Результат на свежих сборках и медиане семи запусков - 0,8x на -O2. До начала этой работы компилятор уже примерно сравнялся с C: результат был около 0,9x. Задача состояла в том, чтобы пройти путь от паритета к устойчивому преимуществу - и выяснить, за счёт чего оно достигается.

Почему компилятор PL/I может быть быстрее C

Оптимизатору проще работать, когда он знает больше о программе: какие значения может принимать переменная, меняется ли счётчик цикла и могут ли две области памяти пересекаться. PL/I в ряде случаев задаёт такие правила явно. Но сами по себе возможности языка ускорения не гарантируют: компилятор должен сохранить эту информацию и передать её LLVM в безопасной форме.

Например, обычные локальные переменные не перекрываются, если программа не декларирует особые способы доступа, такие как base или defined. Это позволяет компилятору понять, что запись в одну переменную не меняет другую. В C при работе с указателями компилятор, наоборот, по-умолчанию должен учитывать возможность пересечения памяти, если программист явно не заявляет о непересечении через restrict. Другой пример - цикл do. В PL/I управляющую переменную такого цикла нельзя менять из его тела, что даёт оптимизатору более надёжное описание цикла.

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

Результаты: где удалось выиграть

В таблице приведены значения относительного времени прогона бенчмарков на -O2 для шести целевых тестов - результат менее единицы означает, что программа на PL/I выполнялась быстрее C.

Среднее для этой выборки из шести тестов составило 0,9x на -O2 и 0,8x - на -O3. По всем 21 бенчмаркам результат составил 0,8x при оптимизации -O2. Исходный код бенчмарков можно найти в папке benchmarks/.

Не каждый тест стал быстрее. Например, десятичные бенчмарки сравнивают разные вычисления: PL/I сохраняет точность фиксированной десятичной арифметики, а версия на C использует double. Поэтому в некоторых таких тестах разница отражает не только качество компиляции, но и различие в семантике и объёме работы.

Что изменили в компиляторе

Меньше лишних переходов в runtime

Вызов runtime-функции в горячем цикле - цикле, который выполняется много раз, - может добавлять заметные накладные расходы. Для некоторых случаев операции mod (нахождения остатка от деления) компилятор теперь генерирует короткую последовательность LLVM IR вместо более общего пути: например, srem, а при делителе-степени двойки и доказанном неотрицательном значении - операцию and. Также была исправлена форма генерируемых циклов и вычислений проверок границ. Если проверка отключена, компилятор теперь старается убрать не только переход, но и ненужную арифметику для этой проверки.

Сведения о PL/I для LLVM

Для обычных локальных переменных компилятор передаёт LLVM информацию о непересечении памяти, а для индексов и диапазонов - соответствующие ограничения. Это помогает оптимизировать загрузки и записи, а также распознавать возможности для векторизации.

Здесь важна осторожность: такие утверждения корректны не для всех переменных и не при любых проверках времени выполнения. Например, для указателей и переменных, использующих общую области памяти (объявленных как defined), компилятор не должен делать предположение о непересечении. Были добавлены тесты не только на случаи, когда оптимизация должна сработать, но и на случаи, где её применять нельзя.

Передача параметров по значению

Параметр, передаваемый по ссылке, потенциально может измениться через указатель. Из-за этого оптимизатору сложнее рассуждать о его значении. Для встроенных функций компилятор теперь может передавать скалярный параметр по значению, если анализ подтверждает, что функции не нужны его адрес и запись через ссылку. Это улучшило отношение с 2,7x до 1,0x на -O2. Неопределённые случаи по-прежнему используют передачу по ссылке: быстрый путь включается только тогда, когда компилятор может доказать, что он безопасен.

Конкатенация строк без постоянных копий

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

Для подходящих случаев result = result || temp компилятор теперь добавляет новый фрагмент в конец существующего буфера. Если доказать безопасность такого пути нельзя, остаётся общий вариант. В отдельном тесте для переменной конкатенации отношение улучшилось с 7,3x до 0,2x; в итоговой таблице для бенчмарка операций над строками оно составляет 0,3x.

Отдельно была исправлена утечка временных буферов, создававшихся при общей конкатенации: для одного теста потребление физической памяти процесса на -O0 снизилось примерно со 109 МБ до 1 МБ. На -O2 скорость выполнения при этом не изменилась.

SIMD и поиск подстроки

В одном отдельном тесте поиск подстроки с постоянным образцом ускорился примерно в 14 раз относительно C-версии с strstr. Наша реализация использует поиск первого байта и проверку совпадения, на ARM64 также применяется обработка блоками с NEON.

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

Что осталось медленнее

Условие «ни один бенчмарк не медленнее C более чем на 15%» выполнить пока не удалось. Среди оставшихся отстающих тестов:

• десятичная арифметика (bcd_decimal.pli и decimal_ops.pli): PL/I реализует точную десятичную арифметику, C - приближенный результат типа double

• ввод и вывод (io_throughput.pli и file_io.pli): ограничены накладными расходами форматирования и реализацией runtime-а

• сигналы (on_conditions.pli) зависят от реализации обработчиков условий

• алгоритм Мандельброта (mandelbrot.pli) чувствителен к шуму измерений и содержит цикл с ранним выходом, который трудно векторизовать.

Как понять, что оптимизация действительно помогла

Многие полезные изменения начинались с инспектирования сгенерированного LLVM IR, по которому видно, что горячий цикл вызывает runtime-функцию, выполняет ненужную арифметику проверки или не распознаётся LLVM как подходящий для векторизации.

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

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

Воспроизвести результаты самостоятельно можно с помощью команды: 

cmake --build build/cmake -j && python3 benchmarks/run_benchmarks.py