Память в flang: регионы, подсчёт ссылок и статически ограниченный режим

Исследование. Ничего в компиляторе не менялось; всё, что здесь измерено, измерено на неизменённом дереве и воспроизводимо командами, приведёнными в тексте.

Вопрос владельца звучал так: какие у flang гарантии по памяти и годится ли идея «выделять память на категорию» — то есть группировать значения по времени жизни, а не отслеживать каждое по отдельности. Идея настоящая, в языкостроении она называется региональным управлением памятью (regions, arenas), и ниже разобрано, применима ли она к flang, чем за неё платят и что вместо неё.

Короткий ответ

Регионы в flang уже есть — ровно один. Печать в C выделяет всё бампом указателя в арене и освобождает её целиком одним действием после того, как вызывающий забрал результат. Это в точности «выделить область, поработать, освободить целиком»; отличие от MLKit только в том, что область одна на весь вызов, а не выведена компилятором по временам жизни.

И это уже больно. Замер ниже: сортировка слиянием четырёх тысяч чисел занимает 1655 МиБ пика кучи при живом результате в 125 КиБ. Утечек нет — valgrind даёт ноль байт в ноль блоков, — но пик кучи в тринадцать с половиной тысяч раз больше полезных данных, и растёт он быстрее квадрата. Программа не течёт; она просто ничего не отдаёт до конца вызова.

Автоматический вывод регионов (как в MLKit) делать не надо, и довод не «дорого», а «мимо». Регионы по построению привязаны к области ВИДИМОСТИ, а наша беда — значение мертво, но имя ещё в области видимости. На нашем замере вывод регионов воспроизвёл бы известный, названный в литературе режим отказа MLKit, а не удачный случай (раздел 4).

Зато измерен вариант в двадцать раз дешевле, и он сработал. Регион на ВЫЗОВ с копией результата наружу — тот же приём, что уже сделан в конкурентности (шаг А2), только применённый к обычному вызову функции. Прототип на напечатанном C: 1 653 МиБ → 3,4 МиБ (486×), время втрое быстрее, а не медленнее, ответы совпали на всех входах сетки, valgrind чист. Объём работы — ~200–300 строк в четырёх файлах, из них по пятнадцать строк в двух точках печати (раздел 3 и раздел 5, вариант Г).

Подсчёт ссылок для flang полон — циклов в значениях flang построить нечем, и это доказано, а не предположено (раздел 2). Он лечит ту же беду и без изъянов копирования, но стоит 2 000–3 500 строк против 200. Следующий шаг, не первый.

А для «кода для ракет» ответ вообще другой, и рекомендация выше туда не годится. Стандарты просят не меньше памяти, а известное заранее число, и запрещают динамическое выделение прямым текстом — включая свои собственные распределители (рабочая группа MISRA отвечала на этот вопрос дословно). Нужен не распределитель поумнее, а режим со статически доказанным пределом. У flang он выразим: в языке уже есть два объявляемых предела того же вида (ящик процесса, запас витков), а 42,2 % корпуса уже сегодня получают многочленную оценку сверху. Оценка работы — ~2 300–3 700 строк. Разбор — в разделе 6.

1. Точка отсчёта: как устроена память в напечатанном C

Что там сейчас

Читать: flang/src/emit/c/flang_runtime.h (строки 32–52 — объяснение решения, 101–133 — API арены) и flang/src/emit/c/flang_runtime.c (строки 54–202 — реализация).

Устройство простое и честно описанное в самом рантайме:

• fl_arena — односвязный список кусков по 64 КиБ минимум (FL_CHUNK_MIN, flang_runtime.c:55), выдача идёт бампом указателя (fl_arena_alloc, строка 81);
• освобождения по одному значению нет вообще. Есть fl_arena_reset (строка 177) — помечает все куски пустыми, память системе не возвращает — и fl_arena_release (строка 188) — отдаёт всё системе через free;
• единственная поблажка — fl_arena_extend (строка 152): продлить на месте можно только последнюю выдачу. Ради неё же заведён fl_grow — хвостовой запас у массива списка, чтобы добавить в цикле не копировал список целиком. Без этого список из n элементов, собранный n вызовами «добавить», оставлял бы ~16·n² байт мусора (комментарий в flang_runtime.h:47–52);
• подсчёта ссылок нет. Сборщика мусора нет. free вызывается ровно в одном месте — в fl_arena_release.

Прогонщик (flang/src/emit/c/flang_cli.c:747) делает fl_arena_reset перед каждым запросом и fl_arena_release (строка 903) в конце процесса.

Почему так сделано, и это правильное решение для своей задачи

Обоснование в рантайме (flang_runtime.h:32–45) верное: программа flang — чистое вычисление без ввода-вывода и изменяемого состояния, значит время жизни всего построенного равно времени жизни вызова. Ручной malloc/free по сгенерированному коду дал бы утечку на каждом раннем возврате по ошибке, а возврат по ошибке возможен почти в каждом узле.

Утечек в смысле «забыли free» здесь нет и быть не может. Это надо сказать прямо, потому что вопрос был именно про гарантии: арена не может потерять блок — она не знает про отдельные блоки.

Замер

Программа-замер (Замер сортировки) строит список из n псевдослучайных чисел, сортирует слиянием (алгоритм дословно из flang/examples/rosetta/merge-sort.flang, все функции сортировки — тотальные) и складывает. Печать в C, сборка штатным Makefile бэкенда (-std=c99 -O2 -Wall -Wextra -Werror -pedantic), измерение valgrind 3.26.0, gcc 15.2.0.

Утечки (valgrind --leak-check=full --show-leak-kinds=all), построение списка из 20 000 чисел:

in use at exit: 0 bytes in 0 blocks
total heap usage: 11 allocs, 11 frees, 3,219,952 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

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

Пик кучи (valgrind --tool=massif), сортировка слиянием. fl_value занимает 32 байта (замерено sizeof), «живо» ниже — это размер отсортированного списка, то есть всё, что вызов обязан был бы удержать при идеальном управлении памятью:

Пик растёт примерно как n^2,3 — быстрее квадрата, при том что сам алгоритм имеет сложность n·log n. Причина не в алгоритме, а в том, что ни один промежуточный список не переиспользуется: каждое слияние строит новый, старые остаются лежать в арене до конца вызова.

Тот же расчёт, где промежуточных структур нет — просто построение списка:

Здесь арена ведёт себя отлично: трёхкратный перерасход, линейный рост. Работают fl_arena_extend и fl_grow.

Вывод замера, который и есть суть проблемы: арена дёшева и безопасна на прямолинейном коде и катастрофична на коде, который строит промежуточные структуры. А промежуточные структуры — это и есть нормальный функциональный код: в чистом языке всякое «изменение» списка есть построение нового.

Сравнение с целью со сборщиком мусора

Та же программа, напечатанная в JavaScript, тот же n = 4000, тот же ответ (199 943 020 в обеих целях — цели сходятся):

То есть примерно 207 МБ против 1655 МиБ, восьмикратная разница — и это при том, что значение в V8 представлено объектом, который заведомо жирнее 32-байтного fl_value. Цель со сборщиком мусора сегодня объективно бережнее к памяти, чем главная цель печати.

Другой замер того же, менее зависимый от представления: какой предел кучи нужен, чтобы расчёт вообще дошёл до конца (node --max-old-space-size, уменьшаем, пока не упрёмся в Reached heap limit):

Разрыв растёт: вчетверо на тысяче, тринадцатикратно на четырёх тысячах.

Машина при замерах была занята другими задачами. Числа massif от загрузки не зависят (massif считает байты, а не время), а вот RSS у node может гулять на десятки мегабайт — цифру 250 МБ надо читать как «сотни мегабайт», а не как точное значение. Числа по арене воспроизводимы точно: massif на одном и том же входе даёт один и тот же байт.

Проверка: не идиома ли виновата

Сортировка выше — тотальная, и тотальной её делает приём «топливо»: рядом с настоящими аргументами едет список, у которого на каждом витке берётся хвост (объяснение — в шапке flang/examples/rosetta/merge-sort.flang). Естественное подозрение: может, память ест топливо, а не арена.

