Details

    • Type: Bug
    • Status: Closed
    • Priority: P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 9
    • Component/s: core-libs

      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.

        Issue Links

          Activity

          Hide
          smarks Stuart Marks added a comment -
          Note also that ArrayList.removeIf can be further improved, doing the removal in a single pass instead of two passes with a BitSet. See JDK-8143577.
          Show
          smarks Stuart Marks added a comment - Note also that ArrayList.removeIf can be further improved, doing the removal in a single pass instead of two passes with a BitSet. See JDK-8143577 .
          Hide
          martin Martin Buchholz added a comment -
          I'm expanding the scope of this change to a rewrite.
          Show
          martin Martin Buchholz added a comment - I'm expanding the scope of this change to a rewrite.
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/a15610e000ba
          User: martin
          Date: 2016-11-29 08:30:02 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/a15610e000ba User: martin Date: 2016-11-29 08:30:02 +0000
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/a15610e000ba
          User: lana
          Date: 2016-12-07 19:33:44 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/a15610e000ba User: lana Date: 2016-12-07 19:33:44 +0000

            People

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

              Dates

              • Created:
                Updated:
                Resolved: