commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Oliver Heger <>
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:
>   *
>   *
> 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.


> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message