Замер скорости: во что нам обходится компиляция и работа

Обе правки из вопроса 3 СДЕЛАНЫ 16 августа, и замер повторён. Мы стали быстрее Python в 1,28 раза там, где были медленнее в 1,37. Разбор — в разделе «После правок» сразу за короткими ответами; остальной отчёт оставлен как был, потому что он объясняет, откуда брались числа.

Отчёт отвечает на три вопроса и ни на что больше. Короткие ответы — здесь, разбор с числами — ниже.

1. Во сколько раз мы медленнее Python и Node?

Компиляция: прямого отношения нет — у Python и Node компиляции нет вовсе, и делить на ноль нечего. Осмысленный вопрос вместо него: сколько раз надо запустить программу, чтобы наша компиляция окупилась. Ответ сегодня — никогда: мы медленнее обоих и в работе, поэтому разовая плата в 1,3 секунды (на программе замера) не возвращается ни на одном числе прогонов. Это и есть худшая новость отчёта, и она названа прямо. После двух правок из вопроса 3 компиляция начинает окупаться против Python на трёх задачах из пяти (за 6, 13 и 20 прогонов), против Node — по-прежнему ни на одной. Подробности — в разделе «Время компиляции».

Работа: медленнее Python в 1,4 раза и медленнее Node в 3,3 раза (геометрическое среднее по пяти задачам). По задачам разброс большой: от 1,04 (НОД) до 2,2 (дерево) против Python и от 2,2 (строки) до 10,3 (Коллатц) против Node. Написанный руками C быстрее нас в 8,6 раза.

2. Какая часть этого — цена доказуемости, а какая — недоделанность?

Ответ распадается надвое, и обе половины важны.

• На функциях, чьё доказательство не оставляет сторожа в работающей программе — а это 2 130 из 2 196 тотальных функций корпуса, 97 % — цена доказуемости 1–9 %, то есть неотличима от нуля на фоне шума. Счётчик шагов, счётчик глубины и сторож стека вместе стоят меньше, чем разброс между прогонами. Всё остальное отставание — недоделанность.
• На функциях, чьё завершение доказано объявленной мерой (66 функций корпуса, 2,4 %), сторож в рантайме стоит в 3 раза дороже самой функции: Евклид с доказательством — 479 мс, он же без доказательства — 156 мс. Приём «топливо» (5 функций во всём корпусе) обошёлся в +33 % на сортировке.

То есть: доказуемость дорога ровно там, где её применили, и почти не применена. Взвешенно по корпусу цена доказуемости — единицы процентов; недоделанность — всё остальное, то есть 90 с лишним процентов отставания.

3. Что дало бы наибольший выигрыш за наименьшую работу?

Третья, дороже всех и важнее всех по памяти: арена. «Сортировка вставками» — тотальная, доказанная, написанная прямо — на 1 000 элементах занимает 5,6 ГиБ, а на 4 000 набрала 178 ГиБ и не досчитала. Это уже не правка, а работа.

Разбор с обоснованием оценок — в разделе «Что делать» в конце.

После правок: что получилось на самом деле

Обе правки сделаны (ветка work/skorost, коммиты c903983 и 2854d2b), замер повторён тем же стендом, теми же одиннадцатью кругами и тем же чередованием. Машина в этот раз была тихая: разброс 1–3 % вместо обычных 30 %, поэтому «до» и «после» ниже сняты заново оба, а не взяты из таблиц старого замера.

Время работы: три столбца

Медиана из 11 прогонов, миллисекунды, полное время процесса.

Разброс «после»: коллатц [131,4 … 145,6], нод [76,5 … 79,5], сортировка [174,6 … 183,1], строки [318,7 … 344,7], дерево [539,7 … 594,6].

Кто из двух правок сколько дал

Флаг на двух задачах из пяти не дал ничего: НОД 0,98 и дерево 1,00 — обе цифры внутри разброса. Прежний замер обещал флагу 1,60 на НОД; на сегодняшнем дереве этого нет, и говорится об этом прямо. Всё, что флаг дал, он дал на коллатце (1,51), сортировке (1,19) и строках (1,11).

Обгоняем ли мы теперь Python

По задачам против Python: коллатц 0,41, нод 0,63, сортировка 0,71, строки 0,77 — быстрее на четырёх из пяти. Дерево 2,02 остаётся медленнее вдвое, и причина названа в разделе «Где мы медленнее и почему»: узел варианта занимает 144 байта против 24 у структуры C. Это ширина значения, а не проверки, и снимается она третьей правкой, которая не сделана.

Цена по времени сборки

Здесь ожидание не подтвердилось, и это стоит сказать отдельно.

На большом файле сборка стала вдвое быстрее, а не вдвое медленнее: с -flto шаг cc -c перестаёт оптимизировать и дешевеет, а оптимизация уезжает на компоновку, где gcc режет программу на разделы и обрабатывает их параллельно. На маленькой программе разделов один, и плата за компоновку видна. Поэтому флаг включён умолчанием, а не спрятан в отдельную строку; кому нужна быстрая сборка — make CFLAGS='-std=c99 -O2', и это написано в самом Makefile.

Вторая правка платит вторым проходом проверки типов на переднем крае: отметка кладётся по её выводу, а раньше этот проход почти всегда пропускался (арифметика есть почти в каждой программе, а частичные формы — редко). Замерено чередованием двух деревьев, 7 кругов, медиана полного времени процесса flang emit c:

Семнадцать миллисекунд на самом большом файле — против семнадцати секунд, которые на нём же тратит cc.

Изъятие: снять правку — замер обязан вернуться

Правило репозитория: правка, от снятия которой ничего не меняется, ничего и не держит. Проверено тремя сборками ОДНОЙ программы, чередующимися внутри круга, 9 кругов:

Снятие отметки возвращает коллатц ровно на уровень «только -flto» (411 против 396 в отдельном замере — разница внутри разброса). Ответы у всех трёх сборок на всех задачах одинаковы: по одному различному значению на задачу.

Что осталось прежним

• Контрольная сумма сходится у всех восьми сборок на всех задачах — стенд это сверяет сам, расхождений ноль;
• счётчики шагов не тронуты: замер показал, что они внутри разброса прибора, и убирать их не надо;
• сторож объявленной меры остался и по-прежнему дорог: доказанный НОД 238,2 мс против обычного 78,6, то есть в 3,03 раза. Прежде было 448,2 против 149,6 — 3,00 раза. Обе записи ускорились примерно одинаково, и доля сторожа не изменилась;
• память не менялась вовсе: ни одна из двух правок не трогает ни ширину значения, ни область памяти на вызов.

Как мерили

Машина. AMD EPYC 7742, два сокета, 64 ядра на сокет, 256 логических процессоров, 499 ГиБ памяти, Linux 7.0.0-29-generic.

Версии.

tsc не измерен и не оценён. В репозитории нет каталога node_modules, глобально установлены только npm и corepack. Ставить TypeScript ради замера значило бы мерить не ту машину, на которой всё остальное; сказать «примерно столько же, сколько…» значило бы выдать догадку за прогон.

Шум, и его здесь много. Машина занята другими работами: во время замеров средняя загрузка держалась между 100 и 190, и в списке процессов постоянно висели чужие счётные задачи по 100–260 % ЦП каждая. Поэтому:

• сборки и языки чередуются внутри каждого круга, а не меряются блоками — иначе всплеск нагрузки достался бы целиком одному участнику;
• приводится медиана, а рядом минимум и максимум, а не среднее: одно попадание в чужой всплеск сдвигает среднее и не сдвигает медиану;
• размах между минимумом и максимумом доходит до 30 %, и разницу меньше 10 % этот замер различать не умеет. Там, где вывод опирается на такую разницу, это сказано прямо.

Все числа — прогоны. В отчёте нет ни одной оценки. Там, где инструмента не оказалось, стоит «нет в системе», а не приблизительное значение.

Что мерили: пять задач, записанных трижды

Задачи выбраны так, чтобы они честно переносились на все три языка и вместе покрывали разные виды работы:

Правило, по которому написаны все три текста: алгоритм один, а записан он так, как эту вещь пишут на данном языке. Никаких библиотечных сокращений ни у кого: ни sorted(), ни Array.prototype.sort, ни регулярных выражений, ни срезов вида lst[0::2]. Разрешены ровно те встроенные формы, которые есть у всех троих: разделение строки и перевод строки в число. Где flang печатается в цикл (хвостовой самовызов), у Python и JS стоит цикл; где flang рекурсирует по-настоящему, рекурсируют и они.

Вход не передаётся снаружи: каждая задача сама строит свои данные одним и тем же линейным конгруэнтным генератором. Иначе замер мерил бы разбор JSON на входе. Выход — одно число, контрольная сумма, чувствительная к порядку: печать стотысячного списка съела бы больше, чем сама сортировка.

Сравнение проверяется, а не обещается. Все восемь сборок обязаны дать одно и то же число на каждой задаче; харнесс это сверяет и объявляет замер недействительным при расхождении. Расхождений нет ни одного.

Тексты — в benchmarks/zamer-skorosti/programs/: zadachi.flang (432 строки), zadachi.py (218), zadachi.mjs (181) и etalon.c (242). Последний — те же пять задач, написанные на C руками; без него отставание flang не разложить на «своё» и «общее для всех компилируемых языков». Полные тексты Python и JavaScript — в приложении в конце этого отчёта.

Две задачи записаны на flang ДВАЖДЫ — и это главный приём всего замера. Сортировка: обычной функцией и тотальной с топливом. НОД: обычной функцией и тотальной с объявленной мерой (убывает б), то есть со сторожем в рантайме. Одно и то же вычисление, одна и та же контрольная сумма, разница только в том, доказано ли завершение. Цена доказуемости тут не рассуждается — она вычитается.

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

Вычёркивание сделано макросами в файле МОДУЛЯ, а не в рантайме: сам рантайм обязан собираться обычным, иначе в нём нечего было бы звать. Все восемь сборок дают одинаковые ответы.

Время компиляции

Итог: путь от исходника до работающей программы

Медиана из 5 прогонов, миллисекунды, полное время процесса.

Точки сравнения на той же машине, в том же чередовании:

python3 -c pass и node -e "" не компилируют ничего — это чистая цена запуска, и сравнивать её с нашим полным путём напрямую бессмысленно. Полезна она как мера того, сколько стоит просто добраться до кода: наш flang check на самом маленьком файле — 123 мс, из них 40–50 мс — старт Node и ещё около 50 мс — чтение 1,6 МиБ собственных модулей компилятора (parser.mjs 218 КиБ, types.mjs 266 КиБ и остальные; замерено пятью прогонами: 42, 54, 52, 59, 40 мс). То есть до первой полезной работы уходит около 100 мс, и от размера программы это не зависит вовсе.

Главное про компиляцию: платим мы не за проверки, а за cc

На самом большом файле репозитория весь наш передний край — 1 197 мс, а сборка порождённого C — 16 996 мс. Мы — 7 % пути, компилятор C — 93 %.

Почему так: 4 548 строк flang превращаются в 29 719 строк C (6,5 раза), и это не считая рантайма, который печатается к каждой программе целиком. У self/parser.flang — 4 336 строк flang → 31 486 строк C, 7,3 раза.

Из чего складываются эти 17 секунд — поштучным замером объектов:

Сумма — 12,7 с, а make -j4 в таблице выше дал медиану 17,0 с при разбросе [10,4 … 26,1]: поштучный замер сделан отдельно и лёг к нижнему краю разброса. Шум на этой машине именно такой, и приукрашивать его нечем.

Наш C при этом дешевле обычного в пересчёте на строку: порождённый модуль — 0,39 мс/строку, рантайм — 0,38, а написанный руками etalon.c — 1,32 (компиляция без линковки; сам запуск cc стоит 0,03 с). Порождённый код многословный, но простой: оптимизировать в нём почти нечего. Семнадцать секунд берутся из объёма, а не из сложности.

Окупается ли компиляция вообще

Сравнивать нашу компиляцию с python3 -c в разах бессмысленно: у Python и Node её нет. Осмысленное сравнение — сколько прогонов нужно, чтобы разовая плата за компиляцию вернулась выигрышем в работе.

Программа замера (zadachi.flang, 432 строки) компилируется за 1 297 мс (emit 223 + make 1 074). Дальше каждый прогон дешевле или дороже, чем у соперника, — и вот на сколько:

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

Как это выглядит после двух правок из раздела «Что делать» (сборка flang-lto-без-типов):

Против Node не окупается по-прежнему ни одна: на всех пяти задачах Node остаётся быстрее даже исправленного flang (от −19 мс на НОД до −328 на дереве).

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

Разложение переднего края по шагам

Внутри одного процесса, медиана из 7 прогонов, миллисекунды. Первый прогон в процессе («холодный») стоит в 1,5–4 раза дороже — движок ещё не видел этого кода; для пользователя, который зовёт flang один раз, настоящее время именно холодное, и оно приведено отдельной строкой.

Что здесь видно.

Доказательства не стоят почти ничего. На самом большом файле анализ тотальности, обязательства, ядро доказательств и законы вместе — 15,8 мс из 520 мс переднего края, то есть 3 %. А от полного пути до работающей программы (18 193 мс) это 0,09 %. Проверка предъявленных доказательств (proofterm.mjs) — 0,10 мс.

Дорого — разбор. Лексер плюс разбор плюс связывание (а связывание это тот же разбор, только импортированных файлов) — 286 мс из 520, 55 %. Дальше генератор кода — 115 мс, 22 %.

Постоянная часть генератора — 4 мс на любую программу. Это чтение рантайма (9 628 строк C) с диска и проверка его на сырые двунаправленные управляющие символы при каждом вызове. От размера программы не зависит.

Рост нелинейный, но умеренный: от 43 строк до 4 548 (в 106 раз) передний край вырос с 12 до 520 мс, то есть в 43 раза. По функциям — с 2 до 545 (272 раза) при том же росте времени в 43 раза.

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

• Харнесс разбирает исходник дважды: один раз чтобы показать цену разбора, второй — чтобы собрать программу для остальных шагов. На types.flang это лишние 48 мс из 520.
• Строка «всего» — это время внутри уже запущенного процесса. Процесс целиком (flang emit c = 1 197 мс) добавляет к нему старт Node, чтение модулей компилятора и запись 2 МиБ файлов на диск.

Время работы

Медиана из 11 прогонов, миллисекунды, полное время процесса — от запуска до ответа. Разделять «запуск» и «счёт» здесь нечестно: у собранного бинарника запуск почти бесплатен, а у Python и Node он стоит заметных миллисекунд, и это их настоящее свойство. Пустая задача (запуститься и ничего не сделать) стоит: flang 5,4, эталон на C 4,1, python 18,7, node 40,5 мс.

Во сколько раз медленнее:

Разброс (минимум … максимум по 11 прогонам) доходит до 30 % — например, у «дерева» flang дал [643 … 963]. Поэтому таблица выше говорит о разах, а не о процентах, и все выводы ниже опираются на разницы больше разброса.

Где мы медленнее и почему

Коллатц — худшая наша задача, и она же самая показательная. Ни одной ячейки памяти под данные, только арифметика и вызовы: 10,3 раза против Node и 31 раз против C. Причина видна прямо в порождённом коде — вот тело цикла:

