Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Benchmarking BitArray implementation using integer arrays vs Bignum based implementation
Max = 100
**************
Warming up --------------------------------------
bitarray gem 189.696k i/100ms
using Bignum 219.494k i/100ms
Calculating -------------------------------------
bitarray gem 6.614M (± 5.0%) i/s - 33.007M in 5.003185s
using Bignum 12.429M (± 7.5%) i/s - 61.897M in 5.015700s
Comparison:
using Bignum: 12428957.2 i/s
bitarray gem: 6614281.1 i/s - 1.88x slower
Max = 1000
**************
Warming up --------------------------------------
bitarray gem 182.312k i/100ms
using Bignum 215.577k i/100ms
Calculating -------------------------------------
bitarray gem 6.555M (± 5.2%) i/s - 32.816M in 5.019837s
using Bignum 12.405M (± 7.0%) i/s - 61.871M in 5.014018s
Comparison:
using Bignum: 12405396.7 i/s
bitarray gem: 6555332.7 i/s - 1.89x slower
Max = 10000
**************
Warming up --------------------------------------
bitarray gem 187.553k i/100ms
using Bignum 224.518k i/100ms
Calculating -------------------------------------
bitarray gem 6.580M (± 5.5%) i/s - 32.822M in 5.004306s
using Bignum 12.419M (± 6.5%) i/s - 61.967M in 5.011550s
Comparison:
using Bignum: 12418745.1 i/s
bitarray gem: 6579692.8 i/s - 1.89x slower
Max = 100000
**************
Warming up --------------------------------------
bitarray gem 188.830k i/100ms
using Bignum 222.503k i/100ms
Calculating -------------------------------------
bitarray gem 6.431M (± 8.1%) i/s - 31.912M in 5.008556s
using Bignum 12.316M (± 6.5%) i/s - 61.411M in 5.008566s
Comparison:
using Bignum: 12316335.9 i/s
bitarray gem: 6431070.9 i/s - 1.92x slower
Max = 1000000
**************
Warming up --------------------------------------
bitarray gem 185.870k i/100ms
using Bignum 225.841k i/100ms
Calculating -------------------------------------
bitarray gem 6.566M (± 5.2%) i/s - 32.899M in 5.024332s
using Bignum 11.940M (± 6.3%) i/s - 59.622M in 5.014487s
Comparison:
using Bignum: 11939524.6 i/s
bitarray gem: 6565999.6 i/s - 1.82x slower
Max = 10000000
**************
Warming up --------------------------------------
bitarray gem 190.013k i/100ms
using Bignum 220.771k i/100ms
Calculating -------------------------------------
bitarray gem 6.399M (± 7.0%) i/s - 31.922M in 5.016081s
using Bignum 12.462M (± 6.0%) i/s - 62.257M in 5.014783s
Comparison:
using Bignum: 12461959.2 i/s
bitarray gem: 6399414.3 i/s - 1.95x slower
Max = 100
**************
Warming up --------------------------------------
bitarray gem 91.716k i/100ms
using Bignum 177.160k i/100ms
Calculating -------------------------------------
bitarray gem 1.530M (± 4.5%) i/s - 7.704M in 5.045728s
using Bignum 5.185M (± 8.4%) i/s - 25.865M in 5.032592s
Comparison:
using Bignum: 5185206.8 i/s
bitarray gem: 1530082.1 i/s - 3.39x slower
Max = 1000
**************
Warming up --------------------------------------
bitarray gem 83.649k i/100ms
using Bignum 171.522k i/100ms
Calculating -------------------------------------
bitarray gem 1.464M (± 8.6%) i/s - 7.277M in 5.016799s
using Bignum 5.308M (± 7.7%) i/s - 26.414M in 5.013903s
Comparison:
using Bignum: 5307930.8 i/s
bitarray gem: 1463939.2 i/s - 3.63x slower
Max = 10000
**************
Warming up --------------------------------------
bitarray gem 67.756k i/100ms
using Bignum 179.229k i/100ms
Calculating -------------------------------------
bitarray gem 946.053k (±11.9%) i/s - 4.675M in 5.012148s
using Bignum 5.398M (± 5.1%) i/s - 27.064M in 5.027168s
Comparison:
using Bignum: 5398210.7 i/s
bitarray gem: 946053.3 i/s - 5.71x slower
Max = 100000
**************
Warming up --------------------------------------
bitarray gem 11.848k i/100ms
using Bignum 179.628k i/100ms
Calculating -------------------------------------
bitarray gem 134.256k (±15.9%) i/s - 663.488k in 5.065455s
using Bignum 5.389M (± 8.0%) i/s - 26.765M in 5.011191s
Comparison:
using Bignum: 5389267.9 i/s
bitarray gem: 134256.2 i/s - 40.14x slower
Max = 1000000
**************
Warming up --------------------------------------
bitarray gem 827.000 i/100ms
using Bignum 181.857k i/100ms
Calculating -------------------------------------
bitarray gem 8.213k (± 3.5%) i/s - 41.350k in 5.041071s
using Bignum 5.390M (± 5.0%) i/s - 26.915M in 5.006523s
Comparison:
using Bignum: 5390114.4 i/s
bitarray gem: 8212.9 i/s - 656.30x slower
Max = 10000000
**************
Warming up --------------------------------------
bitarray gem 126.000 i/100ms
using Bignum 178.121k i/100ms
Calculating -------------------------------------
bitarray gem 1.186k (± 1.9%) i/s - 6.048k in 5.101808s
using Bignum 5.300M (± 8.2%) i/s - 26.362M in 5.017568s
Comparison:
using Bignum: 5300101.8 i/s
bitarray gem: 1185.9 i/s - 4469.39x slower
Max = 100
**************
Warming up --------------------------------------
bitarray gem 177.896k i/100ms
using Bignum 143.451k i/100ms
Calculating -------------------------------------
bitarray gem 5.214M (± 6.6%) i/s - 25.973M in 5.008476s
using Bignum 3.522M (± 6.0%) i/s - 17.644M in 5.031521s
Comparison:
bitarray gem: 5214318.0 i/s
using Bignum: 3522478.9 i/s - 1.48x slower
Max = 1000
**************
Warming up --------------------------------------
bitarray gem 171.756k i/100ms
using Bignum 72.936k i/100ms
Calculating -------------------------------------
bitarray gem 5.326M (± 4.7%) i/s - 26.622M in 5.009369s
using Bignum 1.100M (± 4.5%) i/s - 5.543M in 5.051852s
Comparison:
bitarray gem: 5326400.4 i/s
using Bignum: 1099525.0 i/s - 4.84x slower
Max = 10000
**************
Warming up --------------------------------------
bitarray gem 175.346k i/100ms
using Bignum 57.059k i/100ms
Calculating -------------------------------------
bitarray gem 5.304M (± 5.9%) i/s - 26.477M in 5.012195s
using Bignum 741.557k (±11.3%) i/s - 3.709M in 5.069058s
Comparison:
bitarray gem: 5304478.4 i/s
using Bignum: 741557.0 i/s - 7.15x slower
Max = 100000
**************
Warming up --------------------------------------
bitarray gem 177.651k i/100ms
using Bignum 11.043k i/100ms
Calculating -------------------------------------
bitarray gem 5.314M (± 4.9%) i/s - 26.648M in 5.026753s
using Bignum 173.598k (±25.9%) i/s - 817.182k in 5.006781s
Comparison:
bitarray gem: 5314062.3 i/s
using Bignum: 173597.6 i/s - 30.61x slower
Max = 1000000
**************
Warming up --------------------------------------
bitarray gem 170.910k i/100ms
using Bignum 1.407k i/100ms
Calculating -------------------------------------
bitarray gem 5.355M (± 5.1%) i/s - 26.833M in 5.024713s
using Bignum 15.518k (±25.8%) i/s - 74.571k in 5.064628s
Comparison:
bitarray gem: 5355305.6 i/s
using Bignum: 15518.5 i/s - 345.09x slower
Max = 10000000
**************
Warming up --------------------------------------
bitarray gem 174.442k i/100ms
using Bignum 89.000 i/100ms
Calculating -------------------------------------
bitarray gem 5.006M (±14.9%) i/s - 24.247M in 5.036192s
using Bignum 836.945 (±11.8%) i/s - 4.183k in 5.096637s
Comparison:
bitarray gem: 5006204.4 i/s
using Bignum: 836.9 i/s - 5981.52x slower
# Benchmarking BitArray implementations
# The bitarray gem is based on integer arrays.
# My version `V1::BitArray` (included below) uses Bignum to represent the bit array.
# I benchmarked 3 cases - setting a bit, accessing a bit, and init'ing the bit array.
# The benchmarks show that the gem implementation is better (no surprises there!)
# when it comes to setting bits. The Bignum version is faster by around 1.9X
# for accessing bits, but performance for setting bits degrades exponentially,
# so it's practically useless there.
# Bit array initialization is faster for the Bignum version, but setting bits is
# something you do vastly more often, so it rarely matters. If you're initializing
# such big bit arrays, you probably shouldn't be using Ruby.
require 'bitarray'
require 'benchmark/ips'
module V1
class BitArray
def initialize
@mask = 0
end
def []=(position, value)
if value == 0
@mask ^= (1 << position)
else
@mask |= (1 << position)
end
end
def [](position)
@mask[position]
end
end
end
[100, 1000, 10_000, 100_000, 1_000_000, 10_000_000].each do |x|
puts "\n"
puts "Max = #{x}"
puts '**************'
puts "\n"
max = x
index = x - 5
Benchmark.ips do |x|
x.report('bitarray gem') do |times|
i = 0
while i < times
b1 = BitArray.new(max) # gem
# b1[index] = 1
# b1[index]
i += 1
end
end
x.report('using Bignum') do |times|
i = 0
while i < times
b2 = V1::BitArray.new # my implementation
# b2[index] = 1
# b2[index]
i += 1
end
end
x.compare!
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment