Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated] (original) (raw)

Rémi Forax forax at univ-mlv.fr
Tue Jan 4 01:24:20 UTC 2011

On 01/04/2011 02:02 AM, Ulf Zibis wrote:

Am 03.01.2011 21:16, schrieb Mike Duigou:

On Dec 24 2010, at 17:32 , Ulf Zibis wrote:

Am 23.12.2010 23:59, schrieb Paul Benedict: Ulf, a previous email by Remi said only to invoke size() if the collection is a Set. Thanks I missed that. My guess was, that size() should be always faster than instantiating an iterator for the final for-loop, and then seeing, that there is no element. An earlier webrev had an isEmpty() check in the "c1 is a Set" half of the branch. This optimization would pay off in some cases but cost a small amount in others. Since I don't have any strong sense of whether including it would be of actual benefit or harm I opted to take it out in later revisions. For the same reason you could set the empty-check at 1st place. This would result in the most simple (and fast) code (see my before post). - in all implementations, I have seen, "isEmpty()" is equivalent to "size() == 0"

It's semantically equivalent by definition but the complexities aren't the same. see http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/1c72adc9d5f3/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java near line 1740 or http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/1c72adc9d5f3/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java near line 400 or http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/1c72adc9d5f3/src/share/classes/java/util/concurrent/ConcurrentHashMap.java near line 700.

- "cost a small amount in others" applies rarely; the only implementation, I have seen, where "Set.size() can be expensive", is ConcurrentSkipListSet (are there others?).

By example, Collections.newSetFromMap(new ConcurrentHashMap<>). Also don't forget all Sets that map JDBC results.

- swapping c1 , c2 only happens in the very rare applying cases.

Anyway, isn't size() anyhow cheaper than superfluously looping contains() ? E.g. Given Set c1 with 100 elements and Set c2 with 0 elements. Then we iterate and compare over 100 elements needlessly. -Ulf

Rémi

More information about the core-libs-dev mailing list