Fix glob performance regression introduced by commit 3a95f353704dc2f7061e2c0786c2459ac1db0fd1.

AbstractSet#removeAll has unexpected, yet oddly intentional (and documented), performance characteristics. Suppose we are evaluating 'set.removeAll(collection)' and 'collection.contains(x)' is 'O(e)'. Then 'set.removeAll(collection)' is 'O(set.size())' when 'set.size() <= collection.size()' and 'O(set.size()) * e' otherwise. When 'collection' is e.g. an ArrayList, 'e' is 'collection.size()' and so 'set.removeAll(collection)' is 'O(set.size() * collection.size())', which is bad.

This meant we had poor performance when the excludes patterns of a glob matched more files than the includes patterns.

Note that, while GlobCache#glob() *did* also use removeAll (potentially inefficiently), it was doing so for each list of exclude glob matches individually. So legacy globbing would have suboptimal performance for 'glob(includes=[i_1, i_2, ...i_k], excludes = [e_1, e_2, ..., e_j])' whenever the result of any e_i was larger than the union of all the includes matches. (But skyframe hybrid globbing has the performance issue when the union of the excludes matches is larger than the union of the includes matches, which is more likely to happen in practice.) I fixed this hypothetical problem too.

--
MOS_MIGRATED_REVID=117367755

2 files changed, 6 insertions, 2 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index 748d9abc8f..45e36ed90b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -274,7 +274,9 @@ public class GlobCache {
       results.addAll(getGlob(pattern, excludeDirs));
     }
     for (String pattern : excludes) {
-      results.removeAll(getGlob(pattern, excludeDirs));
+      for (String excludeMatch : getGlob(pattern, excludeDirs)) {
+        results.remove(excludeMatch);
+      }
     }
 
     Preconditions.checkState(!results.contains(null), "glob returned null");
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index fc53e9ee22..40210495c4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -1031,7 +1031,9 @@ public class PackageFunction implements SkyFunction {
             matches.remove(match.getPathString());
           }
         }
-        matches.removeAll(delegate.fetch(delegateExcludesToken));
+        for (String delegateExcludeMatch : delegate.fetch(delegateExcludesToken)) {
+          matches.remove(delegateExcludeMatch);
+        }
         return Lists.newArrayList(matches);
       }