BitMagic Library

Overview

BitMagic C++ Library

BitMagic was created as a Algebra of Sets toolkit for Information Retrieval but currently evolved into a more general Data Science components library for memory compact structures and algorithms on succinct data vectors. BitMagic implements compressed bit-vectors and containers (vectors) based on ideas of bit-slicing transform and Rank-Select compression. All containers are serializable (with compression using state of art Binary Interpolative Coding) for efficient storage and network transfer.

BitMagic offers sets of method to architect your applications to use HPC techniques to save memory (thus be able to fit more data in one compute unit) and improve storage and traffic patterns when storing data vectors and models in files or object stores (SQL or noSQL).

BitMagic facilitates two big classes of scenarios:

  • limited RAM applications (WebAssembly, IoT, Edge computing, desktop/workstation apps)
  • Big Data HPC (petabyte problems) where amount of data is astronomical and computation and storage has to be distributed (need for efficient transfer)

Applications and Use Cases

BitMagic was used as a building blocks for:

  • Algebra of Sets for IR, database inverted index construction
  • Simulation of logical schemes and topologies (like FPGAs)
  • Multidimentional binary distances on compressed bit-vectors building blocks for binary clusterizations, Self-organizing maps
  • Construction of memory compressed bioinformatics models
    • sequence alignments
    • collections of variations and SNPs
    • compression of sequence reads
    • k-mer classification systems
  • Visualization of data-sets in the memory constrained edge configurations (edge comuting, IoT, WebAssembly)
  • Graph and Tree analysis, construction of compressive matrixes of association
  • Web and application logs analytics and systems reliability automation
  • Low latency network scheduling (orchestration) systems

Please visit our use-case notes: http://bitmagic.io/use-case.html

Optimizations and SIMD

BitMagic library is a high performance library, implementing custom optimizations for variety of platforms and build targets:

  • x86 (platform specific available bit-scan instructions)
  • x86 SIMD: SSE2, SSE4.2(POPCNT, LZCNT), AVX2 (BMI1/BMI2), AVX-512(work in progress)
  • Arm (use of specific available bit-scan instructions)
  • WebAssembly (use of WebAsm built-ins and platform specific tricks)
  • WebAssembly SIMD

BitMagic uses a data-parallel vectorized design with a goal not just provide a best single threaded performance but to facilitate highly parallel compute on many-core systems.

Compression algorithms

BitMagic uses a suite of compression algorithms, filters and transformations to reduce memory footprint, storage costs and network data transfer. http://bitmagic.io/design.html

  • Hierachical compression of bit-vectors
  • D-GAP (RLE) of bit-blocks
  • Binary Inetrpolative Coding (BIC)
  • Elias-Gamma Coding
  • Bitwise-Tranposition for vectors (also known as Bit Planes coding or bit-slicing)
  • XOR compression filters
  • Frequency based dictionary remapping (similar to Huffman codes)

Please visit our tech.notes: http://bitmagic.io/articles.html

Main Features (bm::bvector<>)

  • compressed bit-vector container
  • iterator (bm::bvector<>::enumerator to decode the bitset to integers
  • set algebraic operations: AND, OR, XOR, MINUS, NOT on bit-vectors and integer sets
  • fast bit-vector ierator (enumerator) for bit-vector traversal, algorithms for functor-based traversals (similar to std::for_each)
  • fast import (compression) of integer lists (C++ style bulk_insert_iterator or using C array)
  • aggregator: fast vectorized 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. Rank-Select operations are often used in succinct data structures, BitMagic implements a compact RS Index accelerated with SIMD and BMI (PDEP)

Ranges and Intervals (bmintervals.h)

BitMagic supports re-interpretation of bit-vectors as collections of non-overlapping ranges of 1s flanked with 0s (for example: 011110110). Regular set functions provide set intersect / unions intreval operations implement interval iterator and searches for interval boundaries. Ranges and intervals has great utility in bioinformatics, because genomics data are often annotated as coordinate ranges. BitMagic offers building blocks for effciient oprations on intervals encoded as bit-vectors (find interval start/end, check if range is an inetrval, iterate intervals

Three-Valued Logic (bm3vl.h)

BitMagic implements logical operations for 3-valued logic of True/False/Unknown (also trinary logic, trivalent, ternary) in compact two bit-vector representation, supporting Invert, AND, OR operations following Kleene's definitions. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

Serialization with compression

BitMagic uses contept of two-stage serialization-deserialization. The focus is on fast deserialization. BitMagic implements API for fast vector range deserialization and gather deserialization of compressed BLOBs. The ultimate feature of BitMagic is ability to work with compressed data.

Stage One: succinct memory

This is the main in-RAM operational state, where vectors are kept in memory compact form. Succinct is NOT a compression. It is possible to access random elements in containers, decode blocks, iterate vectors, make updates, run search algorithms. Stage One offers transparent use, it vectors look much like STL. Succinct is memory compact but not fully compressed.

Stage Two: compression

BitMagic can serialize all containers and vectors with additional compression based on block of heuristics and codecs. The workhorse coding techniques are: Binary Interpolative Coding (BIC) and Elias Gamma.

BitMagic containers are called "sparse" vectors but in fact its compression schemes works well for both sparse and dense data.

BitMagic is tested on Gov2 benchmark set of inverted lists and number of proprietory data sets. http://bitmagic.io/bm5-cmpr.html

Decompression

Deserialization always go back to Stage One, so data are not completely decoded but instead
succinct in RAM. Our goal here is to both reduce application memory footprint and improve deserialization latency. Decompression algorithms support deserialization of arbitrary ranges or even gather deserializatin of elements.

Succinct vectors

BitMagic supports succinct (memory compact) vectors based on bit-transposition transform
also known as bit-plane compression (BPC) or bit-slicing and Rank-Select compression. Succint vectors are labeled "sparse" but they also work for dense vectors.

Bit transposition solves two purposes: free unused bit plains and isolate regularity and entropy into separate (sparse) bit-vectors. Compression on bit-planes offers both superior memory performance and fast search. One of the design golas was to be able to perform searches on succinct data using vectorized logical operations.

Succinct bit-transposed implementation works well for both integer vectors and string vectors and it rivals other succinct schemes like prefix trees. Succinct vectors can be both sorted and unsorted. The idea here is similar to Apache Arrow-Parquet, but it takes it farther with bit-plane compression and extensive use of accelerated Rank-Select compression.

  • bit-transposed representation offers best memory footprint for numeric vectors when data uses numbers with limited or variable bit rate. If data needs just 27 bits succinct vector will use just that and not the nearest natural 32-bit type. It is adaptive and completely automatic.
  • If string vector needs just a few bits to represent a char in particular position (DNA strings, chemical compounds as smiles, etc. ) BitMagic has an option to do transparent remapping, so DNA string vector would use just 2-3 bits (for ATGCN alphabet), remapping analyses frequencies and similar to Huffman.
  • Rank-Select approach allows to collapse all NULL values and save RAM
  • For deeper compression BitMagic also implements XOR filter which finds possible correlations between bit-planes to reduce enthropy http://bitmagic.io/bm-xor.html

Main features

  • 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.
  • search algorithms for sorted and unsorted succinct vectors (vectors of ints or strings)
  • algorithms on sparse vectors: dynamic range clipping, search, group theory image (re-mapping).
  • all containers are serializable with compression (binary interpolative coding, elias gamma coding)

Serialization and versioning

BitMagic supports serialization evolution - if serialization format changes, old saved data remains readable by the new code. Old code will NOT be able to read new BLOBs. BitMagic changes major version number when serialization format changes.

Memory profiling/monitoring

BitMagic implements memory profiling calls for all vectors. Any vector can be sampled for memory footprint so the top level system can adapt memory managemnet based on the runtime memory profiling. Typical use case is memory cache of objects with compression to RAM and then to eviction to disk based on resource consumption and costs (dynamic balance of demand and supply).

64-bit vs 32-bit

Yes! BitMagic supports 64-bit, can be used with 32-bit address space (less overhead) or full 64-bit address space. 32-bit address space is the default mode 2^31-1 elements should be a good fit for short to medium range IR and data science systems. 64-bit address mode is available using #define BM64ADDR or #include "bm64.h". Current 64-bit implementation allows 2^48-1 vector elements for large scale systems.

WebAssembly and WebAssembly SIMD

BitMagic compiles and work with WebAssmbly (emscripten). Latest versions includes multiple tweaks, specific for the platform. Performance numbers are close to native code without SIMD (sometimes afster). Sample compile line would look like:

emcc -std=c++11 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...

WebAssembly SIMD is supported but it is not ON by default. Use: #define BMWASMSIMDOPT to enable it. Emscripten cmd example:

emcc -std=c++11 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti

Current implementation uses SSE4.2 trans-compilation (via intrinsics), so -msse4.2 is necessary.

ARM

BitMagic fully supports ARM CPU. All releases are stress tested with Raspberry Pi 4. BitMagic implements some algorithmic tweaks and improvements specific for ARM (like use of LZCNT instruction). BitMagic succinct containers can be very useful on embedded systems for edge computing with limited amount of available memory.

ARM NEON SIMD support is a work in progress.

C-library interface:

  • BitMagic library provides C-library wrapper, which builds as a "true C" library. For redistribution it does NOT require C++ Runtime, because it compiles without use of STL, C++ memory allocation (operator new) or exceptions. Our goal here is to eventually provide a bridge to other languiages of data science (Python) and languages of enterprise scale development (Java, Scala) via JNI.

Features In Progress:

  • compressed binary relational and adjacency matrixes and operations on matrixes for Entity-Relationship acceleration, graph operations, social analyticsm materialized RDBMS joins, etc

  • succinct data structures and containers based on bit-transposed data representation and rank-select compression

  • memory efficient dictionaries of strings as an alternative to suffix trees

How to start with BitMagic?


BitMagic C++ is a header only library (easy to build and use in your project) and it comes with a set of examples. It is NOT advised to use tests as a code example to study library usage. Tests do not illustate the best usage patterns and models and often intentionally inefficient.

API documentation and examples: http://www.bitmagic.io/apis.html

Tutorial for Algebra of Sets: http://bitmagic.io/set-algebra.html

Use Cases and Application notes: http://bitmagic.io/use-case.html

Technical notes on performance optmization: http://bitmagic.io/articles.html

Doxygen: http://bitmagic.io/doxygen/html/modules.html

License:

Apache 2.0.

Important! We ask you to explicitly mention BitMagic project in any derived work or our published materials. Proper reference on your product/project page is a REQUIREMENT for using BitMagic Library.

Quality Assurance:

BitMagic library pays serious attention to code quality and test coverage.
As a building blocks library BitMagic needs to be stable and conformant to be useful.

We do not rely on unit tests alone, our tests often use "chaos testing" (aka fuzzing) where stress tests are based on randomized, generated sets and randomized operations. We regularly build and run test suits for Release and Debug mode for various combinations of SIMD optimizations.

All variants of test builds take days to run, so the working master branch is NOT guaranteed to be perfect all the time. For production please use stable github release branches or distributions from SourceForge: https://sourceforge.net/projects/bmagic/files/

If you want to contribute or support BitMagic library:


  1. 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)

  2. Need help with mappings to Python and other languages (BitMagic has C bindings)

How to build BitMagic C++ library:


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:

Unix:

  1. Traditional (in-place build)

Apply a few environment variables by runing bmenv.sh in the project root directory:

$ source ./bmenv.sh

(please use "." "./bmenv.sh" to apply root environment variable)

use GNU make (gmake) to build installation.

$make 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)

  1. 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.
Windows:

If you use cygwin installation please follow general Unix recommendations. MSVC - solution and projects are available via CMAKE.

MacOS

XCODE - project files are available via CMAKE.


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

Python support

Python support is pending and we need help here. If you are enthusiastic about Python and think you can help please contact: anatoliy.kuznetsov @ yahoo dot com

Modern C++ (C++17)

BitMagic library requires CXX-11. It uses move semantics, noexept, initalizer lists, threads. Next public version will use CXX-17 (constexpr ifs, etc).

###Fine tuning and optimizations:

All BM fine tuning parameters are controlled by the preprocessor defines (and compiler keys).

#define Description Width
BMSSE2OPT Turn ON SSE2 code optimizations 128-bit
BMSSE42OPT Turn ON SSE4.2 code optimizations plus POPCNT, BSF, etc 128-bit
BMAVX2OPT Turn on AVX2, POPCNT, LZCNT, BMI1, BMI2 optimizations 256-bit
BMAVX512OPT Turn on AVX-512, (experimental) 512-bit
BMWASMSIMDOPT Turn on WebAssembly SIMD optimizations (128-bit) 128-bit

####Limitations:

SIMD optimization defines are mutually exclusive, you can NOT have BMSSE42OPT and BMAVX2OPT at the same time. Pick just one.

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.

####Examples:

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 a "no-STL project" (like embedded systems) define BM_NO_STL.

This rule only applies to the core bm::bvector<> methods. Auxiliary algorithms, examples, etc would 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

GitHub: https://github.com/tlk00/BitMagic