Замерил. Тот же алгоритм, те же входы, но все функции обычные и топлива нет (ответ совпадает до цифры — 199 943 020):

Топливо не стоит ничего — в цели C хвост списка это срез (указатель плюс длина), а не копия. Вся цена — арена. Доказательство тотальности бесплатно по памяти, и это отдельно приятная новость.

2. Что у flang уже есть для анализа времён жизни

Это главный довод, который просили проверить, а не принять. Проверил.

Чего НЕТ

Анализа побега (escape analysis), времён жизни, владения, заимствования, линейности, регионов в типах — в дереве нет ничего из этого. Ни в flang/src/, ни в flang/self/, ни в flang/proof/. Слова, которые ищутся поиском, находятся, но каждое — про другое: alias в types.mjs это синонимы типов, escape — экранирование строк, область в parser.mjs — стек лексических областей видимости.

Значит вопрос «сколько живёт значение» сегодня решён указом, а не анализом: всё живёт до конца вызова.

Что есть, и это больше, чем я ожидал

1. Замыканий в языке нет и не будет. Это самое важное. Значение-функция в flang — это ТЕГ: функция «Удвоить» не строит замыкания, а называет объявленную функцию (flang/SPEC.md:220–240). Тег представлен вариантом без полей (flang/src/parser.mjs:3885, flang/src/defunc.mjs:740–756 — «Захватывать нечего: замыканий в языке нет»). Анонимных функций в разборе нет вовсе — грепом по parser.mjs ни лямбда, ни lambda. И это не «пока не сделали», а записанное решение: в flang/cat/HOF.md в разделе «Чего решено не делать никогда» стоит «замыканий над локальными именами» и «каррирования по умолчанию».

Почему это решает половину задачи: самое больное место всякого регионального вывода — замыкание, захватившее значение из области. Оно требует поместить само замыкание в регион, живущий не меньше самого долгоживущего захваченного значения, и именно оттуда берётся «загрязнение регионов» — когда почти всё уезжает в глобальную область. У flang такого случая просто нет.

2. Высший порядок снимается дефункционализацией ДО печати. flang/src/defunc.mjs:116 — один проход на все восемь целей: ф от 5 превращается в «применить 1» от ф и 5, диспетчер с конечным списком случаев. После прохода в программе не остаётся ни fnref, ни apply — она снова первопорядковая. Значит анализу не с чем бороться: «кто кого зовёт» известно.

3. Компиляция и так всепрограммная. Раздельной компиляции у языка нет и не планируется (flang/cat/HOF.md, flang/src/link.mjs:3–22 — связывание это слияние объявлений). Обычно это минус; для вывода регионов это подарок: межпроцедурный анализ не упирается в границы модулей.

4. Значения — конечные деревья, строгие, неизменяемые. flang/SPEC.md:155–168: Значение := Скаляр | Список | Запись | Вариант. Ни ссылки, ни ячейки, ни ленивого вычисления (flang/src/interpret.mjs:400, 458 — строгий порядок слева направо), пусть не рекурсивен (interpret.mjs:370–375). Циклическое значение построить нечем. Это прямой ответ на вопрос из задания: подсчёт ссылок для flang полон, отдельный сборщик циклов не нужен.

5. Всепрограммный граф вызовов уже строится — трижды. Основной — в flang/src/totality.mjs:376–536; ребро несёт не только «кто кого», но и происхождение каждого аргумента (totality.mjs:1620–1630). Каркас «сводка на функцию, потом неподвижная точка по графу» написан дважды и обкатан: flang/src/failures.mjs:649–687 (замыкание достижимых отказов) и flang/src/bounded.mjs:259–298 (оценка витков, снизу вверх с мемоизацией).

6. Есть оценка размеров. flang/src/bounded.mjs (716 строк) считает полиномиальную оценку числа витков от размера входа, а заодно содержит размерСверху (строки 597–640) — верхнюю оценку размера значения выражения — и размерЗначения (215–230). Для «сколько байт нужно региону» это заготовка.

7. Есть штатный способ донести результат анализа до печати. totality.mjs:567–650 (markGuards) навешивает пометки на узлы вызова, а defunc.mjs:272 по ним ставит сторожа. Аннотации регионов ехали бы тем же путём.

Чего из этого хватает для вывода регионов, а чего нет

Просили конкретно, поэтому конкретно.

**Анализ происхождения (totality.mjs:1592–1721) для регионов НЕ годится, и причина принципиальная, а не «мало доделали».**

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

И хуже того: происхождение теряется ровно там, где происходит выделение. Смотрите collectCalls: case "construct", case "record", case "list", case "fold", case "map", case "filter", case "call" — все возвращают null, то есть «про это значение не известно ничего». А это в точности полный список мест, где рантайм зовёт fl_arena_alloc. Анализ слеп именно к тем значениям, которые регионам надо было бы размещать.

Второе: происхождение считается **только для функций, помеченных тотальная** (totality.mjs:399). Обычные функции не обходятся вовсе. По корпусу тотальных 79 % (2203 из 2788 объявлений), но в flang/self/ — 69 %, то есть в самом компиляторе каждая третья функция анализу невидима.

Третье: результат не сохраняется по выражениям. collectCalls возвращает происхождение, но наружу уходит только происхождение аргументов вызовов (state.calls[i].origins). Таблицы «узел → факт» в репозитории нет ни одной — регионам она нужна обязательно, потому что регион приписывается месту выделения, а не функции.

Итог по пункту 3. Переиспользовать можно каркас (граф вызовов, неподвижная точка, способ доставить пометки в печать) и решётку сведений — но сам анализ побега пришлось бы писать с нуля. Это новый проход, а не расширение существующего. Зато условия для него необычно хорошие: нет замыканий, нет высшего порядка после понижения, нет раздельной компиляции, нет циклов в данных.

И ещё одно: половина работы уже сделана — в конкурентности

Про это стоит знать отдельно, потому что это прецедент внутри самого репозитория.

flang/conc/RESILIENCE.md, шаг А2 («Арена на пробег: черновик, копия наружу, сброс», строки 450–522). Устройство: обработчик процесса считает в черновой арене; когда он вернулся, живое — ровно новое состояние и остаток ящика; оно переезжает в свободную половину кучи, занятая сбрасывается целиком, половины меняются местами. Отправленное уезжает копией в кучу адресата.

Это и есть региональная схема с копированием на границе, и законна она ровно тем же доводом, что нужен MLKit: «пока обработчик не вернулся, наружу не ушло ничего, поэтому границу между черновиком и „наружу“ есть где провести» (RESILIENCE.md:463–466). Только границу здесь провели динамически — глубоким копированием, — а не статическим анализом.

Замеренный результат (там же, таблица на строке 470):

Обратите внимание на две последние строки: постоянная цена пробега упала (черновик сбрасывается и остаётся горячим в кэше), а заплатили копированием груза. И там же честно записана беда, которую копирование принесло: переезд копирует весь ящик на каждом пробеге, поэтому при растущей очереди прогон идёт квадратично (13,21 с на 32 000 пробегов против 0,18 с на 4 000).

Что из этого следует для нашего вопроса. Схема «регион плюс копия наружу» в flang уже работает, уже измерена и уже показала свою цену: копия на границе стоит O(размера живого) и при неудачном раскладе даёт квадрат. Именно эту копию и убирает вывод регионов — он доказывает, что копировать не надо. То есть у предполагаемой работы есть измеренная в этом же репозитории цена того, что она сэкономит.

3. Опыт: регион на вызов с копией наружу

Прежде чем сравнивать три варианта из задания, я поставил опыт — потому что из разбора выше следовал очень дешёвый четвёртый, и его стоило измерить, а не обсуждать.

Приём. Тот же, что шаг А2 в конкурентности, но применённый не к пробегу процесса, а к обычному вызову функции. У каждой функции в напечатанном C уже есть тонкая обёртка вокруг тела:

fl_status ..._sortirovka(fl_ctx *ctx, fl_value elementy, fl_value *result, fl_error *error) {
  FL_TRY(fl_enter(ctx, "Сортировка", error));
  { const fl_status status = ..._sortirovka_body(ctx, elementy, result, error);
    fl_leave(ctx); return status; }
}

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

