"Population count" is the problem of counting how many bits in a number are set to 1.

There are bit-twiddling and lookup-table algorithmic approaches to this problem, but these are hopefully obsolete now that POPCNT is implemented in the instruction sets of Intel, starting with Nehalem, and AMD, starting with Barcelona.

This project benchmarks various implementations of population count using direct bit manipulation, POPCNT via the gcc intrinsic __builtin_popcountl and POPCNT via inline assembly, with and without the use of OpenMP to divide the work amongst all cores.

The main program benchmarks the implementations using data from /dev/urandom. To build it and test it with a small amount of data:
make && make test

If all implementations run and report the same number of bits set, then everything is working. If your processor doesn't support the POPCNT instruction (e.g., you have a Core 2 Duo), then the program with crash. On linux, you can verify ahead of time whether it will work by checking for 'popcnt' in the Flags section of /proc/cpuinfo . If it fails to compile, you probably need a newer version of gcc (4.4 or later).

You can then benchmark the implementations with a larger amount of data with:
./count_bits <mem>
where mem it the amount of data to use, in megabytes (e.g., 1000 for a gig of data). Larger amounts will take a while to startup as /dev/urandom needs to get you that much random data. You can watch the physical memory used by the process grow (e.g., using top) until it reaches your requested amount.

The text file results.txt has benchmark results on an EC2 c1.xlarge instance.

More discussion on the population count problem:
http://www.reddit.com/r/programming/comments/22p5v/popcount_the_nsa_instruction_missing_from_modern/
http://chessprogramming.wikispaces.com/Population+Count



Copyright 2011 Bobby Impollonia

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.