Skip to content

REPORT.md

Latest commit

 

History

History
258 lines (190 loc) · 18.4 KB

REPORT.md

File metadata and controls

258 lines (190 loc) · 18.4 KB

Отчёт по семестровому проекту: реализация Range Min–Max Tree (RmMTree)

1. Введение

В рамках семестрового проекта была реализована структура данных Range Min–Max Tree (RmMTree) над битовым вектором для операций над правильными скобочными последовательностями (balanced parentheses, BP). Реализация основана на идеях из статьи (ScienceDirect): https://www.sciencedirect.com/science/article/pii/S0304397516300706

Цель проекта — получить

  • сжатую ($o(n)$ доп. памяти)
  • и быструю (все операции выполняются за $O(\log n)$ времени и используют различные оптимизации, существенно уменьшающие константы)
  • структуру, поддерживающую типовой набор запросов:
    • rank / select по битам,
    • операции с excess (префиксная сумма с шагами +1/−1),
    • fwdsearch / bwdsearch,
    • диапазонные запросы минимума/максимума по префиксным суммам,
    • навигацию по скобочной последовательности: close, open, enclose,
    • дополнительные операции rank10 / select10 для шаблона "10".

В проекте присутствуют:

  1. наивная эталонная реализация (для проверки на корректность);
  2. основная, оптимизированная, реализация;
  3. набор тестов на корректность (GoogleTest) с сравнением "наивная vs оптимизированная",
  4. бенчмарки (Google Benchmark) и скрипт построения графиков для визуализации результатов.

2. Постановка задачи и требования

2.1. Входные данные

  • Битовая строка '0'/'1' или массив 64-битных слов uint64_t с укладкой LSB-first (младшие биты — более ранние позиции).
  • Число валидных бит num_bits.

2.2. Основные поддерживаемые операции

Ранг/выборка

  • rank1(i), rank0(i) — количество 1 или 0 на префиксе [0, i).
  • select1(k), select0(k) — позиция k-й единицы/нуля (k 1-based).

Шаблон "10"

  • rank10(i) — число позиций p в [0, i) таких что bit[p]==1 и bit[p+1]==0 и p+1<i.
  • select10(k) — позиция начала k-го шаблона "10" (k 1-based).

Excess и поиски по префиксной сумме

  • excess(i) = rank1(i) - rank0(i) = 2*rank1(i) - i — префиксная сумма шагов: +1 для 1 и -1 для 0.
  • fwdsearch(i, d) — минимальный p ≥ i, где excess(p) = excess(i) + d.
  • bwdsearch(i, d) — максимальный p ≤ i, где excess(p) = excess(i) + d.

Диапазонные min/max по префиксу

  • range_min_query_pos(i, j) — позиция первого минимума на [i..j].
  • range_min_query_val(i, j) — значение соответствующего минимума.
  • Аналогично: range_max_query_pos/val.

Количество минимумов и выбор q-го минимума

  • mincount(i, j) — сколько раз минимум достигается на [i..j].
  • minselect(i, j, q) — позиция q-го минимума (q 1-based).

BP-навигация

Интерпретация: 1 — это '(', 0 — это ')'.

  • close(open_pos) — найти соответствующую закрывающую скобку.
  • open(close_pos) — найти соответствующую открывающую скобку.
  • enclose(pos) — это открывающая скобка ближайшей внешней пары, которая содержит позицию pos внутри себя, а не совпадает с ней (если рассматривать BP как дерево, то enclose(pos) — это открывающая скобка родительского узла для позиции pos, т.е. ближайшая открывающая скобка "на уровень выше").

3. Архитектура решения

Дерево реализовано в двух вариантах:

3.1. NaiveRmM — наивная эталонная реализация

Назначение:

  • служит проверочным эталоном для тестов;
  • реализует те же операции простыми циклами по массиву бит.

Все операции — асимптотически линейные по длине рассматриваемого диапазона:

  • rank: O(n),
  • select: O(n),
  • range_min/max и mincount/minselect: O(j-i) и т.п.

Плюсы:

  • простота,
  • легко проверить корректность логики.

Минусы:

  • очевидны.

3.2. pixie::RmMTree — оптимизированная реализация Range Min–Max Tree

