Efim Beshmenev
237 lines
19 KiB
Markdown
237 lines
19 KiB
Markdown
# Наблюдения и ограничения
|
||
|
||
## Текущая focused-постановка
|
||
|
||
Активное исследование больше не использует старую benchmark-матрицу. Оно
|
||
сравнивает только три варианта `AdaptiveSequence<uint32_t, true>` с одинаковым
|
||
flat hash: forced vector, forced tiered и resize-bound adaptive. Mixed workload
|
||
фиксирован: 97% индексных чтений, 1% hash find (50% hit / 50% miss), 1% вставок
|
||
и 1% удалений.
|
||
|
||
Automatic policy меняет mode, `leaf = ceil(sqrt(N))` и размер hash table только
|
||
при изменении логической capacity. Рост capacity идёт `x2`; один shrink-шаг
|
||
`/2` выполняется при заполнении 12.5%. Поэтому цена перехода входит в измерение,
|
||
но ни storage, ни hash не перестраиваются после каждой отдельной операции.
|
||
|
||
## Final focused run и cutoff
|
||
|
||
Baseline focused-run с 7 повторами и 100000 mixed operations подтвердил
|
||
локальный crossover между двумя соседними размерами. При `N=2048` mixed median
|
||
forced vector равна **31.98M ops/s**, а forced tiered — **32.18M ops/s**:
|
||
преимущество tiered по медиане составляет лишь **0.618%**, при этом tiered
|
||
быстрее в **4 из 7**, а vector — в **3 из 7** paired repeats. Эта граница
|
||
считается неустойчивой и попадающей в шум измерения. При `N=4096` forced tiered
|
||
дал **32.53M ops/s**, forced vector — **17.20M ops/s**, а adaptive с включённым
|
||
в timer переходом `vector -> tiered` — **32.64M ops/s**. Медиана tiered выше
|
||
vector в **1.8911 раза**, и tiered быстрее во всех **7 из 7** paired repeats.
|
||
|
||
Поэтому для текущего `uint32_t` workload принят **cutoff 4096** как первый
|
||
однозначный и устойчивый размер в sweep. Это подтверждённый результат
|
||
focused-серии, но всё ещё калибруемая граница, а не
|
||
универсальная константа для других типов и workload. Полная таблица медиан по
|
||
mixed/read/find/insert/erase и методика опубликованы в
|
||
[`20260813-focused-resize/README.md`](../results/benchmarks/20260813-focused-resize/README.md);
|
||
raw повторы находятся в
|
||
[`20260813-focused-resize/baseline.csv`](../results/benchmarks/20260813-focused-resize/baseline.csv).
|
||
В CSV 189 строк: у всех строк корректные счётчики операций, checksums совпадают
|
||
между тремя кандидатами для каждой пары `(N, repeat)`, а режимы и leaf отдельных
|
||
read/find/insert/erase batches записаны отдельными столбцами.
|
||
|
||
## Historical / retired benchmark evidence
|
||
|
||
Все результаты ниже относятся к прежним workload, кандидатам и policy. Они
|
||
сохранены для аудита истории, но **не участвуют** в выборе текущего cutoff и не
|
||
сравнимы напрямую с focused benchmark.
|
||
|
||
### Что было установлено старой методикой
|
||
|
||
На Ryzen 9 5900X / MSVC 19.51 quick-tuning дал разные оптимумы, поэтому
|
||
фиксированный `leaf=512` отвергнут как итоговая стратегия. Для baseline
|
||
`uint32_t` наблюдалась следующая картина:
|
||
|
||
| Workload | N=10k | N=100k | N=1M |
|
||
|---|---:|---:|---:|
|
||
| uniform edit | 64 | 256 | 1024 |
|
||
| localized edit | 64 | 128 | 256 |
|
||
| mixed 80% read | 128 | 512 | 1024 |
|
||
|
||
Это calibration-наблюдение, а не универсальная таблица. Оно привело к
|
||
динамической модели `leaf` и отдельному `tiered→tiered` переходу. Кандидатная
|
||
геометрия учитывает `sizeof(T)`: дорогие перемещения естественно уменьшают
|
||
выбираемый leaf.
|
||
|
||
Эта таблица относится к исходному bulk layout, где свежие листья заполнялись
|
||
до 100%. Checkpoint `20260810-bulk-slack-smoke-v13` оставляет 1/8 leaf свободной
|
||
после bulk-конверсии: иначе первый случайный insert почти гарантированно платил
|
||
за split и rebuild каталога. В baseline-only smoke после изменения ranking стал
|
||
таким: forced leaf 64 — 0.39608, leaf 128 — 0.36662, adaptive deferred —
|
||
0.34673, reserved vector — 0.29797. Это не межзапусковой speedup и не финальное
|
||
доказательство, а сигнал, что старую таблицу leaf нужно заново проверить на
|
||
одинаковом quick holdout с тремя профилями.
|
||
|
||
### Hysteresis и итоговый quick-checkpoint
|
||
|
||
После v13 выполнены три контрольные серии:
|
||
|
||
- `20260811-hysteresis-smoke-v14` — baseline smoke завершённого hysteresis.
|
||
После согласования правила двухфазной трассы validator проходит на 58 compare
|
||
и 14 adapt ячейках.
|
||
- `20260811-policy-quick-v15-hysteresis` — baseline quick, adapt-only. Среди
|
||
адаптивных policy лучший aggregate score показал `moderate deferred`
|
||
(`0.224689`), но лучший fixed leaf128 остался значительно выше (`0.819729`).
|
||
Серия снабжена source/binary manifests.
|
||
- [`20260811-213422-quick`](../results/benchmarks/20260811-213422-quick/README.md)
|
||
— итоговый engineering quick-checkpoint итерации: tune, adapt, compare и index
|
||
для `scalar`, `baseline`, `avx2`.
|
||
|
||
Профили финальной серии запускались последовательно в фиксированном порядке
|
||
`scalar -> baseline -> avx2`; внутри каждого профиля порядок suites был
|
||
`tune -> adapt -> compare -> index`. Каждый кандидат внутри повтора получал один
|
||
и тот же материализованный trace, а стартовый кандидат циклически сдвигался между
|
||
повторами. Это снижает простое преимущество первого кандидата, но не заменяет
|
||
полную рандомизацию запусков.
|
||
|
||
Aggregate score нормирован по лучшему фиксированному baseline в каждой ячейке;
|
||
выше — лучше. Для compare по всем трём профилям получена такая картина:
|
||
|
||
| Кандидат | Aggregate score |
|
||
|---|---:|
|
||
| forced tiered, leaf64 | 0.395052 |
|
||
| forced tiered, leaf128 | 0.391598 |
|
||
| adaptive deferred | 0.347315 |
|
||
| adaptive eager | 0.326839 |
|
||
| reserved vector | 0.146329 |
|
||
| external deque | 0.080267 |
|
||
| external list-index | 0.012763 |
|
||
|
||
`adaptive deferred` выше reserved vector в этой конкретной quick-матрице, но
|
||
уступает лучшим fixed leaf-конфигурациям. Следовательно, данные не доказывают
|
||
победу над лучшим oracle или универсальное превосходство.
|
||
|
||
По парному агрегированию времени adaptive быстрее vector примерно в 2.37 раза,
|
||
но медленнее leaf64 на 13.74% и leaf128 на 12.75%; leaf256 он опережает на 1.07%.
|
||
Основной regret теперь создаёт не churn, а поздний первый переход. Для blob64 и
|
||
non-trivial при N=100k adaptive делает один switch без rebuild, но до него платит
|
||
за дорогие vector edits; относительно leaf64 проигрыш составляет примерно 2.45x
|
||
и 4.03x. В `read_99`, N=1M наблюдается другая ошибка: доля edits ниже 5% entry
|
||
threshold, хотя их абсолютная стоимость уже оправдывает tiered. Это аргумент за
|
||
накопленный cost/regret в следующей policy, а не только порог доли операций.
|
||
|
||
В adapt-наборе сильнейшими также остались fixed leaf128 (`0.817859`) и leaf256
|
||
(`0.788496`). Лучший адаптивный policy, `moderate deferred`, получил `0.216999`.
|
||
В tuning leaf128 оказался сильнейшим quick-кандидатом во всех трёх профилях:
|
||
scalar `0.878968`, baseline `0.873461`, avx2 `0.887906`. Это локальный результат
|
||
данной матрицы, а не универсальная константа.
|
||
|
||
Лучший единый межпрофильный компромисс — `128/64/3`; `128/64/4` отстаёт от него
|
||
всего на 0.276%, поэтому depth пока находится в пределах измерительного шума.
|
||
Выбор leaf устойчивее: профили совпали в 14 из 15 логических tuning-ячеек.
|
||
Random access выбирал 1024, большинство edit/mixed-ячеек — 64, localized edit
|
||
при N=1M — 128.
|
||
|
||
Итоговый validator pass охватывает 282 compare и 48 adapt ячеек. Первоначальный
|
||
лимит одной leaf-rebuild для phase trace был ошибкой спецификации валидатора:
|
||
трасса содержит две разные edit-фазы, и по одному устойчивому выбору формы на
|
||
каждую фазу не является churn. Только для явно двухфазного сценария лимит был
|
||
исправлен до двух; измерительные CSV не менялись. После исправления полный
|
||
quick-набор прошёл проверку.
|
||
|
||
Validator работает по медианам. В raw compare один repeat двухфазной трассы при
|
||
N=1M имеет три leaf-rebuilds, тогда как медиана равна двум; будущая проверка
|
||
должна применять ограничения также к каждому repeat, не только к median-cell.
|
||
|
||
`std::deque` и `std::list` в этих таблицах — только внешние фиксированные
|
||
baselines, не режимы `AdaptiveSequence`. Для дорогих индексных ячеек harness
|
||
применяет `skipped_cost_guard`; поэтому у них меньше eligible cells, и пропуски
|
||
нельзя интерпретировать как нулевое время или победу кандидата.
|
||
|
||
Index-suite подтверждает полезность специализированного flat hash index для
|
||
случайного lookup относительно линейного поиска vector, но результат относится
|
||
только к lookup-подзадаче и сопровождается существенной памятью под индекс. Он
|
||
не является доказательством общей победы контейнера. Геометрическое среднее
|
||
потребление памяти составило 9.26x от payload vector, с диапазоном 7.00x–17.49x.
|
||
При N=1M suite выполнял лишь 50 запросов, построение индекса исключалось из
|
||
таймера, а свежепостроенный hash был cache-hot; поэтому экстремальные speedup
|
||
нельзя считать устойчивой production-оценкой.
|
||
|
||
Offline oracle, который в каждой calibration-ячейке задним числом выбирает
|
||
лучший leaf, был геометрически примерно в **1.318 раза** быстрее фиксированного
|
||
leaf 512 по срезу `levels=3` quick tuning трёх профилей. По семействам потенциал
|
||
составил около 1.54x для uniform edit, 1.67x для localized edit и 1.37x для
|
||
mixed-80. Это показывает ценность смены shape, но завышает достижимый online
|
||
результат: oracle знает будущее и не платит за переходы. Новый phase benchmark
|
||
как раз включает эту цену.
|
||
|
||
Deferred read adaptation оставлена default. В раннем smoke-тесте eager-вариант
|
||
иногда выигрывал несколько процентов на одном bursty trace, но проигрывал в
|
||
общем из-за проверки на каждом non-const read и создавал неожиданную
|
||
инвалидацию. Фазовые тесты теперь используют явный `adapt_now()` как безопасную
|
||
maintenance point.
|
||
|
||
Компактный flat hash после перехода на 32-bit internal IDs занимал примерно
|
||
28 bytes/element при низкой cardinality и около 54 bytes/element для уникальных
|
||
`uint32_t` при N=100k. Это существенно больше 4-byte payload, поэтому индекс
|
||
остаётся compile-time optional и не входит в storage score. `contains` был
|
||
порядка 4–18 ns в зависимости от cardinality; логически отсортированный
|
||
`find_all` на множестве дубликатов ожидаемо дороже `find_all_ids`.
|
||
|
||
AVX2 дал заметный выигрыш главным образом reserved vector; для tiered/adaptive
|
||
различия малы и смешаны с фиксированным порядком профилей. У
|
||
adaptive-deferred sequential `uint32` найден устойчивый AVX2 codegen outlier:
|
||
1.85–1.98x относительно baseline во всех пяти повторах при верных checksums.
|
||
Он требует отдельного анализа generated code, а не постфактум объяснения SIMD.
|
||
|
||
### Large-scale sweep до 100 миллионов элементов
|
||
|
||
Серии [`large v1`](../results/benchmarks/20260811-large-full-12c-v1/README.md)
|
||
и [`seed-jittered v2`](../results/benchmarks/20260811-large-n100m-512edit-12c-v2/README.md)
|
||
сравнили reserved vector, fixed tiered leaf 64…1024 и текущий adaptive в
|
||
12-worker pool; N=100M ограничивался тремя одновременными процессами. При
|
||
N=100M и чистом чтении vector
|
||
оказался примерно в 10.5 раза, а adaptive — в 8.7 раза быстрее лучшего fixed
|
||
tiered. Уже при 0.01% равномерных middle-правок fixed стал примерно в 7.5 раза
|
||
быстрее обоих.
|
||
|
||
При 5–100% равномерных правок adaptive переключался в tiered и опережал vector
|
||
примерно в 1.5–3 раза, но end-to-end оставался в сотни или тысячи раз медленнее
|
||
fixed oracle: до первого перехода он успевал выполнить сотни O(N)-сдвигов.
|
||
Каждый переход выбрал leaf1024, хотя лучший fixed leaf менялся от 64 до 1024.
|
||
Следовательно, текущая главная проблема — позднее накопление evidence и слабый
|
||
выбор geometry, а не churn, который уже ограничен hysteresis.
|
||
|
||
Эти числа являются co-scheduled throughput, а не изолированной latency: workers
|
||
делят L3/DRAM, а N>1M имеет один repeat на профиль. Поэтому SIMD-профили сохранены
|
||
отдельно, но точный AVX2 speedup по этой серии не утверждается.
|
||
|
||
### Чего нельзя было утверждать по retired-сериям
|
||
|
||
- Не доказано, что adaptive implementation уже имеет geometric mean > 1 против
|
||
лучшего фиксированного контейнера на независимом full holdout.
|
||
- Текущий tiered backend имеет ring offsets на leaf и многоуровневый каталог
|
||
весов, но не реализует offsets/carry на каждом внутреннем узле полноценного
|
||
implicit tiered vector.
|
||
- Split/merge может перестраивать каталог и сдвигать дескрипторы leaf за
|
||
O(number_of_leaves). Именно поэтому uniform edit с маленьким leaf резко
|
||
ухудшался при N=1M. Policy умеет избегать такой shape, но это не заменяет
|
||
дальнейшую оптимизацию backend.
|
||
- Independent blocks реализованы; contiguous/virtual-memory backing пока не
|
||
реализован и не сравнен.
|
||
- Delta overlay пока не реализован. Его следует оценивать как отдельную третью
|
||
структуру, а не добавлять до появления честного выигрыша.
|
||
- Exception safety bulk conversion для throwing move типов требует отдельной
|
||
production-доработки.
|
||
- Финальная серия — quick с пятью повторами, фиксированным последовательным
|
||
порядком профилей, без process affinity/pinning и с планом питания Balanced.
|
||
- Scalar использует внутренний для MSVC `/d2Qvec-`: это проверенный на
|
||
зафиксированной версии компилятора project-novec, но не публичный контракт
|
||
MSVC и не доказательство отсутствия SIMD внутри CRT или x64 runtime.
|
||
|
||
### Бывшая исследовательская граница
|
||
|
||
Phase-aware hysteresis завершён и прошёл трёхпрофильный quick-validator.
|
||
Следующий этап — независимый full holdout с несколькими seeds, affinity/pinning
|
||
и перемешанным порядком профилей/кандидатов, а также сравнение regret policy с
|
||
лучшим fixed leaf oracle. Следующая архитектурная граница — заменить descriptor
|
||
rebuild на настоящий multi-level offset/carry backend. Старые CSV сохраняются,
|
||
чтобы изменение архитектуры нельзя было выдать за улучшение без измерений.
|