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

(coll) Use smaller more optimistic array size increase for AbstractCollection.toArray()

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P4 P4
    • tbd
    • 7
    • core-libs

      A DESCRIPTION OF THE REQUEST :
      In concurrent environment the content of a collection can grow while the iterator is filling the output array in processing method toArray(). In this case a new little bigger array must be allocated. In current implementation the new array becomes 50 % bigger as the before provided array. This seems to pessimistic, so a smaller increase should be more appropriate.

      JUSTIFICATION :
        To big array unnecessarily waste memory resources and increase the chance to reach the maximum array size which anyway must be trimmed later.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Calculate the size for the new internal array by finishToArray() in a reasonable relation to the real collection's size, e.g. the before provided size plus twice the difference between the current size and the current collection's size().
      ACTUAL -
      The internal array becomes 50 % bigger than the before provided array.

      ---------- BEGIN SOURCE ----------
          public <T> T[] toArray(T[] a) {
              // Estimate size of array; be prepared to see more or fewer elements
              int size = size();
              T[] r = a.length >= size ? a :
                      (T[])java.lang.reflect.Array.newInstance
                          (a.getClass().getComponentType(), size);

              Iterator<E> it = iterator();
              int i = 0;
              while (i < r.length) {
                  if (!it.hasNext()) { // fewer elements than expected
                      if (a == r) {
                          a[i] = null; // null-terminate
                      } else if (a.length < i) {
                          return Arrays.copyOf(r, i);
                      } else {
                          System.arraycopy(r, 0, a, 0, Math.min(++i, a.length()); // ensure null-termination
                      }
                      return a;
                  }
                  r[i++] = (T)it.next();
              }
              return finishToArray(r, i, it);
          }

          /**
           * Reallocates the array being used within toArray when the iterator
           * returned more elements than expected, and finishes filling it from
           * the iterator.
           *
           * @param r the array, replete with previously stored elements
           * @param i the current index
           * @param it the in-progress iterator over this collection
           * @return array containing the elements in the given array, plus any
           * further elements returned by the iterator, trimmed to size
           */
          private <T> T[] finishToArray(T[] r, int i, Iterator<E> it) {
              for (int cap = i; it.hasNext(); i++) {
                  if (i == cap) {
                      cap = secureArraySize(i, i + (Math.max(0, size() - i) << 1) + 1);
                      //cap = secureArraySize(i, i + (i >> 4) + 1); // alternative !
                      r = Arrays.copyOf(r, cap);
                  }
                  r[i] = (T)it.next();
              }
              // trim if overallocated
              return (i == r.length) ? r : Arrays.copyOf(r, i);
          }

          /**
           * The maximum size of array to allocate.
           * Some VMs reserve some header words in an array.
           * Attempts to allocate larger arrays may result in
           * OutOfMemoryError: Requested array size exceeds VM limit
           */
          private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

      /**
           * @param old the current size of the array
           * @param size the requested size (must not be bigger than the old size)
           */
      private int secureArraySize(int old, int size) {
              // overflow-conscious code
              assert (size <= old);
              if (size - MAX_ARRAY_SIZE <= 0)
                  return size;
              if (++old < 0) // overflow
                  throw new OutOfMemoryError
                          ("Required array size too large");
              return (old > MAX_ARRAY_SIZE) ?
                      Integer.MAX_VALUE : MAX_ARRAY_SIZE;
          }

      ---------- END SOURCE ----------

            Unassigned Unassigned
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

              Created:
              Updated:
              Imported:
              Indexed: