benchmark Java/Scala BigInt/BitSet implementations

readme.md

scala bits.scala mutable-scala bitset-java > sample-output.txt

will produce something like

pos
mutable-scala 69
bitset-java 102
lsb
mutable-scala 32
bitset-java 41
car
mutable-scala 18
bitset-java 19
emp
mutable-scala 18
bitset-java 20

bits.scala

// benchmark Java/Scala BigInt/BitSet implementations

import scala.util.Random
import scala.collection.mutable
import scala.collection.immutable
import java.util.BitSet
import java.math.BigInteger

// derived from https://github.com/alexmasselot/benchmark-bitarray/blob/master/src/benchmark/bitarray/TimeIt.scala
def timeInMilli(n: Int, f: () => Unit) = {
  //warm up
  var i = 0;
  while (i < 100) {
    f();
    i+=1
  }
  
  
  val t0 = System.currentTimeMillis()
  i = 0;
  while (i < n) {
    f();
    i+=1
  }
  val t1 = System.currentTimeMillis()
  ( 1000*(t1 - t0) / n)
}


val m = 1000
val nbits = 10000
val maxBit = 100000

val rnd = new Random()


trait MyBitSet {
  def get: Int => Boolean
  def car: () => Int
  def lsb: () => Int
  def emp: () => Boolean
}

def bs2my(s: scala.collection.BitSet): MyBitSet = {
  new MyBitSet() {
    def get = (x => s(x))
    def car = (() => s.size)
    def lsb = (() => s.head)
    def emp = (() => s.isEmpty)
  }
}
def bi2my(s: BigInt): MyBitSet = {
  new MyBitSet() {
    def get = (x => s.testBit(x))
    def car = (() => s.bitCount)
    def lsb = (() => s.lowestSetBit)
    def emp = (() => s == 0)
  }
}
def jbs2my(s: BitSet): MyBitSet = {
  new MyBitSet() {
    def get = (x => s.get(x))
    def car = (() => s.cardinality)
    def lsb = (() => s.nextSetBit(0))
    def emp = (() => s.isEmpty)
  }
}
def jbi2my(s: BigInteger): MyBitSet = {
  new MyBitSet() {
    def get = (x => s.testBit(x))
    def car = (() => s.bitCount)
    def lsb = (() => s.getLowestSetBit())
    def emp = (() => s == BigInteger.ZERO)
  }
}

def run(code: String, test: MyBitSet => Unit) {
  val func = code match {
    case "bigint-scala" => {
      () =>
        for (i <- 0 to m) yield {
          val bi = BigInt(0)
          for (j <- 0 until nbits) {
            bi setBit (rnd.nextInt(maxBit))
          }
          bi2my(bi)
        }
    }
    case "mutable-scala" => {
      () =>
        for (i <- 0 to m) yield {
          val bi = mutable.BitSet()
          for (j <- 0 until nbits) {
            bi += (rnd.nextInt(maxBit))
          }
          bs2my(bi)
        }
    }
    case "immutable-scala" => {
      () =>
        for (i <- 0 to m) yield {
          var bi = immutable.BitSet()
          for (j <- 0 until nbits) {
            bi += (rnd.nextInt(maxBit))
          }
          bs2my(bi)
        }
    }
    case "bitset-java" => {
      () => 
        for (i <- 0 to m) yield {
          var bi = new BitSet()
          for (j <- 0 until nbits) {
            bi.set(rnd.nextInt(maxBit))
          }
          jbs2my(bi)
        }
    }
    case "bigint-java" => {
      () => 
        for (i <- 0 to m) yield {
          val bi = BigInteger.valueOf(0)
          for (j <- 0 until nbits) {
            bi setBit rnd.nextInt(maxBit)
          }
          jbi2my(bi)
        }
    }
  }

  val sets = func()
  println(code + " " + timeInMilli(2000, {() => sets.map(test(_)).min}))
}

println("pos")
args.foreach(run(_, {x => x.get(9999) }))
println("lsb")
args.foreach(run(_, {x => x.lsb }))
println("car")
args.foreach(run(_, {x => x.car }))
println("emp")
args.foreach(run(_, {x => x.emp }))