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

[Ulf Zibis]

Hi, I think you could code shorter:

         Collection<?> iterate;
         Collection<?> contains;

         if (c2 instanceof Set) {
             // C2 or both are sets.
             iterate = c1;
             contains = c2;
         } else if (c1 instanceof Set) {
             // c1 is a Set, c2 is a mere Collection.
             iterate = c2;
             contains = c1;
         } else {
             // Both are mere Collections. Iterate over smaller collection.
             // If e.g. c1 contains 3 elements and c2 contains 50 elements and
             // assuming contains() requires ceiling(n/2) comparisons then
             // checking for all c1 elements in c2 would require 75 comparisons
             // vs. all c2 elements in c1 would require 100.
             int c1size = c1.size();
             int c2size = c2.size();

             if (c1size == 0 || c2size == 0) {
                 // One of the collections is empty. Nothing will match.
                 return true;
             }

             if (c1size < c2size) {
                 iterate = c1;
                 contains = c2;
             } else {
                 iterate = c2;
                 contains = c1;
             }
         }

Or even more shorter:

         Collection<?> iterate = c1;
         Collection<?> contains = c2;

         if (c1 instanceof Set) {
             // c1 is a Set (c2 doesn't care then).
             iterate = c2;
             contains = c1;
         } else if (!(c2 instanceof Set)) {
             // Both are mere Collections. Iterate over smaller collection.
             // If e.g. c1 contains 3 elements and c2 contains 50 elements and
             // assuming contains() requires ceiling(n/2) comparisons then
             // checking for all c1 elements in c2 would require 75 comparisons
             // vs. all c2 elements in c1 would require 100.
             int c1size = c1.size();
             int c2size = c2.size();
             if (c1size == 0 || c2size == 0) {
                 // One of the collections is empty. Nothing will match.
                 return true;
             } else if (c1size > c2size) {
                 iterate = c2;
                 contains = c1;
             }
         }

Minor nits:
- correct indentation to multiples of 4
- insert space after "if"
- start comment phrases with capital letter, if ending with "."
- add "e.g." to comment

-Ulf


Am 20.12.2010 01:29, schrieb Mike Duigou:
> I have updated the webrev for CR 6728865 with Rémi's feedback. The new webrev is at:
>
> http://cr.openjdk.java.net/~mduigou/6728865.1/webrev/
>
> The size() comparisons are now done only when both c1 and c2 are not sets and I have removed the isEmpty() micro-optimization.
>
> Mike