Наш проект — pli-llvm, компилятор PL/I с LLVM-бэкендом. Реализованные фичи включают поддержку настоящую десятичную арифметику фиксированной точности, встроенные строки переменной длины, обработку сигналов и управление памятью на уровне языка. В этой статье рассматривается, как такие конструкции представлены в компиляторе и какие оптимизации удалось применить. Для сравнения использовались парные реализации одинаковых алгоритмов на PL/I и C — таких, как тест Коллатца.

Целью было приблизиться к производительности C: среднее отношение времени выполнения кода на PL/I к C в итоге составило около 1,0 на 21 бенчмарке.

Почему возможно обогнать C

Сама семантика языка PL/I дает компилятору дополнительную информацию, которую затем использует LLVM для генерации более оптимизированного кода:

  • Непересекающиеся локальные переменные: обычная переменная в PL/I не пересекается ни с чем, если программа не утверждает обратного (based/define/параметр), тогда как указатель в C может указывать куда угодно — поэтому компиляторы C вынуждены пессимистично предполагать, что два указателя могут совпасть («алиасинг»), и пропускать оптимизации вроде перестановки загрузок или векторизации циклов. PL/I даёт LLVM готовое доказательство; C может предложить лишь обещание restrict.

  • Честные циклы: do i = 1 to n гарантирует, что управляющая переменная не изменяется в теле, тогда как счётчику цикла for в C можно присвоить где угодно, поэтому оптимизатор вынужден постоянно передоказывать количество итераций.

  • Явные формы: fixed binary(p) задаёт точный числовой диапазон; character(n) — точный размер. int в C — это просто «некое машинное слово»: оптимизатор узнаёт диапазоны лишь по факту.

  • Встроенные функции: компилятор раскрывает вызовы встроенных функций прямо в LLVM IR и проводит оптимизацию, зная их семантику и контекст.

Результаты

На 21 бенчмарке компилятор PL/I показал среднее отношение времени 0,9 к clang -O2; в отдельных тестах со строками разница составила 3,5-14 раз.

  • Поиск по строке (string_search.pli в benchmarks/) оказался в 14 раз быстрее C за счет применения SIMD.

  • Операции со строками (string_ops.pli) — быстрее C в ~3 раза благодаря эффективной работе со строками.

  • Стек с controlled storage (controlled_stack.pli) — быстрее C в ~2 раза на -O1.

  • Условия с проверкой границ (condition_ops.pli) — быстрее C в ~1.7 раза на -O1.

  • Сортировка массива (array_sort.pli) на -O2/-O3 — быстрее C в ~1.2 раза.

  • Матрица с плавающей точкой (matrix_float.pli) — быстрее C в ~1.2 раза.

В большинстве остальных сравнимых тестов удалось добиться паритета с C.

Подходы к оптимизации

Сокращение runtime-вызовов (mod и математические функции)

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

На уровне LLVM IR был вызов рантайм-функции:

tail call i64 @pli_mod_ll(i64 %i64.i, i64 2)

стало:

%r = and i64 %m, 1

Остальные математические функции также были переведены на LLVM-интринсики вместо обёрток.

Результат: для теста Коллатца и математических функций отношение времени выполнения изменилось с 3,1 до 1,0.

Целочисленное представление десятичной арифметики

Представление десятичных чисел: в формате double число 0.01 не представимо точно в двоичной системе. Значение fixed decimal(p,q) можно представить как целое с десятичным масштабом: например, 1.99 хранится как 199 при масштабе 2. Арифметика над такими значениями может выполняться целочисленными операциями с последующей корректировкой масштаба.

Что обнаружили: две проблемы в выборе типов:

  • binary × decimal (дробный) уходил во float: выражение i * 1.99 превращалось в fmul + fmul + fcvtzs (две float-операции и конверсия) вместо одного целочисленного mul i64 …, 199.

  • Оператор / для целых операндов также выбирал float: n / 2 проходило через uitofp → fmul 0.5 → fptosi вместо sdiv.

Что сделали:

  • binary(scale 0) × decimal(scale>0) остаётся точным fixed decimal (масштаб произведения = сумма масштабов, сырые scaled integers перемножаются напрямую, без пред-масштабирования).

  • / для целочисленных операндов использует sdiv с прежней проверкой zerodivide; нецелочисленное деление остаётся fdiv.

  • Деление на константную степень десяти LLVM преобразует в умножение с коррекцией сдвигом (smulh + сдвиг вместо udiv); это проверили по машинному коду.

  • Цикл бенчмарка расширили 5 000 → 200 000 итераций, чтобы выйти из шума.

Результат: в оптимизированном IR горячего цикла нет fmul/fcvt/fdiv: используются mul i64, udiv и операции коррекции масштаба. Исправление усечения литералов изменило результат на -O3 с 2,3 до 1,3; последующие изменения умножения и деления — с 1,3 до 0,9. На -O1/-O2 вариант PL/I оказался быстрее C в этом тесте; при этом реализации используют разные числовые модели.

Ограничение сравнения: вывод в PL/I и Си различается по устройству теста: PL/I округляет каждое присваивание до объявленного масштаба, а C-эталон накапливает значение в double и округляет при печати. Поэтому этот тест позволяет сравнивать время выполнения, но не побитовое совпадение результата.

