Population Count functions

_README.textile

The population count function is used in many different scenarios. I first found out about it in the implementation of a HAMT data structure (Hash Array Mapped Trie).

The implementations herein are converted to Ruby from the C functions in this article. MRI is generally faster at these implementations than JRuby, but JRuby shines when any of these functions are called frequently enough to be able to inline the functions.

Platform information

OS	Yosemite 10.10.4
Machine	MacBook Pro (13-inch, Late 2011)
Processor	2.4 GHz Intel Core i5
Memory	16 GB 1333 MHz DDR3

Results

JRuby-9000-pre1

Rehearsal ------------------------------------------------------
population count 1   2.960000   0.060000   3.020000 (  1.576331)
population count 2   3.080000   0.040000   3.120000 (  1.081809)
population count 3   3.440000   0.060000   3.500000 (  1.265052)
population count 4   2.190000   0.040000   2.230000 (  1.083366)
-------------------------------------------- total: 11.870000sec

                         user     system      total        real
population count 1   1.780000   0.020000   1.800000 (  0.908257)
population count 2   0.750000   0.010000   0.760000 (  0.529459)
population count 3   0.560000   0.010000   0.570000 (  0.544030)
population count 4   0.880000   0.010000   0.890000 (  0.863588)

MRI Ruby 2.2.2

Rehearsal ------------------------------------------------------
population count 1   1.130000   0.010000   1.140000 (  1.142925)
population count 2   0.770000   0.000000   0.770000 (  0.772855)
population count 3   0.880000   0.010000   0.890000 (  0.887318)
population count 4   0.780000   0.000000   0.780000 (  0.781267)
--------------------------------------------- total: 3.580000sec

                         user     system      total        real
population count 1   1.180000   0.000000   1.180000 (  1.184153)
population count 2   0.780000   0.000000   0.780000 (  0.786497)
population count 3   0.920000   0.010000   0.930000 (  0.924347)
population count 4   0.840000   0.010000   0.850000 (  0.862379)

population_count.rb

# http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
# https://en.wikipedia.org/wiki/Hamming_weight
# https://en.wikipedia.org/wiki/Hash_array_mapped_trie

M1  = 0x5555555555555555 # binary: 0101...
M2  = 0x3333333333333333 # binary: 00110011..
M4  = 0x0f0f0f0f0f0f0f0f # binary:  4 zeros,  4 ones ...
M8  = 0x00ff00ff00ff00ff # binary:  8 zeros,  8 ones ...
M16 = 0x0000ffff0000ffff # binary: 16 zeros, 16 ones ...
M32 = 0x00000000ffffffff # binary: 32 zeros, 32 ones
H01 = 0x0101010101010101 # the sum of 256 to the power of 0,1,2,3...

def population_count1 x
  x = (x & M1 ) + ((x >>  1) & M1 ) # put count of each  2 bits into those  2 bits 
  x = (x & M2 ) + ((x >>  2) & M2 ) # put count of each  4 bits into those  4 bits 
  x = (x & M4 ) + ((x >>  4) & M4 ) # put count of each  8 bits into those  8 bits 
  x = (x & M8 ) + ((x >>  8) & M8 ) # put count of each 16 bits into those 16 bits 
  x = (x & M16) + ((x >> 16) & M16) # put count of each 32 bits into those 32 bits 
  x = (x & M32) + ((x >> 32) & M32) # put count of each 64 bits into those 64 bits 
  x
end

def population_count2 x
  x -= (x >> 1) & M1             # put count of each 2 bits into those 2 bits
  x = (x & M2) + ((x >> 2) & M2) # put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & M4        # put count of each 8 bits into those 8 bits 
  x += x >>  8                   # put count of each 16 bits into their lowest 8 bits
  x += x >> 16                   # put count of each 32 bits into their lowest 8 bits
  x += x >> 32                   # put count of each 64 bits into their lowest 8 bits
  x & 0x7f
end

def population_count3 x
  x -= (x >> 1) & M1             # put count of each 2 bits into those 2 bits
  x = (x & M2) + ((x >> 2) & M2) # put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & M4        # put count of each 8 bits into those 8 bits 
  (x * H01)>>56                  # returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
end

def population_count4 x
  count = 0
  while x > 0
    x &= x-1
    count += 1
  end
  count
end

def show_it n
  puts "#{n}: #{population_count n}"
end

require 'benchmark'
array = 1_000_000.times.map {|e| e + 1}

Benchmark.bmbm do |x|
  x.report("population count 1") do
    array.each do |n|
      population_count1 n
    end
  end

  x.report("population count 2") do
    array.each do |n|
      population_count2 n
    end
  end

  x.report("population count 3") do
    array.each do |n|
      population_count3 n
    end
  end

  x.report("population count 4") do
    array.each do |n|
      population_count4 n
    end
  end
end; nil