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

(coll) AbstractCollection.retainAll(coll) is slow when collection "coll" is empty

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Open
    • Priority: P5
    • Resolution: Unresolved
    • Affects Version/s: 6u31
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:

      Description

      FULL PRODUCT VERSION :
      java version "1.6.0_24"
      Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
      Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)

      ADDITIONAL OS VERSION INFORMATION :
      Linux 3.0.0-12-generic #20-Ubuntu

      A DESCRIPTION OF THE PROBLEM :
      The method "AbstractCollection.retainAll(Collection<?> c)" is very
      slow when the parameter "c" is empty (and "retainAll" should just
      clear "this" collection). I attached a test that exposes this problem
      and a one-line patch that fixes it. For this test, the patch provides
      822X speedup on my machine.

      The patch is very simple, just call:

      if (c.isEmpty()) { clear(); return true; }

      at the beginning of "retainAll".

        To run the test, do:

      $ java Test

      The output for the un-patched version is:
      Time is 822

      The output for the patched version is:
      Time is 1

      There are other ways to speed up "retainAll", but they are more
      complex, e.g., bug 5028425, whereas the above one-line patch is
      trivial and provides considerable speedup for certain usage scenarios.

      The method "AbstractCollection.removeAll(Collection<?> c)" can be
      similarly optimized by adding "if (c.isEmpty()) return false;", but
      the speed up is not as dramatic as for "retainAll".

      Can you please fix this behavior?


      The patch is:
      ======================================================================
      --- AbstractCollection.java 2012-07-23 14:04:13.525513594 -0500
      +++ AbstractCollection_Fix.java 2012-07-23 14:20:49.725537261 -0500
      @@ -363,6 +363,7 @@
            * @see #contains(Object)
            */
           public boolean retainAll(Collection<?> c) {
      + if (c.isEmpty()) { clear(); return true; }
        boolean modified = false;
        Iterator<E> e = iterator();
        while (e.hasNext()) {
      ======================================================================


      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      $ java Test

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Time is 1
      ACTUAL -
      Time is 822

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.util.ArrayList;

      public class Test {
          public static void main(String[] args) {
              ArrayList<Integer> collection = new ArrayList<Integer>();
              for (int i = 0; i < 100000; i++) collection.add(i);
              ArrayList<Integer> other = new ArrayList<Integer>();
              
              long start = System.currentTimeMillis();
              collection.retainAll(other);
              System.out.println("Time is " + (System.currentTimeMillis() - start));
          }
      }

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

      CUSTOMER SUBMITTED WORKAROUND :
      I realize one can solve this problem from the caller site,
      replacing "collection.retainAll(other)" with something like:

      if (other.isEmpty()) collection.clear();
      else collection.retainAll(other);

      However, this clutters the caller sites a lot.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              smarks Stuart Marks
              Reporter:
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

                Dates

                Created:
                Updated:
                Imported:
                Indexed: