news.shamcode.ru | Black-White Array: новая структура данных с O(log N) аллокаций

Кратко

Black-White Array (BWA) — это упорядоченная структура данных с амортизированным временем операций вставки/поиска/удаления $O(\log N)$ и $O(\log N)$ используемых участков памяти. Пример реализации и оригинальная научная публикация.

Преимущества

Амортизированное время вставки/удаления/поиска $O(\log N)$ - сравнимое с BTree от Google;
Количество аллокаций памяти при операциях вставки так же $O(\log N)$ - меньше давления на сборщик мусора, ниже фрагментация памяти;
Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным;
Позволяет хранить элементы с одинаковыми ключами - не нужно использовать дополнительные структуры для группировки таких элементов;
Низкий оверхед на хранение служебной информации - экономия памяти по сравнению с другими структурами данных;
Удобен для вставки батчами;
Простая сериализация и десериализация;

Компромиссы

Время вставки варьируется от - каждая вторая вставка, до - один раз на N операций, но амортизированное время $O(\log N)$ . Для near-real-time систем это может быть критично. Эффект может быть нивелирован вставкой батчами, или асинхронной вставкой в фоне.
При редких паттернах операций массового удаления, возможна деградация производительности поиска до . Эффект может быть предотвращен вызовом метода Compact().

Подробности

Основная идея

Как известно, любое число N можно представить в двоичной системе счисления, или, говоря языком математики, как сумму степеней двойки.Например, число $5_{10}$ можно представить как , что в двоичной системе будет . Соответственно, для хранения N элементов можно использовать набор массивов, где размер каждого массива будет степенью двойки (1, 2, 4). Таким образом, для хранения 5 элементов нам понадобятся массивы размером 4 и 1. Обобщая, для хранения N элементов нам понадобятся $\log_2 N$ массивов, размер каждого из которых будет степенью двойки.

Чтобы поддерживать упорядоченность элементов, каждый массив должен быть отсортирован внутри. Сортировка между массивами не требуется: элементы из
массива размером 4 могут быть меньше, больше или равны элементу из массива размером 1.

Поиск

Для поиска элемента с ключом K, мы просто последовательно перебираем массивы, выполняя бинарный поиск в каждом из них:

for arrNum := 0; arrNum < len(arrays); arrNum++ {
  index := binarySearch(arrays[arrNum], K) 
    if index != -1 {
        return arrays[arrNum][index]
    }
}

Оптимизация: не нужно искать во всех массивах, только в тех, где сейчас хранятся элементы. Для 5 элементов это будут массивы размером 4 и 1, массив размера 2 можно пропустить. Количество хранимых элементов N в двоичной системе является битовой маской для выбора массивов, в которых нужно искать элементы:

for arrNum := 0; arrNum < len(arrays); arrNum++ {
    if N & (1 << arrNum) == 0 { // Skip unused arrays
        continue
    }
    index := binarySearch(arrays[arrNum], K)
    if index != -1 {
        return arrays[arrNum][index]
    }
}

Оценка трудоёмкости: в худшем случае нам нужно будет искать во всех $\log_2 N$ массивах:

$T_{search} = O(\log_2(N/2)) + O(\log_2(N/4)) + \cdots + O(\log_2 1) = O((\log_2 N)^2)$

В среднем случае, количество операций поиска зависит от вероятности нахождения элемента в каждом массиве. При равномерном распределении вероятностей искомый элемент будет найден в самом большом массиве с вероятностью 1/2, во втором по размеру с вероятностью 1/4 и т.д. Таким образом, среднее количество операций поиска будет: $O(\log_2 N)$ . За подробным доказательством оценки трудоёмкости поиска можно обратиться к оригинальной научной публикации, §4.1, Theorem 5. Мы же посмотрим на бенчмарки. За эталон был взят BTree от Google, с degree равным 32.

В бенчмарке производится вставка нескольких миллионов значений int64 с последующим поиском каждого из них. Как видно из графика, BWA показывает производительность, сравниму�� с BTree. При этом BWA аллоцирует значительно меньше участков памяти и потребляет меньше памяти в целом. Но об этом в следующем разделе.

Вставка

Если при вставке нового элемента массив размера 1 свободен -- мы просто вставляем элемент туда за . Нетрудно заметить, что каждая вторая вставка будет такой - для каждого четного N. Рассмотрим случай, когда массив размера 1 уже занят для N=5. Если массив для вставки элемента занят, он помещается во временный массив. Основные массивы называются "белыми", а временные -- "черными". Отсюда и название структуры данных - Black-White Array. Черный массив объединяется с белым того же размера и помещается в следующий по размеру белый массив (он как раз в два раза больше).
Объединение массивов происходит при помощи слияния (механизм, похожий на merge sort), что обеспечивает сохранение упорядоченности элементов внутри массива, дальше рассмотрим это подробнее.

Пример для N=5, вставляем элемент со значением 11:

Вставляем 11 во временный массив размера 1 (черный);
Объединяем черный массив размера 1 с белым массивом размера 1, получаем массив [11,23];
Помещаем полученный массив в белый массив размера 2 (он был пуст);
Помечаем белый массив размера 1 как свободный.

Если белый массив большего размера занят, то запись результата объединения происходит в черный массив соответствующего размера, и процесс повторяется рекурсивно, пока не найдется (или не будет создан) свободный белый массив.

Слияние массивов

Для объединения двух массивов используется классический алгоритм слияния из сортировки слиянием (merge sort). Так как оба массива уже отсортированы, мы просто
последовательно сравниваем элементы каждого массива, выбирая меньший из них и помещаем его в результирующий массив:

func MergeArrays(arr1, arr2 []Element) []Element {
    merged := make([]Element, len(arr1)+len(arr2))
    src1, src2, dst := 0, 0, 0
    for src1 < len(arr1) && src2 < len(arr2) {
        if arr1[src1].Key <= arr2[src2].Key {
            merged[dst] = arr1[src1]
            src1++
        } else {
            merged[dst] = arr2[src2]
            src2++
        }
        dst++
    }
    // Copy remaining elements: one of sources will be empty  
    copy(merged[dst:], arr1[src1:])
    copy(merged[dst:], arr2[src2:])
    return merged
}

Особый случай вставки

Рассмотрим наиболее интересный случай, когда все массивы заняты, при N=7, вставляем элемент со значением 13:

Так как белый массив размером 1 занят, вставляем 13 во временный массив размера 1 (черный);
Объединяем черный массив размера 1 с белым массивом размера 1, получаем массив [13, 16] (черный, так как белый массив размера 2 занят);
Объединяем черный массив размера 2 [13, 16] с белым массивом размера 2 [11, 23], получаем массив [11, 13, 16, 23] (черный, так как белый массив размера 4 занят);
Так как белый массив размера 8 отсутствует, создаем его.
Объединяем черный массив размера 4 с белым массивом размера 4, записывая результат в только что созданный, белый массив размера 8.

Таким образом эта вставка элемента потребовала перемещения всех 7 элементов, что занимает времени. Однако, такая ситуация возникает только один раз на N вставок.
Нетрудно видеть, что последующая вставки займут , затем , затем снова и т.д. Тогда амортизированное время вставки будет:

$T_{insert} = \frac{O(1) + O(2) + O(1) + O(4) + \cdots + O(N)}{N} = O(\log_2 N)$

За подробным доказательством оценки трудоёмкости вставки можно обратиться к оригинальной научной публикации, §4.1, Corollary 3.
Мы же снова посмотрим на бенчмарки:

Видим, что BWA показывает производительность вставки, даже лучше, чем BTree, несмотря на худший случай для вставки одного элемента. Насколько же плох этот худший случай на практике? На современных процессорах(AMD64 и ARM64) наихудший случай вставки в BWA с ~1M элементов int64 занимает около 10 миллисекунд.
Это может быть проблемой для near-real-time систем с жесткими требованиями по времени отклика. В остальных случаях, амортизированное время вставки $O(\log N)$ показывает себя отлично. Для уменьшения влияния худшего случая вставки, можно использовать вставку батчами, или асинхронную вставку в фоне.

Аллокации памяти - почему это важно?

Меньше аллокаций - меньше давления на сборщик мусора, что особенно важно для языков с GC (Go, Java, Python и т.д.). Сборщик мусора как правило запускается каждые несколько миллисекунд и обходит все "живые" объекты в памяти, затрачивая на это процессорное время, даже если приложение в это время ничего не вычисляет. Если объектов миллионы, то потребление CPU может быть заметным.
Рассмотрим график меньшего масштаба, так как на предыдущем не видны изменения для BWA:

Количество аллокаций памяти при вставке элемента в BWA порядка $O(\log N)$ .

Обратите внимание, что при вставке BWA не производит поиск и позволяет вставлять элементы с одинаковыми ключами без дополнительных приёмов. Среди одинаковых ключей сохраняется порядок вставки (стабильность): более новые элементы будут в более коротких массивах.

Удаление

Для удаления элемента его нужно сначала найти (см. поиск). Далее профессор Моу (автор оригинальной публикации) предлагает заменить значение элемента на специальное void.
В некоторых языках программирования такой подход вполне работает: можно использовать None в Python, undefined в JavaScript и т.д. В Go, C, C++ такой подход не работает, так как эти языки не поддерживают nullable значения для примитивных типов (int, float, etc). Использовать указатели и их значения nil/null не эффективно: дополнительный уровень косвенности и нагрузка на сборщик мусора.
В своей реализации BWA для Go я использую массив битов, где каждый бит соответствует элементу в массивах BWA. Таким образом, при удалении элемента нужно просто установить соответствующий бит в 1 (удален).

Но что, если удаленных элементов становится слишком много? Когда удалённых элементов в каком-либо массиве накапливается половина от общего количества, нужно выполнить процедуру demote (понижение) для него. Суть процедуры: перемещаем все n/2 "живых" элементов из массива размера n в предыдуший по размеру массив (n/2). Если предыдущий массив занят, то выполняем слияние с ним, как при вставке и помещаем результат в текущий массив размером n.

func DemoteArray(arr []Element, deleted []bool) []Element {
	result := make([]Element, 0, len(arr)/2)
	for i := range arr {
        if !deleted[i] {
            result = append(result, arr[i])
        }
    }
	return result
}

Рассмотрим сначала пример удаления и понижения сегмента без объединения с предыдущим (он свободен):

Удаляем элемент со значением 17, из сегмента размера 4, помечая соответствующий бит в массиве удаленных элементов (не приведен на иллюстрации для упрощения);
Удаляем элемент со значением 42, из сегмента размера 4. Теперь в сегменте размера 4 удалено 2 из 4 элементов, что составляет половину. Выполняем понижение:
Перемещаем "живые" элементы [8, 33] в предыдущий сегмент размера 2;
Помечаем сегмент размера 4 как свободный.

Теперь рассмотрим пример удаления и понижения сегмента с объединением с предыдущим (он занят):

Здесь шаги 1 и 2 аналогичны предыдущему примеру. Далее:
3. Перемещаем "живые" элементы [8, 33] в черный сегмент размера 2 (так как белый занят);
4. Объединяем черный сегмент размера 2 с белым сегментом размера 2 [19, 23], получаем [8, 19, 23, 33] и помещаем его в белый сегмент размера 4, который был освобожден процедурой demote.

Таким образом структура данных поддерживает заполнённость сегментов на уровне не менее 50%. Что касается трудоёмкости операции удаления, то интуитивно понятно,
что амортизированное время удаления будет $O(\log N)$ . Понижение самого большого сегмента (размера N/2) происходит не чаще одного раза на N/4 удалений. Понижение меньших сегментов, требует меньше времени и в среднем ��енее вероятно. Подробное доказательство смотрите в оригинальной научной публикации, §4.1, Theorem 7.

Необходимо отметить, что использование массива битов для пометки удаленных элементов требует модификации процедуры поиска: при поиске нужно пропускать элементы, помеченные как удалённые. Подробнее можно посмотреть в исходном коде реализации BWA.

Об авторе оригинальной публикации

Идея BWA принадлежит профессору Йельского университета Джорджу Моу (Z. George Mou), я отправил ему реализацию BWA на Go, и он её одобрил. Сейчас профессор Моу работает над публикацией алгоритма пространственного поиска и его открытой реализации на C++.

Заключение

Black-White Array представляет собой интересную структуру данных, которая сочетает в себе преимущества массивов (последовательное хранение данных, низкий оверхед) и сбалансированных деревьев (логарифмическое время операций).
Однако нужно учитывать компромиссы, такие как вариативное время вставки и возможная деградация производительности поиска при определённых паттернах операций удаления.
Типичная область применения BWA - индексы в памяти, особенно с повторяющимися ключами, где важна скорость вставки и поиска, а также низкое потребление памяти и давление на сборщик мусора.

В статье я намеренно опустил некоторые детали реализации и оптимизации, чтобы сосредоточиться на основных концепциях. Детали и оптимизации можно найти в моей реализации.
Ваши звёзды ★ на GitHub будут для меня лучшей благодарностью! Так же смело присылайте пулл-реквесты с оптимизациями и улучшениями. С вопросами - добро пожаловать в комменты.