Вывод: тип и масштаб значения позволяют компилятору использовать целочисленный путь, сохраняя семантику fixed decimal.

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

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

Исходная ситуация: параметры внутренних процедур передавались по указателю. В бенчмарке это давало отношение времени 2,9. Атрибут AlwaysInline не изменил результат, передача параметра как значения i32 снизила отношение до 1,0.

Что сделали: при генерации IR выбирается способ передачи каждого параметра внутренней процедуры. Передача по значению используется для внутренних процедур с одним входом, если параметр — скаляр fixed/float/pointer, в лексическом поддереве нет записей через него и получения его адреса, и не включены проверки, которым нужен адрес. Проверяются присваивания, addr/byaddr, переменные do, get и вложенные процедуры. Случаи с entry, асинхронными вызовами, optional и defined остаются с передачей по ссылке. В теле процедуры значение при необходимости размещается в ячейке фрейма. Также добавлены инлайнинг небольших внутренних процедур и упрощённая генерация modдля неотрицательных индексов цикла do.

Результат: для вызова функций отношение времени изменилось с 2,9 до около 1,0 на -O2/-O3.

Вывод: способ передачи параметра влияет на оптимизации между процедурами; выбор представления на границе вызова может быть важен не меньше отдельного прохода оптимизатора.

Оптимизация конкатенации и исправление утечки памяти

Стоимость конкатенации в цикле: при наивной реализации для каждого result = result || slice выделяется новый буфер, копируется накопленный результат и добавляется очередной фрагмент. На k-й итерации копируется k символов, поэтому суммарный объём копирования за n итераций растёт как O(n²). В C-эталоне snprintfобрабатывает формат на каждой итерации, а strcat повторно ищет конец строки.

Исходная ситуация: для result = result || temp в цикле выполнялась новая аллокация, две полные копии и заполнение буфера пробелами на каждой итерации; отношение времени составляло 7,3. Оптимизация обрабатывала только константные конкатенации, а переменные конкатенации использовали общий путь.

Что сделали: оптимизацию расширили на переменные конкатенации. Быстрый путь применим к строковым литералам и к указателям на гарантированно непересекающуюся память. Параметры по ссылке могут указывать на цель через вызывающую процедуру; для based/controlled/static/defined непересечение не гарантируется, поэтому они используют общий путь. Самоконкатенация X = X || X безопасна: чтение происходит из диапазона [0, old), запись — начиная с [old, …). Каждый фрагмент добавляется после текущей длины с усечением до min(cap, total); затем обновляется длина, заполнение пробелами пропускается.

Результат: для операций над строками отношение времени изменилось с 7,3 до 0,2-0,3. Цепочка base || '[' || 'item' || '] 'записывается в один буфер последовательными memcpy без промежуточных выделений, а в цикле добавляется только новый хвост. Объём страниц памяти процесса, которые в данный момент находятся в физической оперативной памяти, (RSS) на -O0 снизился с 109 МБ до примерно 1 МБ.

Оптимизация поиска подстроки

Реализация поиска подстроки: встроенная функция PL/I index(haystack, needle) ищет подстроку: вместо цикла с runtime-вызовом можно использовать библиотечные memchr/memcmp; для коротких константных строк возможна также обработка блоками с помощью NEON.

Что сделано: для поиска с константной искомой строкой используется встроенный путь memchr + memcmp, а на ARM64 — NEON-блоки. Тесты учитывают оба варианта: скалярный на x86_64 и NEON на ARM64. В бенчмарке каждую итерацию один байт буфера меняется через substr(buffer, …) = 'x', чтобы LLVM не вынес поиск из цикла как инвариант; иначе измерялась бы оптимизация цикла, а не поиск.

Результат: отношение времени составило 0,1 — примерно в 14 раз меньше, чем у эталона с библиотечным strstr. В данном тесте index получает константную строку 'sentinel'; её первый байт 'S' не встречается в повторяющейся базе, поэтому поиск быстро доходит до конца буфера.

Выводы

Анализируйте IR: многие проблемы обнаружились при просмотре горячих циклов: лишние вызовы рантайм-функций, последовательности fmul+fcvt и fdiv вместо целочисленных операций. IR помогает увидеть, что именно генерирует компилятор.

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

Контролируйте методику измерений: повторные запуски, warmup, привязка к ядру, минимальная длительность, проверка вывода и метаданные компилятора помогают отделить реальные изменения от шума. В ходе работы короткий цикл дал мнимое изменение с 0,7 до 1,3; разбор показал, что результат был связан с шумом.

Проверяйте небольшие изменения измерениями: изменения в атрибутах функций, alwaysInline и буферизации вывода заметно повлияли на отдельные бенчмарки.

На выбранном наборе тестов оптимизации среднее время выполнения программ PL/I доведено до уровня clang -O2. Результаты зависят от теста и платформы: некоторые сценарии остаются медленнее, а в отдельных тестах со строками получено значительное ускорение.

Повторить часть измерений можно так: cmake --build build/cmake -j && python3 benchmarks/run_benchmarks.py.