Uploaded image for project: 'Commons Collections'
  1. Commons Collections
  2. COLLECTIONS-534

Performance bug in CollectionBag::retainAll

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 4.0
    • Fix Version/s: 4.1
    • Component/s: Bag, Collection
    • Labels:
    • Environment:

      Ubuntu 12.04

      Description

      Hi,
      There seems to be a performance bug in the method retainAll in the CollectionBag class.
      The problem is that the code is checking containment over the parameter collection, which could be expensive for some types of collections like ArrayLists.
      One solution could be to convert the Collection into a HashSet and check containment in the HashSet.
      If this is done, then running retainAll on a 1,000,000 collection would take less than 2 seconds instead of 27 mins, according to my experiments.

      ____________________________________________
      Here's a function to expose the bug:

      public static void collectionBagRetainAllTest()

      { ArrayList<Integer> coll=new ArrayList<Integer>(); for(int i=0;i<=1000000;++i) coll.add(new Integer(i)); TreeBag<Integer> treeBag=new TreeBag<Integer>(coll); CollectionBag<Integer> bag = new CollectionBag<Integer>(treeBag); bag.retainAll(coll); }

      _____________________________________

      Here's a proposed patch:

      public boolean retainAll(final Collection<?> coll) {
      if (coll != null) {
      boolean modified = false;
      final Iterator<E> e = iterator();
      HashSet<Object> set=new HashSet<Object>(coll);
      while (e.hasNext()) {
      if (!set.contains(e.next()))

      { e.remove(); modified = true; }

      }
      return modified;
      } else

      { // let the decorated bag handle the case of null argument return decorated().retainAll(null); }

      }
      _____________________________________

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              oswaldo_o Oswaldo Olivo
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: