graphql-java · dondonz · Aug 11, 2022 · Aug 4, 2022 · Aug 8, 2022 · Aug 10, 2022
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;
 
@@ -453,7 +453,9 @@ private Set<GraphQLObjectType> narrowDownPossibleObjects(Set<GraphQLObjectType>
         if (currentOnes.isEmpty()) {
             return resolvedTypeCondition;
         }
-        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);
+    }
+
 }
diff --git a/src/test/groovy/graphql/util/FpKitTest.groovy b/src/test/groovy/graphql/util/FpKitTest.groovy
@@ -97,4 +97,41 @@ class FpKitTest extends Specification {
         then:
         l == ["Parrot"]
     }
+
+    def "set intersection works"() {
+        def set1 = ["A","B","C"] as Set
+        def set2 = ["A","C","D"] as Set
+        def singleSetA = ["A"] as Set
+        def disjointSet = ["X","Y"] as Set
+
+        when:
+        def intersection = FpKit.intersection(set1, set2)
+        then:
+        intersection == ["A","C"] as Set
+
+        when: // reversed parameters
+        intersection = FpKit.intersection(set2, set1)
+        then:
+        intersection == ["A","C"] as Set
+
+        when: // singles
+        intersection = FpKit.intersection(set1, singleSetA)
+        then:
+        intersection == ["A"] as Set
+
+        when: // singles reversed
+        intersection = FpKit.intersection(singleSetA, set1)
+        then:
+        intersection == ["A"] as Set
+
+        when: // disjoint
+        intersection = FpKit.intersection(set1, disjointSet)
+        then:
+        intersection.isEmpty()
+
+        when: // disjoint reversed
+        intersection = FpKit.intersection(disjointSet,set1)
+        then:
+        intersection.isEmpty()
+    }
 }
diff --git a/src/test/java/benchmark/NQExtraLargeBenchmark.java b/src/test/java/benchmark/NQExtraLargeBenchmark.java
@@ -0,0 +1,89 @@
+package benchmark;
+
+import com.google.common.base.Charsets;
+import com.google.common.io.Resources;
+import graphql.execution.CoercedVariables;
+import graphql.language.Document;
+import graphql.normalized.ExecutableNormalizedOperation;
+import graphql.normalized.ExecutableNormalizedOperationFactory;
+import graphql.parser.Parser;
+import graphql.schema.GraphQLSchema;
+import graphql.schema.idl.SchemaGenerator;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Threads;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+import java.io.IOException;
+import java.net.URL;
+import java.util.concurrent.TimeUnit;
+
+import static com.google.common.io.Resources.getResource;
+
+@State(Scope.Benchmark)
+@BenchmarkMode(Mode.Throughput)
+@Warmup(iterations = 2)
+@Measurement(iterations = 2, timeUnit = TimeUnit.NANOSECONDS)
+public class NQExtraLargeBenchmark {
+
+    @State(Scope.Benchmark)
+    public static class MyState {
+
+        GraphQLSchema schema;
+        Document document;
+
+        @Setup
+        public void setup() {
+            try {
+                String schemaString = readFromClasspath("extra-large-schema-1.graphqls");
+                schema = SchemaGenerator.createdMockedSchema(schemaString);
+
+                String query = readFromClasspath("extra-large-schema-1-query.graphql");
+                document = Parser.parse(query);
+            } catch (Exception e) {
+                System.out.println(e);
+                throw new RuntimeException(e);
+            }
+        }
+
+        private String readFromClasspath(String file) throws IOException {
+            URL url = getResource(file);
+            return Resources.toString(url, Charsets.UTF_8);
+        }
+    }
+
+    @Benchmark
+    @Warmup(iterations = 2)
+    @Measurement(iterations = 3, time = 10)
+    @Threads(1)
+    @Fork(3)
+    @BenchmarkMode(Mode.AverageTime)
+    @OutputTimeUnit(TimeUnit.MILLISECONDS)
+    public void benchMarkAvgTime(MyState myState, Blackhole blackhole )  {
+        runImpl(myState, blackhole);
+    }
+
+    @Benchmark
+    @Warmup(iterations = 2)
+    @Measurement(iterations = 3, time = 10)
+    @Threads(1)
+    @Fork(3)
+    @BenchmarkMode(Mode.Throughput)
+    @OutputTimeUnit(TimeUnit.SECONDS)
+    public void benchMarkThroughput(MyState myState, Blackhole blackhole )  {
+        runImpl(myState, blackhole);
+    }
+
+    private void runImpl(MyState myState, Blackhole blackhole) {
+        ExecutableNormalizedOperation executableNormalizedOperation = ExecutableNormalizedOperationFactory.createExecutableNormalizedOperation(myState.schema, myState.document, null, CoercedVariables.emptyVariables());
+        blackhole.consume(executableNormalizedOperation);
+    }
+}