BitMagic Library v.3.7.0 released

- Fixed logical bug in deserialization (multiple deserialization into 1 bit-vector with incorrect OR)
- Performance optimization count_and(), bvector destruction, etc
- Simplified template arguments for bvector<>

Use case: Implementing GROUP BY – HAVING with bit-vectors

In this post I wanted to discuss a design pattern for implementing GROUP BY  -- HAVING requests, common in data-mining application.

Problem description:

Let’s say we have a fact table with multiple fields, all indexed using bit-vector based inverted lists.
Our goal is to run a query which best to describe in pseudo SQL :

SELECT fact1, count(*) FROM FactsTable
WHERE fact1 > ‘value’ AND fact2 BETWEEN 10 and 100 OR fact 3 = ‘valueX’
GROUP BY fact1
HAVING COUNT(*) > 100
The proposed “query plan” for this type of query is a two step process.

Step 1. Program runs a WHERE clause, retrieving bit-vectors corresponding to various parts of the logical expression (fact1 > ‘value’,  fact2 BETWEEN 10 and 100,  fact 3 = ‘valueX’). When all vectors are in memory, series of ANDs and Ors gives us the result. This is a low complexity problem.

Step 2.  Program got the bit-vector from Step 1 (Query Bit-Vector).
All we need to do now is to iteratively read all possible bit-vectors corresponding to fact1. Number of vectors here depends on the total number of variants (facts) in the fact1 field (in other words we are looking at fact1 cardinality). It can be quite large, but many intermediate results have a good chance to be filtered out with a HAVING criteria.

To perform GROUP BY – HAVING we propose to execute logical operation AND between the query vector and all fact1 vectors.  HAVING is trivial – all you need is to count bits in the AND product vector.

Lets look at the pseudo code for this:

LOOP (until we have bit-vectors)

{

     

   bv_file.read(buffer); // read BLOB

   bvect* pbv = new bvect(BM_GAP); // GROUP vect
   // deserialize BLOB

   bm::deserialize(*pbv, buffer); 

   *pbv &= bv_query; // GROUP BY AND 

   if (pbv->count() >= 100 )// HAVING

   {

              // process query results

   }

   delete pbv;

}

Scalability?

Algorithmic complexity of this approach is directly proportional to number on GROUP BY vectors we have to read , deserialize and AND. The good news is that there is no loop iteration carried dependencies, so this algorithm can be easily parallelized – all deserializations, ANDs and bit-counting can be done in parallel. For dense bit-vectors BitMagic will use vector operations with SSE2, SSE4.2 to use wide-parallel hardware acceleration.  So this algorithm is multi-core friendly and should scale well given that IO subsystem is sufficiently capable delivering new the raw data. 

On a well balanced system we will be able to utilize a large number of CPUs / Cores and solve this problem fast. 

BitMagic Library v.3.6.4 released

Release 3.6.4 significantly (up to x2 times) improves performance of deserialization.
This round of optimization should make all bit-vector database IO operations more efficient.

AMD CodeAnalyst Performance Analyzer for Windows®

Sharing some experience with AMD CodeAnalyst profiler.

This profiler from AMD is free, simple, lightweight and implemented as a Visual Studio plugin (apparently there is Linux version, but I did not try it yet). 

Default profiling mode is time-sampling. 

I took a  few screenshots:

From Blog

From Blog

From Blog

Pros and Cons:

1. Easy to use, you can start your session in a few minutes (+)
2. Hot-spot detection is easy, chart based, results are generally believable (+)
3. Profiler is lean and works fast, profiled program is not slowed down. (+)
3. AMD CodeAnalyst is free (+)
4. Different screens (chart and data) sometimes give contradicting results, which is a bit confusing. (-)
    In the screenshots above 1 and 3 indicate different proportion in hot-spot data (maybe I don't understand something or bug in visualization).
5. I failed to get call stack for hot-spots even though configuration promised to collect it. (-)
    This can be a big issue for large projects with multiple code paths.
    Similar tools like Intel Parallel Studio can show call stacks and allows easy call stack analysis.

http://developer.amd.com/cpu/CodeAnalyst/codeanalystwindows/Pages/default.aspx

BitMagic included in the Softpedia Linux software database

 http://linux.softpedia.com/get/Programming/Libraries/BitMagic-library-53513.shtml

BitMagic library version 3.6.3 released

This release fixes critical bug in 64-bit mode (#define BM64OPT) and improves performance of bit-counting related operations.

Parallel superscalar bit-counting

While working on version 3.6.3 collective Internet wisdom brought yet another interesting bit-counting algorithm, which turns to be efficient for 64-bit systems with superscalar execution (a form of parallelizm, where linear code with data-independent instructions is actually executed in parallel).

This code below implements population count for 4 64-bit integers. (Tested with GCC 4.4.1 64-bit Linux). This becomes part of BM 3.6.3 (when SourceForge recovers from its (I hope temporary) down).

inline
unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y,
                    bm::id64_t u, bm::id64_t v)
{
    const bm::id64_t m1 = 0x5555555555555555;
    const bm::id64_t m2 = 0x3333333333333333;
    const bm::id64_t m3 = 0x0F0F0F0F0F0F0F0F;
    const bm::id64_t m4 = 0x000000FF000000FF;

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y;
    u = u + v;
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4;
    x = x + (x >> 32);
    return x & 0x000001FF;
}

SourceForge down :-(

Python wrapper for BitMagic is in the works

Author: William Waites
http://pypi.python.org/pypi/bitmagic

BitMagic library version 3.6.2 -- broken

Bad news, version 3.6.2 confirmed to be broken for 64-bit builds. Urgent patch is coming...

BitMagic library version 3.6.2 released

New features:
- added configurations for MacOS-X
 - optimizations for SSE 4.2 in 64-bit mode

now it is fine to use:
#define BM64OPT
#define BMSSE42OPT

This two options produce SIMD vectorized code for SSE 4.2 which uses 64-bit aware bit-counting

- new algorithm for picking random subset out of bvector<>
see  sample10.cpp

SSE2 vs CUDA in parallel bit stream transposition / similarity. Part 2.

We made a second attempt to work with CUDA to better understand if it looks like a suitable technology for database and data-mining acceleration.
With a very valuable help from our readers we prepared a second version of GPU benchmark and tried to analyze performance and power consumption.

CUDA vs SSE. Part 2.

Win7 vs Ubuntu 9.10 (32-bit vs 64-bit)

This benchmark is designed to illustrate platform-compiler choice for BitMagic derived computational algorithms.

Test total numbers (shorter - faster)

From Blog

Test Platform: Nehalem Core i5, 2.67GHz (Turbo Boost enabled)
BitMagic Library 3.6.2 (not yet released)

Windows 7 32-bit used default 32-bit compile using MSVC8. SSE4 optimization disabled.

Ubuntu 9.10 64-bit GCC 4.4.1 with compile options ( -march=core2 -m64 -msse4 )

BitMagic 64-bit optimizations + SSE4 optimizations:
#define BMSSE42OPT
#define BM64OPT

(this combination will be supported in BitMagic Library 3.6.2).

All measurements in seconds (shorter - faster).

From Blog

As you can see, 32-bit default compile using stock compiler looses in almost every test to 64-bit SSE4.2 version, tuned for the platform.

Yes, this experiment intentionally staged for Windows7+MSVC to loose (by using unfavorable compilation and optimization settings: stock x86 32-bit software suffers from register starvation, ofter ignores presence of SIMD SSE unit. Having said that such resource under-utilization often happens in real-life and it is often ignored as insignificant. From this data we can see that sometimes insignificant things can add-up to measurable values.

BitMagic library version 3.6.1 released

• Elias Gamma decoding optimizations significantly improved bit-vector de-serialization performance. Compressed bit-vectors now save disk space and IO bandwidth without big CPU costs
• Fixed stack overrun introduced in 3.6.0
• First version of SSE 4.2 optimizations for Nehalem (Core i5, i7, etc). Tested with MSVC 2008 and GCC 4.4.1. Use BMSSE42OPT to turn on SSE4.2 support in the code.
  

64-bit portability checklist

Useful article from developers of PVS Studio tool on porting to 64-bit systems.

20 issues of porting C++ code on the 64-bit platform

SSE4.2 readyness. GCC vs MSVC. Deathmatch.

GCC 4.3.2 (cygwin) vs MS VC++ 2008 (Windows 7).

First results porting BitMagic Library to Intel Nehalem SSE4.2 instruction set. :-)

1>Generating code
1>c:\dev\bm\src\bmsse4.h(140) : fatal error C1001: An internal error has occurred in the compiler.
1>(compiler file 'f:\dd\vctools\compiler\utc\src\p2\main.c[0x60375DBB:0x00000000]', line 182)
1> To work around this problem, try simplifying or changing the program near the locations listed above.
1>Please choose the Technical Support command on the Visual C++ 
1> Help menu, or open the Technical Support help file for more information
1>LINK : fatal error LNK1000: Internal error during IMAGE::BuildImage
1>  Version 9.00.30729.01
1>  ExceptionCode            = C0000005
1>  ExceptionFlags           = 00000000
1>  ExceptionAddress         = 60375DBB (60300000) "C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\c2.dll"
1>  NumberParameters         = 00000002
1>  ExceptionInformation[ 0] = 00000000
1>  ExceptionInformation[ 1] = 00000000
1>CONTEXT:
1>  Eax    = 031F666C  Esp    = 0034EC78
1>  Ebx    = 00000000  Ebp    = 0034ECA4
1>  Ecx    = 00000000  Esi    = 03214298
1>  Edx    = 00000000  Edi    = 03201608
1>  Eip    = 60375DBB  EFlags = 00010246
1>  SegCs  = 0000001B  SegDs  = 00000023
1>  SegSs  = 00000023  SegEs  = 00000023
1>  SegFs  = 0000003B  SegGs  = 00000000
1>  Dr0    = 00000000  Dr3    = 00000000
1>  Dr1    = 00000000  Dr6    = 00000000
1>  Dr2    = 00000000  Dr7    = 00000000
1>Build log was saved at "file://c:\dev\bm\bmperf\Release\BuildLog.htm"
1>bmperf - 2 error(s), 5 warning(s)




$ make
======= Building : BitMagic Library Performance Test cygwin GNU_CC
< perf.cpp >
g++ -msse4 -march=core2 -Wall -c  -D_REENTRANT -DCYGWIN_NT -D_GNU_SOURCE  -Wno-d
eprecated    -I/cygdrive/c/dev/bm/src  perf.cpp -o /cygdrive/c/dev/bm/tests/perf
/Release/perf.o -g0 -O2 -march=core2 -fomit-frame-pointer -pipe
perf.cpp: In function 'void EnumeratorTest()':
perf.cpp:497: internal compiler error: in memory_address_length, at config/i386/
i386.c:16380
Please submit a full bug report,
with preprocessed source if appropriate.
See  for instructions.
make: *** [/cygdrive/c/dev/bm/tests/perf/Release/perf.o] Error 1

Notes on Elias Gamma encoding in BitMagic 3.6.0

Version 3.6.0 implements a variant of Elias Gamma Encoding as part of bit-vector serialization.
Wikipedia has an article on this encoding here:
http://en.wikipedia.org/wiki/Elias_gamma_coding

The description is so good that one should be able to implement this encoding after reading a couple of pages.

Older versions of BM library used D-Gap compression which is a variant of run length encoding. Or used plain lists of integers to encode very sparse sets. All this compression methods used word aligned algorithms and rely on presence of long runs of identical bits. Word aligned compression is also very fast.

A lot of practical tests demonstrated that BM based search systems are bandwidth limited. It means that CPU is starved, waiting for memory operations or disk retrieval. Disk retrieval is particularly important because IO and network subsystems never followed terms of Moore Law. Non-Word-Aligned encoding seems to a good answer to this problem.

Elias Gamma encoding developed by Peter Elias postulates bit-encoding of positive (non-zero) integers . Positive non-zero integers are essentially the native format for BM library to store sparse bit-vectors or inverted lists (basic building blocks of efficient bitmap indexes).

Advantages:
1.Simple implementation, requires no compression dictionary. It is easy to compress just a few ints without constructing and storing a dictionary. BM library works with independent blocks of bits (potentially computed in parallel).
2.Implied probability favors small integers – good for BM library since it fragments bit-vector into blocks of 65K bits. Methods allows some blocks to be encoded, and some to remain in GAP or raw bit-block format (if statistical distribution of bits suddenly changes).
3.Compact implementation reduces code bloat, fits into a C++ template library paradigm.

Disadvantages:
1.True adaptive statistical methods (like arithmetic compression) can(should?) give better compression ratio.
2.Encoding and decoding method is sequential, it seems hard to implement a parallel encoder/decoder using SIMD, SSE or GP-GPU. (BM blocks can potentially be decoded in parallel so maybe there is a way to use parallel methods for this).

BitMagic Library v.3.6.0 released

improved bit-vector serialization with bitset compression.
New serialization adds Gamma encoding on top of D-Gap compression. This should
reduce IO for databases and search systems using serialized bit-vectors.

fixed functionality bug in deserialization with logical AND

new serialization API (old API kept for backward compatibility)

BitMagic version 3.5.4 released

The scope of this release is general code cleanup (only partially successful) and SSE2 for GCC compatibility fixes.

GCC supports SSE2 intrinsics, so this port was relatively easy. Practically the only change needed was correct syntax for 16-byte alignment declaration. SSE2 optimizations are now available for Intel C++, GCC and MSVC.

Download: https://sourceforge.net/projects/bmagic/files/

CUDA vs SSE

We all know that GPUs can be incredibly fast at some single precision floating point algorithms.
Developers of BitMagic Library Igor Tolstoy and Anatoliy Kuznetsov made an attempt to implement parallel bit-stream transposition and similarity algorithm (a lot of bit-shifting, population counting and general purpose integer logic) to better understand CUDA and GP-GPU computing in comparison with current (and future) Intel vectorization architectures (SSE2).

Benchmarking, CUDA and SSE source codes, some speculation about Larabee and implications for data-mining and large scale databases here:
http://bmagic.sourceforge.net/bmcudasse2.html