Почему это законно. Ровно тем доводом, которым законен А2: значения flang неизменяемы, замыканий нет, ссылок наружу нет — значит в момент возврата из вызова достижимо ровно то, что лежит в результате. Аргументы вызова лежат ниже отметки (их построил вызывающий) и откатом не задеты.

Что вышло. Прототип: 150 строк нового C (отметка, откат, глубокая копия, решение по порогу) плюс механическая правка обёрток — её сделал скрипт, потому что она и должна быть механической, её печатал бы бэкенд. Порог 256 КиБ, запасная арена одна на программу. Ничего в компиляторе не менялось: правка легла на напечатанный C в каталоге замеров.

Рост из «быстрее квадрата» стал линейным.

Проверки. Ответы совпадают с неправленой сборкой на всех десяти входах сетки (n = 1, 2, 3, 7, 13, 64, 100, 257, 999, 1500). valgrind --leak-check=full на прототипе: 0 bytes in 0 blocks, ERROR SUMMARY: 0 errors from 0 contexts, 31 выделение и 31 освобождение.

Время (n = 2000, восемь прогонов на сборку двумя заходами, машина занята другими задачами):

Разброс по времени — около 20 %, и это шум занятой машины; отношение между сборками (втрое) устойчиво во всех восьми прогонах. Максимальная RSS совпала до килобайта во всех прогонах: 286 720 против 2 048, то есть 140×.

Не «дешевле, чем боялись», а втрое быстрее. Причина та же, что назвал А2 в конкурентности: арена, которую откатывают, остаётся горячей в кэше, а растущая покупает у malloc новые куски и гуляет по всей памяти.

Чего этот опыт НЕ доказывает — и это надо прочесть

Опыт поставлен на одной программе одним алгоритмом, и относиться к его числам надо соответственно. Но у приёма есть и принципиальные изъяны, и они важнее узости выборки:

1. Копия наружу теряет разделение. Значения flang — деревья, но в памяти они могут быть графами: один и тот же подсписок разрешено положить в результат десять раз одним указателем. Глубокое копирование разворачивает такой граф в дерево, и в худшем случае это экспоненциальный взрыв. Ровно та же беда есть и у уже сделанного А2, и там она не названа. Это самый весомый довод в пользу того, что копия наружу — не окончательное решение, а хороший запас времени.
2. Порог — это настройка, а настройка это непредсказуемость. 256 КиБ здесь взяты с потолка. Программа, у которой каждый вызов остаётся чуть ниже порога, не получит ничего.
3. Копия стоит O(размера результата) на каждом откате. У функции, которая возвращает большой список и мало мусорит, это чистый убыток. Здесь спасает порог, но он же — пункт 2.
4. Квадрат при накоплении. А3 в конкурентности уже поймал этот случай: если на каждом витке копировать растущее живое, прогон идёт квадратично (13,21 с на 32 000 пробегов против 0,18 с на 4 000). Тот же капкан стоит и здесь.

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

4. Как регионы работают на самом деле, и где они ломаются

Как компилятор доказывает, что из области ничего не утекло

Основа — Tofte и Talpin, POPL'94 («Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions») и журнальная версия в Information and Computation 132(2), 1997.

Устройство в двух словах. К обычному типу приписывается место — переменная региона ρ. Тип функции несёт латентный эффект φ: множество пометок put(ρ) («эта функция кладёт что-то в ρ») и get(ρ) («читает из ρ»). Дальше всё держится на одном правиле — том самом, ради которого схема и существует:

      TE ⊢ e ⇒ e′ : µ, φ        φ′ = Observe(TE, µ)(φ)
              {ρ1, …, ρk} = frv(φ \ φ′)
———————————————————————————————————————————————————————
   TE ⊢ e ⇒ letregion ρ1···ρk in e′ end : µ, φ′

По-человечески: область ρ можно закрыть вокруг выражения тогда и только тогда, когда ρ не встречается свободно ни в типе результата, ни в типовом окружении. Первое запрещает вернуть наружу указатель в область. Второе запрещает закрывать область, до содержимого которой ещё дотянется остальная программа через какое-нибудь имя в области видимости. Авторы формулируют это дословно: «ρ is purely local to the evaluation of e′, in the sense that the rest of the computation will not access any value stored in ρ».

Теорема корректности — Theorem 4.1 в POPL'94. Интересна не столько она, сколько то, что при её доказательстве обычная схема «свойство сохраняется» не сработала. Цитата авторов: «no matter how we tried to define the notion of consistency, we were unable to prove such a preservation theorem… consistency, in an absolute sense, is not preserved — rather it decreases monotonically. The saving fact is that there is always enough consistency left!» Согласованность пришлось определить относительно эффекта остатка программы: представления обязаны совпадать только там, где остаток программы будет читать.

И самая важная тонкость, которую почти все пересказывают неверно. Схема НЕ запрещает висячим указателям существовать. Она гарантирует только, что их никогда не разыменуют. Подпись к рисунку в статье 1997 года — дословно: «Notice the dangling, but harmless, pointer». Из-за этого добавление сборщика мусора потребовало отдельного дополнительного условия: сборщик ходит по указателям, и «безвредный» висячий указатель становится смертельным. В сегодняшнем MLKit это ключ -gc, который выключает флаг dangling_pointers.

Где ломается — это важнее плюсов

Корень всех бед — «Ground Rule» из руководства MLKit (§7.2): «as long as a value variable is in scope, the value bound to it at runtime will remain allocated».

Регионы привязаны к области ВИДИМОСТИ, а не к ЖИВОСТИ. Значение, которое больше никогда не понадобится, но чьё имя ещё в области видимости, не освобождается. Всё остальное — следствия.

Пять задокументированных мест, где это выходит боком.

1. Значение живёт дольше области. Канонический пример из руководства MLKit — решето Эратосфена: let val rest = sift(x,xs) in sieve(cp rest, x::p) end. Авторы пишут: «because rest is in scope at the recursive application of sieve, the list that is bound to rest will stay allocated for the duration of that call, which is in fact the remainder of the entire computation!» Лечение — переписать исходник, вынеся let внутрь вызова. Алгоритм тот же, семантика та же, память — O(1) против O(n).

2. Замыкание, захватившее значение из области. Регион захваченного значения свободен в типе замыкания, значит letregion вокруг него поставить нельзя, значит захваченное живёт столько же, сколько само замыкание — и не по объектам, а регионами целиком. Для flang это неприменимо: замыканий в языке нет (раздел 2). Это единственный из пяти пунктов, который нас не касается.

3. Функции высшего порядка — самое жёсткое. Region-полиморфной в схеме Tofte–Talpin может быть только функция, связанная через letrec. Параметр — не может. Из POPL'94 дословно: «all the results of the plus operation are put into one region, because the operator is a lambda-bound parameter of the fold operation and hence cannot be region-polymorphic». В версии 1997 года это развёрнуто с асимптотикой: foldl (op ^) "" l даёт Θ(N²) памяти, и чтобы получить Θ(N), надо «specialize foldl to ^, uncurry the resulting function and turn it into a region endomorphism» — то есть отказаться от свёртки и расписать её руками.

Для flang это наполовину неприменимо, наполовину — да. Встроенные отобразить/отфильтровать/свёртка принимают тело, а не функцию, и разворачиваются в цикл прямо в напечатанном C — параметра-функции там нет вовсе. Но дефункционализация проблему не снимает, а переносит: все теги одной арности идут через один диспетчер применить N, и унификация склеила бы регионы всех его случаев в один. Сегодня это ни на что не влияет — функции-значения не использует ни один исходник репозитория, кроме flang/stdlib/higher-order.flang.

4. Рекурсия, при которой область растёт без предела. Пример из ретроспективы авторов (2004): sumit с аккумулятором. «Region inference would force the two branches of the conditional to put their results in the same region… 100 pairs would pile up in the region that contained the initial pair». Костыль — storage mode analysis (attop/atbot/sat), и вот приговор ему от самих авторов: «The storage mode analysis is probably not the best way of handling tail recursion; it is complicated and vulnerable to program changes.»

