Skip to content

Instantly share code, notes, and snippets.

@leventov

leventov/BoundedSetContains.java

Created September 29, 2013 05:49
Show Gist options
  • Save leventov/6749728 to your computer and use it in GitHub Desktop.
Save leventov/6749728 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BoundedSetContains.java
package tests;
import org.openjdk.jmh.annotations.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
@BenchmarkMode(Mode.AverageTime)
@Measurement(time = 100, timeUnit = TimeUnit.MILLISECONDS)
public class BoundedSetContains {
public static final int UPPER_VALUE_BOUND = 1 << 14;
@State
public static class BooleanArrayState_05_load {
boolean[] used = new boolean[UPPER_VALUE_BOUND];
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
Arrays.fill(used, false);
toUse = new int[ixSet.cardinality()];
int j = 0;
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
used[i] = true;
toUse[j++] = i;
}
nextIndex = 0;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_booleanArray_05_load(BooleanArrayState_05_load st) {
boolean[] used = st.used;
for (int i = st.nextIndex; i < UPPER_VALUE_BOUND; i++) {
if (!used[i]) {
st.nextIndex = i + 1;
return i;
}
}
st.nextIndex = 0;
return -1;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_booleanArray_05_load(BooleanArrayState_05_load st) {
boolean[] used = st.used;
int sum = 0;
for (int i : st.toUse) {
used[i] = true;
sum += i;
}
return sum;
}
@State
public static class BooleanArrayState_099_load {
boolean[] used = new boolean[UPPER_VALUE_BOUND];
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
byte[] bits2 = new byte[UPPER_VALUE_BOUND / 8];
while (ixSet.cardinality() < UPPER_VALUE_BOUND * 0.99) {
random.nextBytes(bits2);
ixSet.or(BitSet.valueOf(bits2));
}
Arrays.fill(used, false);
toUse = new int[ixSet.cardinality()];
int j = 0;
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
used[i] = true;
toUse[j++] = i;
}
nextIndex = 0;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_booleanArray_099_load(BooleanArrayState_099_load st) {
boolean[] used = st.used;
for (int i = st.nextIndex; i < UPPER_VALUE_BOUND; i++) {
if (!used[i]) {
st.nextIndex = i + 1;
return i;
}
}
st.nextIndex = 0;
return -1;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_booleanArray_099_load(BooleanArrayState_099_load st) {
boolean[] used = st.used;
int sum = 0;
for (int i : st.toUse) {
used[i] = true;
sum += i;
}
return sum;
}
@State
public static class BitSetState_05_load {
BitSet used;
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
used = BitSet.valueOf(ixBits);
nextIndex = 0;
toUse = new int[used.cardinality()];
int j = 0;
for (int i = used.nextSetBit(0); i >= 0; i = used.nextSetBit(i + 1)) {
toUse[j++] = i;
}
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_bitSet_05_load(BitSetState_05_load st) {
int i = st.used.nextClearBit(st.nextIndex);
st.nextIndex = i + 1;
return i;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_bitSet_05_load(BitSetState_05_load st) {
BitSet used = st.used;
int sum = 0;
for (int i : st.toUse) {
used.set(i);
sum += i;
}
return sum;
}
@State
public static class BitSetState_099_load {
BitSet used;
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
used = BitSet.valueOf(ixBits);
byte[] bits2 = new byte[UPPER_VALUE_BOUND / 8];
while (used.cardinality() < UPPER_VALUE_BOUND * 0.99) {
random.nextBytes(bits2);
used.or(BitSet.valueOf(bits2));
}
nextIndex = 0;
toUse = new int[used.cardinality()];
int j = 0;
for (int i = used.nextSetBit(0); i >= 0; i = used.nextSetBit(i + 1)) {
toUse[j++] = i;
}
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_bitSet_099_load(BitSetState_099_load st) {
int i = st.used.nextClearBit(st.nextIndex);
st.nextIndex = i + 1;
return i;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_bitSet_099_load(BitSetState_099_load st) {
BitSet used = st.used;
int sum = 0;
for (int i : st.toUse) {
used.set(i);
sum += i;
}
return sum;
}
@State
public static class HashSetState_05_load {
HashSet<Integer> used = new HashSet<>();
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
used.clear();
toUse = new int[ixSet.cardinality()];
int j = 0;
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
used.add(i);
toUse[j++] = i;
}
nextIndex = 0;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_hashSet_05_load(HashSetState_05_load st) {
HashSet<Integer> used = st.used;
for (int i = st.nextIndex; i < UPPER_VALUE_BOUND; i++) {
if (!used.contains(i)) {
st.nextIndex = i + 1;
return i;
}
}
st.nextIndex = 0;
return -1;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_hashSet_05_load(HashSetState_05_load st) {
HashSet<Integer> used = st.used;
used.clear();
int sum = 0;
for (int i : st.toUse) {
used.add(i);
sum += i;
}
return sum;
}
@State
public static class HashSetState_099_load {
HashSet<Integer> used = new HashSet<>();
int[] toUse;
int nextIndex;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
used.clear();
while (used.size() < UPPER_VALUE_BOUND * 0.99) {
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
used.add(i);
}
}
toUse = new int[used.size()];
int j = 0;
for (int i : used) {
toUse[j++] = i;
}
nextIndex = 0;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_hashSet_099_load(HashSetState_099_load st) {
HashSet<Integer> used = st.used;
for (int i = st.nextIndex; i < UPPER_VALUE_BOUND; i++) {
if (!used.contains(i)) {
st.nextIndex = i + 1;
return i;
}
}
st.nextIndex = 0;
return -1;
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_hashSet_099_load(HashSetState_099_load st) {
HashSet<Integer> used = st.used;
used.clear();
int sum = 0;
for (int i : st.toUse) {
used.add(i);
sum += i;
}
return sum;
}
@State
public static class ComplementHashSetState_05_load {
HashSet<Integer> free = new HashSet<>();
int[] toUse;
Iterator<Integer> it;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
for (int i = 0; i < UPPER_VALUE_BOUND; i++) {
free.add(i);
}
toUse = new int[ixSet.cardinality()];
int j = 0;
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
free.remove(i);
toUse[j++] = i;
}
it = free.iterator();
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_complementHashSet_05_load(ComplementHashSetState_05_load st) {
Iterator<Integer> it = st.it;
if (it.hasNext()) {
return it.next();
} else {
st.it = st.free.iterator();
return -1;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_complementHashSet_05_load(ComplementHashSetState_05_load st) {
HashSet<Integer> free = st.free;
for (int i = 0; i < UPPER_VALUE_BOUND; i++) {
free.add(i);
}
int sum = 0;
for (int i : st.toUse) {
free.remove(i);
sum += i;
}
return sum;
}
@State
public static class ComplementHashSetState_099_load {
HashSet<Integer> free = new HashSet<>();
int[] toUse;
Iterator<Integer> it;
@Setup(Level.Iteration)
public void setup() {
byte[] ixBits = new byte[UPPER_VALUE_BOUND / 8];
Random random = ThreadLocalRandom.current();
for (int i = 0; i < UPPER_VALUE_BOUND; i++) {
free.add(i);
}
while (free.size() > UPPER_VALUE_BOUND * 0.01) {
random.nextBytes(ixBits);
BitSet ixSet = BitSet.valueOf(ixBits);
for (int i = ixSet.nextSetBit(0); i >= 0; i = ixSet.nextSetBit(i + 1)) {
free.remove(i);
}
}
toUse = new int[UPPER_VALUE_BOUND - free.size()];
int j = 0;
for (int i = 0; i < UPPER_VALUE_BOUND; i++) {
if (!free.contains(i)) {
toUse[j++] = i;
}
}
it = free.iterator();
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public int nextIndex_complementHashSet_099_load(ComplementHashSetState_099_load st) {
Iterator<Integer> it = st.it;
if (it.hasNext()) {
return it.next();
} else {
st.it = st.free.iterator();
return -1;
}
}
@GenerateMicroBenchmark
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public int construction_complementHashSet_099_load(ComplementHashSetState_099_load st) {
HashSet<Integer> free = st.free;
for (int i = 0; i < UPPER_VALUE_BOUND; i++) {
free.add(i);
}
int sum = 0;
for (int i : st.toUse) {
free.remove(i);
sum += i;
}
return sum;
}
}
Raw
pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>tests</groupId>
<artifactId>tests</artifactId>
<version>1.0-SNAPSHOT</version>
<dependencies>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-core</artifactId>
<version>1.0-SNAPSHOT</version>
</dependency>
</dependencies>
<build>
<sourceDirectory>${basedir}/src</sourceDirectory>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.1</version>
<configuration>
<source>1.7</source>
<target>1.7</target>
</configuration>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-shade-plugin</artifactId>
<version>2.0</version>
<executions>
<execution>
<phase>package</phase>
<goals>
<goal>shade</goal>
</goals>
<configuration>
<finalName>microbenchmarks</finalName>
<transformers>
<transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
<mainClass>org.openjdk.jmh.Main</mainClass>
</transformer>
</transformers>
</configuration>
</execution>
</executions>
</plugin>
</plugins>
</build>
</project>
Raw
results.txt
Benchmark Mode Thr Cnt Sec Mean Mean error Units
t.BoundedSetContains.construction_bitSet_05_load avgt 1 20 0 19,184 0,131 usec/op
t.BoundedSetContains.construction_bitSet_099_load avgt 1 20 0 38,319 0,051 usec/op
t.BoundedSetContains.construction_booleanArray_05_load avgt 1 20 0 7,987 0,037 usec/op
t.BoundedSetContains.construction_booleanArray_099_load avgt 1 20 0 16,255 0,031 usec/op
t.BoundedSetContains.construction_complementHashSet_05_load avgt 1 20 0 859,151 10,195 usec/op
t.BoundedSetContains.construction_complementHashSet_099_load avgt 1 20 0 923,588 8,455 usec/op
t.BoundedSetContains.construction_hashSet_05_load avgt 1 20 0 262,920 2,512 usec/op
t.BoundedSetContains.construction_hashSet_099_load avgt 1 20 0 441,306 7,461 usec/op
t.BoundedSetContains.nextIndex_bitSet_05_load avgt 1 20 0 2,086 0,016 nsec/op
t.BoundedSetContains.nextIndex_bitSet_099_load avgt 1 20 0 2,147 0,026 nsec/op
t.BoundedSetContains.nextIndex_booleanArray_05_load avgt 1 20 0 9,264 0,037 nsec/op
t.BoundedSetContains.nextIndex_booleanArray_099_load avgt 1 20 0 65,424 3,507 nsec/op
t.BoundedSetContains.nextIndex_complementHashSet_05_load avgt 1 20 0 27,298 0,145 nsec/op
t.BoundedSetContains.nextIndex_complementHashSet_099_load avgt 1 20 0 142,565 5,737 nsec/op
t.BoundedSetContains.nextIndex_hashSet_05_load avgt 1 20 0 27,159 0,594 nsec/op
t.BoundedSetContains.nextIndex_hashSet_099_load avgt 1 20 0 1948,120 120,741 nsec/op
Raw
tests.iml
<?xml version="1.0" encoding="UTF-8"?>
<module org.jetbrains.idea.maven.project.MavenProjectsManager.isMavenModule="true" type="JAVA_MODULE" version="4">
<component name="NewModuleRootManager" LANGUAGE_LEVEL="JDK_1_7" inherit-compiler-output="false">
<output url="file://$MODULE_DIR$/target/classes" />
<output-test url="file://$MODULE_DIR$/target/test-classes" />
<exclude-output />
<content url="file://$MODULE_DIR$">
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
<excludeFolder url="file://$MODULE_DIR$/target" />
</content>
<orderEntry type="inheritedJdk" />
<orderEntry type="sourceFolder" forTests="false" />
<orderEntry type="library" name="Maven: org.openjdk.jmh:jmh-core:1.0-SNAPSHOT" level="project" />
<orderEntry type="library" name="Maven: args4j:args4j:2.0.16" level="project" />
</component>
</module>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment