Return-Path: X-Original-To: apmail-commons-issues-archive@minotaur.apache.org Delivered-To: apmail-commons-issues-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 0E0491781C for ; Thu, 16 Oct 2014 19:42:35 +0000 (UTC) Received: (qmail 58110 invoked by uid 500); 16 Oct 2014 19:42:34 -0000 Delivered-To: apmail-commons-issues-archive@commons.apache.org Received: (qmail 58019 invoked by uid 500); 16 Oct 2014 19:42:34 -0000 Mailing-List: contact issues-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: issues@commons.apache.org Delivered-To: mailing list issues@commons.apache.org Received: (qmail 58008 invoked by uid 99); 16 Oct 2014 19:42:34 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 16 Oct 2014 19:42:34 +0000 Date: Thu, 16 Oct 2014 19:42:34 +0000 (UTC) From: "Thomas Neidhart (JIRA)" To: issues@commons.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Commented] (COLLECTIONS-534) Performance bug in CollectionBag::retainAll MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/COLLECTIONS-534?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14174144#comment-14174144 ] Thomas Neidhart commented on COLLECTIONS-534: --------------------------------------------- btw. our implementation is more or less equivalent to the one of the default collections in the jdk. > Performance bug in CollectionBag::retainAll > ------------------------------------------- > > Key: COLLECTIONS-534 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-534 > Project: Commons Collections > Issue Type: Bug > Components: Bag, Collection > Affects Versions: 4.0 > Environment: Ubuntu 12.04 > Reporter: Oswaldo Olivo > Labels: perfomance > > 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 coll=new ArrayList(); > for(int i=0;i<=1000000;++i) > coll.add(new Integer(i)); > TreeBag treeBag=new TreeBag(coll); > CollectionBag bag = new CollectionBag(treeBag); > bag.retainAll(coll); > } > _____________________________________ > Here's a proposed patch: > public boolean retainAll(final Collection coll) { > if (coll != null) { > boolean modified = false; > final Iterator e = iterator(); > HashSet