С++ библиотека от Google с контейнерами map и set на B-деревьях
Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree [1] (С++ B-Tree), которая содержит различные контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).
Разница в том, что контейнеры в STL реализованы на чёрно-красных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).
B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел чёрно-красного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают излишек указателей и экономят значительное количество памяти.
По тестам, структуры данных на B-деревьях занимают на 50-80% меньше места [2], по сравнению с чёрно-белыми деревьями. В таблице показано среднее количество байт на элемент в контейнерах set/map разного типа. К примеру, стандартный контейнер set<int32_t> создаёт оверхед 16 байт на каждый из множества маленьких элементов, в то время как альтернативный контейнер btree_set<int32_t> создаёт оверхед всего по 1 байту на элемент.
| Тип | Вставка | B-Tree (32-bit) | Red-Black (32-bit) | B-Tree (64-bit) | Red-Black (64-bit) |
| set<int32_t> | sorted | 4.19 | 20.00 | 4.40 | 40.00 |
| random | 4.90 | 20.00 | 5.15 | 40.00 | |
| set<int64_t> | sorted | 8.39 | 24.00 | 8.80 | 40.00 |
| random | 9.96 | 24.00 | 10.47 | 40.00 | |
| set<string> | sorted | 24.57 | 40.00 | 33.60 | 64.00 |
| random | 29.49 | 40.00 | 40.74 | 64.00 | |
| map<int32_t, void*> | sorted | 8.39 | 24.00 | 8.80 | 48.00 |
| random | 9.96 | 24.00 | 10.47 | 48.00 | |
| map<int64_t, void*> | sorted | 12.60 | 28.00 | 13.20 | 48.00 |
| random | 15.16 | 28.00 | 15.92 | 48.00 | |
| map<string, void*> | sorted | 28.67 | 44.00 | 38.16 | 72.00 |
| random | 34.49 | 44.00 | 46.53 | 72.00 |
На некоторых больших контейнерах есть ещё и выигрыш в скорости доступа за счёт более эффективного использования кэша. На графике [3] показано среднее время выполнения вставки, в зависимости от размеров контейнера.
Разработчик предупреждает об отличии cpp-btree от стандартных контейнеров: поскольку любые операции вставки и удаления узлов в B-дерево аннулируют существующие итераторы, так что в случае необходимости нужно использовать безопасные версии [4].
via Google Open Source Blog [5]
Автор: alizar
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/struktury-danny-h/27007
Ссылки в тексте:
[1] cpp-btree: https://code.google.com/p/cpp-btree/
[2] 50-80% меньше места: https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Memory_usage_comparison
[3] графике: https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Performance_comparison
[4] безопасные версии: https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Safe_B-Tree_maps_and_sets
[5] Google Open Source Blog: http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html
[6] Источник: http://habrahabr.ru/post/169199/
Нажмите здесь для печати.