Details
-
Enhancement
-
Resolution: Unresolved
-
P4
-
9, 10, 11, 17, 19
Description
String.hashCode is the primary example of polynomial hash code. Current code does:
int h = 0;
for (char c : value) {
h = h * 31 + c;
}
...to iteratively compute the hash code. It was illustrated [1] that hand-unrolling the loop, and
computing the hashcode in strides can be beneficial for performance. It is better, however,
to make compiler to optimize the loops like these automatically. Other use cases include
Arrays.hashCode, and any other user-written loop doing the same.
It seems plausible to implode the operations within an unrolled loop into more efficient code.
E.g., given:
<loop by 2> {
t1 = K*t0 + a0;
t2 = K*t1 + a1;
}
...inline t1 into t2, and
<loop by 2> {
// t1 is dead here
t2 = K*(K*t0 + a0) + a1;
}
...and then fold:
<loop by 2> {
// t1 is dead here
t2 = K*K*t0 + K*a0 + a1;
}
Performance benchmarks, perfasm outputs are available here:
http://cr.openjdk.java.net/~shade/8059113/
There, you can see the hand-unrolled versions run up to 1.6x faster.
Multiplying by 31 has additional strength reduction, and partially eliminating that, we have a bit more boosts.
[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-September/028898.html
int h = 0;
for (char c : value) {
h = h * 31 + c;
}
...to iteratively compute the hash code. It was illustrated [1] that hand-unrolling the loop, and
computing the hashcode in strides can be beneficial for performance. It is better, however,
to make compiler to optimize the loops like these automatically. Other use cases include
Arrays.hashCode, and any other user-written loop doing the same.
It seems plausible to implode the operations within an unrolled loop into more efficient code.
E.g., given:
<loop by 2> {
t1 = K*t0 + a0;
t2 = K*t1 + a1;
}
...inline t1 into t2, and
<loop by 2> {
// t1 is dead here
t2 = K*(K*t0 + a0) + a1;
}
...and then fold:
<loop by 2> {
// t1 is dead here
t2 = K*K*t0 + K*a0 + a1;
}
Performance benchmarks, perfasm outputs are available here:
http://cr.openjdk.java.net/~shade/8059113/
There, you can see the hand-unrolled versions run up to 1.6x faster.
Multiplying by 31 has additional strength reduction, and partially eliminating that, we have a bit more boosts.
[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-September/028898.html
Attachments
Issue Links
- duplicates
-
JDK-8186203 Consider unrolling selected hashCode loops
-
- Closed
-
There are no Sub-Tasks for this issue.