Repository: apollographql/apollo-rs
Pull request #881 (2024-07-15 08:36:50)

Introduce a faster hasher
This changeset introduces ahash, a hasher that is faster than the one provided by the stdlib.

It exposes a collections::fast module, that can be used by other libraries that rely on apollo-rs types. This makes it easier for the apollo-rs to swap implementations in the future if needs be.


Patch:
diff --git a/crates/apollo-compiler/Cargo.toml b/crates/apollo-compiler/Cargo.toml
index 67846c2..6f18efe 100644
--- a/crates/apollo-compiler/Cargo.toml
+++ b/crates/apollo-compiler/Cargo.toml
@@ -18,6 +18,7 @@ edition = "2021"
 autotests = false # Most tests/*.rs files are modules of tests/main.rs
 
 [dependencies]
+ahash = "0.8.11"
 apollo-parser = { path = "../apollo-parser", version = "0.7.7" }
 ariadne = { version = "0.4.1", features = ["auto-color"] }
 indexmap = "2.0.0"
diff --git a/crates/apollo-compiler/src/collections.rs b/crates/apollo-compiler/src/collections.rs
new file mode 100644
index 0000000..a863d05
--- /dev/null
+++ b/crates/apollo-compiler/src/collections.rs
@@ -0,0 +1,10 @@
+//! Type aliases for hashing-based collections configured with a specific hasher,
+//! as used in various places thorough the API
+
+use indexmap::IndexMap as IM;
+use indexmap::IndexSet as IS;
+
+pub type IndexMap<K, V> = IM<K, V, ahash::RandomState>;
+pub type IndexSet<T> = IS<T, ahash::RandomState>;
+pub type HashMap<K, V> = std::collections::HashMap<K, V, ahash::RandomState>;
+pub type HashSet<T> = std::collections::HashSet<T, ahash::RandomState>;
diff --git a/crates/apollo-compiler/src/executable/from_ast.rs b/crates/apollo-compiler/src/executable/from_ast.rs
index 7df32fb..74ce323 100644
--- a/crates/apollo-compiler/src/executable/from_ast.rs
+++ b/crates/apollo-compiler/src/executable/from_ast.rs
@@ -14,7 +14,7 @@ pub(crate) fn document_from_ast(
 ) -> ExecutableDocument {
     let mut operations = OperationMap::default();
     let mut multiple_anonymous = false;
-    let mut fragments = IndexMap::new();
+    let mut fragments = IndexMap::with_hasher(Default::default());
     let mut errors = BuildErrors {
         errors,
         path: SelectionPath {
diff --git a/crates/apollo-compiler/src/executable/mod.rs b/crates/apollo-compiler/src/executable/mod.rs
index 32aa31e..34b8d5d 100644
--- a/crates/apollo-compiler/src/executable/mod.rs
+++ b/crates/apollo-compiler/src/executable/mod.rs
@@ -2,6 +2,7 @@
 //! which can contain operations and fragments.
 
 use crate::ast;
+use crate::collections::IndexMap;
 use crate::coordinate::FieldArgumentCoordinate;
 use crate::coordinate::TypeAttributeCoordinate;
 use crate::schema;
@@ -9,7 +10,6 @@ use crate::Node;
 use crate::Parser;
 use crate::Schema;
 use indexmap::map::Entry;
-use indexmap::IndexMap;
 use std::collections::HashSet;
 use std::path::Path;
 
diff --git a/crates/apollo-compiler/src/execution/engine.rs b/crates/apollo-compiler/src/execution/engine.rs
index c840a7d..a434e23 100644
--- a/crates/apollo-compiler/src/execution/engine.rs
+++ b/crates/apollo-compiler/src/execution/engine.rs
@@ -1,4 +1,5 @@
 use crate::ast::Value;
+use crate::collections::IndexMap;
 use crate::executable::Field;
 use crate::executable::Selection;
 use crate::execution::input_coercion::coerce_argument_values;
@@ -20,7 +21,6 @@ use crate::ExecutableDocument;
 use crate::Name;
 use crate::Schema;
 use crate::SourceMap;
-use indexmap::IndexMap;
 use std::collections::HashSet;
 
 /// <https://spec.graphql.org/October2021/#sec-Normal-and-Serial-Execution>
@@ -59,7 +59,7 @@ pub(crate) fn execute_selection_set<'a>(
     object_value: &ObjectValue<'_>,
     selections: impl IntoIterator<Item = &'a Selection>,
 ) -> Result<JsonMap, PropagateNull> {
-    let mut grouped_field_set = IndexMap::new();
+    let mut grouped_field_set = IndexMap::with_hasher(Default::default());
     collect_fields(
         schema,
         document,
diff --git a/crates/apollo-compiler/src/execution/introspection_split.rs b/crates/apollo-compiler/src/execution/introspection_split.rs
index 756b611..a36fec5 100644
--- a/crates/apollo-compiler/src/execution/introspection_split.rs
+++ b/crates/apollo-compiler/src/execution/introspection_split.rs
@@ -1,4 +1,6 @@
 use crate::ast;
+use crate::collections::HashSet;
+use crate::collections::IndexMap;
 use crate::executable::Field;
 use crate::executable::Fragment;
 use crate::executable::FragmentSpread;
@@ -20,8 +22,6 @@ use crate::Node;
 use crate::Schema;
 use crate::SourceMap;
 use indexmap::map::Entry;
-use indexmap::IndexMap;
-use std::collections::HashSet;
 
 /// Result of [`split`][Self::split]ting [schema introspection] fields from an operation.
 ///
@@ -105,7 +105,7 @@ impl SchemaIntrospectionSplit {
             return Ok(Self::None);
         }
 
-        let mut fragments_info = IndexMap::new();
+        let mut fragments_info = IndexMap::with_hasher(Default::default());
         let operation_field_kinds =
             collect_field_kinds(document, &mut fragments_info, &operation.selection_set)?;
         if operation_field_kinds.schema_introspection.is_none() {
@@ -122,7 +122,7 @@ impl SchemaIntrospectionSplit {
                 make_single_operation_document(schema, document, new_operation, fragments);
             Ok(Self::Only(SchemaIntrospectionQuery(introspection_document)))
         } else {
-            let mut fragments_done = HashSet::new();
+            let mut fragments_done = HashSet::with_hasher(Default::default());
             let mut new_documents = Split {
                 introspection: DocumentBuilder::new(document, operation),
                 other: DocumentBuilder::new(document, operation),
@@ -197,8 +197,8 @@ fn check_non_query<'doc>(
         ),
         location: field.location(),
     };
-    let mut fragments_visited = HashSet::new();
-    let mut fragments_to_visit = HashSet::new();
+    let mut fragments_visited = HashSet::with_hasher(Default::default());
+    let mut fragments_to_visit = HashSet::with_hasher(Default::default());
     check_selection_set(
         &mut fragments_visited,
         &mut fragments_to_visit,
diff --git a/crates/apollo-compiler/src/lib.rs b/crates/apollo-compiler/src/lib.rs
index 1de45be..707bd3d 100644
--- a/crates/apollo-compiler/src/lib.rs
+++ b/crates/apollo-compiler/src/lib.rs
@@ -3,6 +3,7 @@
 #[macro_use]
 mod macros;
 pub mod ast;
+pub mod collections;
 pub mod coordinate;
 pub mod diagnostic;
 pub mod executable;
diff --git a/crates/apollo-compiler/src/parser.rs b/crates/apollo-compiler/src/parser.rs
index fe4314f..29f69ff 100644
--- a/crates/apollo-compiler/src/parser.rs
+++ b/crates/apollo-compiler/src/parser.rs
@@ -1,6 +1,7 @@
 use crate::ast;
 use crate::ast::from_cst::Convert;
 use crate::ast::Document;
+use crate::collections::IndexMap;
 use crate::executable;
 use crate::execution::GraphQLLocation;
 use crate::schema::SchemaBuilder;
@@ -12,7 +13,6 @@ use crate::validation::WithErrors;
 use crate::ExecutableDocument;
 use crate::NodeLocation;
 use crate::Schema;
-use indexmap::IndexMap;
 use std::path::Path;
 use std::path::PathBuf;
 use std::sync::Arc;
diff --git a/crates/apollo-compiler/src/schema/from_ast.rs b/crates/apollo-compiler/src/schema/from_ast.rs
index 65d77a9..a226e3f 100644
--- a/crates/apollo-compiler/src/schema/from_ast.rs
+++ b/crates/apollo-compiler/src/schema/from_ast.rs
@@ -45,13 +45,13 @@ impl SchemaBuilder {
                             mutation: None,
                             subscription: None,
                         }),
-                        directive_definitions: IndexMap::new(),
-                        types: IndexMap::new(),
+                        directive_definitions: IndexMap::with_hasher(Default::default()),
+                        types: IndexMap::with_hasher(Default::default()),
                     },
                     schema_definition: SchemaDefinitionStatus::NoneSoFar {
                         orphan_extensions: Vec::new(),
                     },
-                    orphan_type_extensions: IndexMap::new(),
+                    orphan_type_extensions: IndexMap::with_hasher(Default::default()),
                     errors: DiagnosticList::new(Default::default()),
                 };
                 let input = include_str!("../built_in_types.graphql").to_owned();
@@ -941,7 +941,7 @@ fn collect_sticky<'a, V>(
     iter: impl IntoIterator<Item = (&'a Name, V)>,
     duplicate: impl FnMut(&Name, V),
 ) -> IndexMap<Name, V> {
-    let mut map = IndexMap::new();
+    let mut map = IndexMap::with_hasher(Default::default());
     extend_sticky(&mut map, iter, duplicate);
     map
 }
@@ -964,7 +964,7 @@ fn collect_sticky_set(
     iter: impl IntoIterator<Item = ComponentName>,
     duplicate: impl FnMut(&ComponentName, ComponentName),
 ) -> IndexSet<ComponentName> {
-    let mut set = IndexSet::new();
+    let mut set = IndexSet::with_hasher(Default::default());
     extend_sticky_set(&mut set, iter, duplicate);
     set
 }
diff --git a/crates/apollo-compiler/src/schema/mod.rs b/crates/apollo-compiler/src/schema/mod.rs
index 1e7c17c..63a8b85 100644
--- a/crates/apollo-compiler/src/schema/mod.rs
+++ b/crates/apollo-compiler/src/schema/mod.rs
@@ -1,12 +1,12 @@
 //! High-level representation of a GraphQL schema
 
 use crate::ast;
+use crate::collections::IndexMap;
+use crate::collections::IndexSet;
 use crate::validation::FileId;
 use crate::Node;
 use crate::NodeLocation;
 use crate::Parser;
-use indexmap::IndexMap;
-use indexmap::IndexSet;
 use std::collections::HashMap;
 use std::collections::HashSet;
 use std::path::Path;
diff --git a/crates/apollo-compiler/src/validation/field.rs b/crates/apollo-compiler/src/validation/field.rs
index 54e5011..429c6b9 100644
--- a/crates/apollo-compiler/src/validation/field.rs
+++ b/crates/apollo-compiler/src/validation/field.rs
@@ -1,4 +1,5 @@
 use crate::ast;
+use crate::collections::IndexMap;
 use crate::coordinate::FieldArgumentCoordinate;
 use crate::coordinate::TypeAttributeCoordinate;
 use crate::executable;
@@ -10,7 +11,6 @@ use crate::validation::OperationValidationContext;
 use crate::ExecutableDocument;
 use crate::Name;
 use crate::Node;
-use indexmap::IndexMap;
 
 pub(crate) fn validate_field(
     diagnostics: &mut DiagnosticList,
diff --git a/crates/apollo-compiler/src/validation/interface.rs b/crates/apollo-compiler/src/validation/interface.rs
index b7c8cd6..f9c79b1 100644
--- a/crates/apollo-compiler/src/validation/interface.rs
+++ b/crates/apollo-compiler/src/validation/interface.rs
@@ -1,4 +1,5 @@
 use crate::ast;
+use crate::collections::IndexSet;
 use crate::schema::ComponentName;
 use crate::schema::ExtendedType;
 use crate::schema::InterfaceType;
@@ -8,7 +9,6 @@ use crate::validation::field::validate_field_definitions;
 use crate::validation::DiagnosticList;
 use crate::Node;
 use crate::NodeLocation;
-use indexmap::IndexSet;
 
 pub(crate) fn validate_interface_definitions(
     diagnostics: &mut DiagnosticList,
diff --git a/crates/apollo-compiler/src/validation/mod.rs b/crates/apollo-compiler/src/validation/mod.rs
index 8e1baea..16db70e 100644
--- a/crates/apollo-compiler/src/validation/mod.rs
+++ b/crates/apollo-compiler/src/validation/mod.rs
@@ -23,6 +23,7 @@ pub(crate) mod union_;
 pub(crate) mod value;
 pub(crate) mod variable;
 
+use crate::collections::IndexSet;
 use crate::diagnostic::CliReport;
 use crate::diagnostic::Diagnostic;
 use crate::diagnostic::ToCliReport;
@@ -40,7 +41,6 @@ use crate::Name;
 use crate::Node;
 use crate::NodeLocation;
 use crate::SourceMap;
-use indexmap::IndexSet;
 use std::collections::HashMap;
 use std::fmt;
 use std::sync::Arc;
@@ -1102,7 +1102,7 @@ struct RecursionStack {
 impl RecursionStack {
     fn new() -> Self {
         Self {
-            seen: IndexSet::new(),
+            seen: IndexSet::with_hasher(Default::default()),
             high: 0,
             limit: DEFAULT_RECURSION_LIMIT,
         }
diff --git a/crates/apollo-compiler/src/validation/selection.rs b/crates/apollo-compiler/src/validation/selection.rs
index 4889889..ec5fbe0 100644
--- a/crates/apollo-compiler/src/validation/selection.rs
+++ b/crates/apollo-compiler/src/validation/selection.rs
@@ -1,5 +1,6 @@
 use crate::ast;
 use crate::ast::NamedType;
+use crate::collections::IndexMap;
 use crate::coordinate::TypeAttributeCoordinate;
 use crate::executable;
 use crate::executable::BuildError;
@@ -14,14 +15,11 @@ use crate::ExecutableDocument;
 use crate::Name;
 use crate::Node;
 use apollo_parser::LimitTracker;
-use indexmap::IndexMap;
 use std::cell::OnceCell;
 use std::collections::HashMap;
 use std::collections::HashSet;
 use std::collections::VecDeque;
-use std::hash::BuildHasher;
 use std::hash::Hash;
-use std::hash::RandomState;
 use std::rc::Rc;
 use std::sync::OnceLock;
 
@@ -46,9 +44,9 @@ impl<'a> Hash for FieldSelection<'a> {
 
 impl<'a> FieldSelection<'a> {
     fn new(parent_type: &'a NamedType, field: &'a Node<executable::Field>) -> Self {
-        static SHARED_RANDOM: OnceLock<RandomState> = OnceLock::new();
+        static SHARED_RANDOM: OnceLock<ahash::RandomState> = OnceLock::new();
         let hash = SHARED_RANDOM
-            .get_or_init(RandomState::new)
+            .get_or_init(Default::default)
             .hash_one((parent_type, field));
         Self {
             hash,
@@ -72,7 +70,7 @@ pub(crate) fn expand_selections<'doc>(
 ) -> Vec<FieldSelection<'doc>> {
     let mut selections = vec![];
     let mut queue: VecDeque<&executable::SelectionSet> = selection_sets.collect();
-    let mut seen_fragments = HashSet::new();
+    let mut seen_fragments = HashSet::with_hasher(ahash::RandomState::new());
 
     while let Some(next_set) = queue.pop_front() {
         for selection in &next_set.selections {
@@ -84,9 +82,8 @@ pub(crate) fn expand_selections<'doc>(
                     queue.push_back(&spread.selection_set)
                 }
                 executable::Selection::FragmentSpread(spread)
-                    if !seen_fragments.contains(&spread.fragment_name) =>
+                    if seen_fragments.insert(&spread.fragment_name) =>
                 {
-                    seen_fragments.insert(&spread.fragment_name);
                     if let Some(fragment) = fragments.get(&spread.fragment_name) {
                         queue.push_back(&fragment.selection_set);
                     }
@@ -424,7 +421,7 @@ impl<'alloc, 'doc> MergedFieldSet<'alloc, 'doc> {
         alloc: &'alloc Arena<'doc>,
     ) -> &IndexMap<schema::Name, &'alloc [FieldSelection<'doc>]> {
         self.grouped_by_output_names.get_or_init(|| {
-            let mut map = IndexMap::<_, Vec<_>>::new();
+            let mut map = IndexMap::<_, Vec<_>>::with_hasher(Default::default());
             for selection in self.selections {
                 map.entry(selection.field.response_key().clone())
                     .or_default()
@@ -446,7 +443,7 @@ impl<'alloc, 'doc> MergedFieldSet<'alloc, 'doc> {
     ) -> &Vec<&'alloc [FieldSelection<'doc>]> {
         self.grouped_by_common_parents.get_or_init(|| {
             let mut abstract_parents = vec![];
-            let mut concrete_parents = IndexMap::<_, Vec<_>>::new();
+            let mut concrete_parents = IndexMap::<_, Vec<_>>::with_hasher(Default::default());
             for selection in self.selections {
                 match schema.types.get(selection.parent_type) {
                     Some(schema::ExtendedType::Object(object)) => {
@@ -498,7 +495,11 @@ pub(crate) struct FieldsInSetCanMerge<'alloc, 's, 'doc> {
     ///
     /// The value is an Rc because it needs to have an independent lifetime from `self`,
     /// so the cache can be updated while a field set is borrowed.
-    cache: HashMap<&'alloc [FieldSelection<'doc>], Rc<MergedFieldSet<'alloc, 'doc>>>,
+    cache: HashMap<
+        &'alloc [FieldSelection<'doc>],
+        Rc<MergedFieldSet<'alloc, 'doc>>,
+        ahash::RandomState,
+    >,
     // The recursion limit is used for two separate recursions, but they are not interleaved,
     // so the effective limit does apply to field nesting levels in both cases.
     recursion_limit: LimitTracker,


Test patch:
diff --git a/crates/apollo-compiler/tests/merge_schemas.rs b/crates/apollo-compiler/tests/merge_schemas.rs
index 7f06316..10bac83 100644
--- a/crates/apollo-compiler/tests/merge_schemas.rs
+++ b/crates/apollo-compiler/tests/merge_schemas.rs
@@ -1,11 +1,11 @@
 use apollo_compiler::ast;
+use apollo_compiler::collections::IndexMap;
+use apollo_compiler::collections::IndexSet;
 use apollo_compiler::schema;
 use apollo_compiler::schema::Component;
 use apollo_compiler::schema::ComponentName;
 use apollo_compiler::schema::ExtendedType;
 use apollo_compiler::Schema;
-use indexmap::IndexMap;
-use indexmap::IndexSet;
 
 type MergeError = &'static str;
 
diff --git a/crates/apollo-compiler/tests/snapshot_tests.rs b/crates/apollo-compiler/tests/snapshot_tests.rs
index 0cf68b9..4bd5f82 100644
--- a/crates/apollo-compiler/tests/snapshot_tests.rs
+++ b/crates/apollo-compiler/tests/snapshot_tests.rs
@@ -8,6 +8,7 @@
 // Note: ALL #[test] functions must also have #[serial], to make FileId::reset work correctly
 
 use apollo_compiler::ast;
+use apollo_compiler::collections::IndexMap;
 use apollo_compiler::name;
 use apollo_compiler::schema;
 use apollo_compiler::ty;
@@ -15,7 +16,6 @@ use apollo_compiler::validation::DiagnosticList;
 use apollo_compiler::FileId;
 use apollo_compiler::Schema;
 use expect_test::expect_file;
-use indexmap::IndexMap;
 use serial_test::serial;
 use std::env;
 use std::fmt::Write;
@@ -187,7 +187,7 @@ fn graphql_files_in_dir(dir: &Path) -> Vec<PathBuf> {
     paths.sort();
 
     // Check for duplicate numbers.
-    let mut seen = IndexMap::new();
+    let mut seen = IndexMap::with_hasher(Default::default());
     let next_number = paths.len() + 1;
     for path in &paths {
         let file_name = path.file_name().unwrap().to_string_lossy();
@@ -249,7 +249,8 @@ fn test_invalid_synthetic_node() {
                 }
                 .into(),
             )]
-            .into(),
+            .into_iter()
+            .collect(),
         }
         .into(),
     );