On 1/24/15 1:16 PM, Oliver Heger wrote: > 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.
+1 - and transparency. Being able to clearly document behavior (or rely on existing JDK doco) outweighs the benefit here IMO. Phil > > Oliver > >> >> --------------------------------------------------------------------- >> >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> For additional commands, e-mail: dev-h...@commons.apache.org >> > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
