Подграф ниже отметки отката копировать не надо: check types.flang — 14,15 → 6,66 ГиБ и 148 → 118 с

Область на вызов закрывается так: обмерить результат, переложить его в буфер, откатить арену к отметке, переложить обратно. Обмер считал ВЕСЬ результат — в том числе те подграфы, которые построил вызывающий и которые лежат НИЖЕ отметки. Откат их не трогает: он возвращает арене только выданное после отметки. Значит их не надо ни считать, ни возить, — а считались и возились они наравне со всем.

Стоило это не времени, а отказов. Обмер идёт с бюджетом (FL_REGION_GAIN: результат не больше четверти наросшего), и лишние байты чужого подграфа перебирали бюджет там, где своего результата было мало. Область отказывалась от отката — и арена росла до конца прогона.

Насколько крупен резерв — сначала посчитано, потом сделано. Двоичный со счётчиками (обмер идёт дважды: как в стволе и теневым, с отсечением), ствол 8e12cbae:

То есть отсечение переводит в откат 89 % отказавших обмеров на tags.flang (647 555 из 726 402) и 71 % на wal (3 339 из 4 731). Обойдённых узлов при этом на треть меньше (531,6 → 347,4 млн), а живое по тем же согласиям — на четверть (376,0 → 269,2 МБ).

Чем подтверждено. Ветка b/pamyat-otvet, парные прогоны вперемежку, три пары, машина под нагрузкой (load average 32), пик через /usr/bin/time:

Вывод совпал побайтово, код 0 у обеих.

Где выигрыша нет — там правка стоит 5 %. «Сортировка вставками» на 4 000 числах, напечатанная в C: 189,24 → 198,04 с при пике 10 240 КиБ у обеих. Свёртка строит накопитель целиком сама, ниже отметки в её результате нет ничего, отсекать нечего — остаются два сравнения на узел и обход оболочки. Это и есть цена приёма в худшем случае.

Время не выросло только вместе со второй правкой, и без неё правка убыточна. Отсечение само по себе давало на том же файле 28,78 / 28,68 с — плюс 16 % — при той же памяти. Ушли эти 16 % в fl_arena_rollback: он занулял цепочку кусков ДО КОНЦА, а за текущим куском лежат все пустые куски прежних откатов, то есть вся история арены. Пока откатов было 17 тысяч, это не было видно; при 665 тысячах стало главной статьёй. Обход обрывается на arena->current — «после текущего всё пусто» держится с рождения арены (fl_arena_alloc продвигает current только на кусок с used == 0).

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

Оракул «выше отметки» — два сравнения, а не обход. Перед обмером считается ОБОЛОЧКА: наименьший и наибольший адрес памяти, выданной после отметки. Куски — отдельные покупки у malloc и в адресах не подряд, поэтому «внутри оболочки» ещё не значит «выше отметки», — но ошибка в эту сторону безобидна (узел просто скопируется), а обратной быть не может. Обход цепочки — один раз на закрытие, и это дёшево: порог FL_REGION_MIN проходит меньше четырёх процентов закрытий.

Что этим опровергнуто. Заметка five-sixths-of-a-region-survey-pays-to-learn-it-will-not-pay-off закрыла этот резерв как неокупаемый по четырём редакциям. Все четыре были ПРИБЛИЖЕНИЯМИ отсечения — «только верхушка результата», «верхушка и первый ярус», «отсечение статических литералов», — и ни одна не переводила отказ обмера в откат: память менялась на 0,1–1,1 %. Настоящее отсечение меняет её на 30 %. Вывод «горит не обход, а решение, ради которого обход затеян» остаётся верным — просто отсечение меняет именно решение, а не скорость обхода.

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

Связано: five-sixths-of-a-region-survey-pays-to-learn-it-will-not-pay-off, arena-never-releases, memory-peak-scales-with-obligations-not-file-size