В этой статье Анатолий Кузнецов отвечает на вопросы и рассказывает об открытой библиотеке BitMagic C++ Library.
Регулярно просматривая ресурсы интернета, связанные с тематикой 64-битного программирования, я неоднократно встречал упоминание библиотеки BitMagic и то, что она получила существенные преимущества от использования 64-битности. Я решил связаться с автором библиотеки и предложить ему рассказать в интервью о своих исследованиях и разработках.
Вопросы задает: Андрей Карпов - сотрудник компании "Системы программной верификации", занимающийся созданием инструмента PVS-Studio для проверки современных приложений на языке Си++.
На вопросы отвечает: Анатолий Кузнецов - старший инженер по разработке программного обеспечения в NCBI. Является разработчиком открытой библиотеки BitMagic C++ Library.
Здравствуйте Андрей!
Я старший инженер по разработке программного обеспечения, в данный момент я работаю в группе поиска и визуализации биомолекулярной информации NCBI (National Center for Biotechnology Information). Помимо своей основной деятельности я являюсь основным разработчиком и архитектором открытой библиотеки BitMagic C++ Library.
По образованию я инженер-экономист, выпускник Нижегородского Университета им. Лобачевского.
Библиотека BitMagic разрабатывалась как универсальная библиотека шаблонов для работы с компрессированными битовыми векторами. Библиотека решает несколько задач:
Библиотека получилась довольно универсальная, и перечислить все возможные применения, наверное, будет не просто. В данный момент библиотека наиболее интересна в следующих областях:
Я и мои коллеги продолжительное время занимались задачами, связанными с большими базами данных, системами анализа и визуализации. Самую первую рабочую версию, демонстрирующую возможности битовых векторов, показал Максим Шеманарев (он является разработчиком великолепной библиотеки 2D векторной графики Antigrain Geometry). Потом некоторые идеи по эквивалентному представлению множеств были описаны инженером из Европы Koen Van Damm, работавшим над парсерами языков программирования для верификации сложных систем. Были и другие источники. Все это я решил как-то систематизировать и представить в виде библиотеки пригодной для многократного повторного использования в разных проектах.
Библиотека свободна для коммерческого и некоммерческого использования, доступна в виде исходных текстов. Единственным ограничением является требование упоминания библиотеки и авторов при использовании в конечном продукте.
С материалами можно ознакомиться тут: http://bmagic.sourceforge.net.
Действительно, библиотека использует серию оптимизационных приемов ускоряющих работу в 64-битных системах или системах с SIMD командами (128-bit SSE2).
Факторы, ускоряющие выполнение алгоритмов:
В данный момент наиболее быстрым вариантом является использование 128-bit SSE2 оптимизации в 64-битной программе. Такой режим совмещает удвоенное количество x86 регистров и широкое машинное слово для выполнения логических операций.
64-битные системы и программы переживают сейчас настоящий ренессанс. Перевод программ под 64 бита будет происходить быстрее, чем в переход с 16 на 32. Этому будет способствовать выход на массовый рынок 64-битных версий Windows и доступный инструментарий (такой как разрабатываете ваша компания). В условиях постоянного роста сложности систем и объема используемого в них кода такой инструментарий, как PVS-Studio, является хорошим подспорьем, так как сокращает трудозатраты и увеличивает скорость вывода продуктов на рынок.
Текущая версия 3.6.0 библиотеки использует несколько методов сжатия.
Один из примеров просто создает 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;
}Очень хочется реализовать несколько новых методов компрессии векторов с возможностью параллельной обработки данных.
В связи с массовым выходом Intel Core i5-i7-i9 целесообразно выпустить версию библиотеки для SSE 4.2. Компания Intel добавила несколько интересных возможностей, которые можно эффективно использовать. Самым интересным является аппаратная поддержка расчета числа битов (Population Count).
Ведутся эксперименты с nVidia CUDA и другими GPGPU. Графические карты сегодня предоставляют возможность выполнения целочисленных и логических операций - есть возможность использовать их ресурсы для алгоритмов работы с множествами и компрессии.