commit 0f4995615fc2dec3185c422b5fc1272bd0c8541a
author Nathan Harmata <nharmata@google.com> Fri Aug 28 16:59:10 2015 +0000
committer Kristina Chodorow <kchodorow@google.com> Mon Aug 31 19:09:27 2015 +0000
tree 30e75a30ac644ec79df94ea9a62310106f8b8621
parent 5d83e0f0db359c9133b058034e936bbad5604dd2

In GlobVisitor, use a ConcurrentHashSet and sort the results at the end rather than use a synchronized TreeSet that maintains the result in sorted order.

Consider M adds to the set resulting in N unique elements (so M >= N). The old approach was O(MlogN) and the new approach is O(M + NlogN) and has less lock contention; the time spent holding the lock is O(N) vs O(MlogN) - and actually ought to be small in practice because of the internal striping in CHS.

--
MOS_MIGRATED_REVID=101784791

src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java

diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
index 6e1a066..3c16e8e 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
@@ -25,6 +25,7 @@
 import com.google.common.cache.CacheLoader;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
 import com.google.common.collect.Sets;
 import com.google.common.util.concurrent.ForwardingListenableFuture;
 import com.google.common.util.concurrent.Futures;
@@ -505,7 +506,7 @@
       delegate.setException(exception);
     }
 
-    public void set(ArrayList<Path> paths) {
+    public void set(List<Path> paths) {
       delegate.set(paths);
     }
 
@@ -527,8 +528,7 @@
    */
   private static final class GlobVisitor {
     // These collections are used across workers and must therefore be thread-safe.
-    private final Collection<Path> results =
-        Collections.synchronizedSet(Sets.<Path>newTreeSet());
+    private final Collection<Path> results = Sets.newConcurrentHashSet();
     private final Cache<String, Pattern> cache = CacheBuilder.newBuilder().build(
         new CacheLoader<String, Pattern>() {
             @Override
@@ -683,7 +683,7 @@
         } else if (failure.get() != null) {
           result.setException(failure.get());
         } else {
-          result.set(new ArrayList<>(results));
+          result.set(Ordering.<Path>natural().immutableSortedCopy(results));
         }
       }
     }