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/AbstractSet.html#removeAll(java.util.Collection)
