In this article, Anatoliy Kuznetsov answers the questions and tells us about the open BitMagic C++ Library.
While regularly looking through the Internet-resources related to the sphere of 64-bit programming, I often came across mentioning about BitMagic C++ Library and that it had gained a lot of benefits from using 64-bits. I decided to communicate with the library's author and offer him to tell us in an interview about his research and developments.
The questions are asked by: Andrey Karpov - "Program Verification Systems" company's worker developing PVS-Studio tool for verification of modern C++ applications.
The answers are given by: Anatoliy Kuznetsov - chief software engineer in NCBI; developer of the open library BitMagic C++ Library.
Hello Andrey,
I am chief software engineer, at present I am working in the team of searching and visualizing bio-molecular information in NCBI (National Center for Biotechnology Information). Besides my major activity, I am the chief developer and architect of the open library BitMagic C++ Library.
By education I am planning engineer, a graduate of the Lobachevskiy University in Nizhniy Novgorod.
BitMagic was developed as a universal template library for working with compressed bit vectors. The library solves several tasks:
The library turned out to be rather universal and perhaps it wouldn't be easy to list all the possible ways to use it. At present, the library is of most interest in the following spheres:
For a long time, I and my colleagues had been working with the tasks related to large databases, analysis and visualization systems. The very first working version demonstrating bit vectors' abilities was shown by Maxim Shemanaryov (he is the developer of a wonderful 2D vector graphics library Antigrain Geometry). Then, some ideas of equivalent representation of sets were described by Koen Van Damm, an engineer from Europe who was working on the parsers of programming languages for verifying complex systems. There were other sources as well. I decided to systematize it all somehow and present in the form of a library suitable for multiple use in various projects.
The library is free for commercial and non-commercial use and is available in the form of source texts. The only restriction is the demand of mentioning the library and its authors when using it in the finite product.
You can see the materials here: http://bmagic.sourceforge.net.
Really, the library uses a series of optimization methods accelerating work in 64-bit systems or systems with SIMD commands (128-bit SSE2).
Here are the factors accelerating execution of algorithms:
At present, the quickest operation is available when using 128-bit SSE2 optimization in a 64-bit program. This mode combines the double number of x86 registers and the wide machine word to perform logical operations.
64-bit systems and programs are going through a real Renaissance. Migration of programs on 64-bits will be faster than moving from 16 to 32. Appearance of 64-bit versions of Windows on mass market and available toolkits (like the one your company is developing) will stimulate this process. In the environment of constant growth of systems' complexity and the size of code used in them, such a toolkit as PVS-Studio is a good help as it reduces efforts and forces release of products.
The current 3.6.0 version of the library uses several compression methods.
One of the examples simply creates 2 vectors, initializes them and performs the logical operation AND. Further, the class enumerator is used for iteration and printing of the values saved in the vector.
#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;
}The next example demonstrates serialization of vectors and use of compression mode.
#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;
}We wish to implement some new vector compression methods with the ability of parallel data procession.
Due to mass release of Intel Core i5-i7-i9, it is rational to release the library's version for SSE 4.2. Intel company added some interesting features which can be efficiently used. The most interesting is the hardware support of bit number calculation (Population Count).
We are experimenting with nVidia CUDA and other GPGPU. Graphics cards allow you to perform integer and logical operations today - and their resources can be used for algorithms of working with sets and compression.