Don't Fear the Builder
source link: https://richardstartin.github.io/posts/dont-fear-the-builder
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Don't Fear the Builder
Dec 12, 2017 | Richard Startin | javaanalysis
Writing a nontrivial piece of code requires a programmer to make countless tiny decisions, and to produce good quality code quickly, many of these decisions must be made subconciously. But what happens if your instinct is mostly superstitious bullshit? I instinctively avoid allocating objects when I don’t have to, so would not voluntarily resort to using things like EqualsBuilder or HashCodeBuilder from Apache Commons. I feel dismayed whenever I am asked about the relationship between hash code and equals in interviews for contracts. This indicates a lack of mutual respect, but what’s revealing is that enough people passing themselves off as developers don’t know this stuff that it makes the question worth asking. EqualsBuilder and HashCodeBuilder make it so you don’t actually need to know, making it safe to put any object in a HashSet, whoever wrote the class. But should you use these classes just because they protect the naive (and you from the naive)? Is it a runtime tax? Or is any perceived cost magically eradicated by the JVM? It’s time to benchmark my instinct.
Baseline
There are definitely no allocations in the code IntelliJ (or similar) would generate for equals and hashCode automatically. I will use this generated code as the baseline: if I can match or beat this code with EqualsBuilder or HashCodeBuilder respectively, I can dismiss my prejudice. Here’s the baseline class:
public class Baseline {
private final String a;
private final int b;
private final String c;
private final Instant d;
public Baseline(String a, int b, String c, Instant d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Baseline baseline = (Baseline) o;
if (b != baseline.b) return false;
if (!a.equals(baseline.a)) return false;
if (!c.equals(baseline.c)) return false;
return d.equals(baseline.d);
}
@Override
public int hashCode() {
int result = a.hashCode();
result = 31 * result + b;
result = 31 * result + c.hashCode();
result = 31 * result + d.hashCode();
return result;
}
}
It’s not pretty and it’s a real pain to keep generated code up to date when adding and removing fields (you can delete it and regenerate it but it creates merge noise) but there’s no obvious way to improve on this code. It’s correct and looks fast. To benchmark alternatives, I want to look at the effect on set membership queries against a HashSet of various sizes.
Builder Implementation
I will contrast this with the following code using code from Apache Commons (incidentally, also generated by IntelliJ):
public class Builder {
private final String a;
private final int b;
private final String c;
private final Instant d;
public Builder(String a, int b, String c, Instant d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Builder builder = (Builder) o;
return new EqualsBuilder()
.append(b, builder.b)
.append(a, builder.a)
.append(c, builder.c)
.append(d, builder.d)
.isEquals();
}
@Override
public int hashCode() {
return new HashCodeBuilder(17, 37)
.append(a)
.append(b)
.append(c)
.append(d)
.toHashCode();
}
}
This code is a bit neater and easier to maintain, but does it have an observable cost?
HashSet Benchmark
For a parametrised range of HashSet sizes, I measure throughput for calls to contains. This requires that both hashCode and equals are called, the latter potentially several times. There is bias in this benchmark, because the implementation producing the best hash function will minimise the calls to equals, but I am willing to reward the better implementation rather than maniacally isolate any attributable allocation cost.
The code is simple, if a little repetitive. For each implementation, I make some random instances of my class, and make one that I can be sure isn’t in the set. I measure the cost of repeated invocations to the hashCode and equals methods by finding an object, and searching but failing to find an object separately.
@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class HashSetContainsBenchmark {
@Param({"8", "96", "1024", "8192"})
int setSize;
private HashSet<Baseline> baselineSet;
private Baseline presentBaseline;
private Baseline missingBaseline;
private HashSet<Builder> builderSet;
private Builder presentBuilder;
private Builder missingBuilder;
@Setup(Level.Trial)
public void setup() {
setupBaselineState();
setupBuilderState();
}
private void setupBaselineState() {
baselineSet = new HashSet<>();
for (int i = 0; i < setSize; ++i) {
while(!baselineSet.add(newBaselineInstance()));
}
presentBaseline = baselineSet.iterator().next();
do {
missingBaseline = newBaselineInstance();
} while (baselineSet.contains(missingBaseline));
}
private void setupBuilderState() {
builderSet = new HashSet<>();
for (int i = 0; i < setSize; ++i) {
while(!builderSet.add(newBuilderInstance()));
}
presentBuilder = builderSet.iterator().next();
do {
missingBuilder = newBuilderInstance();
} while (builderSet.contains(missingBuilder));
}
@Benchmark
public boolean findPresentBaselineInstance() {
return baselineSet.contains(presentBaseline);
}
@Benchmark
public boolean findMissingBaselineInstance() {
return baselineSet.contains(missingBaseline);
}
@Benchmark
public boolean findPresentBuilderInstance() {
return builderSet.contains(presentBuilder);
}
@Benchmark
public boolean findMissingBuilderInstance() {
return builderSet.contains(missingBuilder);
}
private static Baseline newBaselineInstance() {
ThreadLocalRandom random = ThreadLocalRandom.current();
return new Baseline(UUID.randomUUID().toString(),
random.nextInt(),
UUID.randomUUID().toString(),
Instant.ofEpochMilli(random.nextLong(0, Instant.now().toEpochMilli())));
}
private static Builder newBuilderInstance() {
ThreadLocalRandom random = ThreadLocalRandom.current();
return new Builder(UUID.randomUUID().toString(),
random.nextInt(),
UUID.randomUUID().toString(),
Instant.ofEpochMilli(random.nextLong(0, Instant.now().toEpochMilli())));
}
}
Running this benchmark with org.apache.commons:commons-lang3:3.7 yields the throughput results below. There is an occasional and slight throughput degradation with the builders, but the builder implementation is sometimes faster in this benchmark, but the difference isn’t large enough to worry about.
Where did the builder go?
It’s worth taking a look at the compiler output to find out what happened. Considering the case where the object isn’t found in the set, we can see that the code gets inlined, and the hash code must be quite good. By enabling the args -XX:+PrintCompilation -XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining it’s clear to see that the entire hash code generation gets inlined into the calling loop, and that equals is never executed (suggesting that there are no collisions to resolve here) .
@ 8 java.util.HashSet::contains (9 bytes) inline (hot)
@ 5 java.util.HashMap::containsKey (18 bytes) inline (hot)
\-> TypeProfile (17571/17571 counts) = java/util/HashMap
@ 2 java.util.HashMap::hash (20 bytes) inline (hot)
@ 9 com.openkappa.simd.builder.Builder::hashCode (43 bytes) inline (hot)
@ 8 org.apache.commons.lang3.builder.HashCodeBuilder::<init> (60 bytes) inline (hot)
@ 1 java.lang.Object::<init> (1 bytes) inline (hot)
@ 26 org.apache.commons.lang3.Validate::isTrue (18 bytes) unloaded signature classes
@ 46 org.apache.commons.lang3.Validate::isTrue (18 bytes) unloaded signature classes
@ 15 org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes) inline (hot)
@ 21 java.lang.Object::getClass (0 bytes) (intrinsic)
@ 24 java.lang.Class::isArray (0 bytes) (intrinsic)
@ 49 java.lang.String::hashCode (49 bytes) inline (hot)
@ 19 java.lang.String::isLatin1 (19 bytes) inline (hot)
@ 29 java.lang.StringLatin1::hashCode (42 bytes) inline (hot)
@ 22 org.apache.commons.lang3.builder.HashCodeBuilder::append (17 bytes) inline (hot)
@ 29 org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes) inline (hot)
@ 21 java.lang.Object::getClass (0 bytes) (intrinsic)
@ 24 java.lang.Class::isArray (0 bytes) (intrinsic)
@ 49 java.lang.String::hashCode (49 bytes) inline (hot)
@ 19 java.lang.String::isLatin1 (19 bytes) inline (hot)
@ 29 java.lang.StringLatin1::hashCode (42 bytes) inline (hot)
@ 36 org.apache.commons.lang3.builder.HashCodeBuilder::append (58 bytes) inline (hot)
@ 21 java.lang.Object::getClass (0 bytes) (intrinsic)
@ 24 java.lang.Class::isArray (0 bytes) (intrinsic)
@ 49 java.time.Instant::hashCode (22 bytes) inline (hot)
@ 39 org.apache.commons.lang3.builder.HashCodeBuilder::toHashCode (5 bytes) accessor
@ 6 java.util.HashMap::getNode (148 bytes) inline (hot)
@ 59 com.openkappa.simd.builder.Builder::equals (84 bytes) never executed
@ 126 com.openkappa.simd.builder.Builder::equals (84 bytes) never executed
So the code is clearly small enough to get inlined. But what about the builder itself, isn’t it allocated? Not if it doesn’t escape. On a debug JVM, it’s possible to observe the removal of the builder’s allocation the JVM args -XX:+PrintEscapeAnalysis -XX:+PrintEliminateAllocations. However, on a production JVM, it can be observed indirectly by measuring the difference when escape analysis is disabled with -XX:-DoEscapeAnalysis.
Without escape analysis, the baseline code hardly slows down, whereas the change in the builder benchmarks is stark. The difference of differences here isolates the cost of allocating the HashCodeBuilder on the heap, though the builder has not been allocated on the stack - it has been replaced by its fields, which are allocated on the stack. Escape analysis is enabled by default, and the key point here is that even if the code looks like it might be slower, it might be as good or better - it depends what the JIT does with it.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK