Интервью с Анатолием Кузнецовым, автором библиотеки BitMagic C++ Library
- Введение
- Здравствуйте, Анатолий. Расскажите, пожалуйста, немного о себе. Какими проектами Вы занимаетесь?
- Что такое библиотека BitMagic?
- При решении каких задач BitMagic представляет наибольший интерес для разработчиков?
- Какова история создания библиотеки BitMagic? Что послужило поводом к ее созданию?
- На каких условиях распространяется библиотека BitMagic? Где можно ее скачать?
- Правильно ли я понимаю, что библиотека BitMagic получает существенные преимущества при компиляции в 64-битном варианте?
- Расскажите о методах компрессии, используемых в BitMagic
- Не могли бы Вы привести пару примеров кода, демонстрирующих использование библиотеки BitMagic?
- Какие планы по развитию библиотеки BitMagic?
В этой статье Анатолий Кузнецов отвечает на вопросы и рассказывает об открытой библиотеке BitMagic C++ Library.
Введение
Регулярно просматривая ресурсы интернета, связанные с тематикой 64-битного программирования, я неоднократно встречал упоминание библиотеки BitMagic и то, что она получила существенные преимущества от использования 64-битности. Я решил связаться с автором библиотеки и предложить ему рассказать в интервью о своих исследованиях и разработках.
Вопросы задает: Андрей Карпов - сотрудник компании "Системы программной верификации", занимающийся созданием инструмента PVS-Studio для проверки современных приложений на языке Си++.
На вопросы отвечает: Анатолий Кузнецов - старший инженер по разработке программного обеспечения в NCBI. Является разработчиком открытой библиотеки BitMagic C++ Library.
Здравствуйте, Анатолий. Расскажите, пожалуйста, немного о себе. Какими проектами Вы занимаетесь?
Здравствуйте Андрей!
Я старший инженер по разработке программного обеспечения, в данный момент я работаю в группе поиска и визуализации биомолекулярной информации NCBI (National Center for Biotechnology Information). Помимо своей основной деятельности я являюсь основным разработчиком и архитектором открытой библиотеки BitMagic C++ Library.
По образованию я инженер-экономист, выпускник Нижегородского Университета им. Лобачевского.
Что такое библиотека BitMagic?
Библиотека BitMagic разрабатывалась как универсальная библиотека шаблонов для работы с компрессированными битовыми векторами. Библиотека решает несколько задач:
- Предоставляет битовый контейнер, по-настоящему совместимый по идеологии с STL. Это значит, что контейнер должен поддерживать итераторы, аллокаторы памяти, взаимодействовать с алгоритмами и другими STL контейнерами.
- Библиотека умеет эффективно оперировать с очень длинными и разреженными векторами.
- Предоставляется возможность сериализации векторов для последующей записи их в базы данных или пересылке по сети.
- Разработчику предоставляется набор алгоритмов для реализации теоретико-множественных операций и подсчета расстояний и метрик подобия в многомерных двоичных пространствах.
- Значительное внимание уделяется оптимизации под распространенные системы ускорения расчетов, такие как SSE.
При решении каких задач BitMagic представляет наибольший интерес для разработчиков?
Библиотека получилась довольно универсальная, и перечислить все возможные применения, наверное, будет не просто. В данный момент библиотека наиболее интересна в следующих областях:
- Построение битовых и инвертированных индексов для полнотекстовых поисковых систем, ускорение операций реляционной алгебры (AND, OR, JOIN, и так далее).
- Разработка нестандартных расширений и индексов для существующих СУБД (Oracle Cartridges, MS SQL extended stored procedures). Такие расширения, как правило, помогают интегрировать в СУБД научные, географические или какие-то другие нестандартные данные.
- Разработка алгоритмов анализа данных (data mining).
- Разработка бездисковых индексов и баз данных (in-memory databases).
- Разработка систем точного разграничения доступа с большим количеством объектов (базы данных повышенной секретности с разграничением доступа к отдельным полям и колонкам).
- Системы управления задачами (на вычислительном кластере), системы real-time отслеживание состояния задач, хранение состояний задач, описываемых как конечные автоматы (Finite State Machines).
- Задачи представления и хранения связанных графов
Какова история создания библиотеки BitMagic? Что послужило поводом к ее созданию?
Я и мои коллеги продолжительное время занимались задачами, связанными с большими базами данных, системами анализа и визуализации. Самую первую рабочую версию, демонстрирующую возможности битовых векторов, показал Максим Шеманарев (он является разработчиком великолепной библиотеки 2D векторной графики Antigrain Geometry). Потом некоторые идеи по эквивалентному представлению множеств были описаны инженером из Европы Koen Van Damm, работавшим над парсерами языков программирования для верификации сложных систем. Были и другие источники. Все это я решил как-то систематизировать и представить в виде библиотеки пригодной для многократного повторного использования в разных проектах.
На каких условиях распространяется библиотека BitMagic? Где можно ее скачать?
Библиотека свободна для коммерческого и некоммерческого использования, доступна в виде исходных текстов. Единственным ограничением является требование упоминания библиотеки и авторов при использовании в конечном продукте.
С материалами можно ознакомиться тут: http://bmagic.sourceforge.net.
Правильно ли я понимаю, что библиотека BitMagic получает существенные преимущества при компиляции в 64-битном варианте?
Действительно, библиотека использует серию оптимизационных приемов ускоряющих работу в 64-битных системах или системах с SIMD командами (128-bit SSE2).
Факторы, ускоряющие выполнение алгоритмов:
- широкое машинное слово (логические операции исполняются над широким словом);
- программисту (и компилятору) доступны дополнительные регистры, не так критичен дефицит регистров (есть такой наследственный недостаток у архитектуры x86);
- выравнивание памяти часто ускоряет работу (128-битное выравнивание адресов дает неплохой результат);
- ну и конечно возможность помещать в память одной программы больше объектов и обрабатываемых данных. Это всем понятный и бесценный плюс 64-битного варианта.
В данный момент наиболее быстрым вариантом является использование 128-bit SSE2 оптимизации в 64-битной программе. Такой режим совмещает удвоенное количество x86 регистров и широкое машинное слово для выполнения логических операций.
64-битные системы и программы переживают сейчас настоящий ренессанс. Перевод программ под 64 бита будет происходить быстрее, чем в переход с 16 на 32. Этому будет способствовать выход на массовый рынок 64-битных версий Windows и доступный инструментарий (такой как разрабатываете ваша компания). В условиях постоянного роста сложности систем и объема используемого в них кода такой инструментарий, как PVS-Studio, является хорошим подспорьем, так как сокращает трудозатраты и увеличивает скорость вывода продуктов на рынок.
Расскажите о методах компрессии, используемых в BitMagic
Текущая версия 3.6.0 библиотеки использует несколько методов сжатия.
- "Битвектора" в памяти разбиты на блоки. Если блок не занят или занят полностью - он не аллoцируется. То есть программист свободен устанавливать биты в очень далеком от нуля диапазоне. Установка бита 100,000,000 не вызывает взрыв в потреблении памяти, часто свойственный векторам с плоской линейной моделью.
- Блоки в памяти могут иметь эквивалентное представление в виде площадок - гапов. Фактически это вариант RLE кодирования. В отличие от RLE, наша библиотека не теряет возможности выполнять логические операции или адресовать отдельные биты (random bit access).
- При сериализации "битвекторов" применяется набор других методов: преобразование в списки целых чисел (отражающих нули или единицы) и кодирование списков методом Elias Gamma Coding. При использовании данных методов теряется возможность адресовать отдельные биты, но для записи на диск это не так критично, по сравнению с сокращением затрат на хранение и ввод-вывод.
Не могли бы Вы привести пару примеров кода, демонстрирующих использование библиотеки BitMagic?
Один из примеров просто создает 2 вектора, проводит их инициализацию и выполняет логическую операцию AND. Далее используется класс enumerator для итерирования и печати значений, сохраненных в векторе.
#include <iostream>
#include "bm.h"
using namespace std;
int main(void)
{
bm::bvector<> bv;
bv[10] = true; bv[100] = true; bv[10000] = true;
bm::bvector<> bv2(bv);
bv2[10000] = false;
bv &= bv2;
bm::bvector<>::enumerator en = bv.first();
bm::bvector<>::enumerator en_end = bv.end();
for (; en < en_end; ++en) {
cout << *en << endl;
}
return 0;
}Следующий пример демонстрирует сериализацию векторов и использование режима компрессии.
#include <stdlib.h>
#include <iostream>
#include "bm.h"
#include "bmserial.h"
using namespace std;
// This procedure creates very dense bitvector.
// The resulting set will consists mostly from ON (1) bits
// interrupted with small gaps of 0 bits.
//
void fill_bvector(bm::bvector<>* bv)
{
for (unsigned i = 0; i < MAX_VALUE; ++i) {
if (rand() % 2500) {
bv->set_bit(i);
}
}
}
void print_statistics(const bm::bvector<>& bv)
{
bm::bvector<>::statistics st;
bv.calc_stat(&st);
cout << "Bits count:" << bv.count() << endl;
cout << "Bit blocks:" << st.bit_blocks << endl;
cout << "GAP blocks:" << st.gap_blocks << endl;
cout << "Memory used:"<< st.memory_used << endl;
cout << "Max.serialize mem.:" <<
st.max_serialize_mem << endl << endl;;
}
unsigned char* serialize_bvector(
bm::serializer<bm::bvector<> >& bvs,
bm::bvector<>& bv)
{
// It is reccomended to optimize
// vector before serialization.
bv.optimize();
bm::bvector<>::statistics st;
bv.calc_stat(&st);
cout << "Bits count:" << bv.count() << endl;
cout << "Bit blocks:" << st.bit_blocks << endl;
cout << "GAP blocks:" << st.gap_blocks << endl;
cout << "Memory used:"<< st.memory_used << endl;
cout << "Max.serialize mem.:" <<
st.max_serialize_mem << endl;
// Allocate serialization buffer.
unsigned char* buf =
new unsigned char[st.max_serialize_mem];
// Serialization to memory.
unsigned len = bvs.serialize(bv, buf, 0);
cout << "Serialized size:" << len << endl << endl;
return buf;
}
int main(void)
{
bm::bvector<> bv1;
bm::bvector<> bv2;
// set DGAP compression mode ON
bv2.set_new_blocks_strat(bm::BM_GAP);
fill_bvector(&bv1);
fill_bvector(&bv2);
// Prepare a serializer class
// for best performance it is best
// to create serilizer once and reuse it
// (saves a lot of memory allocations)
//
bm::serializer<bm::bvector<> > bvs;
// next settings provide lowest serilized size
bvs.byte_order_serialization(false);
bvs.gap_length_serialization(false);
bvs.set_compression_level(4);
unsigned char* buf1 = serialize_bvector(bvs, bv1);
unsigned char* buf2 = serialize_bvector(bvs, bv2);
// Serialized bvectors (buf1 and buf2) now ready to be
// saved to a database, file or send over a network.
// ...
// Deserialization.
bm::bvector<> bv3;
// As a result of desrialization bv3
// will contain all bits from
// bv1 and bv3:
// bv3 = bv1 OR bv2
bm::deserialize(bv3, buf1);
bm::deserialize(bv3, buf2);
print_statistics(bv3);
// After a complex operation
// we can try to optimize bv3.
bv3.optimize();
print_statistics(bv3);
delete [] buf1;
delete [] buf2;
return 0;
}Какие планы по развитию библиотеки BitMagic?
Очень хочется реализовать несколько новых методов компрессии векторов с возможностью параллельной обработки данных.
В связи с массовым выходом Intel Core i5-i7-i9 целесообразно выпустить версию библиотеки для SSE 4.2. Компания Intel добавила несколько интересных возможностей, которые можно эффективно использовать. Самым интересным является аппаратная поддержка расчета числа битов (Population Count).
Ведутся эксперименты с nVidia CUDA и другими GPGPU. Графические карты сегодня предоставляют возможность выполнения целочисленных и логических операций - есть возможность использовать их ресурсы для алгоритмов работы с множествами и компрессии.
0