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

ArrayDeque improvements

    XMLWordPrintable

Details

    Description

      We can make many minor improvements to ArrayDeque:

      The default implementation of removeIf is O(n*m), where m is the number of elements removed. Looks like need to add ArrayDeque.removeIf (like ArrayList.removeIf) was overlooked. Methods removeIf, removeAll, and retainAll can share implementation.

      Currently we're restricted to n^2 backing array sizes, with n^2 - 1 capacity. We should allow any capacity and not waste an extra slot, by using a size field instead of a tail field. No need to ever use integer division. We can make the max capacity the maximum allowed by the JVM (Integer.MAX_VALUE - slop), as with other array-backed collections. We should grow by 3/2 instead of 2, for sufficiently large collections.

      The descending iterator implementation can share most code with ascending variant.

      We can implement addAll, guaranteeing only one backing array resize.

      Backing array resize can be a single Arrays.copyOf if we're lucky, and even if we're not, we can just slide the front forwards afterwards.

      Iterators and spliterators should implement forAllRemaining, for efficiency.

      Attachments

        Issue Links

          Activity

            People

              martin Martin Buchholz
              martin Martin Buchholz
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: