Bits counting

One of the most important operations in bit set arithmetic is counting number of 1 bits. BM uses integer-based bitvectors. It means that each bitvector uses arrays of integers as a minimal building block for bit sets. The default method used in BM splits each integer into 4 characters and looks up a table containing bits count. This linear approach can be improved by using 16-bit wide table, but at the cost of a much larger table. Larger table will most probably introduce some additional memory fetch operations, interfere with on CPU cache and finally will fail to deliver a significant performance boost.

int count(long long b)
{
     b = (b & 0x5555555555555555LU) + (b >> 1 & 0x5555555555555555LU);
     b = (b & 0x3333333333333333LU) + (b >> 2 & 0x3333333333333333LU);
     b = b + (b >> 4) & 0x0F0F0F0F0F0F0F0FLU;
     b = b + (b >> 8);
     b = b + (b >> 16);
     b = b + (b >> 32) & 0x0000007F;

     return (int) b;
}

This code was inspired by “Exploiting 64-Bit parallelism” article by Ron Gutman in Dr.Dobb’s Journal September 2000. Tests showed that this code can leave table counting method far behind.

from: http://bmagic.sourceforge.net/bm64opt.htmlCould have been useful for counting 1s in bloom filters for memory buddies work.

Use Gnu Prof to find out how much CPU time is spent in each function and how often they are called.

First, compile the code with the -pg flag

Then, run the program as usual. It will produce a gmon.out file

Run gprof execname to view the output statistics (probably want to redirect or use less)