bitfield.rb

bitfield.rb

#!/usr/bin/env ruby

# This implementation is adapted from Peter Cooper's - original available here:
# https://github.com/peterc/whatlanguage/blob/master/lib/whatlanguage/bitfield.rb
class ArrayBitField
  attr_reader :size
  attr_accessor :field
  include Enumerable
  
  ELEMENT_WIDTH = 32
  
  def initialize(size)
    @size = size
    @field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)
  end
  
  def []=(position, value)
    value == 1 ? @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH) : @field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)
  end
  
  def [](position)
    @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0
  end
end

class StringBitField
  def initialize(size)
    @size = size
    @data = ("\0" * ((@size / 8) + 1)).force_encoding("ASCII-8BIT")
  end

  def []=(pos, value)
    @data.setbyte(pos / 8, (value == 1 ? (@data.getbyte(pos / 8) | (1 << (pos % 8))) : (@data.getbyte(pos / 8) ^ (1 << (pos % 8)))))
  end

  def [](position)
    @data.getbyte(position / 8) & (1 << (position & 0x7)) == 0 ? 0 : 1
  end
end

class BignumBitField
  def initialize(size)
    @num = 0
  end

  def []=(pos, value)
    value == 1 ? (@num |= (1 << pos)) : (@num ^= (1 << pos))
  end

  def [](pos)
    @num[pos]
  end
end

if __FILE__ == $0
  require 'benchmark'

  Benchmark.bmbm do |bm|
    size = 1_000_000
    array_field = ArrayBitField.new(size)
    string_field = StringBitField.new(size)
    num_field = BignumBitField.new(size)

    bm.report("set bits (array)") do
      100000.times do
        array_field[rand(size)] = 1
      end
    end

    bm.report("set bits (string)") do
      100000.times do
        string_field[rand(size)] = 1
      end
    end

    bm.report("set bits (bignum)") do
      100000.times do
        num_field[rand(size)] = 1
      end
    end

    bm.report("read bits (string)") do
      c = 0
      100000.times do
        c += string_field[rand(size)]
      end
    end

    bm.report("read bits (array)") do
      c = 0
      100000.times do
        c += array_field[rand(size)]
      end
    end

    bm.report("read bits (bignum)") do
      c = 0
      100000.times do
        c += num_field[rand(size)]
      end
    end
  end
end