Issues
  • Rust bindings

    Rust bindings

    Hi, thanks for the great library!

    I started two crates for wrapping the C FFI for using in Rust, one is the unsafe low-level bindings (bitmagic-sys) and another a safe/high-level/closer to Rust usage, based on the API of fixedbitset (bitmagic), but I intend to expose more methods over time.

    Overall it is already working, after I commented out a line in cmake. The big problem I'm having is that if I run tests with more than 1 thread, the C++ exception emulation with longjmp/setjmp creates memory corruption. I'm looking into that to see what is going on...

    I didn't register the crates in crates.io because I wanted to check if you first to see if that's OK, and I would also like to try to use the crate a bit more before registering anyway.

    opened by luizirber 5
  • Possible int overflow in encoding.h when compiling on a 32-bit compiler

    Possible int overflow in encoding.h when compiling on a 32-bit compiler

    When compiling w/-Wconversion:

    Error: Implicit conversion loses integer precision: 'unsigned long long' to 'bm::word_t' (aka 'unsigned int')

    As the type of bm::word_t is unsigned int (ie: 32-bits on a 32-bit platform), this function could silently truncate the result of the data. I don't actually use this code so I don't have a test-case available to prove it, but it looks like a reasonable warning.

    {
    #if (BM_UNALIGNED_ACCESS_OK == 1)
    	bm::id64_t a = *((bm::id64_t*)buf_);
    #else
    	bm::word_t a = buf_[0]+
                       ((bm::id64_t)buf_[1] << 8)  +
                       ((bm::id64_t)buf_[2] << 16) +
                       ((bm::id64_t)buf_[3] << 24) +
                       ((bm::id64_t)buf_[4] << 32) +
                       ((bm::id64_t)buf_[5] << 40) +
                       ((bm::id64_t)buf_[6] << 48) +
                       ((bm::id64_t)buf_[7] << 56);
    #endif
        buf_+=sizeof(a);
        return a;
    }
    
    opened by mmastrac 4
  • Xcode false warning on use of uninitialized data in bm.h: bvector<Alloc>::combine_operation_with_block

    Xcode false warning on use of uninitialized data in bm.h: bvector::combine_operation_with_block

    Xcode is warning of this though it's basically impossible to trigger. In this function:

    template<class Alloc> 
    void 
    bvector<Alloc>::combine_operation_with_block(unsigned          nb,
                                                 bool              gap,
                                                 bm::word_t*       blk,
                                                 const bm::word_t* arg_blk,
                                                 bool              arg_gap,
                                                 bm::operation     opcode)
    

    ... the tmp_buf local at the top is not explicitly zero-initialized and Xcode doesn't realize that the goto assign_gap_result will always trigger the if (res_len > threshold) block and return before set_gap_level is called.

    Logic error
    ...vendor/bm/bmfunc.h:2432:43: The left operand of '&' is a garbage value
    …: Calling 'bvector::set_range'
    ...vendor/bm/bm.h:1650:5: Calling 'bvector::set_range_no_check'
    ...vendor/bm/bm.h:2958:1: Entered call from 'bvector::set_range'
    ...vendor/bm/bm.h:2980:10: Assuming 'nbit_left' is not equal to 0
    ...vendor/bm/bm.h:3006:38: Assuming the condition is false
    ...vendor/bm/bm.h:3010:16: Loop body executed 0 times
    ...vendor/bm/bm.h:3069:5: Calling 'bvector::combine_operation_with_block'
    ...vendor/bm/bm.h:2649:1: Entered call from 'bvector::set_range_no_check'
    ...vendor/bm/bm.h:2715:21: Assuming 'res_len' is <= 'threshold'
    ...vendor/bm/bm.h:2742:17: Calling 'set_gap_level'
    ...vendor/bm/bmfunc.h:2429:1: Entered call from 'bvector::combine_operation_with_block'
    ...vendor/bm/bmfunc.h:2432:43: The left operand of '&' is a garbage value
    

    A possible fix for this would be hoisting the code from the if (res_len > threshold) block into its own function and avoiding the goto.

    opened by mmastrac 4
  • Bit-vector statistics: GAP (compressed blocks)=0, BIT (uncompressed blocks)=0

    Bit-vector statistics: GAP (compressed blocks)=0, BIT (uncompressed blocks)=0

    I have a weird behavior of a bm::bvector<> that appears from a given size. The bitvector if full of 1 from 0 to 16.7 million. I expect that a call to select on bm::bvector<>::rs_index_type to be the identity (x->x) But this is not the case from a given size of the bitvector. With 15 million, everything works correctly, but not with 16.7 million. Interestingly when I plot the calc_stat function I have Bit-vector statistics: GAP (compressed blocks)=1, BIT (uncompressed blocks)=0 for the 15 million dataset and Bit-vector statistics: GAP (compressed blocks)=0, BIT (uncompressed blocks)=0 For the 16.7 million

    Is this expected? I tried to use the latest release and the actual codebase for the same result.

    opened by Malfoy 3
  • base_sparse_vector::plain: Correct const variant's return type.

    base_sparse_vector::plain: Correct const variant's return type.

    Return bvector_type_const_ptr, not const bvector_type_ptr, in which the const had no effect due to applying at the wrong level.

    Preemptively address a warning (with -Wignored-qualifiers) that's otherwise likely to break gbench builds using -Werror.

    BTW, I suspect you meant "plane" throughout, but that may not be worth correcting at this point.

    opened by ucko 3
  • bmfunc.h (word_bitcount64): Conditionalize _mm_popcnt_u64 on BM64OPT.

    bmfunc.h (word_bitcount64): Conditionalize _mm_popcnt_u64 on BM64OPT.

    On 32-bit x86 builds with SSE 4.2 enabled, work around the unavailability of _mm_popcnt_u64 by obtaining and adding _mm_popcnt_u32 values for the argument's upper and lower 32 bits.

    opened by ucko 3
  • Packing 2 bits values into a bigger Datatype(INT64)

    Packing 2 bits values into a bigger Datatype(INT64)

    Hi,

    Thank you for all your work and all the resources you had provided.

    Is there any reference to efficiently pack the 2 bits into a larger data type(basically int64)?

    A = 0000.........10(64 bit), B = 0000........11(64 bit), C = 0000........01, and so on, these are int64 values containing 2-bit values.

    So, I want to pack them in an int64 datatype(32 2-bit values) Z = 101101...........(int64 value, containing packed values of A, B, C, D, .............. )

    I want to perform this efficiently. So It would be helpful if you can help me with some references.

    Thanks in advance!

    opened by Darshvino 2
  • Fixes #47

    Fixes #47

    Removed setting stack size in cmake as this was causing build failures for tests on linux and added linking for pthreads for compiling objects and libraries as some tests require these and they were not linked previously.

    opened by anadon 2
  • Building using cmake fails when linking due to unrecognized option 'ck_size'

    Building using cmake fails when linking due to unrecognized option 'ck_size'

    Hello,

    I'm trying to package Bit Magic for guix and use it as a dependency for one of my other projects. The in-place build approach seems to work, but the cmake one appears broken with the following output. I would like to use cmake as it is easier to use (from what I know) than using the more custom primary approach.

    BitMagic$ mkdir bld
    BitMagic$ cd bld/
    BitMagic/bld$ cmake ..
    -- The C compiler identification is GNU 9.2.1
    -- The CXX compiler identification is GNU 9.2.1
    -- Check for working C compiler: /usr/bin/cc
    -- Check for working C compiler: /usr/bin/cc -- works
    -- Detecting C compiler ABI info
    -- Detecting C compiler ABI info - done
    -- Detecting C compile features
    -- Detecting C compile features - done
    -- Check for working CXX compiler: /usr/bin/c++
    -- Check for working CXX compiler: /usr/bin/c++ -- works
    -- Detecting CXX compiler ABI info
    -- Detecting CXX compiler ABI info - done
    -- Detecting CXX compile features
    -- Detecting CXX compile features - done
    -- Configuring done
    -- Generating done
    -- Build files have been written to: /home/anadon/Documents/code/guix-packages/BitMagic/bld
    [email protected]:~/Documents/code/guix-packages/BitMagic/bld$ ls
    CMakeCache.txt  CMakeFiles  cmake_install.cmake  Makefile
    [email protected]:~/Documents/code/guix-packages/BitMagic/bld$ make
    /gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -S/home/anadon/Documents/code/guix-packages/BitMagic -B/home/anadon/Documents/code/guix-packages/BitMagic/bld --check-build-system CMakeFiles/Makefile.cmake 0
    /gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_progress_start /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles/progress.marks
    make -f CMakeFiles/Makefile2 all
    make[1]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    make -f CMakeFiles/strsvsample03.dir/build.make CMakeFiles/strsvsample03.dir/depend
    make[2]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    cd /home/anadon/Documents/code/guix-packages/BitMagic/bld && /gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_depends "Unix Makefiles" /home/anadon/Documents/code/guix-packages/BitMagic /home/anadon/Documents/code/guix-packages/BitMagic /home/anadon/Documents/code/guix-packages/BitMagic/bld /home/anadon/Documents/code/guix-packages/BitMagic/bld /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles/strsvsample03.dir/DependInfo.cmake --color=
    Scanning dependencies of target strsvsample03
    make[2]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    make -f CMakeFiles/strsvsample03.dir/build.make CMakeFiles/strsvsample03.dir/build
    make[2]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    [  1%] Building CXX object CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o
    /usr/bin/c++   -I/home/anadon/Documents/code/guix-packages/BitMagic/src  -Wall -Wextra -Wno-ignored-qualifiers -march=core2 -fPIC -march=core2   -std=gnu++11 -o CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o -c /home/anadon/Documents/code/guix-packages/BitMagic/samples/strsvsample03/strsvsample03.cpp
    In file included from /home/anadon/Documents/code/guix-packages/BitMagic/src/bmserial.h:54,
                     from /home/anadon/Documents/code/guix-packages/BitMagic/src/bmsparsevec_serial.h:33,
                     from /home/anadon/Documents/code/guix-packages/BitMagic/samples/strsvsample03/strsvsample03.cpp:43:
    /home/anadon/Documents/code/guix-packages/BitMagic/src/bmxor.h: In function ‘bm::id64_t bm::compute_xor_complexity_descr(const word_t*, const word_t*, bm::block_waves_xor_descr&, unsigned int&)’:
    /home/anadon/Documents/code/guix-packages/BitMagic/src/bmxor.h:164:56: warning: comparison is always true due to limited range of data type [-Wtype-limits]
      164 |         if ((xor_change <= 1) && (x_descr.sb_change[i] >= 0))
          |                                   ~~~~~~~~~~~~~~~~~~~~~^~~~
    [  2%] Linking CXX executable ../build/bin/strsvsample03
    /gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_link_script CMakeFiles/strsvsample03.dir/link.txt --verbose=1
    /usr/bin/c++   -Wall -Wextra -Wno-ignored-qualifiers -march=core2 -fPIC -march=core2   -Wl,-stack_size,0x100000000 -rdynamic CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o  -o ../build/bin/strsvsample03 
    ld: unrecognized -a option `ck_size'
    collect2: error: ld returned 1 exit status
    make[2]: *** [CMakeFiles/strsvsample03.dir/build.make:87: ../build/bin/strsvsample03] Error 1
    make[2]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    make[1]: *** [CMakeFiles/Makefile2:130: CMakeFiles/strsvsample03.dir/all] Error 2
    make[1]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
    make: *** [Makefile:87: all] Error 2
    
    opened by anadon 2
  • Error from JNI native library

    Error from JNI native library

    While running BitCountTest on Linux: java: /home/kholodov/git/BitMagic/lang-maps/jni/../../src/bm.h:1242: bool bm::bvector<A>::set_bit(bm::id_t, bool) [with Alloc = libbm::mem_alloc<libbm::block_allocator, libbm::ptr_allocator>; bm::id_t = unsigned int]: Assertion `n < size_' failed.

    opened by michkhol 2
  • JNI integration

    JNI integration

    The separate memory management of JVM and the library leads to the very awkward resource management in the Java code, as each created bitvector needs to be destroyed explicitly. The problem can be mitigated by having a custom implementation of the new and delete methods as outlined in the attached file. sorensen.pdf

    opened by michkhol 2
  • Binary self organizing map

    Binary self organizing map

    Hi,

    First I want to thank you for this awesome library.

    I'm experimenting on binary NLP technics and I was wondering if you could publish a bitmagic version of SOM (self organizing map) using about ~ 10 millions of extremely sparse (< 5 / 100 000) binary vectors of same size ~ 1Mbits. The map could be for instance 128 x 128 locations.

    It could be a huge step froward for me to see a correct use of bitmagic on this particular subject.

    Thanks for your help.

    opened by fsicre 6
  • Missing 'install' in CMake

    Missing 'install' in CMake

    I'm packaging in guix which has specific tooling for projects built with cmake. This requires that CMakeLists.txt have information for handling installation of files. I think I'll be able to submit another pull request adding this.

    opened by anadon 0
  • Remove asserts for JNI compilation

    Remove asserts for JNI compilation

    No coredumps, aborts or crashes are allowed under JVM. May be implemented as a platform-specific macro at the compilation stage. Example: https://github.com/tlk00/BitMagic/blob/01f15914f0cbfe7672497590b72a4a5af6664bd4/src/bm.h#L1923

    opened by michkhol 0
