Skip to content

Instantly share code, notes, and snippets.

@whym

whym/bits.scala

Last active Apr 24, 2017
Embed
What would you like to do?
benchmark Java/Scala BigInt/BitSet implementations

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
// 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 }))
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.