3.2.1. Хранение битов

  • std::vector<std::uint64_t> bits;
  • укладка: LSB-first (бит i находится в слове bits[i>>6] на позиции (i & 63)).

Это решение удобно, потому что:

  • rank в блоке можно ускорять через popcount,
  • select в блоке делается через перебор установленных битов (внутри 64 бит),
  • удобно читать байты/16-битные фрагменты для LUT и SIMD.

3.2.2. Идея блокирования и дерева

Битовый вектор делится на листья фиксированного размера block_bits (по умолчанию минимум 64, далее может расти по степеням двойки). Количество листьев:

  • leaf_count = ceil(num_bits / block_bits)

Далее строится сбалансированное двоичное дерево в heap-представлении, где:

  • листья соответствуют блокам,
  • внутренние вершины агрегируют статистики по своим поддеревьям.

Индексация:

  • 1 — корень,
  • first_leaf_index — индекс первого листа (степень двойки ≥ leaf_count),
  • лист k хранится в first_leaf_index + k.

3.2.3. Какие агрегаты хранятся в вершинах

Для каждого узла дерева хранится набор агрегатов (но не в виде структуры, а в отдельных массивах, где индекс массива совпадает с номером узла):

  • segment_size_bits[node] — длина сегмента (в битах), покрываемого узлом.
  • node_total_excess[node] — суммарный excess на сегменте (итоговая сумма шагов +1/−1).
  • node_min_prefix_excess[node] — минимум префиксной суммы внутри сегмента (относительно начала сегмента).
  • node_max_prefix_excess[node] — максимум префиксной суммы внутри сегмента.
  • node_min_count[node] — число позиций, где минимум достигается.
  • node_pattern10_count[node] — число шаблонов "10" внутри сегмента.
  • node_first_bit[node], node_last_bit[node] — крайние биты сегмента (нужны для учёта "10" на границах между детьми/узлами).

4. Ускорение сканирования листьев: LUT по байтам и SIMD

4.1. LUT на 8 бит

Для обработки хвостов и небольших диапазонов сделана lookup table на все 256 возможных значений байта.

Структура ByteAgg хранит для байта:

  • суммарный excess,
  • min/max префикса,
  • количество минимумов,
  • число "10" внутри байта,
  • первый/последний бит,
  • позиции первого min/max.

Также построены таблицы:

  • fwd_pos[byte][delta] — первая позиция в байте, где префикс равен delta (delta ∈ [-8..8]),
  • bwd_pos[byte][delta] — последняя позиция.

Это позволяет:

  • быстро находить минимум/максимум и их позиции на диапазонах, выровненных по байтам,
  • быстро искать нужный префикс для маленьких дельт,
  • ускорить mincount/minselect,
  • ускорить локальные сканирования в fwdsearch/bwdsearch.

4.2. SIMD (AVX2) для поиска по префиксу в листе

В реализации предусмотрена опциональная поддержка AVX2 (PIXIE_AVX2_SUPPORT):

  • берутся 16 бит (get_u16),
  • разворачиваются в 16 "шагов" (+1/−1) по lane’ам,
  • вычисляется префиксная сумма внутри SIMD-регистра,
  • сравнивается с целевым значением, и по mask находится первая/последняя позиция.

Дополнительно использована эвристика:

  • для "маленьких хвостов" и "маленьких дельт" (пример: delta ∈ [-8..8], tail ≤ 256) LUT8 может быть быстрее, чем AVX2 из-за стоимости подготовки SIMD.

5. Выбор размера блока и оценка накладных расходов

В RmMTree предусмотрен механизм выбора block_bits:

  • можно задать явно через конструктор/параметр leaf_block_bits,
  • можно включить ограничение на относительные накладные расходы по памяти (объём вспомогательных массивов по отношению к размеру битвектора, далее — overhead) через max_overhead$^*$,
  • иначе выбирается значение, близкое к ceil_pow2(log2(num_bits)), но не меньше базового порога.

Это даёт возможность балансировать:

  • скорость (меньше блок → больше дерево → больше узлов, но меньше сканирования листа),
  • память (больше блок → меньше узлов → меньше overhead).

$*$ — max_overhead, вообще говоря, задаёт целевую верхнюю границу на overhead. При построении структура увеличивает размер листового блока block_bits, чтобы уложиться в этот лимит. Однако гарантировать выполнение ограничения не всегда возможно:

  • block_bits ограничен сверху значением min(n, 2^14) (введена как защита от неадекватно большого и на практике почти никогда не нужного размера блока), поэтому при слишком строгом лимите может не существовать допустимого размера блока;
  • при очень малом n накладные расходы неизбежно велики, потому что дерево и массивы имеют "постоянную" составляющую, а block_bits нельзя уменьшать ниже 64;
  • дополнительно overhead растёт из-за выравнивания числа листьев до степени двойки (first_leaf_index = bit_ceil(leaf_count)), из-за чего появляются пустые слоты узлов в heap-представлении (они занимают место в массивах, хотя фактически не покрывают биты).

6. Тестирование корректности

Тестирование построено по принципу "оптимизированная реализация должна совпадать с наивной" на большом количестве случайных сценариев.

7. Бенчмаркинг производительности

В проекте реализованы два бенчмарка:

  • src/bench_rmm.cpp — бенчмарк реализации RmMTree,
  • src/bench_rmm_sdsl.cpp — бенчмарк реализации Range Min–Max Tree из библиотеки sdsl-lite.

7.1. Генерация датасетов

  • Используется генератор случайных ПСП;
  • После чего для каждого N заранее подготавливаются пулы запросов:
    • случайные индексы,
    • случайные отрезки [i, j],
    • случайные k для select-операций,
    • случайные delta для fwdsearch/bwdsearch,
    • корректные позиции '(' и ')' для close/open/enclose,
    • для minselect — заранее генерируется q в допустимом диапазоне (через mincount).

7.2. Поддерживаемые параметры бенчмарков (как аргументы командной строки)

  • --min_exp, --max_exp — диапазон размеров N = 2^e,
  • --per_octave — сколько дополнительных точек между степенями двойки,
  • --explicit_sizes — явный список размеров,
  • --Q — число запросов (сэмплов),
  • --p1 — параметр генератора,
  • --seed — seed,
  • --block_bits — размер листа (0 = auto).

8. Визуализация результатов

Реализован скрипт, читающий JSON-выгрузку Google Benchmark и строящий графики:

  • по оси X — N (размер последовательности),
  • по оси Y — cpu_time (нс на операцию),
  • отдельно по каждой операции,
  • опционально сравнивает RmMTree и sdsl-lite на одном графике,
  • может включить --logx и медианное сглаживание --smooth.

9. Практические итоги и наблюдения

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

  • Наличие NaiveRmM позволило сделать строгую проверку "на каждом шаге" для большого количества случайных случаев.
  • Полный перебор коротких строк (1..8) полезен для ловли ошибок на границах:
    • пустые диапазоны,
    • i=0, i=num_bits,
    • различия 0-based / 1-based в open/enclose/bwdsearch,
    • пересечения "10" на границах слов и блоков.

9.2. Производительность

Заложено несколько уровней ускорения:

  • агрегаты снижают работу на больших диапазонах до $O(\log n)$,
  • LUT8 ускоряет "мелкие" сканы и листовые операции без тяжёлых подготовок,
  • AVX2 ускоряет поиски по префиксным суммам на длинных хвостах.

Самая красивая особенность этой реализации заключается в том, что в таких структурах часто именно "листья" становятся bottleneck-ом, но LUT8 и AVX2 позволяют получить немалый практический выигрыш в скорости работы на этих "листьях", а параметр block_bits позволяет подстроить баланс "дерево vs локальное сканирование".

10. Роадмап дальнейшей работы

  1. BP-обёртка:
    • parent, isancestor, depth, lca и т.п. поверх close/open/enclose.
  2. AoS:
    • подумать над слиянием некоторых массивов в Array-of-Structs для улучшения кэш-локальности.
  3. Cуперблоки:
    • объединить несколько соседних листьев в "суперблок" и строить дерево только по суперблокам, а внутри каждого суперблока хранить компактный локальный индекс (например, массив агрегатов по листьям или микро-структуру). Это позволило бы "срезать" несколько нижних уровней дерева, уменьшив число узлов, объём метаданных и количество обращений к памяти при запросах (особенно в fwdsearch/bwdsearch и range min/max).

11. Заключение

В итоге получилась завершённая реализация RmMTree, пригодная для дальнейшего развития в сторону полнофункциональной поддержки succinct-структур над BP.