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 00C22F710 for ; Wed, 17 Apr 2013 19:49:18 +0000 (UTC) Received: (qmail 96497 invoked by uid 500); 17 Apr 2013 19:49:17 -0000 Delivered-To: apmail-commons-issues-archive@commons.apache.org Received: (qmail 96402 invoked by uid 500); 17 Apr 2013 19:49:17 -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 96330 invoked by uid 99); 17 Apr 2013 19:49:17 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 17 Apr 2013 19:49:17 +0000 Date: Wed, 17 Apr 2013 19:49:17 +0000 (UTC) From: "Thomas Neidhart (JIRA)" To: issues@commons.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Updated] (COLLECTIONS-419) Performance problem in AbstractDualBidiMap 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-419?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Thomas Neidhart updated COLLECTIONS-419: ---------------------------------------- Priority: Minor (was: Major) > Performance problem in AbstractDualBidiMap > ------------------------------------------ > > Key: COLLECTIONS-419 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-419 > Project: Commons Collections > Issue Type: Improvement > Affects Versions: 3.2.1 > Environment: java 1.6.0_24 > Ubuntu 11.10 > Reporter: Adrian Nistor > Priority: Minor > Attachments: patch.diff, Test.java > > > Hi, > I am encountering a performance problem in AbstractDualBidiMap. It > appears in version 3.2.1 and also in revision 1355448. I attached a > test that exposes this problem and a one-line patch that fixes it. On > my machine, for this test, the patch provides a 130X speedup. > To run the test, just do: > $ java Test > The output for the un-patched version is: > Time is 5460 > The output for the patched version is: > Time is 42 > The attached test shows that, for a "DualHashBidiMap bidi" object, the > following operation is very slow: > bidi.keySet().retainAll(toRetain) > DualHashBidiMap.keySet() returns a "DualHashBidiMap.KeySet" object, > which inherits "retainAll(Collection coll)" from > "AbstractDualBidiMap.View". Similarly, > bidi.values().retainAll(toRetain) > bidi.entrySet().retainAll(toRetain) > are also slow. This happens for both DualHashBidiMap and > DualTreeBidiMap, which extend AbstractDualBidiMap. > As the patch shows, the problem is that > "AbstractDualBidiMap.View.retainAll(Collection coll)" performs > "coll.contains(it.next())" for each element in the View. > "coll.contains(it.next())" can be very slow, e.g., if "coll" is a > list. > The one-line patch I attached puts the elements of "coll" in a HashSet > (which has very fast "contains()"), if "coll" is not already a set: > "if (!(coll instanceof Set)) coll = new java.util.HashSet