Пять шестых работы обмера области уходит на выяснение «не окупится», а не на саму перекладку
Область арены при закрытии обмеряет результат, чтобы решить, окупится ли откат. Профиль называл этот обмер главным едоком времени — 76 %, из них fl_region_size 44,6 % при 863 миллионах вызовов, — и отсюда напрашивалась правка: не спускаться в поддеревья НИЖЕ отметки, они и так переживут откат.
Правка написана, верна и не окупается. Проверено четырьмя редакциями, тремя парами вперемежку каждая, flang check flang/self/types.flang, все выводы совпали со стволом побайтово, все коды 0:
| редакция | время | память |
|---|---|---|
| только верхушка результата | −0,9 % | −0,1 % |
| отсечение статических литералов | +12,5 % | −1,1 % |
| порог на подготовку | +24,1 % | +0,7 % |
| верхушка и первый ярус | +11,9 % | −0,1 % |
Причина в том, что обмер идёт рекурсией с доводом, и довод этот платится на КАЖДОМ узле. Двоичный, где проверка принадлежности отвечает «своё» всегда — то есть отсечения нет вовсе, а оснастка на месте, — уже теряет 7,5 с из 78,5 с. Отсечение потом эту цену не отбивает.
Число, которое говорит, куда бить вместо этого
Счётчики на том же прогоне: fl_region_close зовётся 30 651 351 раз, порог области проходят 569 554. Из них:
перекладок 88 977 (16 %)
отказов обмера по бюджету 480 374 (84 %)
результат оказался пуст 57Пять шестых всей работы обмера уходит на то, чтобы узнать «не окупится». Отсечение эту долю не трогает вообще: оно ускоряет обход, а обход всё равно доходит до предела бюджета и возвращает «нет».
Значит следующий ход — не отсекать быстрее, а дешёво предсказывать отказ: по чему-то, что известно ДО обхода. Наросший объём известен вычитанием (arena->handed - mark.handed), потолок отношения задан FL_REGION_GAIN; чего не хватает — оценки живого сверху, которую можно получить без полного обхода.
Ловушка, стоившая ложных +19 %
Первая редакция мерилась как «+19 % времени, +11 % памяти», и число это было неправдой о самой правке.
fl_own_region собирал куски области, идя по цепочке mark.chunk->next до её конца. За текущим куском лежат куски прежних откатов — пустые, но из цепочки не вынутые, и число их равно всему, что арена купила за жизнь. В 400 839 закрытиях из 569 554 (70 %) цепочка оказывалась длиннее предела в 64 куска, отсечение молча выключалось, — а список отрезков и сортировка вставками по нему всё равно строились.
То есть измерялась цена подготовки при выключённом отсечении. Обрыв обхода на arena->current это чинит; после починки отсечение работает, и всё равно проигрывает.
Отдельно проверено, что рост памяти шёл НЕ из буфера перекладки: его пик совпал до байта в обеих редакциях — 30 425 440. Рост был из арены, по той же причине.
Что при этом отсекать МОЖНО, а что нельзя
Отсекать по указателю можно записи, варианты и строки: их заполняет ровно одно место, при выдаче, и больше не правит ничто.
Списки нельзя. Быстрый путь fl_b_dobavit пишет grow->items[grow->filled] = item в уже выданный массив: массив может лежать ниже отметки, а положенное в него значение — выше. Признак «массив с запасом» (value.as.list.grow) отличить не помогает, потому что fl_list_slice («хвост») его РОНЯЕТ, и вид того же массива приезжает уже без признака. Первая редакция отсекала списки и сломала вычисление: flang check flang/self/types.flang ответил «FLANG_UNKNOWN_NAME: запись не содержит поле «вид»» кодом 1.
Чему учит
Профиль называет, где ГОРИТ время, но не называет, что с этим делать. Здесь он показал на обмер верно — и предложенная им починка оказалась хуже болезни, потому что горит не обход, а решение, ради которого обход затеян. Число «84 % отказов» из профиля не видно вовсе: его пришлось считать счётчиками, вписанными руками.