Hi Stuart. It looks like the web sites and services I use when developing and those you use are fundamentally different or may be we use just different search engines, because when I have programming problems I usually not end up on Twitter or Reddit or DZone. And the existence of this mailing list seems to be hidden to the net or it's SE ranking is so bad that I can't remember that I ever found a link to it in the last years (before knowing it's existence and explicitly searching for it). However when I search most likely the majority of links point to Stackoverflow.com. Searching Stackoverflow for something like "[Java] [performance] Hashset" you immediatly get to the question https://stackoverflow.com/questions/28671903 which has 65 upvotes and a view count of 8,085. For a 5 years old question this is IMHO pretty impressive. Also one have to keep in mind that we are talking about a performance problem that requires usually an experienced developer and large data sets before the delay becomes so apparently that you start searching for the reason. Your proposed replacement for AbstractSet.removeAll() looks nice and I agree with you regarding the arguments you pointed out on what collection used as "this" and what as argument. That should be clearly a decision of the developer. That the change makes AbstractSet.removeAll "an outlier" is in my opinion only a problem from a very high-level perspective. Only people not aware of the differences between all the Collection implementations and the reason why they exist may expect to have a removeAll() implementation that works identical for every Collection implementation. However regular programmers from my experience rarely come to a point where they use Collection. Personally for me Collection is more or less a synonym for Iterable because iterating over a Collection is one of the few properties that work without major (potential) performance issues for all implementations. Jan Am 25.01.2019 um 01:07 schrieb Stuart Marks:
I wasn't aware that hundreds of developers are hitting this bug every year. I haven't seen any mention of it (besides in the bug database) on Twitter, on Reddit, on DZone, at the conferences I attend, or in several years of core-libs-dev emails. Well, it was mentioned on core-libs-dev once in 2011 [1] although that was a suggestion for improvement, not a complaint about performance.
Nonetheless this is a real problem, and if it's causing difficulties we can certainly take a look at it.
There is, however, more to the story. The ACTUAL problem is a semantic one; see JDK-6394757. [2] Briefly, consider x.removeAll(y). Depending on the relative sizes of x and y, this method might end up using either x's or y's definition of membership, which could differ from each other. (See the bug report for an example.) Thus the semantics of this method depend upon the relative sizes of the collections, which is arguably flawed.
Worse, this behavior is specified to iterate this set or the argument, depending upon their relative sizes. [3] So, fixing this will require an incompatible specification change.
The obvious way to fix this is to get rid of the "optimizations" (that turn out not to be optimizations at all in some cases) and replace it with a simple loop:
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; for (Object e : c) modified |= remove(e); return modified; }
I would argue that iterating the argument and calling remove() on "this" are the right semantics, because you want set membership to be determined by this set, not by whatever collection you pass as an argument. However, I note that AbstractCollection.removeAll and other removeAll implementations iterate over "this" and do a contains() check on the argument. The revised AbstractSet.removeAll would be an outlier here, though it makes sense to me to do it this way.
Is it worth the incompatibility?
s'marks
[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-July/007125.html
[2] https://bugs.openjdk.java.net/browse/JDK-6394757
[3] https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Abstr...)