examples
Class BitSetBenchmark

java.lang.Object
  com.google.caliper.api.Benchmark
      com.google.caliper.SimpleBenchmark
          examples.BitSetBenchmark

All Implemented Interfaces:

com.google.caliper.Benchmark

public class BitSetBenchmark
extends com.google.caliper.SimpleBenchmark

A simple example of a benchmark for BitSet showing some of the issues with micro-benchmarking.

The following is a discussion of how the benchmarks evolved and what they may (or may not) tell us. This discussion is based on the following set of results:

  0% Scenario{vm=java, benchmark=SetBitSetX64} 233.45ns; σ=0.31ns @ 3 trials
 20% Scenario{vm=java, benchmark=SetMaskX64} 116.62ns; σ=0.09ns @ 3 trials
 40% Scenario{vm=java, benchmark=CharsToBitSet} 748.40ns; σ=23.52ns @ 10 trials
 60% Scenario{vm=java, benchmark=CharsToMask} 198.55ns; σ=9.46ns @ 10 trials
 80% Scenario{vm=java, benchmark=BaselineIteration} 67.85ns; σ=0.44ns @ 3 trials

         benchmark   ns logarithmic runtime
      SetBitSetX64  233 XXXXXXXXX|||||||||||||||
        SetMaskX64  117 XXXX|||||||||||||||||
     CharsToBitSet  748 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
       CharsToMask  199 XXXXXXX||||||||||||||||
 BaselineIteration   68 XX|||||||||||||||||
 

Initially things look simple. The timeSetBitSetX64(int) benchmark takes approximately twice as long as timeSetMaskX64(int). However the inner loops in these benchmarks have almost no content, so a more 'real world' benchmark was devised in an attempt to back up these results.

The timeCharsToMask(int) and timeCharsToBitSet(int) benchmarks convert a simple char[] of '1's and '0's to a corresponding BitSet or bit mask. These also processes 64 bits per iteration and so appears to be doing the same amount of work as the first benchmarks.

Additionally the timeBaselineIteration(int) benchmark attempts to measure the raw cost of looping through and reading the source data.

When comparing the benchmarks that use bit masking, we see that the measured time of the SetMaskX64 benchmark (117ns) is roughly the same as the CharsToMask benchmark (199ns) with the BaselineIteration time (68ms) subtracted from it. This gives us some confidence that both benchmarks are resulting in the same underlying work on the CPU.

However the CharsToBitSet and the SetBitSetX64 benchmarks differ very significantly (approximately 3x) even when accounting for the BaselineIteration result. This suggests that the performance of BitSet.set(int) is quite dependent on the surrounding code and how it is optimized by the JVM.

The conclusions we can draw from this are:

1: Using BitSet is slower than using bit masks directly. At best it seems about 2x slower than a bit mask, but could easily be 5x slower in real applications.

While these are only estimates, we can conclude that when performance is important and where bit set operations occur in tight loops, bit masks should be used in favor of BitSets.

2:Overly simplistic benchmarks can give a very false impression of performance.

Constructor Summary

BitSetBenchmark()

Method Summary

static void	main(String[] args)
protected void	setUp()
long	timeBaselineIteration(int reps) This benchmark attempts to measure the baseline cost of both timeCharsToBitSet(int) and timeCharsToMask(int).
String	timeCharsToBitSet(int reps) This benchmark parses a char[] of 1's and 0's into a BitSet.
long	timeCharsToMask(int reps) This benchmark parses a char[] of 1's and 0's into a bit mask.
int	timeSetBitSetX64(int reps) This benchmark attempts to measure performance of BitSet.set(int).
long	timeSetMaskX64(int reps) This benchmark attempts to measure performance of direct bit-manipulation.

Methods inherited from class com.google.caliper.SimpleBenchmark

bytesToUnits, createBenchmark, getInstanceUnitNames, getMemoryUnitNames, getTimeUnitNames, instancesToUnits, nanosToUnits, normalizeScenario, parameterNames, parameterValues, tearDown

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BitSetBenchmark

public BitSetBenchmark()

Method Detail

setUp

protected void setUp()
              throws Exception

Overrides:

setUp in class com.google.caliper.SimpleBenchmark

Throws:

Exception

timeSetBitSetX64

public int timeSetBitSetX64(int reps)

This benchmark attempts to measure performance of BitSet.set(int).

timeSetMaskX64

public long timeSetMaskX64(int reps)

This benchmark attempts to measure performance of direct bit-manipulation.

timeCharsToBitSet

public String timeCharsToBitSet(int reps)

This benchmark parses a char[] of 1's and 0's into a BitSet. Results from this benchmark should be comparable with those from timeCharsToMask(int).

timeCharsToMask

public long timeCharsToMask(int reps)

This benchmark parses a char[] of 1's and 0's into a bit mask. Results from this benchmark should be comparable with those from timeCharsToBitSet(int).

timeBaselineIteration

public long timeBaselineIteration(int reps)

This benchmark attempts to measure the baseline cost of both timeCharsToBitSet(int) and timeCharsToMask(int). It does this by unconditionally summing the character values of the char[]. This is as close to a no-op case as we can expect to get without unwanted over-optimization.

main

public static void main(String[] args)
                 throws Exception

Throws:

Exception