Add smaller set first optimisation

dondonz · dondonz · commit b710226f0a7b · 2022-08-08T12:27:03.000+10:00
diff --git a/src/main/java/graphql/normalized/ExecutableNormalizedOperationFactory.java b/src/main/java/graphql/normalized/ExecutableNormalizedOperationFactory.java
@@ -4,7 +4,6 @@
 import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Sets;
 import graphql.Internal;
 import graphql.collect.ImmutableKit;
 import graphql.execution.CoercedVariables;
@@ -50,6 +49,7 @@
 import static graphql.schema.GraphQLTypeUtil.unwrapAll;
 import static graphql.util.FpKit.filterSet;
 import static graphql.util.FpKit.groupingBy;
+import static graphql.util.FpKit.intersection;
 import static java.util.Collections.singleton;
 import static java.util.Collections.singletonList;
 
@@ -454,15 +454,8 @@ private Set<GraphQLObjectType> narrowDownPossibleObjects(Set<GraphQLObjectType>
             return resolvedTypeCondition;
         }
 
-        // Intersection calculation is expensive when either set is large.
-        // If a set only has one member, it is equivalent and cheaper to calculate via contains.
-        if (resolvedTypeCondition.size() == 1 && currentOnes.contains(resolvedTypeCondition.iterator().next())) {
-            return resolvedTypeCondition;
-        } else if (currentOnes.size() == 1 && resolvedTypeCondition.contains(currentOnes.iterator().next())) {
-            return currentOnes;
-        }
-
-        return Sets.intersection(currentOnes, resolvedTypeCondition);
+        // Faster intersection, as either set often has a size of 1.
+        return intersection(currentOnes, resolvedTypeCondition);
     }
 
     private ImmutableSet<GraphQLObjectType> resolvePossibleObjects(List<GraphQLFieldDefinition> defs, GraphQLSchema graphQLSchema) {
diff --git a/src/main/java/graphql/util/FpKit.java b/src/main/java/graphql/util/FpKit.java
@@ -3,14 +3,14 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
 import graphql.Internal;
 
 import java.lang.reflect.Array;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
-import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
@@ -330,4 +330,27 @@ public static <T> Supplier<T> interThreadMemoize(Supplier<T> delegate) {
         return new InterThreadMemoizedSupplier<>(delegate);
     }
 
+    /**
+     * Faster set intersection.
+     *
+     * @param set1 first set
+     * @param set2 second set
+     * @return intersection set
+     */
+    public static <T> Set<T> intersection(Set<T> set1, Set<T> set2) {
+        // Set intersection calculation is expensive when either set is large. Often, either set has only one member.
+        // When either set contains only one member, it is equivalent and much cheaper to calculate intersection via contains.
+        if (set1.size() == 1 && set2.contains(set1.iterator().next())) {
+            return set1;
+        } else if (set2.size() == 1 && set1.contains(set2.iterator().next())) {
+            return set2;
+        }
+
+        // Guava's Sets.intersection is faster when the smaller set is passed as the first argument.
+        if (set1.size() < set2.size()) {
+            return Sets.intersection(set1, set2);
+        }
+        return Sets.intersection(set2, set1);
+    }
+
 }
