Black-White Array — реализации на C++, Java и Python

Порт структуры данных Black-White Array (BWA) на шаблоны C++, generics Java и Python (через SWIG-обёртку над C++).

Источники:

• Z. George Mou, Black-White Array: A Fast Sorted Data Structure with Logarithmic Memory Allocation — arXiv:2004.09051
• Эталонная реализация на Go: github.com/dronnix/bwarr
• Разбор на русском: habr.com/ru/articles/984184

---

Когда это нужно

BWA — упорядоченный контейнер-мультимножество (аналог std::multiset / TreeMap / SortedList), но без дерева с указателями: данные лежат в наборе плоских отсортированных сегментов размерами 2⁰, 2¹, 2², … Какие сегменты активны, задаёт двоичная запись числа записей:

total = 11 = 1011₂  →  активны сегменты рангов 0 (1 шт.), 1 (2 шт.), 3 (8 шт.)

Берите BWA, если данные читаются/обходятся чаще, чем меняются точечно, а давление на аллокатор или GC критично — на 1M вставок BWA делает 48 аллокаций вместо миллиона у дерева (числа и полная методика — в разделе «Статистика»).

Не берите, если нужен предсказуемый p99.9 latency на каждой отдельной вставке: раз в N вставок случается слияние всего массива за O(N) — на 1M int64 это единицы-десятки миллисекунд (см. профиль задержки ниже).

	BWA	B-tree / RB-tree / skip list
аллокаций на N вставок	O(log N)	O(N)
указателей на элемент	0	2–3
расположение данных	подряд, дружелюбно к кэшу	вразброс по куче
insert / find / erase	O(log N) амортизированно	O(log N) в худшем случае
худшая одиночная вставка	O(N)	O(log N)

---

Механика

Вставка = инкремент двоичного счётчика

Ранг сегмента-приёмника равен позиции младшего единичного бита числа total + 1. Этот сегмент гарантированно свободен целиком, поэтому:

1. новый элемент кладётся в его последнюю ячейку;
2. свободный префикс работает «чёрной» зоной — областью записи;
3. сегменты рангов 0…r−1 по очереди вливаются в накопленный суффикс обычным merge из merge sort, и суффикс удваивается на каждом шаге.

ранг 3, вставляем 17 при total = 7 (сегменты 0, 1, 2 заняты)

  [ _ _ _ _ _ _ _ 17 ]   read=7, w=6, сливаем с рангом 0 = [9]
  [ _ _ _ _ _ _ 9 17 ]   read=6, w=4, сливаем с рангом 1 = [4,20]
  [ _ _ _ _ 4 9 17 20]   read=4, w=0, сливаем с рангом 2 = [1,6,11,30]
  [ 1 4 6 9 11 17 20 30 ]

В статье «чёрные массивы» описаны как отдельные временные буферы. На практике буфер не нужен: его роль играет свободный префикс приёмника. Именно поэтому массив ранга k выделяется один раз за всё время жизни структуры — ради этого BWA и придумана.

Удаление = tombstone + demote

Элемент помечается битом в битмапе надгробий. Когда мёртвых в сегменте ранга k набирается ровно половина (2^(k−1)):

• сегмент ранга k−1 свободен → живые переезжают туда (demote);
• занят → живые сдвигаются в конец сегмента k, и туда же вливается сегмент k−1; активным остаётся k, гаснет k−1.

В обоих случаях total уменьшается ровно на 2^(k−1) — снова арифметика двоичного счётчика. Заполненность гарантированно не ниже 50 %.

Порядок равных элементов (FIFO)

1. равные в одном сегменте — старший по возрасту правее;
2. равные в разных сегментах — старший по возрасту в сегменте старшего ранга;
3. среди равных удалённые правее живых.

Инвариант 3 позволяет находить «самый правый живой из равных» одним бинарным поиском, без линейного досмотра дубликатов. Поэтому erase/get при дубликатах работают по принципу FIFO и не деградируют.

---

Статистика

Прогоны с этой машины (g++ 15.1 -O2 (MSYS2/UCRT64), OpenJDK 22, Windows, 14 ядер). Абсолютные числа зависят от железа и особенно заметны на маленьком N (там счёт идёт на доли миллисекунды и тонет в шуме таймера/JIT) — важны порядок величины и рост с N.

Рост числа аллокаций — главный результат структуры

N	аллокаций BWA (C++)	аллокаций у std::multiset	log₂N
4 096	31	4 096	12
65 536	40	65 536	16
1 048 576	48	1 048 576	20

Логарифмический рост против линейного — разница на N = 1M составляет четыре порядка.

C++ против std::multiset (ключ long long), ускорение по N

N	insert	find	ascend	erase
4 096	x1.6	x1.1	x0.9	x1.2
65 536	x2.5	x1.7	x1.7	x2.4
1 048 576	x9.3	x4.3	x13.2	x5.7

unordered_walk (обход без гарантии порядка, O(N) по памяти подряд) на 1M элементов — x200 к std::multiset::begin()..end(); на маленьком N доминирует шум таймера, ориентируйтесь на 1M.

Java против TreeSet<Long>, N = 1 048 576

  операция                         BWA    выделено  |     TreeSet    выделено ускорение
  ------------------------------------------------------------------------------------
  insert                     223.6 ms     8.3 MiB  |    742.7 ms    35.4 MiB     x3.32
  contains (случайные)       737.9 ms     0.0 MiB  |    768.3 ms     0.0 MiB     x1.04
  remove (всё, вразнобой)    530.3 ms     0.0 MiB  |    762.2 ms     0.0 MiB     x1.44
  аллокаций сегментов у BWA за весь прогон: 21

(«выделено» — ThreadMXBean.getCurrentThreadAllocatedBytes, то есть ровно то, что придётся собирать сборщику мусора; у TreeSet на порядок больше при том же N.)

Цена: распределение задержки одной вставки, N = 1 048 576

C++:  p50 ≈ 0 мкс   p99 = 1 мкс    p99.9 = 6 мкс     max = 8.8 мс
Java: p50 ≈ 0 мкс   p99 = 1 мкс    p99.9 = 13 мкс    max = 31–33 мс*

max — то самое единственное слияние всего массива за O(N); в Java на этот пик обычно накладывается пауза GC (звёздочка), поэтому число заметно больше.

Вывод: BWA хороша там, где важны пропускная способность и давление на аллокатор — in-memory индексы, аналитика, батчевая обработка. Для систем с жёстким SLA на p99.9 одной операции пик в единицы-десятки миллисекунд может быть неприемлем.

Воспроизвести: make cpp-bench / make java-bench (сборка → build/).

---

API

C++

#include "bwarr/black_white_array.hpp"

bwarr::BlackWhiteArray<long long> a;          // std::less по умолчанию
a.insert(42);
if (a.contains(42))            { /* ... */ }
if (const auto* p = a.find(42)) { /* ... */ }
a.erase(42);

// Компаратор как второй параметр шаблона — как у std::set
struct ById { bool operator()(const Row& x, const Row& y) const { return x.id < y.id; } };
bwarr::BlackWhiteArray<Row, ById> rows;
rows.insert(Row{7, 1.5});
const Row* r = rows.find(Row{7, 0});   // поиск по ключу, возвращается вся запись

a.ascend([](const long long& v) { std::cout << v << ' '; return true; });  // false прерывает
a.descend(...);
a.unordered_walk(...);   // O(N), без порядка, максимально быстро

метод	смысл
insert(v), insert_range(first, last)	вставка
contains(v), find(v), count(v)	поиск
replace_or_insert(v)	заменить равный или вставить
erase(v), erase_min(), erase_max()	удаление
min(), max()	границы (std::optional)
ascend, descend, unordered_walk, to_vector	обходы
size, empty, entry_count, segment_count	размеры
allocation_count, memory_bytes, layout	диагностика
clear(drop_memory), compact()	управление памятью
validate()	проверка инвариантов (для тестов)

Требования к T: default-конструируемый, move/copy-присваиваемый.

Java

import bwarr.BlackWhiteArray;

BlackWhiteArray<Long> a = BlackWhiteArray.ofNatural();
a.insert(42L);
a.contains(42L);
a.remove(42L);

// Свой компаратор + подсказка по размеру (ни одной аллокации на первых 100k)
BlackWhiteArray<Row> rows = BlackWhiteArray.of(Comparator.comparingInt(r -> r.id), 100_000);
Row r = rows.get(new Row(7, 0));

for (Long v : a) { /* Iterable<T>, обход по возрастанию */ }
a.ascend(v -> { System.out.println(v); return true; });
a.unorderedWalk(v -> true);

метод	смысл
of(cmp), of(cmp, capacityHint), ofNatural(), ofNatural(hint)	фабрики
insert, insertAll, replaceOrInsert	вставка
contains, get, count	поиск
remove, removeMin, removeMax	удаление
min, max	границы (null, если пусто)
ascend, descend, unorderedWalk, iterator, toList	обходы
size, isEmpty, entryCount, segmentCount	размеры
allocationCount, layout, toString	диагностика
clear(dropMemory), compact	управление памятью
validate	проверка инвариантов

