commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (COLLECTIONS-425) performance problem in ListOrderedMap.remove()
Date Tue, 24 Jul 2012 22:13:34 GMT

     [ https://issues.apache.org/jira/browse/COLLECTIONS-425?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Adrian Nistor updated COLLECTIONS-425:
--------------------------------------

    Description: 
Hi,

I am encountering a performance problem in ListOrderedMap.remove().
It appears in version 3.2.1 and also in revision 1365132.  I attached
a test that exposes this problem and a simple patch that fixes it.  On
my machine, for this test, the patch provides a 213X speedup.

To run the test, just do:

$ java Test

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

The output for the patched version is:
Time is 7

The patch changes the "ListOrderedMap.remove(Object key)" code from:

{code:java|borderStyle=solid}
Object result = getMap().remove(key);
insertOrder.remove(key);
{code}

to:

{code:java|borderStyle=solid}
if (decorated().containsKey(key)) {
    result = decorated().remove(key);
    insertOrder.remove(key);
}
{code}

If "decorated()" does not contain the key, there is no need to remove
it.  This change significantly speeds up the code by avoiding the call
to "insertOrder.remove(key)", which is very expensive because
"insertOrder" is an ArrayList, and removing from an ArrayList is a
linear time operation.

It may appear that the check "if (decorated().containsKey(key))" may
slow down the code when "decorated()" contains the key, because it
adds a new operation "decorated().containsKey(key)", without avoiding
the calls to "getMap().remove(key)" and "insertOrder.remove(key)".

I attached a test, TestWorstCase.java, that show that, even when
removing only existing keys (i.e., "decorated().containsKey(key)"
always returns "true"), the patched version takes almost the same time
as the un-patched version.

To run TestWorstCase, just do:

$ java TestWorstCase

The output for the un-patched version for TestWorstCase is:
Time is 96

The output for the patched version for TestWorstCase is:
Time is 97

The reason why the patch does not slow down the code, even for this
worst case, is because "decorated().containsKey(key)" is a
"containsKey()" on a HashMap (very fast, constant time operation),
whereas "insertOrder.remove(key);" is a "remove()" on an ArrayList
(very slow, linear time operation).  So the time taken by
"decorated().containsKey(key)" is negligible compared to the time
taken by "insertOrder.remove(key);".  In other words, most of the time
is spent inside "insertOrder.remove(key)", and performing one
additional fast operation cannot be noticed.

Is this truly a bug? If so, can you please confirm if the patch is
correct?

Thanks,

Adrian


  was:
Hi,

I am encountering a performance problem in ListOrderedMap.remove().
It appears in version 3.2.1 and also in revision 1365132.  I attached
a test that exposes this problem and a simple patch that fixes it.  On
my machine, for this test, the patch provides a 213X speedup.

To run the test, just do:

$ java Test

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

The output for the patched version is:
Time is 7

The patch changes the "ListOrderedMap.remove(Object key)" code from:

Object result = getMap().remove(key);
insertOrder.remove(key);

to:

if (decorated().containsKey(key)) {
    result = decorated().remove(key);
    insertOrder.remove(key);
}

If "decorated()" does not contain the key, there is no need to remove
it.  This change significantly speeds up the code by avoiding the call
to "insertOrder.remove(key)", which is very expensive because
"insertOrder" is an ArrayList, and removing from an ArrayList is a
linear time operation.

It may appear that the check "if (decorated().containsKey(key))" may
slow down the code when "decorated()" contains the key, because it
adds a new operation "decorated().containsKey(key)", without avoiding
the calls to "getMap().remove(key)" and "insertOrder.remove(key)".

I attached a test, TestWorstCase.java, that show that, even when
removing only existing keys (i.e., "decorated().containsKey(key)"
always returns "true"), the patched version takes almost the same time
as the un-patched version.

To run TestWorstCase, just do:

$ java TestWorstCase

The output for the un-patched version for TestWorstCase is:
Time is 96

The output for the patched version for TestWorstCase is:
Time is 97

The reason why the patch does not slow down the code, even for this
worst case, is because "decorated().containsKey(key)" is a
"containsKey()" on a HashMap (very fast, constant time operation),
whereas "insertOrder.remove(key);" is a "remove()" on an ArrayList
(very slow, linear time operation).  So the time taken by
"decorated().containsKey(key)" is negligible compared to the time
taken by "insertOrder.remove(key);".  In other words, most of the time
is spent inside "insertOrder.remove(key)", and performing one
additional fast operation cannot be noticed.

Is this truly a bug? If so, can you please confirm if the patch is
correct?

Thanks,

Adrian


    
> performance problem in ListOrderedMap.remove()
> ----------------------------------------------
>
>                 Key: COLLECTIONS-425
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-425
>             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, TestWorstCase.java, patch.diff
>
>
> Hi,
> I am encountering a performance problem in ListOrderedMap.remove().
> It appears in version 3.2.1 and also in revision 1365132.  I attached
> a test that exposes this problem and a simple patch that fixes it.  On
> my machine, for this test, the patch provides a 213X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 1497
> The output for the patched version is:
> Time is 7
> The patch changes the "ListOrderedMap.remove(Object key)" code from:
> {code:java|borderStyle=solid}
> Object result = getMap().remove(key);
> insertOrder.remove(key);
> {code}
> to:
> {code:java|borderStyle=solid}
> if (decorated().containsKey(key)) {
>     result = decorated().remove(key);
>     insertOrder.remove(key);
> }
> {code}
> If "decorated()" does not contain the key, there is no need to remove
> it.  This change significantly speeds up the code by avoiding the call
> to "insertOrder.remove(key)", which is very expensive because
> "insertOrder" is an ArrayList, and removing from an ArrayList is a
> linear time operation.
> It may appear that the check "if (decorated().containsKey(key))" may
> slow down the code when "decorated()" contains the key, because it
> adds a new operation "decorated().containsKey(key)", without avoiding
> the calls to "getMap().remove(key)" and "insertOrder.remove(key)".
> I attached a test, TestWorstCase.java, that show that, even when
> removing only existing keys (i.e., "decorated().containsKey(key)"
> always returns "true"), the patched version takes almost the same time
> as the un-patched version.
> To run TestWorstCase, just do:
> $ java TestWorstCase
> The output for the un-patched version for TestWorstCase is:
> Time is 96
> The output for the patched version for TestWorstCase is:
> Time is 97
> The reason why the patch does not slow down the code, even for this
> worst case, is because "decorated().containsKey(key)" is a
> "containsKey()" on a HashMap (very fast, constant time operation),
> whereas "insertOrder.remove(key);" is a "remove()" on an ArrayList
> (very slow, linear time operation).  So the time taken by
> "decorated().containsKey(key)" is negligible compared to the time
> taken by "insertOrder.remove(key);".  In other words, most of the time
> is spent inside "insertOrder.remove(key)", and performing one
> additional fast operation cannot be noticed.
> Is this truly a bug? If so, can you please confirm if 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

        

Mime
View raw message