Efim Beshmenev
125 lines
9.2 KiB
Markdown
125 lines
9.2 KiB
Markdown
# Large-scale исследование: fixed tiered, adaptive и vector
|
||
|
||
Статус: exploratory throughput study с 12-worker pool; для N=100M одновременно
|
||
работали не более трёх процессов. Это эвристически снижало риск pagefile на
|
||
машине с 32 GiB RAM, но RSS/page faults отдельно не измерялись.
|
||
Это основной отчёт для серий
|
||
[`20260811-large-full-12c-v1`](../20260811-large-full-12c-v1/) и текущего
|
||
seed-jittered holdout `v2`.
|
||
|
||
## Что измерено
|
||
|
||
- Ryzen 9 5900X, 32 GiB RAM, MSVC 19.51, Windows build 26200.
|
||
- Release x64 `/O2`, статический runtime `/MT`, без IPO/LTO.
|
||
- Профили `scalar` (`project-novec`), обычный `baseline` и `/arch:AVX2`.
|
||
- `uint32_t`, размеры от 100 тысяч до 100 миллионов элементов.
|
||
- В каждой ячейке один и тот же материализованный trace для семи кандидатов:
|
||
reserved `std::vector`, forced tiered с leaf 64/128/256/512/1024 и
|
||
`adaptive_shape_deferred`.
|
||
- Плотность правок: 0%, 0.01%, 0.1%, 1%, 5%, 20%, 50% и 100%; отдельно
|
||
локализованные, bursty и phase-сценарии.
|
||
- `v1` использует короткий горизонт 256 правок при N=100M и периодическое
|
||
размещение steady-правок. `v2` исправляет методический alias: 512 правок
|
||
размещаются seed-зависимой выборкой с точным общим количеством.
|
||
|
||
Все коэффициенты ниже — `время кандидата / время лучшего fixed-tiered`.
|
||
Значение больше единицы означает проигрыш кандидата.
|
||
|
||
## Масштабирование
|
||
|
||
| Серия | N | Adaptive / best fixed | Vector / best fixed | Adaptive / vector | Adaptive победил fixed |
|
||
|---|---:|---:|---:|---:|---:|
|
||
| v1 | 100K | 1.425x | 1.342x | 1.062x | 18/42 |
|
||
| v1 | 1M | 17.75x | 30.98x | 0.573x | 6/42 |
|
||
| v1 | 10M | 133.82x | 177.07x | 0.756x | 3/42 |
|
||
| v1, короткий horizon | 100M | 621.77x | 559.89x | 1.111x | 3/42 |
|
||
| v2, seed-jittered | 100M | 379.28x | 572.36x | 0.663x | 3/42 |
|
||
|
||
Геометрическое среднее берётся по workload и трём профилям. Строки v1 и v2
|
||
при N=100M не являются парным сравнением: у них намеренно различаются horizon
|
||
и временное размещение правок.
|
||
|
||
## N=100M: зависимость от плотности
|
||
|
||
| Сценарий | Правок | Лучший leaf | Adaptive / fixed | Vector / fixed | Adaptive / vector | Итог adaptive |
|
||
|---|---:|---:|---:|---:|---:|---|
|
||
| steady uniform | 0% | 1024 | 0.115x | 0.095x | 1.212x | остаётся vector |
|
||
| steady uniform | 0.01% | 512 | 7.46x | 7.19x | 1.037x | остаётся vector |
|
||
| steady uniform | 0.1% | 128 | 50.58x | 58.51x | 0.864x | остаётся vector |
|
||
| steady uniform | 1% | 1024 | 379.88x | 437.19x | 0.869x | остаётся vector |
|
||
| steady uniform | 5% | 128 | 438.56x | 1317.81x | 0.333x | 1 switch -> leaf1024 |
|
||
| steady uniform | 20% | 1024 | 1700.61x | 4736.79x | 0.359x | 1 switch -> leaf1024 |
|
||
| steady uniform | 50% | 256 | 6626.61x | 10059.97x | 0.659x | 1 switch -> leaf1024 |
|
||
| steady uniform | 100% | 256 | 7145.17x | 11632.45x | 0.614x | 1 switch -> leaf1024 |
|
||
| steady localized | 0.1% | 256 | 76.05x | 78.99x | 0.963x | остаётся vector |
|
||
| steady localized | 1% | 128 | 583.65x | 521.20x | 1.120x | остаётся vector |
|
||
| steady localized | 20% | 256 | 2828.02x | 6551.50x | 0.432x | 1 switch -> leaf1024 |
|
||
| steady localized | 100% | 64 | 13819.58x | 21605.68x | 0.640x | 1 switch -> leaf1024 |
|
||
| bursty uniform | 1% | 1024 | 245.92x | 672.61x | 0.366x | 1 switch -> leaf1024 |
|
||
| uniform -> localized -> reads | 20% | 512 | 5150.01x | 8124.41x | 0.634x | поздний switch -> leaf1024 |
|
||
|
||
## Fixed leaf и накладные расходы
|
||
|
||
Ни один leaf не является универсальным. В 42 profile/workload-ячейках v2
|
||
победители распределились так: leaf512 — 31.0%, leaf1024 — 26.2%, leaf256 —
|
||
23.8%, leaf128 — 14.3%, leaf64 — 4.8%. Локализованные 100%-правки выбрали
|
||
leaf64, а чистое чтение — leaf1024.
|
||
|
||
Среднее наблюдаемое время построения N=100M: vector 0.171 s, adaptive 0.765 s,
|
||
forced tiered 1.61–1.89 s. Финальный учтённый объём: vector 0.419 GiB,
|
||
adaptive в среднем 0.671 GiB, fixed tiered 0.860–0.989 GiB. Это не peak RSS:
|
||
временная копия при конверсии в эту колонку не входит. Наблюдаемый переход
|
||
adaptive занимал 0.788–1.284 s под совместной нагрузкой трёх N=100M-процессов.
|
||
|
||
В измеренном бинарнике конструктор benchmark-адаптера vector сначала копировал
|
||
данные, а затем переносил их при `reserve`; после серии harness исправлен на
|
||
reserve-before-copy. На `ns/op` это не влияло, но 0.171 s следует считать
|
||
верхней оценкой старого construction path, а не чистой ценой построения vector.
|
||
|
||
## Вывод
|
||
|
||
На этой матрице fixed tiered действительно лучше текущего adaptive для любого
|
||
устойчивого ненулевого потока middle insert/erase при N=100M. Исключение —
|
||
чистое чтение: vector примерно в 10.5 раза, а adaptive в 8.7 раза быстрее
|
||
лучшего forced-tiered.
|
||
|
||
Adaptive уже полезнее голого vector: после перехода он выигрывает у vector в
|
||
1.5–3 раза на плотных и bursty-трассах. Но он слишком долго накапливает
|
||
evidence в vector, успевает заплатить за сотни O(N)-сдвигов и всегда выбирает
|
||
leaf1024, хотя oracle часто выбирает 64–512. Поэтому его основной проигрыш —
|
||
не стоимость tiered hot path, а поздний первый переход и недостаточно
|
||
чувствительное правило выбора geometry.
|
||
|
||
Следующая версия policy должна накапливать фактический regret в наносекундах,
|
||
масштабировать решение с N и стоимостью наблюдаемых сдвигов, а не ждать почти
|
||
фиксированную долю/число операций. Pending-переход также надо отменять после
|
||
смены фазы, если будущая экономия уже исчезла. Для выбора leaf нужны отдельные
|
||
сигналы локальности и плотности: единый leaf1024 здесь явно не является
|
||
приемлемым ответом.
|
||
|
||
## Ограничения
|
||
|
||
- Это co-scheduled throughput: pool имеет 12 закреплённых workers, а N=100M
|
||
выполнялся по три процесса одновременно; они всё равно делят L3 и память.
|
||
Профильные scalar/baseline/AVX2 времена нельзя трактовать как чистый SIMD
|
||
speedup; выводы агрегированы по всем трём профилям.
|
||
- Для N выше 1M выполнен один repeat на профиль, чтобы vector при N=100M
|
||
оставался практически измеримым.
|
||
- Исследован `uint32_t`; большие и non-trivial типы требуют отдельного large run.
|
||
- v1 steady schedule был периодическим. Для основных N=100M-выводов выше
|
||
используется исправленный seed-jittered v2.
|
||
- Сохранённый бинарник использовал multiset-like финальный checksum: он ловил
|
||
расхождение значений, но не гарантировал обнаружение перестановки. После run
|
||
checksum заменён order-sensitive rolling digest; operation timer не изменён.
|
||
- Сильные коэффициенты являются end-to-end regret короткой фазы, а не
|
||
стационарной скоростью adaptive после уже завершённого перехода.
|
||
|
||
Машиночитаемые данные: `large-raw.csv`, `cell-medians-large.csv`,
|
||
`comparison-large.csv`, `comparison-by-size.csv`,
|
||
`comparison-by-workload.csv`, `fixed-leaf-winners.csv`, `large-plan.json`,
|
||
`environment.json`, source/binary manifests и per-cell partial/log файлы.
|
||
|
||
Команды postprocess записаны в `analysis-command.txt`. Для повторения только
|
||
этого N=100M holdout используется `large_benchmark.bat full 12 3 huge`; детали
|
||
есть в `docs/benchmarking.md`.
|