Benchmarking BitArray implementation using integer arrays vs Bignum based implementation

bit-array-access.txt

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

bit-array-initialize.txt

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

bit-array-set.txt

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

bitarray-benchmark.rb

# 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