commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Oliver Heger <oliver.he...@oliver-heger.de>
Subject Re: [collections] Revert a performance related fix in 4.1
Date Sat, 24 Jan 2015 20:16:16 GMT
Hi Thomas,

On 24.01.2015 19:21, Thomas Neidhart wrote:
> Hi,
>
> from time to time some researchers trying to find performance bugs in
> open-source software create issues for collections.
>
> One of the easy targets is the Collection#retainAll(Collection) method
> as the default implementation in AbstractCollection calls contains on
> the provided collection.
>
> Now, in the worst-case this may lead to a runtime complexity of O(n^2),
> i.e. when the collection has a contains implementation with O(n) complexity.
>
> The proposed solution is usually to create an intermediate set and use
> it to speed up the contains calls.
>
> My position was always that a given Collection class shall not overwrite
> this method trying to optimize its runtime behavior for any possible
> input by creating such intermediate data structures as this will just
> increase the space complexity (in many cases unnecessarily). Instead,
> the runtime complexity was documented (one can even question this as the
> Collection framework should be well-known by java users).
>
> It looks like that at 2 occasions these "performance bugs" got fixed:
>
>   * https://issues.apache.org/jira/browse/COLLECTIONS-426
>   * https://issues.apache.org/jira/browse/COLLECTIONS-427
>
> and I would like to revert these fixes as they are wrong imho and just
> create a precedent for further tickets.
>
> Does anybody challenge my rationale behind this or can I go ahead with it?
>
> Thomas

I follow your reasoning. It seems that the proposed "optimization" would 
have a negative impact on average use cases while trying to prevent 
users from doing something stupid.

A general purpose library should focus on such average use cases.

Oliver

>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message