Algorithms and tools for integer set algebra operations used for information retrieval, indexing of databases, scientific algorithms, ranking, clustering and signal processing.
BitMagic library uses compressed bit-vectors as a main vehicle for implementing set algebraic operations, because of high efficiency and bit-level parallelism of this representation. To compress memory it uses delta / prefix sum coding. One of our goals is constant improvement of performance via SIMD vectorization (SSE2, SSE4.2, AVX2), CPU cache-friendly algorithms and data-parallel thread-safe structures.
- compressed bit-vector container with mechanisms to iterate integer set it represents
- set algebraic operations: AND, OR, XOR, MINUS on bit-vectors and integer sets
- aggregator: fast logical AND, OR, AND-MINUS operations on groups of bit-vectors
- serialization/hybernation of bit-vector containers into compressed BLOBs for persistence (or in-RAM compression)
- set algebraic operations on compressed BLOBs (on the fly deserialization with set-algebraic function)
- statistical algorithms to efficiently construct similarity and distance metrics, measure similarity between bit-vectors, integer sets and compressed BLOBs
- operations with rank: population count distances on bit-vector
- sparse vector(s) for native int types using bit transposition and separate compression of bit-plains, with support of NULL values (unassigned) for construction of in-memory columnar structures. Bit-transposed sparse vectors can be used for on-the fly compression of astronomical, molecular biology or other data, efficient store of associations for graphs, etc.
- algorithms on sparse vectors: dynamic range clipping, search, group theory image (re-mapping). Collection of algorithms is increasing, please check our samples and the API lists.
-
compressed binary relational and adjacency matrixes and operations on matrixes for Entity-Relationship acceleration, graph operations, social analyticsm materialized RDBMS joins, etc
-
portable C-library layer working as a bridge to high level languages like Python, Java, Scala, .Net
License: Apache 2.0
-
GitHub master accepts patch requests Our branching policy is that master cannot be considered fully stable between the releases. (for production stability please use release versions)
-
We need help with real-life cases and benchmarks
-
We need help with mappings to Python and other languages (BitMagic has C bindings)
BitMagic C++ is a header-only software package and you probably can just take the sources and put it into your project directly. All C++ library sources/headers are in src directory.
However if you want to use our makefiles you need to follow the next simple instructions:
- Traditional (in-place build)
Apply a few environment variables by runing bmenv.sh in the project root directory:
$ ./bmenv.sh
use GNU make (gmake) to build installation.
$gmake rebuild
or (DEBUG version)
$gmake DEBUG=YES rebuild
The default compiler on Unix and CygWin is g++. If you want to change the default you can do that in makefile.in (should be pretty easy to do)
- CMake based build Project now comes with a set of makefiles for cmake, you can just build it or generate project files for any cmake-supported environment.
If you use cygwin installation please follow general Unix recommendations. MSVC - solution and projects are available via CMAKE generation
XCODE - project files are available via CMAKE generation
BitMagic library for C and JNI mappings.
BitMagic library is available for C language (this is work in progress). The main objective of C build is to bridge BitMagic into other programming languages. C build is in the subdirectory "lang-maps".
C build creates versions of BitMagic build for SSE and AVX and adds CPU identification, so the upper level system can support dynamic CPU identification and code dispatch.
C build uses C++ compiler, but does not use RTTI, exceptions (simulated with long jump) and C++ memory management, so it is C++ language neutral, without runtime dependencies. Algorithms and behavior are shared between C and C++.
Current state of development:
- bit-vector functionality is available via C interface
Yes, we need it! If you are enthusiastic about Python and think you can help please contact: anatoliy.kuznetsov @ yahoo dot com
API documentation and examples: http://www.bitmagic.io/apis.html
All BM fine tuning parameters are controlled by the preprocessor defines (and compiler keys).
BM library supports CXX-11. Move semantics, noexept, initalizer lists.
BM library includes some code optimized for 64-bit systems. This optimization gets applied automatically.
BM library contains code using intrinsics for SIMD extensions SSE2, SSE4.2, AVX2.
To turn on SSE2 optimization #define BMSSE2OPT in your build environment. To use SSE4.2 #define BMSSE42OPT SSE42 optimization automatically assumes SSE2 as a subset of SSE4.2. (you don’t have to use both BMSSE2OPT and BMSSE42OPT at the same time).
To turn on AVX2 - #define BMAVX2OPT This will automatically enable AVX2 256-bit SIMD, popcount (SSE4.2) and other compatible hardware instructions.
BM library does NOT support multiple code paths and runtime CPU identification. You have to build specifically for your target system or use default portable build.
To correctly build for the target SIMD instruction set - please set correct code generation flags for the build environment.
BitMagic examples and tests can be build with GCC using cmd-line settings:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
or
make BMOPTFLAGS=-DBMSSE42OPT rebuild
It automatically applies the right set of compiler (GCC) flags for the target build.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
OR
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
BM library supports "restrict" keyword, some compilers (for example Intel C++) generate better code (out of order load-stores) when restrict keyword is helping. This option is turned OFF by default since most of the C++ compilers does not support it. To turn it ON please #define BM_HASRESTRICT in your project. Some compilers use "__restrict" keyword for this purpose. To correct it define BMRESTRICT macro to correct keyword.
If you want to use BM library in no STL-free project you need to define BM_NO_STL variable.
This rule only applies to the core bm::bvector<> methods. Auxiliary algorithms may still use STL.
Follow us on twitter: https://twitter.com/bitmagicio
Thank you for using BitMagic library!
e-mail: [email protected]
WEB site: http://bitmagic.io