for (;;) {
  FL_TRY(fl_tick(ctx, "Шагов Коллатца", error));
  fl_value fl_t16 = fl_nothing();
  FL_TRY(fl_lte(ctx, n, fl_number(1.0), &fl_t16, error));
  bool fl_t17 = false;
  FL_TRY(fl_cond(ctx, fl_t16, &fl_t17, error));
  ...
      FL_TRY(fl_div(ctx, n, fl_number(2.0), &fl_t20, error));

Каждое n делить на 2 — это вызов функции из другой единицы трансляции, которая берёт два значения по 32 байта, проверяет у обоих тег, делит два double, кладёт результат по указателю и возвращает статус. Компилятор cc подставить её на место не может: рантайм лежит в отдельном .c, а межмодульная оптимизация не включена. sizeof(fl_value) — **32 байта против 8 у double**.

Дерево — вторая по тяжести (2,2 раза против Python), и там же худшая память. Узел дерева в flang — это fl_variant (24 байта) плюс три fl_field по 40 байт = 144 байта на узел против 24 байт у структуры на C. Отсюда и таблица памяти.

НОД и строки почти догоняют Python (1,04 и 1,16) — и по понятной причине: в НОД внутренний цикл короткий (среднее число витков Евклида — единицы), а в строках заметная часть работы уходит на встроенные формы рантайма (разделение пятнадцатимегабайтной строки, перевод куска в число), то есть на обычный компилированный C, а не на порождённый.

Пиковая память

/usr/bin/time, максимальный резидентный размер, МиБ:

Где данных нет (коллатц, НОД), мы ровно на уровне C. Где данные есть — мы в 12 раз тяжелее Python на сортировке и в 16 раз на дереве. Это арена: она не отдаёт ничего до конца вызова, поэтому каждая промежуточная копия остаётся лежать.

Арена: там, где это уже не «в разы», а «не работает»

Взята «Сортировка вставками» из flang/examples/rosetta/quicksort.flang — тотальная, доказанная структурно, написанная прямо, без единой хитрости. То есть не надуманный случай, а обычная программа на этом языке.

Восемь-девять раз на удвоение входа, то есть рост кубический. Сверх таблицы: на 4 000 элементах эта же программа набрала 178 ГиБ и не досчитала за две с половиной минуты — процесс пришлось снять, чтобы не уронить машину.

Алгоритм здесь квадратичен по времени, и это нормально; кубическая ПАМЯТЬ — целиком следствие двух решений рантайма: арена не освобождает промежуточное, а «Приписать в начало» у списка-массива копирует. Оба решения объяснены в шапке flang_runtime.h честно и обоснованно — но цена у них такая.

Что из этого цена доказуемости, а что недоделанность

Здесь три отдельных прибора, и каждый мерит свою вещь вычитанием.

Прибор 1: счётчик шагов, счётчик глубины, сторож стека

Это то, без чего объявленные пределы (FLANG_RECURSION_LIMIT) перестали бы быть пределами. Вычеркнуто тремя способами — от «не считать» до «убрать вызовы целиком»:

Разница между первым и последним столбцом — 0,9 … 8,9 %, и она целиком внутри разброса. Что это именно шум, видно по двум местам, где вычёркивание работы сделало программу МЕДЛЕННЕЕ: на коллатце сборка с выключенным счётом дала 652 мс против 641 у базовой, на сортировке сборка с вычеркнутым fl_tick — 348 против

1. Физически такого быть не может; значит и разницы в другую сторону этот

прибор на таких величинах не различает.

Вывод: счётчики стоят неотличимо от нуля. Их убирание не купило бы ничего, а стоило бы объявленных гарантий.

Отдельная заметка на будущее. Счётчик шагов нужен обычным функциям: они вправе не завершаться, и без него напечатанная программа крутилась бы вечно вместо FLANG_RECURSION_LIMIT. У тотальной функции завершение доказано, и счётчик там логически избыточен — но fl_tick печатается ей ровно так же (в zadachi.flang его несут и «Через один», и «Слить с топливом», обе доказанные). Это несогласованность, а не расход: убрать её значит выиграть ноль. Приводится потому, что «доказано, а всё равно проверяем» — единственное такое место, найденное замером, и оно ничего не стоит.

Доля в превышении над написанным руками C:

Прибор 2: сторож объявленной меры — и вот он дорог

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

Доказательство утроило время функции. Это честная цена, а не изъян: без него тотальная на IEEE-754 была бы ложным обещанием (остатки пары (φ, 1) не кончаются никогда), и сторож переводит ложь в отказ FLANG_MEASURE. Но цена именно такая, и её надо знать.

Считая от эталона на C: доказанный НОД превышает его на 430 мс (479,1 − 48,9), и из этих 430 мс 322 мс — сторож (479,1 − 156,5), то есть 75 %. Остальные 25 % — та же недоделанность, что и везде.

Прибор 3: приём «топливо»

Сортировка слиянием, записанная обычной функцией и тотальной с топливом. Тот же алгоритм, тот же ответ:

Топливо здесь — не украшение подписи: доказанная запись на каждом уровне склеивает две половины в список-топливо для слияния, и это лишний проход по всем данным.

Насколько всё это распространено в корпусе

Свод npm run proof:ledger по 162 файлам, 2 799 функциям:

Параметр-топливо встречается в корпусе у 5 функций (fibonacci, 704-binary-search, primes-by-trial-division и две в merge-sort).

Итого 71 функция из 2 799 — 2,5 % платит за доказуемость что-то измеримое. Остальные 97,5 % платят счётчиками, а те неотличимы от нуля.

Что остаётся: недоделанность

Всё, что не объяснено выше, — а это от 91 % (строки) до 99 % (сортировка) превышения над написанным руками C. Разбирается она тем же вычитанием:

Четыре причины, в порядке измеренного вклада:

1. Межмодульной оптимизации нет. Рантайм и модуль программы лежат в разных единицах трансляции, поэтому cc не может подставить fl_add на место вызова. Один флаг -flto даёт 1,03–1,60 раза.

2. Проверки типов делаются дважды. fl_add перед каждым сложением смотрит теги обоих значений — те самые типы, которые тайпчекер уже доказал на исходнике. Выключение этих проверок даёт ещё 1,09–3,15 раза (сверх -flto). Вместе две правки дают 1,83 раза геометрическим средним и до 4,95 раза на арифметике.

3. Значение упаковано широко. sizeof(fl_value) = 32 байта, double = 8. Узел варианта с тремя полями = fl_variant (24) + 3 × fl_field (40) = 144 байта против 24 у структуры на C. Это же объясняет и память: сортировка 192 МиБ против 6 у C, дерево 330 против 66.

4. Арена не отдаёт ничего до конца вызова. Отдельно от упаковки: даже узкие значения, положенные в арену, останутся лежать. Кубический рост на «Сортировке вставками» — целиком отсюда.

Причины 3 и 4 — это уже не флаг и не двести строк; это перестройка представления значений и памяти рантайма, то есть отдельная работа. Но и она относится к недоделанности, а не к гарантиям: ни одно обещание языка от ширины fl_value не зависит.

Ответ одним абзацем

На 97,5 % функций корпуса доказуемость стоит неотличимо от нуля и по компиляции (3 % переднего края, 0,09 % полного пути), и по работе (1–9 %, и всё это внутри разброса). На оставшихся 2,5 % она стоит дорого и честно: сторож объявленной меры утраивает функцию, топливо добавляет треть. Всё прочее отставание — недоделанность. Из восьмикратного разрыва с написанным руками C две механические правки снимают 1,8 раза (геометрическим средним), и одна из них — две строки.

Что делать: выигрыш на единицу работы

1. -flto в порождаемом Makefile — две строки — СДЕЛАНО

Коммит c903983. Ниже — как рассуждали до работы; что вышло, сказано в разделе «После правок». Одна оговорка отсюда не подтвердилась: «сборка дольше примерно вдвое» верно только для маленькой программы, а на большом файле сборка стала вдвое быстрее. Поэтому флаг сделан умолчанием, а не отдельной строкой CFLAGS_RELEASE, как рекомендовалось ниже.

Сейчас порождаемый Makefile пишет CFLAGS ?= -std=c99 -Wall -Wextra -Werror -pedantic -O2. Строка живёт в двух местах, потому что бэкенд C существует в двух реализациях, и они сверяются побайтово: flang/src/emit/c.mjs:825 и flang/self/emit-c.flang:3211. Ни один тест не проверяет текст этих флагов — тесты собирают своими.

Проверено прогоном: с полным строгим набором (-Werror -pedantic) -flto собирается без единого предупреждения и даёт тот же ответ.

Цена: сборка небольшой программы дольше примерно вдвое (0,79 → 1,40 с, медиана из трёх). На фоне 17 секунд make для self/types.flang это заметно, и потому разумнее сделать -flto не умолчанием, а отдельной строкой CFLAGS_RELEASE — чтобы автор выбирал между «собрать быстро» и «работать быстро».

2. Не печатать проверку тега там, где тип уже доказан — СДЕЛАНО

Коммиты 2854d2b и следующий за ним. Оценка ниже — 150–250 строк — оказалась близкой: около 100 строк кода в эталоне (types.mjs и emit/c.mjs, без комментариев) плюс около 160 в копии на самом flang, потому что отдавать типы наружу таблицей не понадобилось вовсе. В компиляторе уже был проход, который кладёт на узлы дерева отметки анализа (доказанная непустота, проверка убывания меры), и тип лёг туда же третьей отметкой. Верхняя граница выигрыша, обещанная ниже, взята полностью: коллатц 3,26 раза сверх -flto при обещанных 3,15.

fl_add, fl_sub, fl_mul, fl_div, fl_mod, fl_lt, fl_lte, fl_gt, fl_gte начинаются с fl_numbers, который смотрит теги обоих аргументов. Эту же работу тайпчекер уже проделал на исходнике — и выбросил результат: checkTypes возвращает { ok, diagnostics, types }, где types — только сигнатуры функций, а типов на узлах выражений нет вовсе.

Значит правка не в одну строку в case "binary" (emit/c.mjs:1248), как хотелось бы, а из двух частей: тайпчекер обязан начать отдавать выведенный тип на узел, а генератор кода — читать его и печатать fl_number(a.as.number + b.as.number) вместо вызова. Честная оценка — 150–250 строк в types.mjs и emit/c.mjs, плюс столько же в самоприменённой копии, если держать побайтовое совпадение.

Верхняя граница выигрыша измерена сборкой, где проверки выключены совсем (сверх -flto): коллатц 3,15×, дерево 1,19×, нод 1,19×, строки 1,14×, сортировка 1,09×.

Оговорка, которую пришлось дописать по итогу работы: проверку тега снять совсем НЕЛЬЗЯ, и это выяснилось прогоном корпуса. Граница входа сверяет не всё — вид неизвестно (параметр полиморфизма и значение-функция) она пропускает, потому что сверять его не с чем. Через эту дверь чужое значение доезжает до доказанного места: «Отобразить» от Удвоить и [1, "два"] со снятой проверкой отвечало 1.32e-309 вместо FLANG_TYPE — то есть отказ менялся на неверный ответ. Поэтому снят не тег, а межмодульный вызов: сверка печатается одним if в теле вызывающего, а арифметика считается выражением. Цена честности измерена: коллатц 132,5 мс вместо 121,6 без сверки — 9 %, и 2 % по геометрическому среднему.

3. Арена и ширина значения — это уже работа, а не правка

sizeof(fl_value) = 32 байта при 8 у double; узел варианта с тремя полями — 144 байта при 24 у структуры C. Арена не отдаёт ничего до конца вызова. Отсюда и 12–16-кратная память, и кубический рост на «Сортировке вставками».

Оценивать это числом строк было бы враньём: и то и другое — решения архитектуры, и оба обоснованы в шапке flang_runtime.h (одно представление вместо двух; никаких утечек на раннем возврате по ошибке). Но записать их следует как долг: ни одно обещание языка от них не зависит, то есть платится за них не доказуемость, а её отсутствие в этом месте.

Чего делать НЕ надо

Убирать счётчик шагов, счётчик глубины или сторож стека. Замер показал, что все трое вместе стоят меньше разброса между прогонами, а держат они объявленный предел, без которого напечатанная программа в C падала бы по SIGSEGV вместо FLANG_RECURSION_LIMIT. Это единственное место отчёта, где ответ — «оставить как есть», и он подкреплён тремя независимыми абляциями.

Как повторить

Все скрипты лежат в benchmarks/zamer-skorosti/. Ни один не трогает репозиторий: всё собирается в указанный каталог.

# 1. Собрать восемь вариантов одной программы плюс эталон на C
benchmarks/zamer-skorosti/sobrat.sh /tmp/zamer

# 2. Время работы: пять задач, восемь сборок, чередование, 11 кругов
node benchmarks/zamer-skorosti/rabota.mjs /tmp/zamer --кругов 11

# 3. Пиковая память тех же задач
node benchmarks/zamer-skorosti/pamyat.mjs /tmp/zamer

# 4. Рост арены на «Сортировке вставками» (с пределом адресного пространства)
mkdir -p /tmp/zamer/qs
node flang/bin/flang.mjs emit flang/examples/rosetta/quicksort.flang \
  --target c --out /tmp/zamer/qs --max-steps 2000000000
make -C /tmp/zamer/qs -j4
benchmarks/zamer-skorosti/arena.sh /tmp/zamer/qs

# 5. Время компиляции: итоги процессами, вместе с точками сравнения
node benchmarks/zamer-skorosti/kompilyaciya.mjs --кругов 5

# 6. Время компиляции: слагаемые внутри одного процесса
node benchmarks/zamer-skorosti/faz.mjs flang/self/types.flang --повторов 7

# 7. Свод по корпусу: чем несётся обещание «тотальная» и где сторожа
npm run proof:ledger

Разовая проба одной задачи на трёх языках, с временем и памятью:

benchmarks/zamer-skorosti/probe.sh /tmp/zamer/base/flang_cli "Обход дерева" дерево 100000

**Перед node в ручных прогонах ставьте LC_ALL=C.UTF-8** — имена задач записаны кириллицей, и без этого аргументы приезжают побитыми. Харнессы ставят её сами.

Приложение: тексты на Python и JavaScript

Приложены целиком, чтобы сравнение можно было проверить, а не принять на веру. Текст на flang — benchmarks/zamer-skorosti/programs/zadachi.flang (432 строки), эталон на C — benchmarks/zamer-skorosti/programs/etalon.c (242 строки).

zadachi.py

# SPDX-FileCopyrightText: 2026 Digitable (Marat Zimnurov)
# SPDX-License-Identifier: BSD-2-Clause
"""Те же четыре задачи, что в zadachi.flang, на Python 3.

Правило перевода — шаг в шаг:
  • где flang печатается в цикл (хвостовой самовызов) — здесь цикл;
  • где flang рекурсирует по-настоящему — здесь рекурсия;
  • никаких библиотечных сокращений: ни sorted(), ни срезов вида lst[0::2].
    Разрешены ровно те встроенные формы, которые есть и у flang: разделение
    строки (str.split ↔ «разделить … по …») и перевод строки в число
    (int ↔ «к числу»).

Запуск:  python3 zadachi.py ЗАДАЧА РАЗМЕР
         python3 zadachi.py коллатц 20000
Печатает одно число — ту же контрольную сумму, что и остальные два языка.
"""
import sys

A = 25173
C = 13849
M = 65536


def chisla(skolko, zerno):
    """«Числа»: хвостовой самовызов — значит цикл."""
    out = []
    x = zerno
    for _ in range(skolko):
        x = (A * x + C) % M
        out.append(x)
    return out


def otpechatok(elementy):
    """«Отпечаток»: свёртка."""
    acc = 0
    for e in elementy:
        acc = (acc * 31 + e) % 1000003
    return acc


# ── задача 1: счёт на числах ────────────────────────────────────────────────


def shagov_kollatca(n):
    """«Шагов Коллатца»: хвостовой самовызов — цикл."""
    nabrano = 0
    while n > 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        nabrano += 1
    return nabrano


def kollatc(predel):
    """«Сумма Коллатца»: тоже хвостовой, но вызов внутрь — настоящий."""
    summa = 0
    tekushchee = 1
    while tekushchee <= predel:
        summa += shagov_kollatca(tekushchee)
        tekushchee += 1
    return summa


# ── задача 1-бис: НОД ───────────────────────────────────────────────────────
# У flang эта задача записана дважды — с объявленной мерой (и сторожем в
# рантайме) и без неё. Здесь запись одна: понятия «доказано» у Python нет, и
# изображать его было бы подлогом. Ответ у всех записей один.


def nod(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def nod_zadacha(predel):
    summa = 0
    tekushchee = 1
    while tekushchee <= predel:
        summa += nod(tekushchee, 40902)
        tekushchee += 1
    return summa


# ── задача 2: сортировка слиянием ───────────────────────────────────────────


def cherez_odin(elementy, s):
    """«Через один»: каждый второй, начиная с позиции s."""
    out = []
    i = s
    n = len(elementy)
    while i < n:
        out.append(elementy[i])
        i += 2
    return out


def sliyanie(pervyy, vtoroy):
    """«Слияние»: хвостовой самовызов — цикл с двумя указателями."""
    out = []
    i = 0
    j = 0
    n = len(pervyy)
    m = len(vtoroy)
    while i < n and j < m:
        if pervyy[i] <= vtoroy[j]:
            out.append(pervyy[i])
            i += 1
        else:
            out.append(vtoroy[j])
            j += 1
    while i < n:
        out.append(pervyy[i])
        i += 1
    while j < m:
        out.append(vtoroy[j])
        j += 1
    return out


def sortirovka(elementy):
    """«Сортировка»: рекурсия настоящая — значит и здесь рекурсия."""
    if len(elementy) <= 1:
        return elementy
    levaya = cherez_odin(elementy, 0)
    pravaya = cherez_odin(elementy, 1)
    return sliyanie(sortirovka(levaya), sortirovka(pravaya))


# ── задача 3: обход дерева ──────────────────────────────────────────────────
# Лист — None, узел — кортеж (ключ, слева, справа). Значения неизменяемы, как
# у flang: вставка переписывает путь и возвращает новое дерево.


def vstavit(derevo, novyy):
    if derevo is None:
        return (novyy, None, None)
    kl, l, p = derevo
    if novyy < kl:
        return (kl, vstavit(l, novyy), p)
    return (kl, l, vstavit(p, novyy))


def sobrat_derevo(skolko, zerno):
    derevo = None
    x = zerno
    for _ in range(skolko):
        x = (A * x + C) % M
        derevo = vstavit(derevo, x)
    return derevo


def summa_dereva(derevo):
    if derevo is None:
        return 0
    kl, l, p = derevo
    return (kl + summa_dereva(l)) + summa_dereva(p)


def glubina_dereva(derevo):
    if derevo is None:
        return 0
    _, l, p = derevo
    gl = glubina_dereva(l)
    gp = glubina_dereva(p)
    return (gl if gl > gp else gp) + 1


def obhod_dereva(skolko):
    derevo = sobrat_derevo(skolko, 12345)
    return summa_dereva(derevo) + 1000000 * glubina_dereva(derevo)


# ── задача 4: разбор строк ──────────────────────────────────────────────────


def udvoit_tekst(tekst, raz):
    for _ in range(raz):
        tekst = tekst + "," + tekst
    return tekst


def razbor_strok(raz):
    tekst = udvoit_tekst("17,42,8,99,3,71,25,60,14,88", raz)
    acc = 0
    for kusok in tekst.split(","):
        acc = (acc * 31 + int(kusok)) % 1000003
    return acc


# ── точки входа ─────────────────────────────────────────────────────────────


def sortirovka_zadacha(skolko):
    return otpechatok(sortirovka(chisla(skolko, 12345)))


ZADACHI = {
    "коллатц": kollatc,
    "нод": nod_zadacha,
    "сортировка": sortirovka_zadacha,
    "дерево": obhod_dereva,
    "строки": razbor_strok,
}


def main(argv):
    if len(argv) != 3 or argv[1] not in ZADACHI:
        sys.stderr.write("использование: zadachi.py {%s} РАЗМЕР\n" % "|".join(ZADACHI))
        return 2
    sys.setrecursionlimit(200000)
    sys.stdout.write("%d\n" % ZADACHI[argv[1]](int(argv[2])))
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

zadachi.mjs

/* SPDX-FileCopyrightText: 2026 Digitable (Marat Zimnurov) */
/* SPDX-License-Identifier: BSD-2-Clause */
/**
 * Те же четыре задачи, что в zadachi.flang, на JavaScript (Node.js).
 *
 * Правило перевода — шаг в шаг, как и у zadachi.py:
 *   • где flang печатается в цикл (хвостовой самовызов) — здесь цикл;
 *   • где flang рекурсирует по-настоящему — здесь рекурсия;
 *   • никаких библиотечных сокращений: ни Array.prototype.sort, ни filter по
 *     индексу. Разрешены ровно те встроенные формы, которые есть и у flang:
 *     String.prototype.split (↔ «разделить … по …») и Number (↔ «к числу»).
 *
 * Запуск:  LC_ALL=C.UTF-8 node zadachi.mjs ЗАДАЧА РАЗМЕР
 * Печатает одно число — ту же контрольную сумму, что и остальные два языка.
 */
const A = 25173
const C = 13849
const M = 65536

function chisla(skolko, zerno) {
  const out = []
  let x = zerno
  for (let i = 0; i < skolko; i += 1) {
    x = (A * x + C) % M
    out.push(x)
  }
  return out
}

function otpechatok(elementy) {
  let acc = 0
  for (const e of elementy) acc = (acc * 31 + e) % 1000003
  return acc
}

/* ── задача 1: счёт на числах ─────────────────────────────────────────────── */

function shagovKollatca(n) {
  let nabrano = 0
  while (n > 1) {
    n = n % 2 === 0 ? n / 2 : 3 * n + 1
    nabrano += 1
  }
  return nabrano
}

function kollatc(predel) {
  let summa = 0
  for (let tekushchee = 1; tekushchee <= predel; tekushchee += 1) {
    summa += shagovKollatca(tekushchee)
  }
  return summa
}

/* ── задача 1-бис: НОД ────────────────────────────────────────────────────── */
/* У flang эта задача записана дважды — с объявленной мерой (и сторожем в
   рантайме) и без неё. Здесь запись одна: понятия «доказано» у JavaScript нет,
   и изображать его было бы подлогом. Ответ у всех записей один. */

function nod(a, b) {
  while (b !== 0) {
    const ost = a % b
    a = b
    b = ost
  }
  return a
}

function nodZadacha(predel) {
  let summa = 0
  for (let tekushchee = 1; tekushchee <= predel; tekushchee += 1) summa += nod(tekushchee, 40902)
  return summa
}

/* ── задача 2: сортировка слиянием ────────────────────────────────────────── */

function cherezOdin(elementy, s) {
  const out = []
  for (let i = s; i < elementy.length; i += 2) out.push(elementy[i])
  return out
}

function sliyanie(pervyy, vtoroy) {
  const out = []
  let i = 0
  let j = 0
  while (i < pervyy.length && j < vtoroy.length) {
    if (pervyy[i] <= vtoroy[j]) {
      out.push(pervyy[i])
      i += 1
    } else {
      out.push(vtoroy[j])
      j += 1
    }
  }
  while (i < pervyy.length) {
    out.push(pervyy[i])
    i += 1
  }
  while (j < vtoroy.length) {
    out.push(vtoroy[j])
    j += 1
  }
  return out
}

function sortirovka(elementy) {
  if (elementy.length <= 1) return elementy
  const levaya = cherezOdin(elementy, 0)
  const pravaya = cherezOdin(elementy, 1)
  return sliyanie(sortirovka(levaya), sortirovka(pravaya))
}

/* ── задача 3: обход дерева ───────────────────────────────────────────────── */
/* Лист — null, узел — массив [ключ, слева, справа]. Значения не правятся:
   вставка переписывает путь и возвращает новое дерево, как у flang. */

function vstavit(derevo, novyy) {
  if (derevo === null) return [novyy, null, null]
  const [kl, l, p] = derevo
  if (novyy < kl) return [kl, vstavit(l, novyy), p]
  return [kl, l, vstavit(p, novyy)]
}

function sobratDerevo(skolko, zerno) {
  let derevo = null
  let x = zerno
  for (let i = 0; i < skolko; i += 1) {
    x = (A * x + C) % M
    derevo = vstavit(derevo, x)
  }
  return derevo
}

function summaDereva(derevo) {
  if (derevo === null) return 0
  return derevo[0] + summaDereva(derevo[1]) + summaDereva(derevo[2])
}

function glubinaDereva(derevo) {
  if (derevo === null) return 0
  const gl = glubinaDereva(derevo[1])
  const gp = glubinaDereva(derevo[2])
  return (gl > gp ? gl : gp) + 1
}

function obhodDereva(skolko) {
  const derevo = sobratDerevo(skolko, 12345)
  return summaDereva(derevo) + 1000000 * glubinaDereva(derevo)
}

/* ── задача 4: разбор строк ───────────────────────────────────────────────── */

function udvoitTekst(tekst, raz) {
  for (let i = 0; i < raz; i += 1) tekst = tekst + "," + tekst
  return tekst
}

function razborStrok(raz) {
  const tekst = udvoitTekst("17,42,8,99,3,71,25,60,14,88", raz)
  let acc = 0
  for (const kusok of tekst.split(",")) acc = (acc * 31 + Number(kusok)) % 1000003
  return acc
}

/* ── точки входа ──────────────────────────────────────────────────────────── */

const ZADACHI = {
  "коллатц": kollatc,
  "нод": nodZadacha,
  "сортировка": (skolko) => otpechatok(sortirovka(chisla(skolko, 12345))),
  "дерево": obhodDereva,
  "строки": razborStrok,
}

const [, , zadacha, razmer] = process.argv
if (zadacha === undefined || ZADACHI[zadacha] === undefined) {
  process.stderr.write(`использование: node zadachi.mjs {${Object.keys(ZADACHI).join("|")}} РАЗМЕР\n`)
  process.exit(2)
}
process.stdout.write(`${ZADACHI[zadacha](Number(razmer))}\n`)