БитМаджик
v.7.13.4
BitMagic был создан как набор инструментов Алгебры множеств для поиска информации, но в настоящее время превратился в более общую библиотеку компонентов Data Science для компактных структур памяти и алгоритмов для кратких векторов данных. BitMagic реализует сжатые битовые векторы и контейнеры (векторы) на основе идей побитового преобразования, сжатия Rank-Select и логических вычислений на моделях со сжатием памяти.
Все краткие контейнеры BitMagic являются сериализуемыми (со сжатием с использованием современного двоичного интерполяционного кодирования) для эффективного хранения и передачи по сети. Все контейнеры доступны для быстрого поиска в сжатом виде.
BitMagic предлагает наборы методов и инструментов для проектирования ваших приложений с использованием технологий высокопроизводительных вычислений для оперативной экономии памяти (таким образом, возможность разместить больше данных в одном вычислительном блоке), улучшения хранения и структуры трафика при хранении векторов данных и моделей в файлах или объектах. хранилища (SQL или noSQL), оптимизируйте пропускную способность системы от низкоуровневого (кеши ЦП) до обмена сетью и хранилищем.
BitMagic поддерживает два больших класса сценариев:
BitMagic использовался в качестве строительных блоков для:
Пожалуйста, посетите наши примечания по использованию: http://bitmagic.io/use-case.html.
Библиотека BitMagic — это высокопроизводительная библиотека, реализующая оптимизацию для различных платформ и целей сборки:
BitMagic использует векторизованный дизайн с параллельными данными с целью не только обеспечить наилучшую однопоточную производительность, но и облегчить параллельные вычисления в многоядерных системах.
BitMagic использует набор алгоритмов сжатия, фильтров и преобразований для уменьшения объема памяти, затрат на хранение и передачи данных по сети. http://bitmagic.io/design.html
Пожалуйста, посетите наши технические заметки: http://bitmagic.io/articles.html.
BitMagic поддерживает переинтерпретацию битовых векторов как набор непересекающихся диапазонов единиц, окруженных нулями (например: 011110110). Обычные функции множеств обеспечивают операции пересечения множеств/объединений между интервалами, реализуют интервальный итератор и ищут границы интервалов. Диапазоны и интервалы очень полезны в биоинформатике, поскольку данные геномики часто обозначаются как диапазоны координат. BitMagic предлагает строительные блоки для эффективных операций с интервалами, закодированными в виде битовых векторов (найти начало/конец интервала, проверить, является ли диапазон интервалом, выполнить итерацию интервалов).
BitMagic реализует логические операции для трехзначной логики True/False/Unknown (также троичная логика, трехвалентная, троичная) в компактном двухбитовом векторном представлении, поддерживая операции Invert, AND, OR в соответствии с определениями Клини. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic использует концепцию двухэтапной сериализации-десериализации. Основное внимание уделяется быстрой десериализации. BitMagic реализует API для быстрой десериализации векторного диапазона и десериализации сжатых BLOB-объектов. Главной особенностью BitMagic является возможность работы со сжатыми данными.
Это основное рабочее состояние оперативной памяти, при котором векторы хранятся в компактной форме памяти. Краткость — это НЕ сжатие. Можно получать доступ к случайным элементам в контейнерах, декодировать блоки, перебирать векторы, вносить обновления, запускать алгоритмы поиска. Stage One предлагает прозрачное использование, его векторы очень похожи на STL. Succinct — это компактный формат памяти, но не полностью сжимаемый.
BitMagic может сериализовать все контейнеры и векторы с дополнительным сжатием на основе блочных эвристик и кодеков. К рабочим методам кодирования относятся: двоичное интерполяционное кодирование (BIC) и Элиас Гамма.
Контейнеры BitMagic называются «разреженными» векторами, но на самом деле их схемы сжатия хорошо работают как с разреженными, так и с плотными данными.
BitMagic тестируется на эталонном наборе инвертированных списков Gov2 и наборе собственных наборов данных. http://bitmagic.io/bm5-cmpr.html
Десериализация всегда возвращается на первый этап, поэтому данные не декодируются полностью, а вместо этого
краткий в оперативной памяти. Наша цель здесь — уменьшить объем памяти приложения и улучшить задержку десериализации. Алгоритмы декомпрессии поддерживают десериализацию произвольных диапазонов или даже сбор десериализации элементов.
BitMagic поддерживает краткие (компактные в памяти) векторы на основе преобразования битов.
также известное как сжатие битовой плоскости (BPC) (также известное как битовая нарезка) плюс сжатие с выбором ранга. Сжатые векторы BitMagic ошибочно называются «разреженными», но они прекрасно работают с плотными векторами.
Транспонирование битов решает две цели: освободить неиспользуемые битовые поля и изолировать регулярность и энтропию в отдельные (разреженные) битовые векторы. Сжатие на битовых плоскостях обеспечивает как превосходную производительность памяти, так и быстрый поиск. Одна из целей разработки — выполнять поиск без индекса по кратким векторам с использованием быстрых векторизованных логических операций.
Краткие векторы BitMagic доступны для поиска без индексов в сжатой в памяти форме. Это быстро!
Краткая реализация транспонирования битов хорошо работает как для целочисленных векторов (со знаком или без знака), так и для строковых векторов. Он конкурирует с другими краткими схемами, такими как деревья префиксов. Сжатые векторы могут быть как отсортированными, так и неотсортированными. Идея здесь аналогична Apache Arrow-Parquet, но она идет дальше за счет побитового сжатия и широкого использования ускоренного сжатия Rank-Select.
BitMagic поддерживает эволюцию сериализации (протокола) — если формат сериализации изменяется, старые сохраненные данные остаются доступными для чтения новым кодом. Старый код НЕ сможет читать новые BLOB-объекты. BitMagic меняет основной номер версии при изменении формата сериализации.
BitMagic реализует вызовы профилирования памяти для всех векторов. Любой вектор может быть выбран для определения объема памяти, чтобы система верхнего уровня могла адаптировать управление памятью на основе профилирования памяти во время выполнения. Типичный вариант использования — кэширование объектов в памяти со сжатием в ОЗУ и последующим вытеснением на диск в зависимости от потребления ресурсов и затрат (динамический баланс спроса и предложения).
Да! BitMagic поддерживает 64-разрядную версию, может использоваться с 32-разрядным адресным пространством (меньше накладных расходов) или с полным 64-разрядным адресным пространством. 32-битное адресное пространство является режимом по умолчанию. Элементы 2^31-1 должны хорошо подходить для систем IR и обработки данных малого и среднего радиуса действия. Режим 64-битной адреса доступен с помощью #define BM64ADDR или #include "bm64.h". Текущая 64-битная реализация позволяет использовать векторные элементы 2^48-1 для крупномасштабных систем.
BitMagic компилируется и работает с WebAssmbly (emscripten). Последние версии включают в себя несколько настроек, специфичных для платформы. Показатели производительности близки к нативному коду без SIMD (иногда позже). Пример строки компиляции будет выглядеть так:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD поддерживается, но по умолчанию он не включен. Используйте: #define BMWASMSIMDOPT , чтобы включить его. Пример Emscripten cmd:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti
Текущая реализация использует транс-компиляцию SSE4.2 (через встроенные функции), поэтому необходим -msse4.2 .
BitMagic полностью поддерживает процессоры ARM. Все выпуски проходят стресс-тестирование с Raspberry Pi 4. BitMagic реализует некоторые алгоритмические настройки и улучшения, специфичные для ARM (например, использование инструкции LZCNT). Краткие контейнеры BitMagic могут быть очень полезны во встроенных системах для периферийных вычислений с ограниченным объемом доступной памяти.
Доступна поддержка Arm Neon SIMD (через библиотеку SSE2NEON).
BitMagic C++ — это библиотека только для заголовков (легкую в сборке и использовании в вашем проекте), которая поставляется с набором примеров. НЕ рекомендуется использовать тесты в качестве примера кода для изучения использования библиотеки. Тесты не иллюстрируют лучшие шаблоны и модели использования и часто намеренно неэффективны.
Документация и примеры API: http://www.bitmagic.io/apis.html.
Учебник по алгебре множеств: http://bitmagic.io/set-algebra.html.
Варианты использования и рекомендации по применению: http://bitmagic.io/use-case.html.
Технические примечания по оптимизации производительности: http://bitmagic.io/articles.html.
Doxygen: http://bitmagic.io/doxygen/html/modules.html.
Апач 2.0.
Важный! Мы просим вас явно упоминать проект BitMagic в любой производной работе или наших опубликованных материалах. Правильная ссылка на странице вашего продукта/проекта является ОБЯЗАТЕЛЬНЫМ условием использования библиотеки BitMagic.
Библиотека BitMagic уделяет серьезное внимание качеству кода и тестовому покрытию.
Чтобы быть полезной, библиотека строительных блоков BitMagic должна быть стабильной и совместимой.
Мы не полагаемся только на модульные тесты, в наших тестах часто используется «тестирование хаоса» (также известное как фаззинг), где стресс-тесты основаны на рандомизированных сгенерированных наборах и рандомизированных операциях. Мы регулярно создаем и запускаем тестовые комплекты для режимов выпуска и отладки для различных комбинаций SIMD-оптимизаций.
Все варианты тестовых сборок выполняются в течение нескольких дней, поэтому работающая основная ветка НЕ гарантированно будет всегда идеальной. Для производства используйте стабильные ветки выпуска GitHub или дистрибутивы SourceForge: https://sourceforge.net/projects/bmagic/files/
Мастер GitHub принимает запросы на исправления. Наша политика ветвления заключается в том, что мастер не может считаться полностью стабильным между выпусками. (для стабильности производства используйте релизные версии)
Нужна помощь с сопоставлением с Python и другими языками (BitMagic имеет привязки C)
BitMagic C++ — это пакет программного обеспечения, предназначенный только для заголовков, и вы, вероятно, можете просто взять исходные коды и напрямую поместить их в свой проект. Все исходные коды/заголовки библиотеки C++ находятся в каталоге src.
Однако если вы хотите использовать наши make-файлы, вам необходимо следовать следующим простым инструкциям:
Примените несколько переменных среды, запустив bmenv.sh в корневом каталоге проекта:
$ source ./bmenv.sh
(пожалуйста, используйте "." "./bmenv.sh" для применения корневой переменной среды)
используйте GNU make (gmake) для сборки установки.
$make rebuild
или (версия DEBUG)
$gmake DEBUG=YES rebuild
Компилятором по умолчанию в Unix и CygWin является g++. Если вы хотите изменить значение по умолчанию, вы можете сделать это в makefile.in (это должно быть довольно легко сделать)
Если вы используете установку Cygwin, следуйте общим рекомендациям Unix. MSVC — решение и проекты доступны через CMAKE.
Xcode — файлы проекта доступны через CMAKE.
Библиотека BitMagic для сопоставлений C и JNI.
Библиотека BitMagic доступна для языка C (работа в стадии разработки). Основная цель сборки C — соединить BitMagic с другими языками программирования. Сборка C находится в подкаталоге «lang-maps».
Сборка C создает версии сборки BitMagic для SSE и AVX и добавляет идентификацию ЦП, поэтому система верхнего уровня может поддерживать динамическую идентификацию ЦП и отправку кода.
Сборка C использует компилятор C++, но не использует RTTI, исключения (имитируемые с помощью длинного перехода) и управление памятью C++, поэтому она нейтральна к языку C++ и не зависит от времени выполнения. Алгоритмы и поведение являются общими для C и C++.
Текущее состояние разработки:
Ожидается поддержка Python, и нам нужна помощь. Если вы увлечены Python и думаете, что можете помочь, свяжитесь с: anatoliy.kuznetsov @ yahoo dot com.
Для библиотеки BitMagic требуется CXX-11. Он использует семантику перемещения, noexept, списки инициализаторов, потоки. Следующая общедоступная версия будет использовать CXX-17 (constexpr ifs и т. д.).
###Точная настройка и оптимизация:
Все параметры тонкой настройки BitMagic контролируются определениями препроцессора (и целевыми ключами компилятора для генерации кода).
| #определять | Описание | Ширина |
|---|---|---|
| БМССЕ2ОПТ | Оптимизация кода SSE2 | 128-битный |
| БМССЕ42ОПТ | Оптимизация кода SSE4.2, а также POPCNT, BSF и т. д. | 128-битный |
| БМАВХ2ОПТ | Оптимизация AVX2, POPCNT, LZCNT, BMI1, BMI2 | 256-битный |
| БМАВХ512ОПТ | AVX-512, (экспериментальный) | 512-битный |
| BMWASMSIMDOPT | Оптимизация SIMD WebAssembly (через SSE4.2) | 128-битный |
| ДБМНЕОНОПТ | Оптимизация Arm Neon SIMD (через трансляцию SSE2) | 128-битный |
####Ограничения:
Определения оптимизации SIMD являются взаимоисключающими, вы НЕ можете использовать BMSSE42OPT и BMAVX2OPT одновременно. Выберите только один.
Библиотека BM НЕ поддерживает несколько путей кода и идентификацию ЦП во время выполнения. Вам необходимо выполнить сборку специально для вашей целевой системы или использовать переносимую сборку по умолчанию.
####Примеры:
Примеры и тесты BitMagic можно построить с помощью GCC, используя настройки командной строки:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
или
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Он автоматически применяет правильный набор флагов компилятора (GCC) для целевой сборки.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
ИЛИ
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
Библиотека BM поддерживает ключевое слово «restrict», некоторые компиляторы (например, Intel C++) генерируют более качественный код (неупорядоченные загрузочные хранилища), когда ключевое слово «restrict» помогает. По умолчанию эта опция отключена, поскольку большинство компиляторов C++ ее не поддерживают. Чтобы включить его, определите #define BM_HASRESTRICT в своем проекте. Некоторые компиляторы используют для этой цели ключевое слово «__restrict». Чтобы исправить это, определите макрос BMRESTRICT для исправления ключевого слова.
Если вы хотите использовать библиотеку BM в «проекте без STL» (например, встроенных системах), определите BM_NO_STL.
Это правило применимо только к основным методам bm::bvector<>. Вспомогательные алгоритмы, примеры и т. д. по-прежнему будут использовать STL.
Следуйте за нами в Твиттере: https://twitter.com/bitmagicio
Благодарим вас за использование библиотеки BitMagic!
электронная почта: [email protected]
ВЕБ-сайт: http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
