You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Adrian Nistor (JIRA)" <ji...@apache.org> on 2012/06/19 18:01:42 UTC
[jira] [Created] (COLLECTIONS-409) ListOrderedSet.addAll() is very
slow
Adrian Nistor created COLLECTIONS-409:
-----------------------------------------
Summary: ListOrderedSet.addAll() is very slow
Key: COLLECTIONS-409
URL: https://issues.apache.org/jira/browse/COLLECTIONS-409
Project: Commons Collections
Issue Type: Bug
Affects Versions: 3.2.1
Environment: java 1.6.0_24
Ubuntu 11.10
Reporter: Adrian Nistor
Attachments: Test.java, patch.diff
Hi,
I am encountering a performance problem in ListOrderedSet.addAll().
It appears in version 3.2.1 and also in revision 1351465 (18 Jun
2012). I have attached a test that exposes this problem and a
three-line patch that fixes it. On my machine, for this test, the
patch provides a 79X speedup.
To run the test, just do:
$ java Test
The output for the un-patched version is:
Time is 1837
The output for the patched version is:
Time is 23
As the patch shows, the problem is that
ListOrderedSet.addAll(int index, Collection<? extends E> coll)
performs:
"setOrder.add(index++, e)" for each element in "coll". This is very
expensive, because "setOrder" is an ArrayList, and inserting an
element in the middle of an ArrayList shifts all the elements to the
right.
The patched version avoids this cost by inserting all the elements at
once, thus performing only one insert.
Is this a bug? If so, can you please confirm that the patch is
correct?
Thanks,
Adrian
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (COLLECTIONS-409) ListOrderedSet.addAll() is very
slow
Posted by "Adrian Nistor (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-409?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrian Nistor updated COLLECTIONS-409:
--------------------------------------
Attachment: Test.java
patch.diff
> ListOrderedSet.addAll() is very slow
> ------------------------------------
>
> Key: COLLECTIONS-409
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-409
> Project: Commons Collections
> Issue Type: Bug
> Affects Versions: 3.2.1
> Environment: java 1.6.0_24
> Ubuntu 11.10
> Reporter: Adrian Nistor
> Attachments: Test.java, patch.diff
>
>
> Hi,
> I am encountering a performance problem in ListOrderedSet.addAll().
> It appears in version 3.2.1 and also in revision 1351465 (18 Jun
> 2012). I have attached a test that exposes this problem and a
> three-line patch that fixes it. On my machine, for this test, the
> patch provides a 79X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 1837
> The output for the patched version is:
> Time is 23
> As the patch shows, the problem is that
> ListOrderedSet.addAll(int index, Collection<? extends E> coll)
> performs:
> "setOrder.add(index++, e)" for each element in "coll". This is very
> expensive, because "setOrder" is an ArrayList, and inserting an
> element in the middle of an ArrayList shifts all the elements to the
> right.
> The patched version avoids this cost by inserting all the elements at
> once, thus performing only one insert.
> Is this a bug? If so, can you please confirm that the patch is
> correct?
> Thanks,
> Adrian
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (COLLECTIONS-409) ListOrderedSet.addAll() is very
slow
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-409?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart resolved COLLECTIONS-409.
-----------------------------------------
Resolution: Fixed
Fix Version/s: 4.0
Applied the patch in r1351821.
Thanks for reporting!
> ListOrderedSet.addAll() is very slow
> ------------------------------------
>
> Key: COLLECTIONS-409
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-409
> Project: Commons Collections
> Issue Type: Bug
> Affects Versions: 3.2.1
> Environment: java 1.6.0_24
> Ubuntu 11.10
> Reporter: Adrian Nistor
> Fix For: 4.0
>
> Attachments: Test.java, patch.diff
>
>
> Hi,
> I am encountering a performance problem in ListOrderedSet.addAll().
> It appears in version 3.2.1 and also in revision 1351465 (18 Jun
> 2012). I have attached a test that exposes this problem and a
> three-line patch that fixes it. On my machine, for this test, the
> patch provides a 79X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 1837
> The output for the patched version is:
> Time is 23
> As the patch shows, the problem is that
> ListOrderedSet.addAll(int index, Collection<? extends E> coll)
> performs:
> "setOrder.add(index++, e)" for each element in "coll". This is very
> expensive, because "setOrder" is an ArrayList, and inserting an
> element in the middle of an ArrayList shifts all the elements to the
> right.
> The patched version avoids this cost by inserting all the elements at
> once, thus performing only one insert.
> Is this a bug? If so, can you please confirm that the patch is
> correct?
> Thanks,
> Adrian
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (COLLECTIONS-409) ListOrderedSet.addAll() is
very slow
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-409?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13397032#comment-13397032 ]
Hudson commented on COLLECTIONS-409:
------------------------------------
Integrated in commons-collections #23 (See [https://builds.apache.org/job/commons-collections/23/])
[COLLECTIONS-409] Improve performance of ListOrderedSet#addAll, add missing javadoc. Thanks to Adrian Nistor for reporting and providing a patch. (Revision 1351821)
Result = SUCCESS
tn : http://svn.apache.org/viewvc/?view=rev&rev=1351821
Files :
* /commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
> ListOrderedSet.addAll() is very slow
> ------------------------------------
>
> Key: COLLECTIONS-409
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-409
> Project: Commons Collections
> Issue Type: Bug
> Affects Versions: 3.2.1
> Environment: java 1.6.0_24
> Ubuntu 11.10
> Reporter: Adrian Nistor
> Fix For: 4.0
>
> Attachments: Test.java, patch.diff
>
>
> Hi,
> I am encountering a performance problem in ListOrderedSet.addAll().
> It appears in version 3.2.1 and also in revision 1351465 (18 Jun
> 2012). I have attached a test that exposes this problem and a
> three-line patch that fixes it. On my machine, for this test, the
> patch provides a 79X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 1837
> The output for the patched version is:
> Time is 23
> As the patch shows, the problem is that
> ListOrderedSet.addAll(int index, Collection<? extends E> coll)
> performs:
> "setOrder.add(index++, e)" for each element in "coll". This is very
> expensive, because "setOrder" is an ArrayList, and inserting an
> element in the middle of an ArrayList shifts all the elements to the
> right.
> The patched version avoids this cost by inserting all the elements at
> once, thus performing only one insert.
> Is this a bug? If so, can you please confirm that the patch is
> correct?
> Thanks,
> Adrian
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira