Повторное сканирование голов тегов при десериализации (отложенная задача «3b»)

Статус: отложено, не реализовано. Записано по итогам A/B-прогона от 2026-08-01. Файл в фокусе: XmlSerDe.Common/EmbeddedHelperCode.cs — XmlNode2.GetFirstLength, XmlNode2.GetFirst, конструктор XmlNode2, ScanHead_Core.

Документ самодостаточный: чтобы взяться за задачу, читать переписку не нужно.

Обновление от 2026-08-01, после второго A/B-прогона. Задача 3a (раздел 4) реализована: GetFirst больше не разбирает голову повторно. Вместе со слитным сканированием головы это дало 9.153 us → 7.132 us, Ratio 0.92 → 0.74, при неизменных аллокациях. Контрольный прогон штатного SerializeDeserializeFixture на спокойной машине подтвердил: 6.554 us против baseline 8.515 us, Ratio 0.77. Разделы 3.2 и 4 описывают код до этой правки и оставлены как есть, потому что именно они объясняют, откуда взялась задача 3b; актуальные числа и то, что осталось несделанным, — в разделе 7.

1. Откуда взялась задача

Правки на соответствие XML 1.0 (коммиты 7abc8e7, 7b61d56, 2d9d54b) замедлили десериализацию. A/B-прогон показал, что виноваты две функции внутри ScanHead_Core:

Вариант	Mean	Ratio к System.Xml
текущий код	7.972 us	0.91
без второго прохода в `FindEndOfNodeName`	7.187 us	0.82
со старым `FindUnquotedGt` (`IndexOf('>')`)	7.072 us	0.82
без обеих проверок (доспековый горячий путь)	6.697 us	0.74

Вместе — около 1.28 us, то есть ~16% времени десериализации.

Пока разбирались, вскрылась вещь крупнее самих этих правок, и это как раз задача 3b. Она ортогональна корректности: речь не о том, чтобы упростить проверки, а о том, чтобы перестать выполнять их по многу раз над одним и тем же текстом.

2. Суть проблемы одной строкой

На один разбор тестового документа ComplexFixture.AuxXml, в котором 26 элементов, приходится 135 вызовов ScanHead_Core — в среднем 5.2 разбора головы на элемент. Самые глубокие ноды разбираются по 7 раз.

Счётчики сняты временной инструментацией (см. раздел 6):

ScanHead_Core=135; FindUnquotedGt=135 (quote hops=24);
ParseFirstFoundAttribute=14; DecodeAttributeValue=9

Обратите внимание на контраст: атрибутный код вызывается 9–14 раз и в бюджете не виден вовсе, а разбор головы — 135 раз.

3. Механика: почему сканов в 5 раз больше, чем элементов

Задействованы три места.

3.1. `GetFirstLength` рекурсивно обходит всё поддерево

private static int GetFirstLength(ref XmlParseContext settings, roschar nodes)
{
    ScanHead_Core(nodes, trimmed, out var fullHeadLength, out var nodeType, out var isBodyLess);
    // ...
    while (true)
    {
        // ищем '<'
        if (ch1 == '/') { /* нашли свой закрывающий тег -> return */ }
        else
        {
            var childLength = GetFirstLength(ref settings, innerNodes); // рекурсия в ребёнка
            index += lcl + childLength;
        }
    }
}

Чтобы узнать длину ноды X, нужно найти её парный закрывающий тег, а для этого — пропустить всех вложенных потомков. Реализовано это полноценным рекурсивным разбором: GetFirstLength(X) вызывает ScanHead_Core для головы каждой ноды поддерева X.

3.2. `GetFirst` разбирает голову ноды дважды

public static void GetFirst(ref XmlParseContext settings, roschar nodes,
                            roschar xmlnsAttributeName, ref XmlNode2 result)
{
    var length = GetFirstLength(ref settings, nodes);   // скан #1 головы этой ноды
    // ...
    result = new XmlNode2(settings, nodes.Slice(0, length), xmlnsAttributeName);
}

а конструктор XmlNode2 независимо делает то же самое:

ScanHead_Core(fullNode, trimmed, out var fullHeadLength, out DeclaredNodeType, out IsBodyless); // скан #2

GetFirstLength уже посчитал ровно fullHeadLength, nodeType и isBodyLess для этой самой ноды — и выбросил их, оставив только суммарную длину.

3.3. Генерируемый код зовёт `GetFirst` на каждого ребёнка

while(true)
{
    XmlSerDe.Common.XmlNode2.GetFirst(ref settings, internals, xmlNode.XmlnsAttributeName, ref child);
    if(child.IsEmpty) break;
    // ... разбор ребёнка ...
    internals = internals.Slice(child.FullNode.Length);   // переход к следующему брату
}

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

3.4. Итоговая формула

Пусть S(X) — сколько раз вызывается GetFirstLength(X). Тогда

S(X) = 1 (из собственного GetFirst) + S(parent) (из обхода родителя)

потому что обход родителя повторяется столько раз, сколько раз вызывается сам родитель. Отсюда S(X) = глубина(X), а число разборов головы = S(X) + 1 (плюс скан в конструкторе).

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

Глубина	Ноды	Сканов на ноду	Итого
0	`InfoContainer`	1	1
1	`InfoCollection`	2	2
2	`BaseInfo` ×3	3	9
3	`Email`, `BasePersonificationInfo1/2`, `HotKeyUsed`, `StepsCounter`, `EventsTime`	4	24
4	`SerializeKeyValue` ×3	5	15
5	`Key` ×3, `Value` ×3	6	36
6	`StartTime` ×3, `SecondsSpan` ×3	7	42
	26 элементов		129

Замерено 135. Модель объясняет 129; остаток — почти наверняка полиморфная ветка DeserializeBody для BaseInfo и завершающие пустые вызовы GetFirst в циклах.

Вывод: стоимость разбора головы линейна по глубине вложенности. Документ глубиной 6 платит семикратно. Документ глубиной 12 будет платить тринадцатикратно — то есть на реальных иерархических схемах штраф больше, чем на тестовом документе.

4. Что делает задача 3a и почему её мало

3a (отдельная, простая, уже сделана) — отдать наружу из GetFirstLength уже посчитанные fullHeadLength / nodeType / isBodyLess и передать их в конструктор XmlNode2, вместо повторного ScanHead_Core. Это убирает ровно один скан на материализованную ноду: 129 → 104, около 20%.

3a убирает слагаемое «+1». Задача 3b — убрать множитель S(X) = глубина(X), который и есть основная проблема.

Как 3a оказалась реализована (важная деталь для 3b). Наружу отдаётся не nodeType, а nodeTypeLength. Спан, полученный через out из метода, у которого есть параметр ref XmlParseContext settings, компилятор обязан считать потенциально ссылающимся на этот ref, и сохранить такой спан в поле ref struct уже нельзя — CS8352. Начало имени вызывающей стороне и так известно (fullHeadPrefixLength + 1), поэтому конструктор режет спан сам. Любой вариант из раздела 5, который захочет вернуть спаны через out из GetFirstLength, упрётся в то же ограничение — планируйте отдавать индексы и длины.

Замер 3a: 8.615 us → 7.187 us, то есть −1.43 us (−17%). Это больше, чем стоят обе спековые правки вместе взятые (1.28 us), хотя по счётчикам 3a убирает лишь пятую часть сканов. Причина в том, что убираются самые дорогие сканы — головы уже материализованных нод, а не короткие проходы по хвостам.

5. Варианты решения

Вариант A. Дешёвый подсчёт баланса тегов вместо рекурсивного разбора

GetFirstLength нужен только конец ноды. Полный разбор головы каждого потомка для этого избыточен: достаточно линейно идти по тексту, считая глубину — <имя увеличивает, </имя> уменьшает, /> не меняет.

Что даёт: асимптотика прежняя (O(размер поддерева) на ноду), но константа падает в разы: вместо ScanHead_Core со всеми проверками §2.3/§2.4 — дешёвые посимвольные тесты.
Плюсы: локальная правка, сигнатуры не меняются, генератор не трогается.
Минусы и ловушки: обязаны корректно пропускать комментарии , блоки CDATA (<![CDATA[ ... ]]>) и — главное — кавычки внутри головы: <Foo attr="a>b"> содержит легальный > внутри значения атрибута (XML 1.0 §2.4). Именно на этом уже спотыкались, см. FindUnquotedGt и тесты в SpecComplianceFixture. То есть «дешёвый» скан всё равно обязан быть quote-aware.
Оценка: самый безопасный из трёх, но и потолок ниже — квадратичность по глубине остаётся.

Вариант B. Мемоизация длин нод

Кешировать offset -> length при первом обходе и переиспользовать при повторных.

Где держать состояние: XmlParseContext — это ref struct, который уже передаётся везде как ref settings. Значит он может нести изменяемое состояние, в том числе Span<int> на стеке вызывающей стороны. Это ключевой факт: отдельный кеш не ломает ref-struct-модель и не требует поля-синглтона.
Что даёт: каждая нода разбирается один раз, суммарно O(n). Наибольший выигрыш.
Минусы: нужен ассоциативный контейнер по int-смещению в стековом буфере (открытая адресация), нужна оценка размера буфера и поведение при переполнении (деградация к текущему поведению). Плюс аккуратность: смещения должны считаться от одного и того же корневого спана, иначе ключи не совпадут — а по коду спаны многократно режутся.
Оценка: лучший результат, средняя сложность, требует внимания к ключам.

