Skip to content

Instantly share code, notes, and snippets.

Embed
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
You can’t perform that action at this time.