5. Данные, разделяемые между областями, склеиваются унификацией. Вывод регионов в MLKit построен на унификации, без подтипирования. Любое место, где два типа обязаны совпасть, сливает регионы. Пример из руководства: if true then cp1 l else l — «because the two branches of the conditional are required to have the same region-annotated type with place, l and cp1 l are forced to be in the same regions». Одна as-связка в образце меняет функцию из «кладёт в свежий регион» в «дописывает в регион аргумента» — и это не ошибка, а поведение по построению.

Плюс отдельный класс, признанный в самой первой статье: дисциплина стека проигрывает там, где времена жизни не вложены. POPL'94: «creating a large argument for a function which only uses it for a small part of its activation leads to waste of memory». Проверено снаружи — Aiken, Fähndrich, Levien, PLDI'95: на их сетке «maximum storable values» для Appel(100) их схема даёт 306, схема Tofte–Talpin — 20 709.

Чем MLKit за это платит и когда честно сдаётся

Платит объёмом компилятора. Замер по клону github.com/melsman/mlkit v4.7.22: src/Compiler/Regions/ — 20 836 строк SML в 38 файлах, то есть 35,7 % всего компилятора (58 424 строки). Из одиннадцати печатаемых фаз компилятора восемь — региональные: spreading, region inference, multiplicity inference, K-нормализация, storage mode, dropping of regions, physical size inference, call conversion. Опубликованной цифры по доле регионов нет, эта измерена агентом на клоне.

Платит сложностью алгоритма. Вывод разбит надвое ради завершаемости: алгоритм S (синтаксически направленный) — O(n³), алгоритм R (неподвижная точка для полиморфной рекурсии) — O(n⁴). На программе simple в 1 148 строк это 11,73 с плюс 14,21 с (замер TOPLAS'98, HP 9000s700).

Платит неполнотой. TOPLAS'98 дословно: «The algorithm does not always infer principal types. The incompleteness of the algorithm has to do with the handling of polymorphic recursion.» Существование главных типов для правил Tofte–Talpin — открытая проблема до сих пор.

А сдаётся он — зовёт сборщик. Hallenberg, Elsman, Tofte, PLDI'02, «Combining Region Inference and Garbage Collection». Мотив в самой статье: «can a combination of garbage collection and region inference reduce the need for tuning programs?» Числа оттуда (Table 1 против Table 2, резидентная память):

И Table 3 — кто именно освободил память: на logic вывод регионов утилизирует 0,1 % мусора, остальные 99,9 % вычищает сборщик; на tyan — 7,7 % против 92,3 %. Это не «регионы плюс лёгкая подстраховка», это «на этом классе программ регионы не работают вовсе».

Отдельно стоит знать ещё две вещи из той же статьи, потому что они портят простую картину:

• быстрее всего по времени — чистые регионы без сборщика («the fastest execution is obtained by relying solely on region-based memory management»), просто они текут;
• регионы плюс сборщик часто ХУЖЕ по памяти, чем один сборщик: tyan −107 %, vliw −45 %, mlyacc −38 %, «mostly due to waste in regions».

Профиль самого компилятора MLKit при сборке (подпись к Figure 5 в PLDI'02): «The global region r1 is by far the largest. **Without the garbage collector, region r1 would grow without ever decreasing.**» Компилятор, написанный авторами схемы, под чистыми регионами течёт.

Что об этом сказали сами авторы

Ретроспектива Tofte, Birkedal, Elsman, Hallenberg (Higher-Order and Symbolic Computation 17(3), 2004) — там есть раздел «что разочаровало», и первый пункт читается так:

Unless combined with garbage collection, leaving region inference completely to the compiler is probably not a good idea. It makes region-annotated terms unnecessary big and vulnerable to program changes.

И общее ощущение:

here was a technology, which could produce astonishing results when it worked well, but it was too difficult to hit those precise points where the results were good. Moreover, if it was difficult for the people who developed the technology, what would be the chances of success with the average programmer?

Знаменитая история «10 строк из 58 000» (программа AnnoDomini) обычно пересказывается без второй половины. Полностью она такая: правкой десяти строк из 58 000 удалось убрать течи, «On the other hand, it required a regions expert to locate and change the 10 lines», и компиляция этих 58 000 строк занимала полтора часа.

Взгляд со стороны — команда Cyclone, PLDI'02: «Programming with the Kit is convenient, as the compiler automatically infers all region annotations. However, small changes to a program can have drastic, unintuitive effects on object lifetimes. Thus, to program effectively, one must understand the analysis and try to control it indirectly by using certain idioms.»

Куда пришла эта линия за тридцать лет

1994  чистый автоматический вывод
1997  «It would probably be better to allow programmers to state their
       intentions directly»                                    (IC 132(2))
2002  добавили сборщик, потому что вывод один не тянет         (PLDI'02)
2004  «leaving region inference completely to the compiler is
       probably not a good idea»                               (ретроспектива)
2024  добавили ЯВНЫЕ аннотации регионов и эффектов             (ReML, POPL'24)

MLKit жив (v4.7.22, релиз 1 августа 2026, поддерживает Мартин Эльсман), но сборщик в нём выключен по умолчанию, а свежая работа автора — ReML, расширение SML явными аннотациями регионов, с мотивировкой: сделать программы «robust to changes in the program source code and to compiler updates, including compiler optimisations».

Cyclone: та же дуга, только начатая с другого конца

Cyclone (Jim, Grossman и др., USENIX'02, PLDI'02) — это регионы, объявленные руками и проверенные типами. Полезны три их вывода.

Первый: аннотаций нужно немного, но цифра «8 %» вводит в заблуждение. Абстракт PLDI'02: перенос C на Cyclone требует правки около 8 % строк, из которых лишь 6 % — собственно региональные аннотации (Гроссман в диссертации сводит это к «одна явная аннотация примерно на 200 строк»). Но в поздней работе той же команды (Sci. Comput. Program. 62(2), 2006) есть таблица с драйверами Linux, и там доля изменённых строк — 36–57 %.

Второй: они попробовали схему Tofte–Talpin и отступили. Дословно, PLDI'02: «In our original Cyclone design, we tried to use TT-style effect variables. However, we found that the approach does not work well in an explicitly typed language» — и дальше две причины: инварианты алгоритма унификации трудно удержать в явно типизированном языке, а эффектные переменные в интерфейсах библиотек «making the libraries harder to understand and use».

Третий, и для нас главный: лексических регионов им не хватило. ISMM'04, дословно: «Unfortunately, LIFO arenas suffer from several well-known limitations that we encountered repeatedly. In particular, they are not suited to computations such as server and event loops.» И механика провала: если объявить область внутри цикла, между витками нельзя пронести ничего; если снаружи — всё живёт до конца цикла; «For loops that do not terminate, such as a server request loop or event loop, this is a disaster as the LIFO restriction can lead to unbounded storage requirements.»

Поэтому в Cyclone добавили уникальные указатели, swap, заимствование alias и — подсчёт ссылок (регион ` RC ` с ручными alias_refptr/drop_refptr`). Их же честный отчёт о цене: перенос BetaFTPD на подсчёт ссылок «required 21 % of the code to be changed, significantly more than the other ports… we were forced to spend some time tracking down memory leaks that arose from failing to decrement a count».

Сегодня на сайте Cyclone написано: «Cyclone is no longer supported… Several of Cyclone's ideas have made their way into Rust.»

Rust — это регионы, только проверяемые, а не выводимые

Не метафора: модуль в rustc называется буквально «Region inference (NLL)», а 'a: 'b читается «регион 'a переживает регион 'b». Отличий от MLKit два, и оба принципиальные:

1. Rust не выводит, ГДЕ размещать. letregion в MLKit решает и размещение, и точку освобождения. Времена жизни в Rust только проверяют, что ссылка не переживёт объект; куда положить объект, пишет программист (Box, Vec, стек). Отсюда — нет ни multiplicity inference, ни storage mode analysis, ни physical size inference, ни потерь на «region waste».
2. Вывод не пересекает границу функции. Сигнатура — контракт; тело вызываемого при проверке вызывающего не читается.

Заплатил Rust за это владением и правилом «либо разделяешь, либо меняешь» (&mut не может быть разделён). Из-за этого двусвязный список, граф и любые внутренние алиасы требуют Rc/RefCell/unsafe — ровно та стена, в которую упёрся Cyclone. Для flang эта цена нулевая: разделяемого изменяемого состояния в языке нет вовсе. Но и выигрыш от неё нулевой по той же причине.

Главный вывод раздела — и он про flang

Разберём замеренную беду из раздела 1 по напечатанному C, а не на словах. Вот внутренность Слить дословно из сгенерированного файла:

fl_value fl_t24 = fl_nothing();
FL_TRY(..._slit(ctx, h1, vtoroy, &fl_t24, error));          /* список длины k   */
return ..._pripisat_v_nachalo(ctx, g1, fl_t24, result, error); /* строит длины k+1 */

fl_t24 мёртв в ту секунду, когда «Приписать в начало» его дочитала. Но на уровне flang это имя, связанное пусть, и оно в области видимости ровно до конца вызова.

Что сделал бы вывод регионов. Результат «Приписать в начало» возвращается наружу, значит его регион свободен в типе результата, значит по боковому условию правила letregion закрыть его внутри Слить нельзя. А fl_t24 пришёл из рекурсивного Слить, чей регион результата унификация склеит с тем же самым. Итог: промежуточные списки всех n уровней оказываются в одном регионе, живущем до возврата самого верхнего Слить. **Это буквально пример sumit из ретроспективы авторов и пример concat с Θ(N²) из статьи 1997 года** — то есть известный, названный, задокументированный режим отказа регионов.

Что сделал бы подсчёт ссылок: счётчик fl_t24 падает до нуля сразу после того, как «Приписать в начало» с ним закончила, — освобождение немедленное, пик O(n).

Что сделала копия наружу (замерено): на возврате из Слить достижим только результат, всё остальное откатывается. 486×.

Итого замеренная беда — это значение, которое мертво, но ещё в области видимости: результат Слить на уровне k+1 больше не нужен, как только Приписать в начало его прочитала, но имя ещё живо, вызов ещё не вернулся.

Регионы привязаны к области видимости, а не к живости — по построению, а не по недоделке. Ground Rule запрещает освобождать то, чьё имя в области видимости. Значит вывод регионов на нашем замере дал бы мало или ничего — это в точности форма примера с решетом из руководства MLKit и примера sumit из ретроспективы, то есть известный режим отказа, а не удачный случай.

А мой опыт из раздела 3 сработал (486×) именно потому, что он не региональный в этом смысле: он опирается на живость (что достижимо из результата), а не на область видимости. Тем же свойством обладает и подсчёт ссылок.

Вывод регионов — не тот инструмент для той беды, которая у нас измерена.

5. Четыре варианта, цена каждого и рекомендация

Просили сравнить три. Их и сравниваю, но добавляю четвёртый — тот, что измерен в разделе 3, потому что без него сравнение было бы нечестным.

Откуда берутся оценки объёма

Не из воздуха, а из двух измеримых обстоятельств этого репозитория.

Первое: всё, что меняет напечатанный код, платится дважды. Эталон на JavaScript (flang/src/) и самоприменение на flang (flang/self/) обязаны давать один и тот же C побайтово — это проверяется неподвижной точкой раскрутки (flang/self/SPEC.md, «Критерий готовности»). Плюс третьим шагом заново печатается замороженная точка раскрутки bootstrap/ — 5,8 МБ, 7 файлов. Множитель по опыту дерева: totality.mjs 1780 строк → totality.flang 2858 (×1,6); defunc.mjs 831 → defunc.flang 929 (×1,1); emit/c.mjs 1885 → emit-c.flang 3386 (×1,8).

Второе: память в рантайме уже сосредоточена. Во всём flang_runtime.c (2103 строки) ровно 12 вызовов fl_arena_alloc, а конструкторов значений пять: fl_text, fl_list_alloc, fl_record_new, fl_variant_new, fl_list_slice. Напечатанный код malloc не зовёт никогда — только эти функции. Значит смена схемы памяти — это в первую очередь правка рантайма, а не правка печати. Это очень хорошая новость для любого из вариантов.

Вариант А. Регионы с автоматическим выводом (как MLKit)

Для сравнения: у MLKit региональная машинерия — 20 836 строк, 35,7 % всего компилятора. Оценка выше вчетверо меньше, и это не оптимизм: у flang нет замыканий, нет настоящего высшего порядка после понижения, нет модулей и нет раздельной компиляции. Но она честна ровно настолько, насколько честен любой счёт до написания первой строки.

Против, и это решает вопрос: раздел 4 показал, что на нашей измеренной беде вывод регионов дал бы мало или ничего. Беда — «значение мертво, но имя ещё в области видимости», а регионы по построению привязаны к видимости (Ground Rule). Плюс приговор самих авторов после десяти лет работы: «leaving region inference completely to the compiler is probably not a good idea», плюс неполнота алгоритма, плюс открытая до сих пор проблема главных типов, плюс O(n⁴).

Отдельно про самоприменение. Компилятор flang — это flang/self/, 56 474 строк, из которых треть функций обычные, не тотальные. Алгоритм со сложностью O(n⁴) на дереве такого размера — риск, который надо было бы мерить до, а не после. MLKit тратил полтора часа на 58 000 строк.

Вердикт: нет. Дорого, ненадёжно, и — главное — мимо цели.

Вариант Б. Регионы, объявленные вручную (как Cyclone)

Кода вдвое меньше, чем в варианте А. Но:

1. Это новые слова в языке, а язык весь построен на том, что программист пишет предметную область, а не машину. Слово регион в языке, где нет даже слова указатель, — это смена жанра, а не добавление возможности.
2. Библиотеки дороже приложений. Отчёт Cyclone: аннотации «impose negligible burden on the application writer, but a somewhat larger burden on the library writer». Наша библиотека — stdlib и self.
3. Своя же команда Cyclone признала, что лексических регионов не хватает: «not suited to computations such as server and event loops… this is a disaster as the LIFO restriction can lead to unbounded storage requirements». У flang есть процессы и есть цикл событий.

Вердикт: нет. Меняет язык ради результата, который в самой Cyclone признан недостаточным.

Вариант В. Подсчёт ссылок (как Lean 4)

Сначала главный вопрос из задания — и ответ на него положительный.

Циклов в значениях flang не бывает, значит подсчёт ссылок ПОЛОН — отдельный сборщик циклов не нужен. Доказательство прямое, не рассуждение по аналогии:

• грамматика значений закрыта: Значение := Скаляр | Список | Запись | Вариант (flang/SPEC.md:155–168) — ни ссылки, ни ячейки, ни изменяемого поля;
• вычисление строгое, слева направо (flang/src/interpret.mjs:400, 458);
• пусть не рекурсивен: значение считается во ВНЕШНЕЙ среде, и только потом имя связывается для тела (interpret.mjs:370–375);
• ленивых вычислений и отложенных значений нет ни одного;
• изменяемого состояния нет вовсе — из-за этого же анализ завершаемости и стоит на «значения — конечные деревья» (totality.mjs:31–34).

Строится значение строго снизу вверх из уже готовых значений. Замкнуть ссылку на себя нечем. Разделение (один подсписок в двух местах) — сколько угодно, это направленный ациклический граф; цикл — нет.

Оценка объёма:

Цена по скорости. Замера у меня нет, и выдавать оценку за замер я не буду. Известное из литературы: Cyclone, где подсчёт ссылок вводили руками, — «required 21 % of the code to be changed… we were forced to spend some time tracking down memory leaks that arose from failing to decrement a count». У нас счётчики расставлял бы компилятор, так что этой беды не будет; останется цена самих операций на каждой передаче значения.

А вот чего не видно из литературы и что специфично для flang — представление. fl_value это 32 байта, и они заняты целиком:

• список — {items, count, grow}, три слова;
• строка — {utf8, bytes, points}, три слова.

Хвост списка и подстрока — это срезы: указатель внутрь чужого массива. Чтобы уменьшить счётчик, срез обязан знать, где начало владеющего блока, а места под этот указатель у строки нет. У списка место, считайте, есть: поле grow сейчас NULL у всякого среза, и его можно занять под владельца. У строки пришлось бы расширять fl_value до 40 байт — то есть +25 % на КАЖДОЕ значение программы, включая числа.

Это не приговор варианту, но это настоящая цена, которой нет ни в одной статье про Lean 4, потому что там представление другое.

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

Вариант Г. Регион на вызов с копией наружу — измерен

Тот, что в разделе 3. Повторю числа: n = 4000, 1 652,9 МиБ → 3,4 МиБ (486×), время при n = 2000 0,35–0,42 с → 0,11–0,15 с (втрое, устойчиво по восьми прогонам), ответы совпали на десяти входах сетки, valgrind чист.

Это в двадцать-тридцать раз дешевле варианта А и в десять дешевле варианта В — при измеренном результате, которого у А и В нет.

Чего в прототипе не хватает до рабочего состояния — называю поимённо, потому что это и есть остаток работы:

1. **Найденная рассуждением, а не тестом, опасность: fl_grow переживает откат.** Проверено по коду (flang_runtime.c:2005–2060). fl_b_dobavit на быстром пути зовёт fl_arena_extend и тут же **правит grow->capacity на месте**: grow->capacity += grow->capacity. Если сам список и его fl_grow лежат НИЖЕ отметки, а продление случилось ВЫШЕ неё, то откат заберёт продлённую половину, а grow->capacity останется удвоенным — он ниже отметки и откатом не задет. Следующее добавить пройдёт проверку count < grow->capacity и запишет в память, уже выданную кому-то другому.

На моём замере не выстрелило (десять входов, valgrind чист), но это латентная ошибка, а не отсутствующая, и полагаться на то, что она не встретилась, нельзя. Лечится дёшево — запомнить отметку в fl_grow либо запретить fl_arena_extend пересекать отметку, — но лечиться обязана до всякого попадания в дерево.

1. Глубокая копия разворачивает разделяемый подграф в дерево (раздел 3, пункт 1). В худшем случае экспонента. Это же верно и для уже сделанного А2 в конкурентности, где не записано.
2. Порог настройкой. 256 КиБ взяты с потолка; нужен либо обоснованный выбор, либо привязка к размеру куска арены.
3. Квадрат при накоплении — капкан, уже пойманный шагом А3.

Рекомендация

Делать вариант Г. Не делать А. Не делать Б. Вариант В держать как следующий шаг, а не как альтернативу.

Доводы по порядку веса:

1. Только у Г есть замеренный результат на этом дереве. 486× по памяти и втрое по времени — это не оценка, это два прогона valgrind. У А и Б нет ни одного числа, полученного на flang, а у литературных чисел MLKit знак тревожный: вывод регионов утилизирует 0,1 % мусора на logic.
2. Наша беда — не та, которую лечат регионы. Измерено: значение мертво, но имя в области видимости. Регионы привязаны к видимости по построению.
3. Г в двадцать раз дешевле А и ложится в четыре файла, две из которых — по пятнадцать строк в двух точках печати.
4. Приём в этом репозитории уже обкатан. Шаг А2 в конкурентности — та же схема, те же доводы законности, измеренный ноль байт на пробег. Мы бы не вводили новую технику, а распространили сделанную.
5. Г ничего не отнимает. Ни слова в языке, ни строчки в исходниках пользователя, ни одной новой обязанности программиста.

От чего придётся отказаться, если делать Г:

• От обещания «память не хуже, чем у хорошего сборщика». Г — компромисс с порогом, а не гарантия. Программа, чьи вызовы стабильно остаются под порогом, не получит ничего.
• От сохранения разделения при копии. Это настоящая, а не гипотетическая потеря, и она может обернуться взрывом на значениях с сильным разделением.
• От предсказуемости на худшем случае — а это ровно то, что нужно критичным системам. Для них Г не годится, и это подводит к разделу 6.

Когда браться за В (подсчёт ссылок). Когда выстрелит пункт 2 — то есть когда найдётся программа, где копия наружу дороже мусора, который она убирает. Подсчёт ссылок снимает и пункт 2, и пункт 3, и пункт 4 разом, потому что он поштучный и не копирует. Полнота его для flang доказана выше. Но браться за 2 000–3 500 строк, пока 200 строк дают 486×, — это оптимизировать вслепую.

Чего НЕ делать ни в каком случае: вводить в язык слова для регионов (вариант Б). Это единственный из четырёх, который меняет язык, и он же — тот, чью недостаточность признала команда, его придумавшая.

6. Что нужно критичным системам — и почему ответ там другой

Этот раздел отвечает на вопрос владельца «код для ракет» — и ответ здесь не тот, что в разделе 5. Настоящие стандарты просят не «поменьше памяти», а «ноль выделений после старта», и рекомендованный выше вариант Г им не годится по определению: он распределитель памяти времени выполнения.

6.1. Что требуют настоящие стандарты

MISRA C — прямой запрет, и он же закрывает лазейку «напишем свой распределитель».

• Директива 4.12: «Dynamic memory allocation shall not be used», категория Required, анализ Undecidable. Не изменилась ни в MISRA C:2012, ни в MISRA C:2023.
• **Правило 21.3: «The memory allocation and deallocation functions of <stdlib.h> shall not be used», категория Required. То есть директива запрещает приём, а правило — его стандартную реализацию**.
• Правило 17.2: «Functions shall not call themselves, either directly or indirectly» — рекурсия запрещена, категория Required. Это не смежная тема, а та же самая: без рекурсии граф вызовов ациклический, и глубина стека считается статически.
• Правило 18.8: переменной длины массивы запрещены (иначе размер стека не посчитать статически).

И вот главное. Рабочая группа MISRA прямо отвечала на вопрос «а если я напишу свой пул-распределитель, это считается?» — ответ на форуме MISRA:

the headline rule is unambiguous — dynamic allocation shall not be used. This applies to the standard library functions [malloc(), free(), etc] but also to any user-defined equivalent functions.

Ответ MISRA на «сделаем распределитель поумнее» — «он тоже запрещён». Именно поэтому весь раздел 5 к критичным системам не относится.

Обоснование запрета (по разбору Bagnara и др., один из авторов MISRA C:2023, arXiv:2112.12823) — четыре пункта, и они ровно те, что перечислены в задании: исчерпание памяти, фрагментация («free memory can be filled by very small fragments»), недетерминированное время («variable and possibly long latency… This is unacceptable for systems that have to meet hard real-time constraints») и неопределённое поведение при неправильном использовании.

DO-178C (авионика) — НЕ запрещает, а требует доказательств. Сам DO-178C объектный, а не кодировочный стандарт: динамическая память там нигде не запрещена. Требование живёт в §6.3.4.f (таблица A-5, объект 6) — «accuracy and consistency», куда входит анализ стека и памяти, — и в §11.8, который обязывает разработчика написать свой кодировочный стандарт. Запрет, таким образом, приезжает через MISRA или JSF++, которые в этот стандарт и вписывают.

DO-332 (дополнение по объектной технологии) добавляет к DO-178C ровно два объекта, и один из них — про динамическую память: OO.A-7[OO10] / §OO.6.8.1, «Verify the use of dynamic memory management is robust». В приложении OO.D.1.6.1 перечислены семь уязвимостей, каждая с критерием:

И таблица OO.D.1.6.3 — кто за что отвечает при пяти способах выделения (object pooling, stack, scope, manual heap, automatic heap/GC). Про сборщик мусора там сказано ровно то, чего и следовало ожидать: он снимает с прикладного кода почти всё, но перекладывает это на менеджер памяти, «which comes with major challenges for certification»; время сборки в общем случае непредсказуемо (риск g), а перемещение объектов задевает риск f.

А теперь что делают на практике. Обзор AdaCore/Ferrous Systems (Comar, Dross, Gilcher, Moy, «Dynamic Memory Management in Critical Embedded Software»):

Given the difficulty of guaranteeing that these requirements are satisfied, many coding standards for critical software forbid heap allocation either completely or after initialization. The most common pattern allowing heap allocation in critical software consists in an initialization phase where memory is dynamically allocated, and never deallocated.

И там же про сборщик мусора: «In cases where it applies, garbage collection clearly provides the best user experience. But the cost of certifying the MMI prevents this technique from being used in many cases.»

Остальные стандарты — то же самое, разными словами.

• JSF++ (Lockheed Martin, бортовое ПО F-35), правило AV 206: «Allocation/deallocation from/to the free store (heap) shall not occur after initialization.» Обоснование — фрагментация и «non-deterministic delays». Правило AV 119 запрещает рекурсию, с исключением: можно, если доказано, что ресурсов хватит на максимальную глубину.
• «Power of 10» Хольцмана (IEEE Computer 39(6), июнь 2006), правило 3: «Do not use dynamic memory allocation after initialization.» Правило 1 — никакой рекурсии, правило 2 — у каждого цикла статически проверяемый предел витков. И вот ключевая фраза обоснования, ради которой весь раздел:

> In the absence of recursion, an upper bound on the use of stack memory can > be derived statically, thus making it possible to prove that an application > will always live within its resource bounds.

К правилу 1: «Avoiding recursion results in having an acyclic function call graph, which code analyzers can exploit to prove limits on stack use and boundedness of executions.»

• JPL D-60411 (тот же Хольцман), правило 5: «There shall be no use of dynamic memory allocation after task initialization» — и явно про malloc(), sbrk(), alloca().
• NASA F Prime (полётное ПО JPL), сегодня: «Flight Software coding standards forbid dynamic memory allocation outside of system initialization. This is for safety and reliability reasons.»
• IEC 61508-3, таблица B.1: «No dynamic objects» — HR (highly recommended) на SIL 2–4. Но там есть примечание, и оно для нас важнее самого запрета:

> Measures 2 and 3a do not need to be applied if a compiler is used which > ensures that sufficient memory for all dynamic variables and objects will be > allocated before runtime, or which inserts runtime checks.

То есть компилятор, доказывающий предел, снимает запрет. Это ровно та дверь, в которую мог бы войти flang.

• ISO 26262-6:2018, таблица 6, строка 1b: «No dynamic objects or variables, or else online test during their creation» — highly recommended для ASIL B/C/D.

Итог по стандартам, коротко: господствующая практика — не «умный распределитель», а «не выделять ничего после старта». Для этого нужны ровно две вещи: нет выделений после инициализации и нет (или ограничена) рекурсия — вместе они делают граф вызовов ациклическим, а каждый кадр статически измеримым. Всё остальное в этих стандартах (массивы переменной длины, гибкие члены, указатели на функции, alloca) — следствия того же требования.

Оговорка, чтобы не пересолить: новые стандарты для C++ смягчились. MISRA C++:2008 правило 18-4-1 было Required и абсолютным, а в MISRA C++:2023 «Dynamic memory should not be used» — уже Advisory, зато рядом появилось Required «Dynamic memory shall be managed automatically». AUTOSAR C++14 (A18-5-5) требует не запрета, а доказанных свойств: ограниченное худшее время, отсутствие фрагментации, отсутствие исчерпания — и «an executable is supposed to define its maximal memory needs, which are pre-allocated for this executable during its startup».

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

Есть, и он сильнее, чем можно было ожидать.

SCADE / Lustre — существующее доказательство. Генератор кода KCG в SCADE Suite квалифицирован по DO-178C уровня A / DO-330 TQL-1, а исходный язык (Scade 6, потомок Lustre и Esterel) — декларативный потоковый. Ansys описывает свойства порождаемого кода дословно: «static memory allocation, static bounded loops, no recursion», «bounded memory and reaction time» — «guaranteed by construction». В производстве с 1999 года, сотня бортовых изделий.

То есть декларативный язык, компилируемый в статически ограниченную память и сертифицированный по высшему уровню, существует уже двадцать пять лет. Цена: Scade — синхронный потоковый язык. Ни рекурсии, ни динамических структур данных, ни функций высшего порядка; программа — фиксированная сеть уравнений над потоками, работающая по такту.

Что ещё стоит знать из этого ряда:

• Hume (Hammond, Michaelson) — язык уровней: HW → FSM → Template → PR → Full. FSM-Hume даёт жёсткую статическую оценку памяти, отказываясь от рекурсии, высшего порядка и полиморфизма; Template-Hume разрешает только предопределённые комбинаторы с известной стоимостью; Full-Hume — полноценный язык без всяких гарантий. Замысел — не пять языков, а лестница переписывания: писать вне уровней, анализировать, и «where analysis is problematic… offending constructs are reformulated in a lower level». Это ровно та форма «пометки на функции», которую я предложил выше, — и она уже опробована.
• LFPL (Hofmann, Nordic J. Computing 7(4), 2000) — самый резкий пример: компилируется в C, **не содержащий malloc вовсе, потому что «место» — первоклассная величина, которую программа передаёт из рук в руки. Цена названа честно: аффинная линейность (список нельзя использовать дважды, разделения нет), только первый порядок, и ни одна функция не может возвращать больше, чем получила**. Плюс дыра: начальные данные всё-таки создаёт malloc, а размер ячейки — максимум по всем типам программы.
• RAML (Hoffmann) — выводит многочленную оценку по памяти и времени автоматически, но 26 функций из 164 в CompCert (15,8 %) оценки не получают вовсе. Полезный ориентир: даже лучший в своём классе автоматический анализ накрывает не всё.
• Ivory (Galois, SMACCMPilot) и Copilot (Galois/NASA Langley) — встроенные языки, где всё выделение снято в фазу метапрограммы, а остаток работает без кучи и с постоянной памятью.
• **pragma Restrictions в Ada** — самое близкое к «режиму» в промышленном языке: No_Allocators, No_Local_Allocators, **No_Standard_Allocators_After_Elaboration** — буквально правило 3 из «Power of 10» как ключ языка.

И одна отрезвляющая вещь, которая касается нас напрямую. Пометка total в Idris и Agda не даёт никаких гарантий по памяти — только по завершению. Тотальная функция может съесть гиперэкспоненту. **Это ровно про нашу тотальная: 79 % корпуса доказанно завершается, и это НЕ означает, что 79 % корпуса укладывается в известную память. Ценность тотальности здесь другая и тоже большая: она делает законным** применение отдельного анализа ресурсов, который на незавершающейся функции был бы бессмысленным.

6.2. Выразим ли у flang режим «вся память известна на этапе компиляции»

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

Прецедент первый: объявленный ящик. принимает «T» с ящиком N сообщений (flang/conc/SPEC.md:2161, шаг А3 в RESILIENCE.md:524). Довод, ради которого это сделано, записан там прямым текстом и он же — довод всего этого раздела:

Объявленный ящик делает исход свойством ПРОГРАММЫ, а не машины: десятикратная разница в пределе памяти (6 МиБ против 64) не меняет ни числа пробегов, ни состояний, ни отказов — шестнадцать и шестнадцать. Без объявленного ящика тот же залив при 6 и 8 МиБ проходит 13 852 и 27 316 пробегов, то есть отвечает на вопрос «что будет» словами «зависит от того, где запустишь».

Это и есть в точности то, чего требуют критичные системы: не «памяти хватит», а «исход не зависит от того, сколько её на машине».

Прецедент второй: объявленный запас витков. обрабатывает «шаг счёта» с запасом 100000 витков (flang/conc/SPEC.md:186) — объявленный бюджет времени на обработчик.

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

Что для этого уже есть, измеренно

1. Завершаемость доказывается. По корпусу — 2 203 объявления из 2 788 (79 %) помечены тотальная, и пометка проверена, а не заявлена: stdlib 97,8 %, core 100 %, examples 96,2 %, self 68,9 %.

2. Оценка сверху на число витков уже выводится. flang/src/bounded.mjs (716 строк) даёт многочлен от размера входа с числовыми коэффициентами, а не «O(n)»: витков ≤ 12·н + 7 можно сверить с квантом, а «линейна» — нельзя.

Замерил покрытие по всему корпусу (оценитьВитки на 147 файлах, 2 930 объявлений):

Почему не выходит у остальных — по числу случаев:

Важное про этот хвост: большая часть отказов каскадная. «Зовёт функцию без оценки X» означает, что не вышло у X, а не у самой функции. Значит доля 42,2 % — это не потолок метода, а текущее состояние: доведи до оценки десяток корневых функций вроде «Взять поле» и «Строка поля», и поднимется сразу заметный пласт.

3. Пределы уже упираются в объявленное, а не в машину. FL_MAX_DEPTH, FL_MAX_STEPS и сторож стека (flang_runtime.h:230–284) сведены в одну точку fl_enter, и исчерпание стека переводится в объявленный FLANG_RECURSION_LIMIT вместо SIGSEGV. Замер оттуда же: при стеке 8 МиБ функция с одним параметром проходит 23 807 кадров, с сорока связываниями — 1 518; поэтому предел стережёт сторож, а не надежда.

Чего не хватает — конкретно

Для «вся память известна на этапе компиляции» нужны три вещи. Первой нет совсем, вторая слабая, третья есть.

Не хватает 1: объявленного предела на размер входа. Оценка bounded.mjs — это многочлен **от н**, а н берётся из значения во время выполнения (размерЗначения). Чтобы получить число на этапе компиляции, надо чтобы н было объявлено. То есть нужна ровно та же форма, что у ящика:

функция «Разобрать пакет»
  принимает байты: список числа не длиннее 1500

Тогда витков ≤ 12·н + 7 при н ≤ 1500 превращается в витков ≤ 18 007 — число, известное компилятору.

Не хватает 2: оценки размера ВЫДЕЛЕННОГО, а не только числа витков. В bounded.mjs есть размерСверху (строки 597–640), но она заметно слабее основной оценки: разбирает только literal, list, record, construct, if, binary — и возвращает null на call, пусть, разбор, свёртка, отобразить, отфильтровать и на встроенных формах. Она к тому же не экспортируется. Это заготовка, а не анализ памяти. Довести её до уровня основной оценки — работа того же порядка, что сама bounded.mjs: +400–700 строк в flang/src/bounded.mjs плюс зеркало в flang/self/, которого сегодня нет вовсе (bounded.mjs в самоприменение не переписан).

Не хватает 3 (а вот это как раз есть): режима «не выделять после старта». Если известны и число витков, и размер выделяемого, то верхняя оценка памяти считается умножением, и дальше — арена фиксированного размера, выделенная один раз при старте. Это буквально три строчки в рантайме: fl_arena_init заменяется на «взять один блок ровно на N байт», а fl_arena_alloc при нехватке возвращает NULL, который уже сегодня превращается в объявленный FLANG_MEMORY (flang_runtime.h:227–228). Механизм отказа при исчерпании памяти в рантайме уже есть и уже объявлен.

Оценка работы на режим «память известна заранее»

Дороже рекомендованного варианта Г (200–300 строк) примерно в десять раз, но и обещает совсем другое: не «памяти стало меньше», а «сколько её будет, известно до запуска».

И честно про долю. Даже когда всё это написано, режим накроет не всю программу: сегодня 42,2 % объявлений получают оценку витков, а оценка размера пока слабее. Значит правильная форма режима — не «весь язык теперь такой», а пометка на функции, как тотальная: компилятор либо доказывает предел, либо отказывается печатать эту функцию в этом режиме. Ровно тот же порядок, что уже принят для тотальности, и ровно та же честность: пометка, которую нельзя поставить голословно.

7. Итог: две разные работы, а не одна

Самое важное, что дало это исследование, — вопрос оказался двумя вопросами, и ответы у них разные, почти противоположные.

Вопрос первый: «как перестать тратить в тысячу раз больше памяти, чем нужно». Он про обычные программы: компилятор flang, разбор данных, счёт. Ответ — раздел 5, вариант Г: регион на вызов с копией наружу, ~200–300 строк в четырёх файлах, измеренные 486× по памяти и втрое по времени. Не потому что это красиво, а потому что это единственный вариант, у которого есть числа, полученные на этом дереве, и потому что беда, которую он лечит, измерена.

Вопрос второй: «как писать код, которому доверяют критичные системы». Он не про экономию памяти вообще. Стандарты просят не меньше памяти, а известное заранее число, и «умный распределитель» они запрещают прямым текстом — включая свой собственный. Ответ — раздел 6: режим со статически доказанным пределом, ~2 300–3 700 строк в 7–9 файлах, пометкой на функции, как тотальная.

Вариант Г для второго вопроса не годится вообще — он распределитель времени выполнения, а MISRA запрещает и такие. Это не изъян рекомендации; это разные задачи.

Что делать по порядку

1. Довести вариант Г до рабочего состояния (раздел 5). Прежде всего вылечить найденную опасность с fl_grow, потом выбрать порог не с потолка. Самое дешёвое из всего, что здесь рассмотрено, и единственное с замером.
2. Записать в конкурентности изъян, который там не записан: глубокая копия в шаге А2 разворачивает разделяемый подграф в дерево. Это уже в дереве и уже работает — значит уже может выстрелить.
3. Если и когда решите заниматься критичными системами — начинать не с памяти, а с bounded.mjs: довести размерСверху до уровня основной оценки и написать зеркало в flang/self/, которого нет вовсе. Без оценки размера разговора о статическом пределе не существует.
4. Подсчёт ссылок — когда выстрелит изъян копирования. Он полон для flang (циклов в значениях не бывает), но 2 000–3 500 строк против 200 — это не то, с чего начинают.

Чего делать не надо, и это тоже полноценный ответ

Не делать автоматический вывод регионов. Довод не «дорого» (хотя дорого — 5 500–9 500 строк), а «мимо». Замеренная беда flang — значение мертво, но имя ещё в области видимости; регионы привязаны к области видимости по построению (Ground Rule). Разбор конкретного места в разделе 4 показывает, что вывод регионов на нашем замере воспроизвёл бы известный режим отказа MLKit, а не удачный случай. К этому — приговор самих авторов после десяти лет работы и тридцатилетняя дуга от чистого вывода (1994) обратно к явным аннотациям (ReML, 2024).

Не вводить слова для регионов в язык. Единственный из четырёх вариантов, который меняет язык, — и тот, чью недостаточность признала сама команда Cyclone: «not suited to computations such as server and event loops».

Что во всём этом уже сделано и просто не было названо

Стоит сказать отдельно, потому что это меняет тон разговора. Идея владельца — «выделять память на категорию» — в flang уже реализована, дважды:

• арена на вызов в цели C — одна область на всё вычисление (flang_runtime.h:32–52);
• арена на пробег плюс копия наружу в конкурентности — шаг А2, две половины кучи, живое переезжает, занятая сбрасывается целиком (flang/conc/RESILIENCE.md:450–522), измерено 0,0 байта на пробег.

Первая — самая грубая форма приёма (одна область), вторая — уже настоящая. Рекомендация раздела 5 — это распространить вторую на обычные вызовы, а не завести что-то новое. Идея правильная, техника настоящая, половина работы сделана; недоделана как раз та половина, где измерены 1 655 МиБ.

Как воспроизвести замеры

Всё, что здесь измерено, получено на неизменённом дереве. Программы замера и прототип лежат вне репозитория (каталог замеров), в компиляторе не менялось ничего.

# печать в C и сборка
node flang/bin/flang.mjs emit ЗАМЕР.flang --target c --out КАТАЛОГ \
     --max-steps 2000000000 --max-depth 4000000
make -C КАТАЛОГ

# утечки
echo '{"fn":"Построить и отсортировать","args":[{"n":"4000"}]}' \
  | valgrind --leak-check=full --show-leak-kinds=all КАТАЛОГ/flang_cli --json

# пик кучи
echo '{"fn":"Построить и отсортировать","args":[{"n":"4000"}]}' \
  | valgrind --tool=massif --massif-out-file=ОТЧЁТ КАТАЛОГ/flang_cli --json
grep mem_heap_B ОТЧЁТ | sed 's/mem_heap_B=//' | sort -n | tail -1

# покрытие оценкой витков по корпусу — оценитьВитки из flang/src/bounded.mjs
# на всех .flang в stdlib, core, examples, self

Окружение замеров: valgrind 3.26.0, gcc (Ubuntu) 15.2.0, node v26.7.0, Linux x86-64. Машина во время замеров была занята другими задачами: числа massif от этого не зависят (он считает байты), числа по времени гуляли в пределах 20 %, максимальная RSS совпадала до килобайта.