javier-m
7/11/2017 - 6:52 PM

Simple benchmark of BingInteger vs BitSet

Simple benchmark of BingInteger vs BitSet


import java.math.BigInteger
import java.util.*
import kotlin.system.measureNanoTime

val ANSI_RESET = "\u001B[0m"
val ANSI_BLACK = "\u001B[30m"
val ANSI_RED = "\u001B[31m"
val ANSI_GREEN = "\u001B[32m"
val ANSI_YELLOW = "\u001B[33m"
val ANSI_BLUE = "\u001B[34m"
val ANSI_PURPLE = "\u001B[35m"
val ANSI_CYAN = "\u001B[36m"
val ANSI_WHITE = "\u001B[37m"

fun createBitSet(bi: BigInteger): BitSet {
	val bia = bi.toByteArray()
	val l = bia.size
	val bsa = ByteArray(l + 1)
	System.arraycopy(bia, 0, bsa, 0, l)
	bsa[l] = 0x01
	return BitSet.valueOf(bsa)
}

fun main(args: Array<String>){
	println("Benchmarking BigInteger vs BitSet!")
	val timesExec = 1_000_000
	var random = Random(100)

	////////////////EMPTY INITIALIZATION////////////////
	println("$ANSI_GREEN------------------------------EMPTY INITIALIZATION------------------------------$ANSI_RESET")
	runTimedExecution {
		label = "bitset initialization"
		times = timesExec
		action = {
			var bitSet = BitSet(64)
		}
	}

	runTimedExecution {
		label = "bigint initialization"
		times = timesExec
		action = {
			var bigInt = BigInteger.ZERO
		}
	}

	////////////////INITIALIZATION////////////////
	println("$ANSI_GREEN------------------------------INITIALIZATION------------------------------$ANSI_RESET")
	runTimedExecution {
		label = "bitset initialization"
		times = timesExec
		action = {
			var bitSet = createBitSet(BigInteger("981398134987198"))
		}
	}

	runTimedExecution {
		label = "bigint initialization"
		times = timesExec
		action = {
			var bigInt = BigInteger("981398134987198")
		}
	}

	////////////////SET BIT////////////////
	println("$ANSI_GREEN------------------------------SET BIT------------------------------$ANSI_RESET")
	random = Random(100)
	runTimedExecution {
		label = "bitset set"
		times = timesExec
		action = {
			var bitSet = createBitSet(BigInteger("981398134987198"))
			for (i in 1..100) {
				bitSet.set(random.nextInt(64))
			}
		}
	}

	random = Random(100)
	runTimedExecution {
		label = "bigint set"
		times = timesExec
		action = {
			var bigInt = BigInteger("981398134987198")

			for (i in 1..100) {
				bigInt = bigInt.setBit(random.nextInt(64))
			}
		}
	}

	////////////////GET BIT////////////////
	println("$ANSI_GREEN------------------------------GET BIT------------------------------$ANSI_RESET")
	random = Random(101)
	runTimedExecution {
		label = "bitset get"
		times = timesExec
		action = {
			var bitSet = createBitSet(BigInteger("981398134987198"))
			for (i in 1..100) {
				bitSet.get(random.nextInt(64))
			}
		}
	}

	random = Random(101)
	runTimedExecution {
		label = "bigint get"
		times = timesExec
		action = {
			var bigInt = BigInteger("981398134987198")
			for (i in 1..100) {
				bigInt.testBit(random.nextInt(64))
			}
		}
	}

	////////////////SET & GET BIT////////////////
	println("$ANSI_GREEN------------------------------SET & GET BIT------------------------------$ANSI_RESET")
	random = Random(102)
	runTimedExecution {
		label = "bitset set & get"
		times = timesExec
		action = {
			var bitSet = createBitSet(BigInteger("981398134987198"))
			for (i in 1..100) {
				bitSet.set(random.nextInt(64))
				bitSet.set(random.nextInt(64), false)
				bitSet.get(random.nextInt(64))
			}
		}
	}

	random = Random(102)
	runTimedExecution {
		label = "bigint set & get"
		times = timesExec
		action = {
			var bigInt = BigInteger("981398134987198")
			for (i in 1..100) {
				bigInt = bigInt.setBit(random.nextInt(64))
				bigInt = bigInt.clearBit(random.nextInt(64))
				bigInt.testBit(random.nextInt(64))
			}
		}
	}
}

fun runTimedExecution(executionDeclaration: Execution.() -> Unit) {

	val execution = Execution()
	execution.executionDeclaration()

	println("--------------------START--------------------")
	println(">> timing execution [${execution.label}]")

	var maxTime = Long.MIN_VALUE
	var minTime = Long.MAX_VALUE
	var avgTime = 0.0
	val times = mutableListOf<Long>()

	println(">> executing ${execution.times} times")
	for (i in 1..execution.times) {
		val time = measureNanoTime {
			if (execution.action != null) {
				execution.action?.invoke()
			}
		}

		times.add(time)
		maxTime = Math.max(maxTime, time)
		minTime = Math.min(minTime, time)
		avgTime += time
	}

	avgTime /= execution.times.toDouble()

	println(">> time in nanoseconds")
	println(">> min time: $minTime")
	println(">> max time: $maxTime")
	println(">> median time: $ANSI_BLUE ${times[times.size / 2]} $ANSI_RESET")
	println(">> avg time: $avgTime")
	println("---------------------END---------------------")
}

class Execution {
	var label: String = "_"

	var times: Int = 1
		get() { return field}
		set(value) {
			if (value <= 0)
				throw Exception()
			field = value
		}

	var action: (() -> Unit)? = null
}