Tech.notes on compression and performance optimization
Overview of Compression Algorithms in BitMagic Library
Big picture description of succinct and compression methods used for bit-vectors and columnar data types. Bit-vectors, H-compression, D-GAP(RLE), Elias Gamma, Binary Interpolative Coding, Bit-plane compression, XOR compression.
XOR compression of bit-transposed vectors
XOR compression is complementary filtering technique based on Hamming dissimilarity to better encode bit-transposed containers and collections of bit-vectors.
Binary Interpolative Coding
Binary Interpolative Coding is a new encoding technique for compression of integer sequences. It offers 30% better compression ratio than delta coding + elias-gamma when applied to bit-vectors.
Fast index construction (DNA fingerprints)
How to get indexing system from cold to operational in a matter of seconds. This tech.note discusses real-life scenario of DNA fingerprinting using SIMD, multi-threading and bandwidth optimizations.
Optimizations of Rank-Select operations
BitMagic Library implements Rank-Select index for fast succinct data structures. In this technical note we reviw data structures used for index construction, applicable SIMD optimizations and use of BMI1/2 instructions.
Fast logical operations on groups of vectors (Aggregator) (bm::aggregator<>)
BitMagic Library implements utilities for fast operations on groups of vectors. In this technical note we reviw cache-blocking optimization techniques, use of on-the-fly computed digests for pruning of search space, study impact of multi-way memory read, use of prefect and impact of SIMD (SSE4.2, AVX2) on performance.
Bit-transposed sparse vector as tool for compressed associative container
BitMagic Library implements functionality for fast and memory efficient set to set relations. In this technical note we reviw cache-blocking optimization techniques and AVX2 can set to set Image operations and access to sparse bit-tranposed data 4-5x times faster. AVX2 SIMD code examples, useful for designers of hash-maps, sparse vectors and matrix algorithms.
Bit-transposed sparse vector as compressed associative container
BitMagic Library implements functionality for fast and memory efficient set to set relations. In this technical note we reviw cache-blocking optimization techniques and AVX2 can set to set Image operations and access to sparse bit-tranposed data 4-5x times faster. AVX2 SIMD code examples, useful for designers of hash-maps, sparse vectors and matrix algorithms.
Technical notes: Performance of sort in compressive memory
Techincal notes on performance of sort algorithms on compressive containers
Case study: memory consumption and performance of star scheme ER JOIN acceleration
Tech.notes analyzes the performance and memory characteristics of BitMagic library leveraging very sparse vectors while performing set algebra operations used for join acceleration. The goal of this case study is to analyze memory footprint of various types of set representations based on data generated to mimic analytical requests to join relational tables with one-to-many relationship and answer question of applicability of bit-vectors for RDBMS join acceleration.
SSE2 vs CUDA
Some thoughts on perspectives of GPU computing for bit-vector operations. Can you accelerate database search and functions with a graphics card? Is it feasible to build a GPU accelerated database system?
SIMD vectorization - SSE2
Contemporary x86 CPUs offer variety of special commands for vector-based parallelism, where one command can process multiple data elements. SIMD - single instruction multiple data. Use of this special instructions is a valuable resource for tuning and optimization of algorithms.
Efficient Binary Metrics
BitMagic Library implements efficient algorithms for binary distances, used in building clusters and trees. Article explains principles of optimization of algorithms sensitive to CPU cache locality and memory bandwidth.
Allocation and memory usage optimizations
Bitsets generally offer perfect performance characteristics but in some cases they are becoming inefficient due to excessive memory usage. It usually happens when we try to allocate big number of dense, sparse or even empty bitvectors.
Delta GAP (DGAP) and hierarchical compression
Bitmaps and inverted lists often benefit from some variants of RLE compression. BitMagic uses a variant, which allows fast binary search and memory consumption compatible with sorted integer lists. Hierarchical compression technique is used to manage lists of blocks in memory. When bit-vectors are serialized, we employ simple, yet efficient Elias Gamma coding. Latest versions of BitMagic also support Binary Interpolative Coding, which is even better than Elias-Gamma.
64-bit programming and optimization
64-bit programming checklist, examples of optimization techniques.