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

[Ulf Zibis]

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.
But:
Given Set c1 with 100 elements and Set c2 with 0 elements.
Then we iterate and compare over 100 elements for nothing.

Result map for method disjoint():

           c1    |         Set        |        mere
c2   | elements |   0 |   3 |  50 |   0 |   3 |  50
---------------------------------------------------------------------
      |    0     |true |true|true |true |true|true

Set  |    3     |true |t/f  |t/f |true|t/f |t/f

      |   50 |true |t/f  |t/f |true|t/f |t/f
---------------------------------------------------------------------
      |    0 |true |true|true |true |true|true

mere |    3 |true |t/f  |t/f |true|t/f |t/f

      |   50 |true |t/f  |t/f |true|t/f |t/f
---------------------------------------------------------------------


(1) Iteration over in current webrev.3:

           c1    |         Set        |        mere
c2   | elements |   0 |   3 |  50 |   0 |   3 |  50
---------------------------------------------------------------------
      |    0     |  c2  |c2 |c2 |  c1 |c1 |c1

Set  |    3     |  c2  |c2 |c2 |c1 |c1 |c1

      |   50 |  c2  |c2 |c2 |c1 |c1 |c1
---------------------------------------------------------------------
      |    0 |  c2  |c2 |c2 |none |none|none

mere |    3 |  c2  |c2 |c2 |none|  c1|c2

      |   50 |  c2  |c2 |c2 |none|  c1|c1
---------------------------------------------------------------------


(2) Ideal iteration over:

           c1    |         Set        |        mere
c2   | elements |   0 |   3 |  50 |   0 |   3 |  50
---------------------------------------------------------------------
      |    0     |none |none|none|none|none|none

Set  |    3     |none|c1/2*|c2*|none|c1 |c1

      |   50 |none|c1*|c1/2*|none|c1 |c1
---------------------------------------------------------------------
      |    0 |none |none|none|none |none|none

mere |    3 |none|c2 |c2 |none|c1/2|c2

      |   50 |none|c2 |c2 |none|  c1|c1/2
---------------------------------------------------------------------
* Optimum could differ depending on types of Sets e.g. HashSet, TreeSet,
   so further optimization is thinkable.


(3) Ideal iteration over, according "Set.size() can be expensive":
(I only found ConcurrentSkipListSet, are there others? Anyway, isn't size() anyhow cheaper than 
superfluously looping contains() ?)

           c1    |         Set        |        mere
c2   | elements |   0 |   3 |  50 |   0 |   3 |  50
---------------------------------------------------------------------
      |    0     |c1/2|c1/2|c1/2|c1 |c1 |c1

Set  |    3     |c1/2|c1/2|c1/2|c1 |c1 |c1

      |   50 |c1/2|c1/2|c1/2|c1 |c1 |c1
---------------------------------------------------------------------
      |    0 |c2 |c2 |c2 |none |none|none

mere |    3 |  c2 |c2 |c2 |none|c1/2|c2

      |   50 |c2 |c2 |c2|none|  c1|c1/2
---------------------------------------------------------------------


Why you introduce variables iterate and contains?
You could simply swap c1 with c2...

Shortest code for (2) with minimal swapping:

         int c1size, c2size;
         if ((c1size= c1.size())== 0 || (c2size= c2.size())== 0) {
             // At least one collection is empty. Nothing will match.
             return true;
         }
         if (!(c2 instanceof Set)) Optimize:{
// AsSet'scontains() impl predictably performs better(< O(N/2))
             // thanmere Collection's, iterate over latter c2, except ...
if (!(c1 instanceof Set)) {
                 // If both are mere collections, iterate over smaller collection.
                 // E.g. if c1 contains 3 elements and c2 contains 50 elements and
                 // assuming contains() requires (N+1)/2comparisons thenchecking
                 // for all c1 elements in c2 would require 76.5 comparisons
                 // vs. all c2 elements in c1 would require 100.
                 if (c1size <= c2size) {
                     break Optimize;
                 }
             }
Collection<?> temp = c1;
c1 = c2;
             c2 = temp;
         }

Shortest code for (3), on a par with (1) with minimal swapping:

         if (!(c2 instanceof Set)) Optimize:{
// AsSet'scontains() impl predictably performs better(< O(N/2))
             // thanmere Collection's, iterate over latter c2, except ...
if (!(c1 instanceof Set)) {
                 // Both are mere collections.
                 int c1size, c2size;
                 if ((c1size= c1.size())== 0 || (c2size= c2.size())== 0) {
                     // At least one collection is empty. Nothing will match.
                     return true;
                 }
                 // Iterate over smaller collection.
                 // E.g. if c1 contains 3 elements and c2 contains 50 elements and
                 // assuming contains() requires (N+1)/2comparisons thenchecking
                 // for all c1 elements in c2 would require 76.5 comparisons
                 // vs. all c2 elements in c1 would require 100.
                 if (c1size <= c2size) {
                     break Optimize;
                 }
             }
Collection<?> temp = c1;
c1 = c2;
             c2 = temp;
         }

-Ulf