[LANG-345] Optimize HashCodeBuilder.append(Object)

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 2.3
• Fix Version/s: 2.4
• Assignee: Unassigned
• Reporter: Venkatesh Prasad Ranganath
• Created: 04/Jul/07 19:22
• Updated: 09/Aug/07 01:59
• Resolved: 09/Aug/07 01:59

Description

In HashCodeBuilder.append(Object), java.lang.Class.isArray() is used to check if the input argument is an array. This check is expensive in comparison with an "instanceof" check. While a single instanceof check will not suffice, even the required 9 instance of checks prove to be faster than this single check. This is illustrated by the data from a profiling session.

CPU SAMPLES BEGIN (total = 71) Sat Jun 30 16:51:43 2007
rank self accum count trace method
1 45.07% 45.07% 32 300138 java.lang.Class.isArray
2 14.08% 59.15% 10 300141 java.util.AbstractList.hashCode
3 12.68% 71.83% 9 300142 java.util.AbstractList.hashCode
4 4.23% 76.06% 3 300030 sun.nio.cs.UTF_8$Decoder.decodeArrayLoop
5 4.23% 80.28% 3 300144 java.util.AbstractList.hashCode
6 2.82% 83.10% 2 300143 Test.run2
7 2.82% 85.92% 2 300139 java.util.ArrayList.get
8 1.41% 87.32% 1 300140 java.util.AbstractList.hashCode
9 1.41% 88.73% 1 300145 java.util.AbstractList.hashCode
10 1.41% 90.14% 1 300027 sun.nio.cs.UTF_8$Decoder.<init>
11 1.41% 91.55% 1 300012 java.nio.DirectByteBuffer.<init>
12 1.41% 92.96% 1 300089 sun.security.provider.Sun.<clinit>
13 1.41% 94.37% 1 300132 sun.security.provider.Sun.<init>
14 1.41% 95.77% 1 300071 java.lang.StringCoding.decode
15 1.41% 97.18% 1 300031 sun.reflect.NativeConstructorAccessorImpl.newInstance
16 1.41% 98.59% 1 300048 java.net.URLClassLoader.defineClass
17 1.41% 100.00% 1 300137
sun.net.www.ParseUtil.canonizeStringCPU SAMPLES END

The profiled program is given below. While run1() uses HashCodeBuilder.append(Object), run2() uses an optimized version of the same code. While 45% of the time is spent in Class.isArray() (hence, in run1()), only ~3% of the time is spent in run2(). So, we can replace the body of HashCodeBuilder.append(Object) with that from OptimizedHashCodeBuilder.append(Object) and improve the performance by 15x.

import org.apache.commons.lang.builder.HashCodeBuilder;

public class Test {

public static void main(String[] s)

{ java.util.ArrayList o = new java.util.ArrayList(); o.add("Hello"); o.add("World"); run1(o); run2(o); }

static void run1(Object o) {
for (int i = 0; i < 10000; i++) {
HashCodeBuilder h = new HashCodeBuilder();
for (int k = 0; k < 100; k++)

{ h = h.append(o); }
}
}

static void run2(Object o) {
for (int i = 0; i < 10000; i++) {
HashCodeBuilder h = new OptimizedHashCodeBuilder();
for (int k = 0; k < 100; k++) { h = h.append(o); }

}
}
}

class OptimizedHashCodeBuilder extends HashCodeBuilder {
public HashCodeBuilder append(final Object object) {
if (object == null)

{ super.append(object); }

else {
// 'Switch' on type of array, to dispatch to the correct handler
// This handles multi dimensional arrays
if (object instanceof long[])

{ append((long[]) object); }

else if (object instanceof int[])

{ append((int[]) object); }

else if (object instanceof short[])

{ append((short[]) object); }

else if (object instanceof char[])

{ append((char[]) object); }

else if (object instanceof byte[])

{ append((byte[]) object); }

else if (object instanceof double[])

{ append((double[]) object); }

else if (object instanceof float[])

{ append((float[]) object); }

else if (object instanceof boolean[])

{ append((boolean[]) object); }

else if (object instanceof Object[])

{ // Not an array of primitives append((Object[]) object); }

else

{ // the simple case, not an array, just the element append(object.hashCode()); }

}
return this;
}
}