Skip to content

Instantly share code, notes, and snippets.

@knugie

knugie/bit_count_benchmark.rb

Last active May 25, 2022 19:25
Show Gist options
  • Save knugie/3865903 to your computer and use it in GitHub Desktop.
Save knugie/3865903 to your computer and use it in GitHub Desktop.
Download ZIP
bit_count_benchmark
Raw
bit_count_benchmark.rb
#!/usr/bin/env ruby
# coding: utf-8
require 'benchmark'
@count = 2_000_000
@lenght = 49
@pre_compute_16 = Array.new((2**16)) { |f| f.to_s(2).count('1') }
Strategy = Struct.new(:name, :method, :before)
def cpu_linux
`cat /proc/cpuinfo 2> /dev/null`.split("\n").find do |line|
line =~ /model name/
end.gsub(/\A[^:]*: /, '').gsub(/\s+/, ' ').strip
rescue
nil
end
def cpu_osx
`sysctl -n machdep.cpu.brand_string 2> /dev/null `.strip
rescue
nil
end
def cpu_name
cpu_linux || cpu_osx
end
def mem_linux
`cat /proc/meminfo 2> /dev/null`.split("\n").find do |line|
line =~ /MemTotal/
end.gsub(/\A[^:]*: /, '').gsub(/\s+/, ' ').strip
rescue
nil
end
def mem_osx
`sysctl -n hw.memsize 2> /dev/null`.strip
rescue
nil
end
def mem_size
mem_linux || mem_osx
end
def ruby_version
ENV['RUBY_VERSION']
end
def platform
RUBY_PLATFORM
end
# create an integer with randomly set bits, max. (bit-)length is lenght
def bit_rand(length = @lenght)
rand(2**length)
end
# create integers with randomly set bits, max. (bit-)length is @lenght
def sample_norm(count = @count)
sample = []
count.times.each do
sample << bit_rand(@lenght)
end
sample.freeze
end
# create integers with exacctly 5 bits set, max. (bit-)length is 49
def sample_lotto(count = @count)
sample = []
all = Array.new(49) { |e| 2**e }
count.times.each do
sample << all.sample(6).reduce(:|)
end
sample.freeze
end
# Make sure all strategies have the same result for the same input
# This is a test. It does not proof the correctness of the implementation
def test(strategies, *args)
result = true
sample = args[0]
sample.each do |int|
all = []
all << { int => strategies.map do |strategy|
strategy.before.call if strategy.before
strategy.method[int]
end }
all.each do |test_result|
next unless test_result.first[1].uniq.length != 1
test_result = false
puts "ERROR: #{test_result.first[0]}:"
puts test_result.first[1].zip(strategies.map(&:name)).map { |e|
' ' + e.inspect
} * "\n"
end
end
result
end
def benchmark(strategies, *args)
sample = args[0]
Benchmark.bm(strategies.map { |strgy| strgy.name.length }.max) do |analyse|
strategies.each do |strategy|
analyse.report(strategy.name) do
strategy.before.call if strategy.before
sample.each do |int|
strategy.method[int]
end
end
end
end
end
############################
############################
strategies = [
Strategy.new('scan_regex', proc do |int|
int.to_s(2).scan(/1/).size
end),
Strategy.new('scan_string', proc do |int|
int.to_s(2).scan('1').size
end),
Strategy.new('continuous_right_shift', proc do |int|
count = 0
until int == 0
count += int & 1
int >>= 1
end
count
end),
Strategy.new('access_bit_fast', proc do |int|
int[0] + int[1] + int[2] + int[3] + int[4] +
int[5] + int[6] + int[7] + int[8] + int[9] +
int[10] + int[11] + int[12] + int[13] +
int[14] + int[15] + int[16] + int[17] +
int[18] + int[19] + int[20] + int[21] +
int[22] + int[23] + int[24] + int[25] +
int[26] + int[27] + int[28] + int[29] +
int[30] + int[31] + int[32] + int[33] +
int[34] + int[35] + int[36] + int[37] +
int[38] + int[39] + int[40] + int[41] +
int[42] + int[43] + int[44] + int[45] +
int[46] + int[47] + int[48]
end),
Strategy.new('count_string', proc do |int|
int.to_s(2).count('1')
end),
Strategy.new('progressive_right_shift', proc do |int|
# works only for numbers < 2**128
int -= (int >> 1) & @m1
int = (int & @m2) + ((int >> 2) & @m2)
int = (int + (int >> 4)) & @m4
int = (int + (int >> 8)) & @m8
int = (int + (int >> 16)) & @m16
int += int >> 32
(int + (int >> 64)) & 255
end, proc do
@m1 = 0x55555555555555555555555555555555
@m2 = 0x33333333333333333333333333333333
@m4 = 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
@m8 = 0x00ff00ff00ff00ff00ff00ff00ff00ff
@m16 = 0x0000ffff0000ffff0000ffff0000ffff
end),
Strategy.new('bit_elimination_for', proc do |int|
count = 0
while int != 0
int &= int - 1
count += 1
end
count
end),
Strategy.new('bit_elimination_until', proc do |int|
count = 0
until int == 0
int &= int - 1
count += 1
end
count
end),
Strategy.new('bit_elimination_while', proc do |int|
count = 0
while int > 0
int &= int - 1
count += 1
end
count
end),
Strategy.new('pre_compute_16', proc do |int|
# only works for numbers with 49 bits or less
@pre_compute_16[(int & 0xffff)] +
@pre_compute_16[(int >> 16 & 0xffff)] +
@pre_compute_16[(int >> 32 & 0xffff)] +
@pre_compute_16[(int >> 48)]
end),
Strategy.new('count_bits_pre', proc do |int|
count_bits_pre(int)
end, proc do
require 'count_bits/count_bits_pre' # available at https://github.com/knugie/count_bits
end),
Strategy.new('count_bits_swar', proc do |int|
count_bits_swar(int)
end, proc do
require 'count_bits/count_bits_swar' # available at https://github.com/knugie/count_bits
end),
Strategy.new('count_bits_for', proc do |int|
count_bits_for(int)
end, proc do
require 'count_bits/count_bits_for' # available at https://github.com/knugie/count_bits
end),
Strategy.new('count_bits_gcc', proc do |int|
count_bits_gcc(int)
end, proc do
require 'count_bits/count_bits_gcc' # available at https://github.com/knugie/count_bits
end)
]
puts "CPU : #{cpu_name}"
puts "MEM : #{mem_size}"
puts "RUBY : #{ruby_version}"
puts "PLATFORM : #{platform}\n"
puts '"NORM":'
print ' TEST... '
if test(strategies, sample_norm(2_000))
puts 'OK'
puts " BENCHMARK (#{@count}):"
print ' PREPARE... '
sample = sample_norm
puts 'OK'
puts ' RUN...'
benchmark(strategies, sample)
puts "\n\"NORM\" FINISHED\n"
end
print "\n" + '"LOTTO":' + "\n"
print ' TEST... '
if test(strategies, sample_lotto(2_000))
puts 'OK'
puts " BENCHMARK (#{@count}):"
print ' PREPARE... '
sample = sample_lotto
puts 'OK'
puts ' RUN...'
benchmark(strategies, sample)
puts "\n\"LOTTO\" FINISHED\n"
end
puts "\nDONE"
# $ ./bit_count_benchmark.rb
# CPU : Intel(R) Core(TM) i5-5287U CPU @ 2.90GHz
# MEM : 17179869184
# RUBY : ruby-2.3.0
# PLATFORM : x86_64-darwin15
#
# "NORM":
# TEST... OK
# BENCHMARK (2000000):
# PREPARE... OK
# RUN...
# user system total real
# scan_regex 17.670000 0.020000 17.690000 ( 17.721376)
# scan_string 14.550000 0.010000 14.560000 ( 14.568586)
# continuous_right_shift 5.880000 0.010000 5.890000 ( 5.898474)
# access_bit_fast 2.660000 0.000000 2.660000 ( 2.659211)
# count_string 2.480000 0.000000 2.480000 ( 2.486868)
# progressive_right_shift 1.560000 0.010000 1.570000 ( 1.567323)
# bit_elimination_for 2.560000 0.000000 2.560000 ( 2.572606)
# bit_elimination_until 2.510000 0.000000 2.510000 ( 2.509089)
# bit_elimination_while 2.380000 0.000000 2.380000 ( 2.386093)
# pre_compute_16 0.630000 0.010000 0.640000 ( 0.639559)
# count_bits_pre 0.490000 0.000000 0.490000 ( 0.488323)
# count_bits_swar 0.280000 0.000000 0.280000 ( 0.291042)
# count_bits_for 0.330000 0.000000 0.330000 ( 0.328376)
# count_bits_gcc 0.300000 0.000000 0.300000 ( 0.303232)
#
# "NORM" FINISHED
#
#
# "LOTTO":
# TEST... OK
# BENCHMARK (2000000):
# PREPARE... OK
# RUN...
# user system total real
# scan_regex 7.920000 0.010000 7.930000 ( 7.938885)
# scan_string 6.690000 0.010000 6.700000 ( 6.701425)
# continuous_right_shift 5.250000 0.000000 5.250000 ( 5.259603)
# access_bit_fast 2.700000 0.010000 2.710000 ( 2.698250)
# count_string 2.320000 0.000000 2.320000 ( 2.328138)
# progressive_right_shift 1.600000 0.000000 1.600000 ( 1.606361)
# bit_elimination_for 0.880000 0.000000 0.880000 ( 0.889635)
# bit_elimination_until 0.860000 0.010000 0.870000 ( 0.863004)
# bit_elimination_while 0.830000 0.000000 0.830000 ( 0.827884)
# pre_compute_16 0.600000 0.000000 0.600000 ( 0.604132)
# count_bits_pre 0.310000 0.000000 0.310000 ( 0.318315)
# count_bits_swar 0.290000 0.000000 0.290000 ( 0.290661)
# count_bits_for 0.280000 0.000000 0.280000 ( 0.285280)
# count_bits_gcc 0.290000 0.000000 0.290000 ( 0.299003)
#
# "LOTTO" FINISHED
#
#
# DONE
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment