Skip to content

Instantly share code, notes, and snippets.

@tsuna
Created February 9, 2012 18:56
Show Gist options
  • Save tsuna/1782008 to your computer and use it in GitHub Desktop.
Save tsuna/1782008 to your computer and use it in GitHub Desktop.
Java integer hash set micro-benchmark
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import com.stumbleupon.mr.HashIntSet; // OpenJDK's HashSet hacked to use built-in `int'
import gnu.trove.set.hash.TIntHashSet;
import com.google.caliper.Param;
import com.google.caliper.SimpleBenchmark;
final class setbench {
public static class HashSetBench extends SimpleBenchmark {
private HashSet<Integer> hs;
@Param int size;
@Override protected void setUp() {
hs = new HashSet<Integer>(size);
for (int i = 0; i < size; i++) {
hs.add(i);
}
}
public int timeContains(final int n) {
int dummy = 0;
for (int i = 0; i < n; i++) {
if (hs.contains(i)) {
dummy++;
}
}
return dummy;
}
}
public static class HashIntSetBench extends SimpleBenchmark {
private HashIntSet hs;
@Param int size;
@Override protected void setUp() {
hs = new HashIntSet(size);
for (int i = 0; i < size; i++) {
hs.add(i);
}
}
public int timeContains(final int n) {
int dummy = 0;
for (int i = 0; i < n; i++) {
if (hs.contains(i)) {
dummy++;
}
}
return dummy;
}
}
public static class TIntHashSetBench extends SimpleBenchmark {
private TIntHashSet hs;
@Param int size;
@Override protected void setUp() {
hs = new TIntHashSet(size);
for (int i = 0; i < size; i++) {
hs.add(i);
}
}
public int timeContains(final int n) {
int dummy = 0;
for (int i = 0; i < n; i++) {
if (hs.contains(i)) {
dummy++;
}
}
return dummy;
}
}
}
@tsuna
Copy link
Author

tsuna commented Feb 9, 2012

contains() speed

HashSet<Integer>

 size   ns linear runtime
  100 10.2 ============================
 1000 10.7 =============================
10000 11.0 ==============================

HashIntSet

 size   ns linear runtime
  100 5.19 ============================
 1000 5.26 ============================
10000 5.52 ==============================

TIntHashSet

 size   ns linear runtime
  100 11.2 ======================
 1000 15.0 ==============================
10000 11.3 ======================

Memory footprint

  • HashSet: 48 bytes per item (32 bytes for HashMap$Entry + 16 bytes for Integer)
  • HashIntSet: 24 bytes per HashIntMap$Entry
  • TIntHashSet: 5 bytes per entry (one int in an array and one byte in another array).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment