Notes and Articles

... on compression and performance

Methods for population count using prefix sum operations

Brief overview of various bit vector population counting methods in BitMagic library. Optimization potential with SSE4.2/AVX2 enabled systems.

Case study: memory consumption and performance of star scheme ER JOIN acceleration

Article 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.


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.

64-bit programming and optimization

64-bit programming checklist, examples of optimization techniques.