Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6787888

Optimization for java.util.ArrayList :: ensureCapacity()

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Duplicate
    • Icon: P5 P5
    • None
    • 7
    • core-libs

      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.

            Unassigned Unassigned
            ndcosta Nelson Dcosta (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved:
              Imported:
              Indexed: