Для получения триального ключа
заполните форму ниже
Team License (базовая версия)
Enterprise License (расширенная версия)
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
GBP
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

>
>
>
Интервью с Анатолием Кузнецовым, авторо…

Интервью с Анатолием Кузнецовым, автором библиотеки BitMagic C++ Library

08 Ноя 2009

В этой статье Анатолий Кузнецов отвечает на вопросы и рассказывает об открытой библиотеке 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: http://www.antigrain.com). Потом некоторые идеи по эквивалентному представлению множеств были описаны инженером из Европы 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. Графические карты сегодня предоставляют возможность выполнения целочисленных и логических операций - есть возможность использовать их ресурсы для алгоритмов работы с множествами и компрессии.

Популярные статьи по теме
Зло живёт в функциях сравнения

Дата: 19 Май 2017

Автор: Андрей Карпов

Возможно, читатели помнят мою статью под названием "Эффект последней строки". В ней идёт речь о замеченной мной закономерности: ошибка чаще всего допускается в последней строке однотипных блоков текс…
Как PVS-Studio оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

Автор: Андрей Карпов

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Любите статический анализ кода!

Дата: 16 Окт 2017

Автор: Андрей Карпов

Я в шоке от возможностей статического анализа кода, хотя сам участвую в разработке инструмента PVS-Studio. На днях я был искренне удивлён тому, что анализатор оказался умнее и внимательнее меня.
Бесплатный PVS-Studio для тех, кто развивает открытые проекты

Дата: 22 Дек 2018

Автор: Андрей Карпов

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…
PVS-Studio ROI

Дата: 30 Янв 2019

Автор: Андрей Карпов

Время от времени нам задают вопрос, какую пользу в денежном эквиваленте получит компания от использования анализатора PVS-Studio. Мы решили оформить ответ в виде статьи и привести таблицы, которые по…
Характеристики анализатора PVS-Studio на примере EFL Core Libraries, 10-15% ложных срабатываний

Дата: 31 Июл 2017

Автор: Андрей Карпов

После большой статьи про проверку операционной системы Tizen мне было задано много вопросов о проценте ложных срабатываний и о плотности ошибок (сколько ошибок PVS-Studio выявляет на 1000 строк кода)…
Эффект последней строки

Дата: 31 Май 2014

Автор: Андрей Карпов

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …
Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей

Дата: 21 Ноя 2018

Автор: Андрей Карпов

Краткое описание технологий, используемых в инструменте PVS-Studio, которые позволяют эффективно обнаруживать большое количество паттернов ошибок и потенциальных уязвимостей. Статья описывает реализа…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

Автор: Андрей Карпов

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
PVS-Studio для Java

Дата: 17 Янв 2019

Автор: Андрей Карпов

В седьмой версии статического анализатора PVS-Studio мы добавили поддержку языка Java. Пришло время немного рассказать, как мы начинали делать поддержку языка Java, что у нас получилось и какие дальн…

Комментарии (0)

Следующие комментарии

На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Этот сайт использует куки и другие технологии, чтобы предоставить вам более персонализированный опыт. Продолжая просмотр страниц нашего веб-сайта, вы принимаете условия использования этих файлов. Если вы не хотите, чтобы ваши данные обрабатывались, пожалуйста, покиньте данный сайт. Подробнее →
Принять