JDK-6787888 : Optimization for java.util.ArrayList :: ensureCapacity()
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 7
  • Priority: P5
  • Status: Closed
  • Resolution: Duplicate
  • OS: linux
  • CPU: x86
  • Submitted: 2008-12-21
  • Updated: 2021-03-03
  • Resolved: 2010-08-06
Related Reports
Duplicate :  
Description
A DESCRIPTION OF THE REQUEST :
ensureCapacity method has some scope of faster multiplication  - when computing the newCapacity .

  public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1; // Use bit-wise operators .
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }


JUSTIFICATION :
Divisions are inherently not justified when compared to bitwise operators that are way faster ahead of the division. Here we can use it all the more for division by 2.

This results in a significance performance improvement , when adding a large number of elements to an existing arrayList since the capacity is increased every time we reach the limit.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
int newCapacity = ( oldCapacity * 3) >> 1 + 1
ACTUAL -
Slower bitwise operation.

---------- BEGIN SOURCE ----------
int newCapacity = ( oldCapacity * 3) >> 1 + 1
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Performance issue.

Comments
EVALUATION The ensureCapacity() method has been modified in the fix for 6933217 that also changed the division to use the bit-wise operation: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/ec45423a4700
06-08-2010

PUBLIC COMMENTS My inclination would be to let the source code be cleaner and leave such simple peephole optimizations to HotSpot.
13-01-2009