Искусство разрушения: HArray

Начало

Всем привет. В прошлом топике мы тестировали открытый исходный код HArray. Кто не знаком, краткое резюме по этому проекту. Первое — это Key/Value контейнер, который построен совершенно иначе, чем Hashtables или Binary Trees, на совершенно других алгоритмах. Это открывает путь принципально иных, фундаментальных преимуществ.

1. Очень высокая скорость работы. Бенчмарки можно посмотреть тут. Тестирование без всяких подвохов, Key/Value контейнер имеет достаточно простые сценарии использования. В среднем HArray в 5-10 раз быстрее работает чем типичные реализации контейнеров вроде std::map, при этом имея даже немного более широкую функциональность. И в многих кейсах работает быстрее чем Hashtables, особенно на скорости вставок. Единственный кейс где Hashtables уверенно обгоняет HArray, это ключи последовательной природы, вроде 1,2,3 и тд. Но ирония в том, что для таких ключей Вам не нужен HArray, не нужен Hashtables или другой map, а подойдет обычный массив.

2. Малое потребление памяти. Для монотонных ключей, которые имеют общий префикс (пути к файлам, пути к обьектам, словари и тд) возможна компрессия данных по сравнению с оригинальным их размером. Компрессия данных невозможна в бинарных деревьях и тем более в хештаблицах, где перерасход памяти стабильно составляет в 2-3 раза.

3. Данные в контейнере находятся в сортированом (или близком к этому) виде. Возможность очень быстро определять, есть ли ключ с каким либо префиксом в контейнере. Доступна широкая функциональность по скану ключей. Возможность сканировать поддиапазоны ключей. При этом при сканировании поддиапазона мы не читаем все ключи вподряд, а как бы сканируем только «хвосты» ключей. Такая функциональность недоступна в хештаблицах и доступна в неоптимальном виде в бинарных деревьях.

4. Специфические, но не синтетические, контр примеры. Это когда вставляются длинные ключи с похожими префиксами. Они не использовались в бенчмарках, чтобы не давать HArray явное преимущество, но на этих контр примерах потребление памяти и скорость работы может отличатся в десятки и сотни раз в пользу HArray.

5. Нет хешфункций, нет коллизий. HArray отлично работает с большими обьемами данных, вставить миллиард ключей или больше в такую структуру не проблема. При этом плавное потребление памяти и почти константное время на вставках/поиске, которое зависит скорее от длины ключа, а не от количества ключей.

6. Еще немного плюшек: Возможность задавать правила сортировки ключей внутри контейнера. Нет Stop World событий на вставке (это когда структуре в какойто момент необходимо полностью перестроится, что занимает время). Сериализация/десериализация на диск, на скоростях близких к максимальной скорости работы диска (поскольку структура сбрасывает и подымает на диск страницы памяти, а не делает обход всего графа).

7. Удаление ключей.

И на этом остановимся подробней.

Разрушение

Сложный клеточный автомат характеризуется не только тем, как развивается и усложняется его структура в процессе роста но и регенеративными свойствами. Например, как организм может запускать процесс программируемой клеточной гибели. Как одни клетки, могут отдавать другим клеткам сигналы, чтобы разбирать их на элементарные строительные блоки и утилизировать. Как могут использоваться эти блоки для построения и поддеркжи жизнедеятельности других клеток. И наконец, как организм может выводить излишки из организма мертвых разрушенных тканей, попутно сворачивая и оптимизируя свою структуру.

В HArray, как в поисковом алгоритме который наиболее приближен (по моему мнению) к биологическим живым системам, процесс разрушения ключей очень похож на то, что происходит в живом микромире. Когда мы удаляем ключ, этот ключ должен быть разобран на базовые строительные блоки: ContentCells, BranchCells, BlockCells, VarCells. Блоки ключей которые не нужны, формируют мертвые ткани (died fibres), которые связаны между собой и готовы к переиспользованию для построения новых ключей. Если таких тканей слишком много, они должни быть выведены из контейнера, чтобы не занимать лишнюю память, а сама структура данных должна быть упрощена. Начинается обратный процесс развития, сложное схлопывается в простое и наоборот, развивается и усложняется при добавлении новых ключей.

Собственно процесс удаления ключей существенно сложнее, чем добавление. Представьте что у вас есть небоскреб, который состоит из сотен миллионов кирпичиков, арок, перегородок, пилонов, оконных рам и тд. У вас задача вынуть серию блоков где-то на 5м, 6м и 38м этаже, но так, чтобы все здание не рухнуло.

Это интересный процесс. И еще интересней, повторить то, как работают клеточные автоматы.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті