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

[Rémi Forax]

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