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.

To write to a file:

BufferedWriter outputStream = 
  new BufferedWriter(new FileWriter("filename.txt"));
outputStream.write("hello");

To read a file from disk:

BufferedReader in = new BufferedReader(new FileReader("foo.in"));
while ((strLine = in.readLine()) != null)   {
      // Print the content on the console
      System.out.println (strLine);
    }

A very simple makefile template:

CC=g++

CFLAGS=-I.
DEPS = SuperFastHash.h TcpDumper.h
%.o: %.cpp $(DEPS)
	$(CC) -c -o $@ $< $(CFLAGS)

hellomake: msb.o parseTest.o rabinpoly.o TcpDumper.o 
	g++ -o dumpPrinter parseTest.o TcpDumper.o -I.

To read in a file from python

infile = file(filename, "r")  

while(infile):
  line = infile.readline()     
  if(line == ""):         
    break     
  else:     
    print line