JDK-6506618 : java.lang.String#hashCode() enhancement
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.lang
  • Affected Version: 6
  • Priority: P5
  • Status: Closed
  • Resolution: Won't Fix
  • OS: windows_2003
  • CPU: x86
  • Submitted: 2006-12-20
  • Updated: 2011-02-16
  • Resolved: 2006-12-20
Description
A DESCRIPTION OF THE REQUEST :
The java.lang.String#hashCode() method uses multiplication on 31 (h*31 + ... ) in hash code generation. More faster method is   (h<<5) - h.
Because  x*31 == (x<<5)  - x;
(x<<5 == x*32);

JUSTIFICATION :
Need more faster hashCode method.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
More faster hashCode generation.
ACTUAL -
Actual java.lang.String#hashCode() method uses multiplication operation in hash code generation. It more slow than shft and subtraction.

---------- BEGIN SOURCE ----------
public void testHashCode(){
		int h1 = 28167, h2 = 28167;
		for (int i = 0; i < 1000; i++) {
			h1= h1*31;
			h2 = (h2<<5) - h2;
			assertEquals(h1,h2);
		}
		long c = 1000000000;
		long start = System.currentTimeMillis();
		for (int i = 0; i < c; i++) {
			h1= h1*31;
		}
		long t1 = System.currentTimeMillis()-start;
		
		start = System.currentTimeMillis();
		for (int i = 0; i < c; i++) {
			h2 = (h2<<5) - h2;
		}
		long t2 = System.currentTimeMillis() - start
		;
		
		System.out.println("t1 - "+t1 + ", t2 - "+t2);
		System.out.println("dif-" +(t1-t2));
	}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use (h<<5) - h  instead  h*32

Comments
EVALUATION The submitted code was tested within Sun in a best case scenario and the largest improvement seen was 0.01%. And slight rearrangement of the code loops involved showed shift actually running faster. But these differences are so small they are not statistically significant, because of many factors that can affect the measurements. With current computers the difference between shift and multiply instructions for integers tends to be small and in some cases overlapping of functional units within the CPU masks out the difference completely. However, consider the other code within the hashCode method and consider how infrequently that method is being executed in relation to all the other code executed by any *real world application*. These two factors divide the actual advantage of the suggested optimization by such a large number that the overall change in execution speed may be too small to measure! So this wouldn't be an actual enhancement and the request is declined. Additional information about performance tuning information including other issues related to microbencharks is available here: http://java.sun.com/performance/reference/whitepapers/tuning.html
20-12-2006