Классы не потокобезопасны.

Python (SWIG-обёртка над C++)

Int64Array/DoubleArray/StrArray — фиксированные инстанциации C++-шаблона (int/float/str). ObjectArray — произвольный Python-объект с компаратором в рантайме (естественный < либо key=, как у sorted()), на порядок медленнее первых трёх — оправдан, только когда реально нужен произвольный тип ключа. Подробности, отличия от C++/Java API и сборка — в python/README.md.

import bwarr

a = bwarr.Int64Array()             # или bwarr.new(int); есть DoubleArray/StrArray
a.insert(5); a.insert(3); a.insert(3)

len(a), 3 in a, a.count(3)         # (3, True, 2)
a.to_vector()                       # [3, 3, 5] — обычный list
a.min_value(), a.max_value()         # (3, 5); IndexError на пустом контейнере
a.erase(3)                            # bool

rows = bwarr.ObjectArray(key=lambda r: r.id)   # произвольный класс, сравнение по ключу

---

Сборка и запуск

make              # тесты C++ и Java
make cpp-test     # 42 теста, 21 067 проверок
make cpp-san      # то же под AddressSanitizer + UBSan
make cpp-bench    # против std::multiset, по трём N
make cpp-demo     # наглядная механика
make java-test    # 43 теста, 21 082 проверки
make java-bench   # против TreeSet, с учётом выделенной памяти
make java-demo
make python-test  # 21 тест; нужен swig в PATH, в `make test` не входит
make python-demo

Через CMake:

cmake -S cpp -B build -DCMAKE_BUILD_TYPE=Release && cmake --build build && ctest --test-dir build

C++ и Java не требуют внешних зависимостей (C++17, JDK 11+; самописный раннер тестов вместо Maven/Gradle/GoogleTest). Python-обёртка дополнительно требует swig — см. python/README.md.

---

Структура репозитория

cpp/      header-only C++17: black_white_array.hpp + тесты + бенчмарк + demo
java/     generics-реализация + тесты + бенчмарк + demo
python/   SWIG-обёртка над cpp/: Int64Array/DoubleArray/StrArray + ObjectArray + тесты + demo
Makefile

Тесты в cpp/ и java/ разбиты по темам один в один (test_basics.cpp ↔ BasicsTest.java, и так по каждому файлу — duplicates, erase, traversal, memory, types, fuzz); отчёт группируется по файлам, так что расхождения между реализациями видно построчно. python/tests/test_bwarr.py проверяет то же поведение через публичный Python API.

---

Проверка корректности

C++: 42 теста / 21 067 проверок, дополнительно под AddressSanitizer + UndefinedBehaviorSanitizer — чисто. Java: 43 теста / 21 082 проверки (на один больше — iteratorMatchesAscend, у C++ нет Iterable). Python: 21 тест (unittest), поверх публичного API.

Все три реализации фаззятся против эталонных структур (std::multiset / TreeMap / отсортированный список) на плотных и разреженных ключах. validate()/validate вызывается после каждой мутации в тестах на удаление и проверяет инварианты: размеры сегментов = 2^ранг, сортированность внутри сегмента, согласованность счётчика надгробий, порог заполненности 50%, корректность подсказок min_live/max_live, равенство суммы размеров активных сегментов значению total.

---

Об этом порте

Портирована вся механика эталонной Go-реализации: in-place каскадное слияние, tombstone, demote, merge-при-удалении, FIFO-инварианты, ленивые подсказки границ, опция «не освобождать мелкие сегменты». Главные отличия:

• битовый tombstone-битмап вместо []bool/bool[] — 1 бит на запись вместо байта (для int64 это 1.5% накладных расходов вместо 12.5%);
• STL-компаратор «строго меньше» вместо трёхзначной функции в C++; обычный Comparator в Java;
• диапазонные итераторы (AscendRange и т.п.) и Clone не портированы — обходы сделаны k-путевым слиянием через кучу, а не отдельной машинерией итераторов.

Подводный камень при портировании: C++ merge пишет в тот же массив, откуда читает, и в конце указатели записи и чтения могут совпасть. x = std::move(x) для std::string в этой точке молча портит данные (объект остаётся в неопределённом состоянии) — баг не воспроизводился на long long, поймал его только тест на строках. В Go copy() с такими перекрытиями работает корректно по спецификации языка, поэтому там этой проблемы в принципе нет.