United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-7192942 : (coll) Inefficient calculation of power of two in HashMap

Details
Type:
Enhancement
Submit Date:
2012-08-21
Status:
Closed
Updated Date:
2014-02-12
Project Name:
JDK
Resolved Date:
2013-08-01
Component:
core-libs
OS:
generic
Sub-Component:
java.util:collections
CPU:
generic
Priority:
P4
Resolution:
Fixed
Affected Versions:
8
Fixed Versions:

Related Reports
Backport:
Backport:

Sub Tasks

Description
This is a SUNBUG for 100189: https://bugs.openjdk.java.net/show_bug.cgi?id=100189

Constructor does this:

public HashMap(int initialCapacity, float loadFactor) {
  ...
  int capacity = 1;
  while (capacity < initialCapacity)
      capacity <<= 1;
  ...
}

It is magnitude+ faster to do this:

static final double LOG2 = Math.log(2.0);
public HashMap(int initialCapacity, float loadFactor) {
  ...
  int capacity = 1 << ((int)Math.ceil(Math.log(initialCapacity)/LOG2 ));
  ...
}


Given the error checking in the head of the constructor, this code should just
plug-in.

                                    

Comments
The issue was already fixed in jdk8 with 

A function roundUpToPowerOf2() was introduced that does the calculation faster than in a loop.
However this function can also be optimized a bit.
                                     
2013-07-30
URL:   http://hg.openjdk.java.net/jdk8/tl/jdk/rev/36f4cf8872f3
User:  dmeetry
Date:  2013-08-01 14:21:16 +0000

                                     
2013-08-01
URL:   http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/36f4cf8872f3
User:  lana
Date:  2013-08-13 18:14:45 +0000

                                     
2013-08-13



Hardware and Software, Engineered to Work Together