Вариант C. Однопроходная токенизация

Один линейный проход по документу строит плоский массив записей (start, length, headLength, depth), дальше генерируемый код ходит по индексам.

Что даёт: честный O(n), разбор головы ровно один раз на элемент.
Минусы: это смена модели — с ленивого обхода ref struct на предварительный разбор. Меняется контракт с генератором, правка большая. И главное — бьёт по главному преимуществу библиотеки: сейчас десериализация аллоцирует 1.12 KB против 16.49 KB у System.Xml (Alloc Ratio 0.07). Массив записей это ломает, если не брать буфер из ArrayPool<int> и не возвращать его.
Оценка: наибольший потолок, наибольший риск. Браться только если A и B не хватило.

Рекомендуемый порядок: сначала 3a, затем вариант B; вариант A — как запасной, если B упрётся в ключи смещений; вариант C — отдельным заходом и только по необходимости.

6. Как это мерить

Стенд (XmlSerDe.PerformanceTests/HotPathAbFixture.cs плюс переключатель AbSwitch в EmbeddedHelperCode.cs) на момент написания лежит в рабочем дереве незакоммиченным и подлежит либо удалению, либо продвижению в основной код. Если его к моменту чтения уже нет — воспроизводится так.

6.1. Счётчики вызовов

Временно добавить в EmbeddedHelperCode.cs статический класс со счётчиками и инкременты в ScanHead_Core, FindUnquotedGt, ParseFirstFoundAttribute, DecodeAttributeValue. Прогнать один Deserialize и распечатать. Обязательно откатить перед замерами времени — статические инкременты сами по себе искажают горячий путь.

6.2. A/B-переключатель — важная методическая грабля

Переключатель вариантов обязан быть static readonly, инициализируемым из переменной окружения:

public static readonly bool OldFindUnquotedGt =
    Environment.GetEnvironmentVariable("XMLSERDE_AB_OLD_GT") == "1";

RyuJIT сворачивает такое поле примитивного типа в константу на tier-1 и целиком выкидывает мёртвую ветку — горячий путь получается ровно такой же, как при обычной правке исходника.

Обычный static bool для этого не годится. Первый прогон был сделан на нём, и он исказил результат примерно на 1 us: проверка мутабельного статика сломала инлайнинг FindEndOfNodeName, и текущий код показал Ratio 0.97 вместо реальных 0.88. Ошибка одинакова для всех вариантов, но по величине сравнима с самим измеряемым эффектом.

6.3. Конфигурация BenchmarkDotNet

Каждый вариант — отдельная job со своими переменными окружения (то есть отдельный процесс со своим JIT), System.Xml как baseline внутри каждой job:

AddJob(Job.Default.WithRuntime(CoreRuntime.Core80).WithLaunchCount(3).WithId("A-current"));
AddJob(Job.Default.WithRuntime(CoreRuntime.Core80).WithLaunchCount(3).WithId("B-...")
    .WithEnvironmentVariable("XMLSERDE_AB_OLD_GT", "1"));

WithLaunchCount(3) обязателен: BDN запускает каждую пару (бенчмарк, job) в отдельном процессе, и один процесс, поймавший постороннюю нагрузку, перекашивает и Mean, и Ratio. В прогоне без него baseline одной job уехал на 10% (10.259 us против ~9.26 у остальных) и дал взаимно противоречивые выводы.

Как читать результат: сравнивать варианты между собой по Mean, но обязательно проверять, что baseline System.Xml во всех job совпал в пределах пары процентов. Если не совпал — прогон невалиден, перезапускать. Абсолютный Mean между разными запусками несравним: он уезжает вместе с рантаймом, SDK и состоянием машины (эталонный System.Xml на неизменном коде гулял от 7.26 до 10.26 us).

Санитарная проверка: эффекты независимых правок должны складываться. В валидном прогоне 0.785 + 0.900 ≈ 1.275 сошлось с точностью 5% — это и был главный признак, что замер чистый. Во втором прогоне так же: предсказание 9.153 − 0.725 − 1.428 = 7.000 против измеренных 7.132, расхождение 1.9%. Небольшая недоаддитивность здесь ожидаема и имеет правильный знак — 3a убирает часть вызовов ScanHead_Core, поэтому ускорение самого ScanHead_Core после 3a приносит меньше. Если знак окажется обратным (эффекты «сверхскладываются»), замер испорчен.

WithLaunchCount(3) не панацея. Во втором прогоне baseline одной job всё равно уехал (12.877 us при StdDev 3.26 и медиане 11.295 против 9.6–10.1 у остальных). Ratio этой job пришлось выбросить, но сам подопытный в ней был измерен устойчиво (StdDev 0.17), так что абсолютный Mean остался пригоден. Отсюда практическое правило: смотреть на StdDev и Median каждой строки отдельно, а не только на сводный Ratio.

6.4. Корректность

Гонять dotnet test XmlSerDe.Tests с включённым флагом варианта и без него: 107/107. Особенно важен SpecComplianceFixture — там лежат <Foo attr="1>2">, самозакрывающийся <Foo attr="a>b"/>, полиморфная десериализация с лишним > в атрибуте, пропуск пролога (PI/DOCTYPE) и нормализация пробелов в значениях атрибутов.

7. Опорные числа

Машина: Windows 11, 13th Gen Intel Core i7-13700H, .NET 8.0.29, X64 RyuJIT AVX2. Документ: ComplexFixture.AuxXml, 26 элементов, максимальная глубина 6.

Абсолютные числа двух прогонов между собой несравнимы (машина во втором была заметно загруженнее), поэтому таблицы разделены. Сравнивать можно Ratio.

Прогон 1 — цена спековых правок:

Показатель	Значение
`Deserialize: System.Xml` (baseline)	~8.7 us, 16.49 KB
`Deserialize: XmlSerDe`, спековый код	7.972 us, 1.12 KB, Ratio 0.91
`Deserialize: XmlSerDe`, доспековый горячий путь	6.697 us, Ratio 0.74

Прогон 2 — что сделано (слитный ScanHead + 3a):

Вариант	Mean	Ratio
было (Z)	9.153 us	0.92
слитный `ScanHead` без инлайна	8.615 us	(baseline job испорчен)
слитный `ScanHead` с `AggressiveInlining`	8.428 us	0.87
+ 3a	7.132 us	0.74

Итог: −22%, при этом ни одна проверка на соответствие XML 1.0 не отменена — то есть доспековая производительность возвращена не ценой корректности.

Контрольный прогон штатного SerializeDeserializeFixture (не A/B-стенда, машина спокойная — StdDev baseline 0.12 против 0.25–0.38 в прогоне 2):

Method	Mean	StdDev	Ratio	Allocated	Alloc Ratio
`Deserialize: System.Xml`	8.515 us	0.1201 us	1.00	16.49 KB	1.00
`Deserialize: XmlSerDe`	6.554 us	0.0767 us	0.77	1.12 KB	0.07

Ratio 0.77 против 0.74 на A/B-стенде. Расхождение в пределах того, что даёт разное состояние машины; важно, что подтверждение получено другим бенчмарком, без переключателей в горячем пути. Историческая точка отсчёта в README — 0.88.

Прочее:

Показатель	Значение
Вызовов `ScanHead_Core` на документ (до 3a)	135
Элементов в документе	26
Исторический Ratio (README, .NET 8)	0.80

Аллокации во всех вариантах обоих прогонов одинаковы (1.12 KB, Alloc Ratio 0.07) — вся разница чисто процессорная. Это же и критерий приёмки для 3b: аллокации не должны вырасти.

Что осталось необъяснённым. В прогоне 1 слитное сканирование дало ровно столько же, сколько полный отказ от второго прохода в поиске конца имени, — как если бы быстрый путь для > не работал вовсе. Гипотеза была в невстроенном вызове; прогон 2 её подтвердил лишь частично (инлайн вернул 0.187 us из ожидавшегося большего). Остаток не объяснён. На результат это не влияет — после 3a разница между вариантами с инлайном и без него (7.132 против 7.187) лежит внутри шума, — но если браться за 3b, стоит иметь в виду, что модель стоимости самого ScanHead сходится с замером не полностью.

8. Риски

Кавычки в голове тега. Любой упрощённый скан обязан помнить, что > внутри значения атрибута легален. Это уже было источником бага.
Ключи смещений (вариант B). Спаны многократно режутся; смещение должно считаться от единого корня, иначе кеш будет молча промахиваться — и это не проявится как падение тестов, только как отсутствие ускорения.
Аллокации (вариант C). Не потерять Alloc Ratio 0.07 — это заявленное преимущество библиотеки, оно ценнее нескольких процентов CPU.
Соблазн мерить «на глаз». По опыту этой сессии две оптимизации, обоснованные рассуждением о сложности, а не замером, оказались замедлением и были откачены. Помогли только правки с конкретным механизмом (порог SIMD, векторный скан против посимвольного). Любой вариант из раздела 5 проводить через A/B по методике раздела 6.
Ref safety (CS8352). См. раздел 4: возвращать спаны через out из GetFirstLength нельзя, пока у метода есть параметр ref XmlParseContext. Отдавайте индексы и длины. Обнаруживается сразу на компиляции, но может увести проект в тупик, если архитектуру кеша спроектировать вокруг возврата спанов.

FilesExpand file tree

perf-redundant-head-scans.md

Latest commit

History