Releases(v7.11.2)
  • v7.11.2(Apr 17, 2022)

    Bug fixes:

    1. Fixed bug in rank-select index assisted compute of rank (affecting compressive sparse vector)
    2. Fixed bug with potential misaligned reads in SIMD mode
    3. Fixed bug in deserialization of empty sparse vector

    New features and improvements:

    1. Improved read-only mode for bm::bvector<> to allocate one contiguos memory block for the arena to better reduce memory fragmentation. This improvement also affects read-only mode memory allocation for bit-vector based succinct vectors.

    2. succinct vector for strings (bm::str_sparse_vector) remap() method improved to use less memory in the process

    3. Added bit-vector immutability methods into C-language mappings

    Release notes: http://bitmagic.io/bm-7.11.2.html

    Source code(tar.gz)
    Source code(zip)
  • v7.10.3(Feb 13, 2022)

    Release Notes: BitMagic 7.10.3

    Bug fixes:

    1. Fixed bug in serialization/deserialization of empty null-able bm::str_sparse_vector<> (could case crashes and assertion faults)
    2. Fixed corner case bug in XOR compression of empty succinct vectors
    3. C language interface (libbm) – fixed incorrect handling of CPU SIMD capabilities (AVX2)

    New features and improvements:

    1. Implemented immutable (read-only) bit-vectors. New version of BitMagic library first introduces an API for making vectors immutable. Immutable mode has two advantages: better memory footprint and faster analytical operations.

    Mutable writable vectors in BitMagic are implemented using block allocation strategy (that is why sparse vectors). To facilitate edits in compressive mode vectors do space reservations to avoid frequent re-allocations which otherwise be a performance killer in multi-threaded scenarios. Such memory reservations is obviously not free and goes against the idea of memory succinct operations. New version adds APIs to freeze vectors to read-only mode, which assembles all blocks together into one memory arena (heap defragmentation, which can reduce memory footprint for your program) and drops any reservations made for editing (reduce RAM consumption). An additional extra benefit is that immutable mode now uses contiguous arena of memory, giving CPU a better chance for cache memory reuse and more efficient hardware prefetch. Performance benchmarking shows that this factor can give 1 to 5 percent performance improvements on data-science operations like binary distance functions (Dice). The performance advantage is not super-significant, but it is a nice bonus for applications which can use and benefit from read-only mode. Special note: current implementation still turns read-write mode back on deserialization of vectors because current serialization format remains without changes for this release.
    https://github.com/tlk00/BitMagic/tree/master/samples/bvsample26

    1. New method for random access read from the Rank-Select succinct vector bm::rsc_sparse_vector<>::gather() – new method can give you 10% and better performance improvement comparing to naïve random access. Actual performance improvement depends on the access pattern and data pattern. https://github.com/tlk00/BitMagic/tree/master/samples/rscsample06

    2. Improved performance of Rank-Select index. The most notisable performance improvement is for Arm and configurations without efficient SIMD acceleration. SSE4.2 and AVX2 builds show minor improvement or parity with the previous version

    3. Improved “noexcept” declarations in the code (improved WASM target performance)

    4. Improved bm::bvector<>insert()/shift_right() to avoid unnecessary deoptimization of compressed blocks

    Release notes: http://bitmagic.io/bm-7.10.3.html

    Source code(tar.gz)
    Source code(zip)
  • v7.9.3(Jan 5, 2022)

    Release Notes: BitMagic 7.9.3

    1. Improved bm::sparse_vector_scanner<>::pipeline::set_search_mask() with ability to specify AND mask. Search mask is very useful optimization tool for cases when search can be limited/prunned by a prior knoweledge or a prior search on a more selective index. SQL example: Field1 = 10 AND Field2 IN ('value1', 'value2') One side of an SQL expression Field1 = 10 as a bit-vector can now be fed into a pipeline index-free search scanner to potentially make search significantly faster. Example: https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample07

    2. bm::str_sparse_vector<> - fixed a few bugs related to processing of succinct vectors with NULL values.

    3. New API bm::str_sparse_vector<>::compare() - optimized comparison for construction of sort method taking two indexes of elements to perform comparison.

    4. Optimizations for SSE2, SSE4.2 code for logical set subtraction (AND NOT).

    5. Minor optimizations of bm::aggregator<> - collection of algorithms for logical expression search.

    6. All succinct vectors: Implemented new API functions for bulk set_null() and clear() of vector elements. New methods take bm::bvector<> as an input to set/clear marked elements. New operations are significantly faster than random access element assignments. https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample04

    7. All succinct vectors: New method try_get() for conditional access to not NULL elements. New method is somewhat faster than separate is_null()/get() calls. https://github.com/tlk00/BitMagic/tree/master/samples/rscsample01

    8. Integer succinct vectors: optimizations of random element access (10% gain in some cases).

    9. New example on how to use algorithms for bit-vector traversal: bm::for_each_bit(), bm::for_each_bit_range(), bm::visit_each_bit(), bm::visit_each_bit_range(). https://github.com/tlk00/BitMagic/tree/master/samples/bvsample25

    10. Minor optimizations for Rank-Select index construction and search.

    Release notes: http://bitmagic.io/bm-7.9.3.html

    Source code(tar.gz)
    Source code(zip)
  • v7.8.0(Nov 27, 2021)

    Release Notes: BitMagic 7.8.0

    1. Implemented complete set of index-free search methods on compressive memory vectors with bm::sparse_vector_scanner<>: GT, GE, LT, LE, RANGE fast search functions. New search logic uses fast bit-vector operations without de-compressing the succinct models to solve search logic problems fast and without external indexes overhead New functionality is important for both search systems and columnar databases.

    2. New example on how to use the new scanner search functions: https://github.com/tlk00/BitMagic/tree/master/samples/svsample10

    3. SSE2 improvements: added more SSE2 kernels and optimizations.

    4. First version of ARM NEON optizations (as SSE2 to NEON translation). Tested on R-Pi, it adds up to 25% performance gain in some logic search benchmarks.

    Release notes: http://bitmagic.io/bm-7.8.0.html

    Source code(tar.gz)
    Source code(zip)
  • v7.7.7(Nov 12, 2021)

    1.Fixed a bug in bm::bvector<>::merge() - destructive OR operation, when arg vectors is empty and uninitialized function did not implement a correct logical OR (serious issue!)

    2.Implemented a new logical idiom bvector<>::bit_or_and() as C := C OR (A AND B) Fused OR+AND is an often used idiom in query systems, implementations of SQL and operation on memory compressed structures. Fused implementation uses multiple optimizations and does not require a temporary vector, avoiding allocations and memory copy. New idiom is 2x times faster in synthetic tests of uncompressed bit-vectors.

    1. bm::aggregator::pipeline now implements a fast mode to run multiple AND-SUB queries with an optional aggregation of results via an OR function.

    Aggregator logical pipeline implements fast idioms used in BitMagic succinct vectors to implement sparse/dense vector search or query requests.

    bm::aggregator::pipeline uses cache memory bandwidth and optimizations to implement series of AND-SUB as: (bv1 AND bv2 AND bv3…) AND NOT (bvS1 OR bvS2 OR … ) with an optional final accumulation of multiple search requests using OR logical function.

    Aggregator pipeline is used internally in BitMagic to implement succinct bit-sliced vector searches (bm::scanner<>) 2-3 times faster. The speed achieved in 7.7.7 release demonstrates performance levels otherwise specific to systems using indexes. Fast index-free searches can significantly reduce both the systems footprint (RAM and disk) and complexity of implementation.

    1. Algebra of Sets tutorial (bvsetalgebra.cpp) example reworked to illustrate use of new fused OR-AND operations and aggregator pipeline (AND-SUB-OR).

    https://github.com/tlk00/BitMagic/tree/master/samples/bvsetalgebra

    1. bm:scanner::pipeline implements fast multiple string search in memory compressed string vector with an optional OR stage (under the hood uses bm::aggregator<>). Latest version makes a change in semantics to use compile-time options to configure pipeline, new options result in faster code due to compile-time specialization (C++-17 is very useful there).

    OR stage helps to implement a SQL idiom: Field1 IN (value1, value2… valueN) for cases where list of search values is in the tens of thousands or more or Field1 IN (SELECT FieldN FROM…) idiom using memory compressed index-free search.

    New version adds important optimizations of the algorithms to automatically tune-up for a typical L2 cache size, but also adds a manual override (batch_size) to tune and tweak the system for a specific HW configuration and data distribution statistics. The auto-tune topic definitely deserves more optimization in the future.

    New usage modes and benchmarks are available at: https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample07

    Release notes: http://bitmagic.io/bm-7.7.7.html

    Source code(tar.gz)
    Source code(zip)
  • v7.6.0(Oct 17, 2021)

    • fixed regression bug from 7.5.0 in dynamic matrix allocation algorithms of succinct vectors

    • bm::aggregator<> reworked to support new pipeline mode for AND-MINUS ("all this but not that" queries) aggregation, using L1/L2 cache and algorithmic optimizations to run thousands of coordinated aggregations times faster than it was possible in previous versions

    • bm::scanner<> implements string new string search method for bulk search with bm::aggregator<>::pipeline under the hood. New bm::scanner<>::pipeline can run multiple string searches in unordered succinct string vectors times faster. It also implements new search methods which can be used to run massive queries and construct results (inverted list bit-vectors) or run stat analysis computing results population count without materializing the vectors (effectively histogram construction).

    -New example: strsvsample07 added to illustrate use of fast scanner and scanner pipeline 3x times, with synthetic benchmarks showing 3x better performance for bulk search cases.

    • Parallel compute engine and thread pools reworked to use Modern C++ approach based on lambdas rather than function pointers. New development lays the internal foundation for BitMagic parallel algorithms to unfold its potential on multi-threaded systems.

    Release notes: http://bitmagic.io/bm-7.6.0.html

    Source code(tar.gz)
    Source code(zip)
  • v7.5.0(Sep 12, 2021)

    Release Notes: BitMagic 7.5.0

    • BitMagic now requires C++17 compiler
    • bm::sparse_vector<> - succinct vector using principles of bit slicing (or bitwise transposition) reworked to support signed integer types. Previous versions were designed for unsigned types and it was a limitation. Signed types use complement codes, which may not be friendly to bit-slicing approach because negative ints with small absolute values become strings of 1s on the binary level -1 (represented as 11111). New version handles this case and automatically transforms signed values into “sign and magnitude” internal representation to have good memory and disk serialization efficiency (BM vectors are designed to be used as a variable binary encoders for non-sparse cases). New feature is consistently supported in serialization, scanner search and should be completely transparent for the programmer
    • bm:: str_sparse_vector<> reworked to transparently support dynamic string length. The initial configuration used as a template parameter is now means the initial value (16 in the example below) typedef bm::str_sparse_vector<char, bvector_type, 16> str_sv_type; When a string with length above the specified parameter added, the container automatically resize its internal bit-matrix to correctly support it. No need to conservatively pre-allocate values now. This is a significant internal change which will allow to implement succinct vectors of arrays based on the same bit-slicing principles. -New example: svsample07a added to illustrate use of fast scanner and interval enumerator to study the properties of unsorted integer sequences in compact memory mode.

    Release notes: http://bitmagic.io/bm-7.5.0.html

    Source code(tar.gz)
    Source code(zip)
  • v7.4.0(Jul 3, 2021)

    1. Continued effort to provide better version for WebAssembly, first WASM SIMD build is available using: #define BMWASMSIMDOPT (or define via makefile).

    emcc command like may look like: emcc -std=c++11 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti

    Please note that WebAssembly SIMD is implemented as cross-compilation tweak for SSE4.2 (thus needs -msse4.4 flag).

    WebAssembly SIMD is still an experimental feature for all browsers but Google Chrome. Initial performance observations sometimes show faster than native(without SIMD) speed for optimized algorithms.

    1. Implemented 3-valued logic operations (INVERT, AND, OR) following the Kleene truth tables. https://en.wikipedia.org/wiki/Three-valued_logic

    Usage example: https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

    1. Fixed bugs in parallel algorithms (race condition).
    Source code(tar.gz)
    Source code(zip)
  • v7.3.1(Feb 4, 2021)

  • v7.3.0(Jan 25, 2021)

    BitMagic v.7.3.0 focuses on improving compression (speed and rate) of bit-transposed vectors and data frames.

    XOR compression filter went through additional testing on real-life datasets, resulted in significant re-implementation of algorithms to optimize for 32/64-bit systems or SIMD. New implementation includes a version of task-parallel algorithms (not final and poorly documented at this moment) to calculate XOR similarity model using multiple cores/threads (gives times faster performance). Future versions will provide better documentation/examples.

    Continued effort to provide better version for WebAssembly. Improved compressed container serialization (compression rate and speed). Fixed threading issue in C mappings (contributed by Luiz Irber) affecting Rust bindings (applicable to other languages). Fixed issue with bm::str_sparse_vector<> with remapping of non-English characters (issue isolated by Andrea Asztalos). Fixed compilation issue related to Clang compiler compatibility and [[fallthrough]] (fix by Aaron Ucko).

    Source code(tar.gz)
    Source code(zip)
  • v7.2.0(Sep 23, 2020)

    Release Notes: BitMagic 7.2.0

    1. Continued effort to provide more optimized version for ARM CPU. Optimized bm::bvector<> bit-vector left-right shifting for better ARM performance. As a low level function this functionality impacts multiple scenarious related to costruction or update of sorted compressed containers.

    2. Lots of focus on improving compressed container serialization (compression rate). New serialization format takes advantage of Binary Interpolated Coding which results in significant reduction in size of serialized BLOBs.

    For more detail please visit updated use case for compression of dictionaries here: http://bitmagic.io/star-search.html

    1. The main focus of this release was to improve memory compact container for strings. bm::str_sparse_vector<> while it is called "sparse vector" this container demonstrates excellent compression performance on dense vectors (20 to 30% improvements on different cases).
    • Performance improvements for bm::str_sparse_vector<>::const_iterator (up to 2x times faster now)
    • bm::str_sparse_vector<>::const_iterator can now iterate on substrings
    • new methods for bm::sparse_vector_scanner<> bm::sparse_vector_scanner<>::find_eq_str_prefix(..) - prefix search bm::sparse_vector_scanner<>::find_eq_str(..) scan the vector, return bit-vector resultset of matching indexes
    • new example on how to use compressed vector functionality (substring iterators, scanner) https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample06
    • new algorithm for bit-transposed dictionary remapping, it is now based on character frequency analysis and substitution similar to Huffman coding
    • fixed bug in bm::str_sparse_vector<>::back_insert_iterator related to processing of NULL-able vectors

    Release notes: http://bitmagic.io/bm-7.2.0.html

    Source code(tar.gz)
    Source code(zip)
  • v7.1.0(Sep 8, 2020)

    1. Fixed bug (rooted in 6.x.x versions) of AND operation. This is rare, but potentially serious issue, please upgrade your version asap.

    2. ARM CPU improvements

    ARM CPU is getting much attention nowdays, BitMagic library succinct containers are very useful in situations of limited memory and edge computing. This release improves suppirt there.

    BitMagic v.7.1.0 was formally tested and verified to work on 32-bit ARM (Raspberry Pi). Formal ARM testing showed certain pain points of BitMagic (bitscan algorithms reliance on POPCNT). As part of 7.1.0 release we introduced a different approach to bitscan based on CLZ (count leading zeroes) which is available natively on ARM. This resulted in significant improvement in performance of bvector<>::enumerator on ARM.

    ARM testing also showed ways to improve Rank-Select algorithms and succinct containers based on Rank. Some optimizations are still in progress, subject of follow up releases.

    ARM NEON SIMD support is planned as well.

    Release notes: http://bitmagic.io/bm-7.1.0.html

    Source code(tar.gz)
    Source code(zip)
  • v7.0.0(Jul 31, 2020)

    1. Improvements to Binary Interpolative Coding as a workhorse compression method for bit-vectors. New serialization format is backward compatible and gives 5-6% improved compression (based on Gov2 tests).
    2. Fixed bug in bvector<>::select() (Rank-select index) algorithm

    Release notes and tests: http://bitmagic.io/bm-7.0.0.html

    Source code(tar.gz)
    Source code(zip)
  • v6.4.0(May 13, 2020)

    1. New algorithm bm::rank_range_split(...) (bmalgo.h) to determine N ranges with the same rank (population count). See example: (samples/bvsample24) New algorithm can be used for planning of parallel processing when bit-vector defines a pool of tasks which needs to be broken into a few sub-groups based on equal weight.

    2. AVX2 optimizations for population counting for bm::aggregator<>

    3. New bm::bvector<>::enumerator constructor to take const bm::bvector<>& reference.

    4. Rank-Select compressed container rsc_sparse_vector<> constructor to explicitly define NOT NULL values. This new mode is for use case when rsc_container values are known and can now be randompy assigned using rank-select index. This new mode is times faster for construction of compressed containers in compact memory.

    See samples\rscsample04

    1. implemented rsc_sparse_vector<>::inc(size_type i) and variants to increment succinct container values in compact memory. This new functions can be used for memory compact term-requency analysis or building hystograms in compact memory.

    See samples\rscsample04

    1. Fixed bug in bm::sparse_vector_find_first_mismatch algorithm

    2. improved compilers support of [[fallthrough]] in a Clang corner case (thanks to Aaron Ucko)

    3. fixed compilation issues related (GCC) related to handling of attribute((always_inline)) (forced inline)

    Release notes: http://bitmagic.io/bm-6.4.0.html

    Source code(tar.gz)
    Source code(zip)
  • v6.3.0(Apr 1, 2020)

    1.The main story for this release is to improves rsc_sparse_vector<> (Rank-Select compressed container) to add const_iterator class to simplify (and speed up) access to container content.

    1. New exmple: samples/rscsample03 illustrates usage models for: rsc_sparse_vector<>::const_iterator

    2. Performance optimizations:

    • improved speed of rsc_sparse_vector<>::decode* methods (up to 2x improvement)
    • improved performance of bvector<>::enumerator
    1. New method to compute corrected rank bvector<>::rank_corrected() New method computes rank() minus value(0 or 1) of the index value. rank_corrected() is faster than an equivalent expression of "rank()-test()" BitMagic uses it now in succinct algorithms for address resolution.

    Release notes: http://bitmagic.io/bm-6.3.0.html

    Source code(tar.gz)
    Source code(zip)
  • v6.2.0(Mar 5, 2020)

    Release Notes: BitMagic 6.2.0

    1.This release introduces a new group of algorithms for re-interpretation of bit-vectors as a ranges/intervals. Bit-interval is a contiguous block of 1s flanked with 0s as “011110”. For example bit-vector “0101110” can be interpreted as two ranges / intervals of set values: [1..1],[3..5]. New version adds a new header for interval algorithms and iterators. New algorithms are: bm::find_interval_end(..) – search for end of bit-block coordinate bm::find_interval_start(..) – search for start of bit-block coordinate bm::is_inetrval(…) – check if two coordinates represent an solid block of 1s flanked with 0s (an interval) bm::interval_enumerator<> - const forward iterator to interpret a bit-vector as intervals.

    1. Re-worked examples sample22 and sample23 to illustrate new interval algorithms and interval_enumerator<>. https://github.com/tlk00/BitMagic/blob/master/samples/bvsample22/sample22.cpp https://github.com/tlk00/BitMagic/blob/master/samples/bvsample23/sample23.cpp

    2. Minor improvements for WebAssembly build for cleaner ‘noexcept’ declaration which positively affects performance.

    Release notes: http://bitmagic.io/bm-6.2.0.html

    Source code(tar.gz)
    Source code(zip)
  • bm6.1.0(Feb 8, 2020)

    Release Notes: BitMagic 6.1.0

    1. Performance improvements for WebAssembly Emscripten builds with exceptions enabled. 2-5 times better performance in synthetic tests and real life applications.

    2. New bvector<> functions for ranges and intervals Example: https://github.com/tlk00/BitMagic/blob/master/samples/bvsample22/sample22.cpp

    Detailed release notes: http://bitmagic.io/bm-6.1.0.html

    Source code(tar.gz)
    Source code(zip)
  • bm6.0.0(Jan 20, 2020)

    Release Notes: BitMagic 6.0.0

    1. This is major version release; it changes the serialization format for bit-vectors. New serialization format now uses more compact variable byte encoding for internal technical information. New release is backward compatible, old BLOBs does not need to be re-encoded. Old programs needs to be recompiled to read new serailized BLOBs. Compression rate improvements should within 1% but for large collections of bit-vectors and sparse vectors it makes positive difference.

    2. New serialization format now supports bookmarks for efficient range deserialization. Bookmarks increase serialization size, so it is not enabled by default. If you are not using range deserialization you do not need bookmarks.

    serializer::set_bookmarks(bool enable, unsigned bm_interval);

    If you use range deserialization (and want it to work faster) you need to setup bookmarking to allow deserializer to rewind through the BLOB when range deserialization request is processed.

    bm_interval parameter in this case defines how often bookmarks are added between blocks of encoding. Block size is 64K elements. bm_interval = 64 would mean serializer will inject a skip reference every 64 blocks. Increasing this number keeps the BLOB smaller at the expense of the rewind precision. This affects performance and size not the result of the deserialization.

    Range deserialization would work even without bookmarks.

    1. Bookmarks and range deserialization works for all bit-transposed sparse vectors.

    Code snippet to illustrate setting bookmarks:

        // serialize sparse vector
        bm::sparse_vector_serial_layout<svector_u32> sv_lay;
        {
            BM_DECLARE_TEMP_BLOCK(tb)
            sv1.optimize(tb);
    
    
            bm::sparse_vector_serializer<svector_u32> sv_serializer;
            sv_serializer.set_bookmarks(true, 64);
    
            sv_serializer.serialize(sv1, sv_lay);
        }
    
        const unsigned char* buf = sv_lay.buf();
    
    
        bm::sparse_vector_deserializer<svector_u32> sv_deserial;
        sv_deserial.deserialize_range(sv2, buf, 1, 4);
    

    https://github.com/tlk00/BitMagic/blob/bm-6.0.0/samples/svsample08/svsample08.cpp

    1. Build environment for cmake fixes, enabled pthreads credits to Joshua Marshall (jrmarsha at mtu.edu).

    2. Bit-trasposed sparse vector added copy_range() method for efficient range slicing str_sparse_vector<>::copy_range(...)

    3. Bit-transposed rank-select compressed succinct vector added copy_range() method for range slicing. rsc_sparse_vector<>::copy_range(...)

    4. Fixed serialization performance regression, unnecessary initialization
      of temporary buffers (introduced in v.5.0.0)

    5. Fixed minor corner case crash in copying of empty bit-vectors

    Technical notes: http://bitmagic.io/bm-6.0.0.html

    Source code(tar.gz)
    Source code(zip)
  • bm5.3.0(Nov 27, 2019)

    Release Notes: BitMagic 5.3.0

    1. New method to find first mismatch between two bit-vectors. bm::bvector<>::find_first_mismatch(..) It was possible to use XOR operation to identify all mismatches, new method is works faster for cases when only first mismatch is important. New method is optimized for for SSE4.2 and AVX2. If mismatch not found it returns false which is an indication that two vectors are identical.

    2. New method to check bit-vectors for equality. bool bm::bvector<>::equal(const bvector& bvect) const

    3.bm::operation_deserializer<> class simplified deserialization methods signatures not to require to pass an external scratch memory (temp block). Algebra of Sets sample simplified to reflect this change. https://github.com/tlk00/BitMagic/tree/master/samples/bvsetalgebra

    1. Fixed compilation defects in C language mappings.

    Application notes: http://bitmagic.io/bm-5.3.0.html

    Source code(tar.gz)
    Source code(zip)
  • bm5.2.0(Oct 15, 2019)

    Implements selective (gather or range) deserialization for all types of bit-transposed sparse vectors. New deserialization allows selective extraction out of compressed BLOBs in one operation which is faster, simple and allocates less. New API is based on logical AND operation on bit-vectors. Notes: http://bitmagic.io/bm-5.2.0.html

    Source code(tar.gz)
    Source code(zip)
  • b5.1.1(Sep 15, 2019)

    1. Fixed corner case crash on OR-ing multiple empty bit-vectors using overloaded operator syntax: bv_t = bv0 | bv1 | bv2;

    2. Sign of life with WebAssemblies BitMagic library traces its legacy to 32-bit systems and still maintains compatibility there It helped in this case to run in browser environment. v.5.1.1 includes some tweaks to better enable some platform features like build-in popcount, lead zero count, etc.

    There is still work to better understand how to do exceptions and error conditions handling, but it is already clear that the library passes the core tests in all major browsers supporting WebAssemblies.

    1. Important fixes to cleanup warnings on case fall through and shadowed parameters, better support some C++17 features like [[fallthrough]]

    2. rsc_sparse_vector<> container (rank-select compressed vector for scalar ints) - implemented proper back-insert iterator.

    3. Succinct containers: back insert iterators now do on the fly memory optimization. The new feature reduces main memory footprint of ETL processes in environments with memory pressure.

    Source code(tar.gz)
    Source code(zip)
  • v5.0.0(Jul 20, 2019)

    1. Fixed crash related to agressive -O3 optimizations on GCC

    2. Implemented new algorithm: lower_bound search for integer in bit-transposed container: bm::sparse_vector_scanner<>::lower_bound() Documented as an API sample svsample07.cpp https://github.com/tlk00/BitMagic/blob/master/samples/svsample07/svsample07.cpp

    3. New compressed serialization using Binary Interpolated Encoding. Tested on Gov2 collection it gives approximately 25% improvement in disk footprint comparing to previous version which was using Delta Elias Gamma encoder. New serialization is backward compatible, BitMagic will read old BLOBs. New serialization default is level 5. If you like to keep using Elias Gamma - use level 4.

    Source code(tar.gz)
    Source code(zip)
  • v4.0.0(Jun 26, 2019)

    Release Notes: BitMagic 4.0.0

    Implemented 64-bit address mode for indexing problems with more than 4 billion elements. #define BM64ADDR to enable the new mode or use #include bm64.h

    Known limitations: it only supports 48-bit (2^48-1) elements, you cannot use both 32-bit and 64-bit address modes in one compile unit (implementation is based on pre-processor)

    Added new example to explain how to enable 64-bit mode. https://github.com/tlk00/BitMagic/blob/master/samples/bvsample01_64/bvsample01_64.cpp

    Added bm::bvector<>::erase() method to delete a bit in bit-vector

    Added bm::bvector<>::shift_left()

    Source code(tar.gz)
    Source code(zip)
  • bm5.4.0(Dec 7, 2019)

    Release Notes: BitMagic 5.4.0

    1. Fixed minor corner case bug in bm::bvector<>::invert(). The bug was inversion of a vector of size() == 0.

    2. Minor performance improvements for bm::bvector<>::find_first_mismatch(..) - find first mismatch between two bit-vectors.

    3. New bit-transposed sparse vector algorithm. template bool sparse_vector_find_first_mismatch(const SV& sv1, const SV& sv2, typename SV::size_type& midx);

    Algorithm helps finding first mismatch between two bit-transposed vectors without reverse de-transposition, using operations on bit plains.

    1. New example for bm::sparse_vector_find_first_mismatch(...) https://github.com/tlk00/BitMagic/tree/master/samples/svsample09"> Use case explains how to implement DNA compression using bit-transposed sparse vector and construct comparison function without decode. http://bitmagic.io/dna-compare.html

    Technical notes: http://bitmagic.io/bm-5.4.0.html

    Source code(tar.gz)
    Source code(zip)
  • bm3.20.0(Mar 19, 2019)

    Release Notes: BitMagic 3.20.0

    1. bm::str_sparse_vector<> - bit-transposed succinct container for strings now implements const_iterator and back_insert_iterator. Both iterators implement transparent transpositions of the container elements and work significantly faster than random element access methods.

    2. Added new examples to illustrate usage of bm::str_sparse_vector<>

    3. bm::bvector<> - implemented new, improved algorithms for bit-shifting of compressed blocks

    4. Fixed number of warnings and compile regressions for 32-bit systems

    5. Fixed logical bug in SSE4.2, AVX2 implementations of fused SHIFT-RIGHT-AND. The bug affected sparse vector search algorithms.

    Source code(tar.gz)
    Source code(zip)
  • v.3.18.00(Dec 24, 2018)

    Release Notes

    1. This release was about optimizations of search algorithms in bit-transposed sparse strings (memory efficient dictionaries) see str_sparse_vector<> in bmstrsparsevec.h Current release implemented re-mapping of dictionary charactes based on their presense in the transposed plains. This trick is makes bit-matrix more succinct and facilitates faster search.

    Optimizations resulted in 2x times improvement in both linear dictionary scan (unsorted column) and binary search (sorted index). Some extra large cases (hundreds of millions of strings) showed performance parity with STL map with up to 20x times (sic!) memory footprint advantage.

    1. Updated example for memory efficient dictionaries (it uses NASA NED extragalactic database) to provide new performance metrics and explain optimization methods. see xsample05.cpp Tech.Note: http://bitmagic.io/star-search.html
    Source code(tar.gz)
    Source code(zip)
  • v.3.17.00(Dec 4, 2018)

    1. Optimizations of memory compression for (SSE4.2 and AVX2) Faster bvector<>::optimize(), faster serialization for SIMD builds.

    2. New experiental container for bit-transposed sparse strings (for memory efficient dictionaries) see str_sparse_vector<> in bmstrsparsevec.h

    3. New example/benchmark for memory efficient dictionaries (xsample05.cpp) Tech.Note: http://bitmagic.io/star-search.html

    Source code(tar.gz)
    Source code(zip)
  • v.3.16.00(Nov 10, 2018)

    1. Implemented new method to set multiple bits in bit-vector bvector<>::set(...) New method uses SSE4.2 and AVX2 accelerated algorithms. https://github.com/tlk00/BitMagic/blob/master/samples/bvsample12/sample12.cpp

    2. Implemented bvector<>::bulk_insert_iterator
      to do fast construction of vectors C++/STL style. https://github.com/tlk00/BitMagic/blob/master/samples/bvsample19/sample18.cpp

    3. New method bvector<>::merge()
      to combine multiple bit-vectors (logical OR) faster. https://github.com/tlk00/BitMagic/blob/master/samples/bvsample19/sample19.cpp

    4. New example/benchmark for fast fingerprint/index construction. http://bitmagic.io/dna-search-idx.html

    Source code(tar.gz)
    Source code(zip)
  • v.3.15.00(Oct 27, 2018)

    1. Implemented new API for right shift of bit-vectors bvector<>::shift_right()

    2. Implemented fast aggregator SHIFT-AND for pattern searches.

    3. New example for fingerprint based substring search (xsample04.cpp) with SHIFT-AND bitap algorithm. Tech. note: http://bitmagic.io/dna-search.html

    Source code(tar.gz)
    Source code(zip)
    bm-3.15.0.tar.gz(11.89 MB)
  • v.3.14.50(Oct 8, 2018)

    1. Optimizations for rank-select operations using rs-index, SIMD(SSE4.2, AVX2) and BMI2 instructions. Tech.note: http://bitmagic.io/rank-select.html
    2. New example (sample17.cpp) to illustrate use of rs-index. http://bitmagic.io/doxygen/html/sample17_8cpp-example.html
    Source code(tar.gz)
    Source code(zip)
    bm-3.14.5.tar.gz(11.43 MB)
Owner
Anatoliy Kuznetsov
search systems, db internals, bio-informatics, software optimization, distributed systems, data-parallel programming, SIMD optimization, WASM
Anatoliy Kuznetsov
A library of generic data structures.

Collections-C A library of generic data structures including a list, array, hashtable, deque etc.. Examples Building and Installing Using the library

Srđan Panić 2.4k Jun 26, 2022
A simple C library for working with KD-Trees

kdtree Overview kdtree is a simple, easy to use C library for working with kd-trees. Kd-trees are an extension of binary search trees to k-dimensional

John Tsiombikas 331 Jun 19, 2022
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

PpHd 493 Jun 20, 2022
Linear Linked List Library

list.h Implementations for singly-linked and doubly-linked list functions. Basic Working Example #include <stdio.h> #include <stdlib.h> #include "list

Nick Bulischeck 41 Jun 23, 2022
C header library for typed lists (using macros and "template" C).

vector.h C header library for typed lists (using macros and "template" C). Essentially, this is a resizable array of elements of your choosing that is

Christopher Swenson 28 May 6, 2022
Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as task graphs that are scheduled concurrently and asynchronously on both CPUs and GPUs.

Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as tasks in a graph structure, where edges represent task dependencies

null 23 May 11, 2022
nanoplan is a header-only C++11 library for search-based robot planning.

nanoplan is a header-only C++11 library for search-based robot planning. The primary design goals are correctness, ease-of-use, and efficiency (in tha

Jordan Ford 14 May 17, 2022
libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Ilya Grebnov 89 Jun 21, 2022
An open source library for C

Eric O Meehan C Library Introduction Eric O Meehan's C Library is an open source collection of tools for the C programming language. The project is in

Eric O Meehan 90 Jun 12, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Lprogrammers Lm9awdine 47 May 29, 2022
Experimental managed C-strings library

Stricks Managed C strings library. ?? API Why ? Because handling C strings is tedious and error-prone. Appending while keeping track of length, null-t

Francois Alcover 79 Jun 21, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

LibC+ Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -lC+ Better than C, not as much as c++ Usage

BnademOverflow 47 May 29, 2022
Simple C++ Genetic Algorithm library

crsGA: Simple C++ Genetic Algorithm library crsGA is a simple C++ template library for developing genetic algorithms, plus some other utilities (Logge

Rafael Gaitán 6 Apr 24, 2022
A library of type safe sets over fixed size collections of types or values, including methods for accessing, modifying, visiting and iterating over those.

cpp_enum_set A library of type safe sets over fixed size collections of types or values, including methods for accessing, modifying, visiting and iter

Carl Dehlin 22 Jun 16, 2022
small library to bind functions to theirs string analog

congenial-disco Small library. Helps invoke function by name. Work in progress. Build Clone repository: git clone https://github.com/glensand/congenia

Gleb Bezborodov 4 Mar 28, 2022
A fast Python Common substrings of multiple strings library with C++ implementation

A fast Python Common substrings of multiple strings library with C++ implementation Having a bunch of strings, can I print some substrings which appea

Đào Nguyên Dương 6 Sep 14, 2021
Behavior Trees Library in C++. Batteries included.

This C++ 14 library provides a framework to create BehaviorTrees. It was designed to be flexible, easy to use, reactive and fast.

null 1.4k Jun 27, 2022
A library of assorted data structures in C

C Data Structures A library of data structures in C. Documentation is available here. Maps Stores key/value pairs. Keys are null-terminated strings, w

Don Isaac 3 Sep 29, 2021
A simple & stupid data structure library for C

HDataStruct - Hans' Data Structures Library A simple & stupid data structure library for C. Introduction This is a small C library containing several

Hans Wan 3 Oct 6, 2021