On 5/4/20 6:44 PM, Alan Snyder wrote:
What problem are you trying to solve?
The Collections framework explicitly does not support custom membership
semantics. If you think it should, file an RFE and create a JEP. It’s not a
small change and tinkering is not the way to get there.
There are already three different kinds of sets in the JDK that support
different membership semantics: sets derived from IdentityHashMap, ordinary sets
like HashSet, and the SortedSet/NavigableSet family. Arguably the last already
supports custom membership semantics, as it's possible for callers to provide
their own comparators. I'm trying to fix semantic bugs in the way various
collection operations handle situations with mixed membership semantics, and
secondarily, to avoid pathological performance problems that have arisen.
If your present concern is performance surprises, be aware that your new
proposal has the same problem as the old one. Although it removes some
data-dependent performance surprises, it adds a potential JDK-dependent
performance surprise. The data-dependent performance issues can be detected by
testing, but no amount of testing can alert a developer to the possibility that
an unexpected implementation change in a future JDK might cause a big
performance hit.
You may have mis-remembered the performance problem that I am concerned about.
It involves using removeAll to remove a relatively small number of elements from
a large, hash based collection. The performance hit is the need to iterate over
the entire collection and test every element regardless of the number of
elements being removed. Although the performance problem may be exacerbated when
the argument is a List, the problem exists for any collection that is much
smaller than the target collection.
You're conflating two different parts of the performance issue.
This is illustrated in an article that Jon Skeet posted back in 2010, [1] which
is linked from JDK-6982173. Briefly, Skeet observed that a removeAll using a
List of 300,000 elements could take nearly 3 minutes, whereas iterating a
HashSet of 1,000,000 elements would take only 38ms.
(These numbers are from 2010, and hardware is certainly different today, and
these aren't rigorous benchmarks. However, an informal benchmark that shows the
difference between 3 minutes and 38ms is a pretty clear demonstration of a
performance problem.)
Taking 3 minutes for this kind of operation is clearly pathological behavior,
which is what I'm trying to address. Although it seems impossible to prevent it
from ever happening, putting some special cases for handling List into places
such as HashSet.removeAll would seem to cover the most of the common cases.
It's true that if you're removing a small set from a large set, iterating the
"wrong" set might take 38ms instead of a much smaller time (probably
microseconds). This would indeed be a performance regression. (It might also be
an improvement in correctness, if the sets have different membership contracts.)
The fact is that there are performance regressions from one JDK release to the
next. Sometimes they're introduced by accident, and we try to address these
where possible. Sometimes they're introduced intentionally, as part of various
tradeoffs. That's what's going on here. I'm improving the correctness of the
system and avoiding pathological performance problems, while introducing a
performance regression that seems modest relative to the pathological
performance issue that's being mitigated.
s'marks
[1]
https://codeblog.jonskeet.uk/2010/07/29/there-s-a-hole-in-my-abstraction-dear-liza-dear-liza/
Alan
On May 4, 2020, at 5:25 PM, Stuart Marks <stuart.ma...@oracle.com
<mailto:stuart.ma...@oracle.com>> wrote:
On 5/1/20 10:41 PM, Jason Mehrens wrote:
1. I assume you are using "c instanceof List" instead of "!(c instanceof
Set)" to correctly handle IdentitityHashMap.values()? The instanceof List
seems like safe choice but it is too bad we can still fool that check by
wrapping List as an unmodifiableCollection. If
splitIterator().characteristics() could tell us that the collection used
identity comparisons I think we would be able to determine if it was safe to
swap the ordering in the general case as we could check for IDENTITY, SORTED,
and comparator equality.
I'm using "instance List", not for the reason of IdentityHashMap.values()
specifically (though that's a good example), but mainly to try to be minimal.
While I think getting the semantics right takes priority, the change does
impact performance, so I want to reintroduce the performance heuristic in the
safest manner possible. Checking for !Set seems dangerous, as there might be
any number of Collections out there that aren't Sets and that aren't
consistent with equals. Checking for instanceof List seemed like the safest
and most minimal thing to do.
In fact, I'm not even sure how safe List is! It's certainly possible for
someone to have a List that isn't consistent with equals. Such a thing might
violate the List contract, but that hasn't stopped people from implementing
such things (outside the JDK).
I also toyed around with various additional tests for when it would be
profitable to switch iteration to the smaller collection. This could be
applied to a variety of consistent-with-equals set implementations in the JDK.
The benefits of swapping the iteration is more modest in these cases compared
to List, however. Avoiding repeated List.contains() helps avoid
quasi-quadratic (O(M*N)) performance. Swapping iteration order of sets gets us
only the smaller of O(M) vs O(N), which is still linear.
Also, as you noted, this heuristic is easily defeated by things like the
collection wrappers.
2. Should code applied to HashSet.removeAll also be applied to
HashMap.keySet().removeAll and HashMap.entrySet().removeAll?
Collections::newSetFromMap will end up having different behavior if it is
not consistently applied.
I think the *results* will be consistent, but the *performance* might not be
consistent.
But these cases could result in pathological performance if removeAll(list) is
called, so I'm a bit concerned about them. If we agree that "instanceof List"
is a reasonable heuristic, then I don't have any objection in principle to
adding it to these locations as well. But I want to be careful about
sprinkling ad hoc policies like this around the JDK.
I note that the erroneous size-based optimization was copied into, and
therefore needs to be removed from ConcurrentSkipListSet (JDK-8218945) and the
set views of CHM (JDK-8219069). I'd more concerned about getting these cleaned
up in the short term.
3. Not to derail this thread but do think we need a new JIRA ticket to
address Collections.disjoint? Seems like it has similar sins of calling size
and using "!(c2 instanceof Set)" but I don't want to muddy the waters by
covering any solutions to that method in this thread.
Yeah I'm not sure what to do about Collections.disjoint().
Note that there are some statements in bug reports (possibly even made by me!)
that assert that Collections.disjoint should be consistent with Set.removeAll.
I don't think that's the case. As discussed elsewhere, removeAll() needs to be
consistent about relying on the membership semantics of the argument collection.
As Collections.disjoint currently stands, it has the big "Care must be
exercised" disclaimer in its spec, and it goes to some length to make a bunch
of tests and vary the iteration accordingly. The programmer can get a speedup
using disjoint() compared to copying a set and then calling retainAll(),
provided sufficient care is taken. Maybe that's an acceptable tradeoff.
If you have any ideas about how disjoint()'s spec or implementation could be
improved, you could file a JIRA issue, or I could file one if you sent me the
info.
s'marks
