mergiraf/mergiraf
mergiraf/mergiraf
9
213
Fork 45
Code Issues 51 Pull requests 7 Releases 19 Activity Actions

perf: use rustc-hash in more places #215

Merged
ada4a merged 4 commits from ada4a/mergiraf:moar_fxhash into main 2025-02-18 13:29:31 +01:00
Conversation 1 Commits 4 Files changed 5 +28 -25
5 changed files with 28 additions and 25 deletions
Download patch file Download diff file Expand all files Collapse all files

13
src/class_mapping.rs
View file

@ -1,6 +1,7 @@
use std::{collections::HashMap, fmt::Display, hash::Hash};
use std::{fmt::Display, hash::Hash};
use itertools::Itertools;
use rustc_hash::FxHashMap;
use crate::{matching::Matching, pcs::Revision, tree::AstNode};
@ -83,10 +84,10 @@ impl Hash for RevNode<'_> {
/// to PCS, following the 3DM-Merge algorithm from Spork
#[derive(Debug, Default)]
pub struct ClassMapping<'a> {
map: HashMap<RevNode<'a>, Leader<'a>>,
representatives: HashMap<Leader<'a>, HashMap<Revision, RevNode<'a>>>,
exact_matchings: HashMap<Leader<'a>, i8>,
empty_repr: HashMap<Revision, RevNode<'a>>, // stays empty (only there for ownership purposes)
map: FxHashMap<RevNode<'a>, Leader<'a>>,
representatives: FxHashMap<Leader<'a>, FxHashMap<Revision, RevNode<'a>>>,
exact_matchings: FxHashMap<Leader<'a>, i8>,
empty_repr: FxHashMap<Revision, RevNode<'a>>, // stays empty (only there for ownership purposes)
}
impl<'a> ClassMapping<'a> {
@ -140,7 +141,7 @@ impl<'a> ClassMapping<'a> {
/// Finds all the representatives in a cluster designated by its leader.
/// This can return an empty map if the cluster only contains this node!
fn internal_representatives(&self, leader: Leader<'a>) -> &HashMap<Revision, RevNode<'a>> {
fn internal_representatives(&self, leader: Leader<'a>) -> &FxHashMap<Revision, RevNode<'a>> {
self.representatives
.get(&leader)
.unwrap_or(&self.empty_repr)

4
src/matching.rs
View file

@ -1,4 +1,4 @@
use rustc_hash::FxHashMap;
use rustc_hash::{FxHashMap, FxHashSet};
use std::collections::HashSet;
use crate::tree::AstNode;
@ -128,7 +128,7 @@ impl<'tree> Matching<'tree> {
let size_left = left.size();
let size_right = right.size();
let right_descendants: HashSet<&AstNode<'_>> = right.dfs().collect();
let right_descendants: FxHashSet<&AstNode<'_>> = right.dfs().collect();
let mapped = left
.dfs()
.flat_map(|left_descendant| self.get_from_left(left_descendant).into_iter())

15
src/multimap.rs
View file

@ -1,5 +1,5 @@
use rustc_hash::{FxHashMap, FxHashSet};
use std::{
collections::{HashMap, HashSet},
hash::Hash,
iter::{FromIterator, FusedIterator},
};
@ -7,8 +7,8 @@ use std::{
/// A map which associates a set of values to each key.
#[derive(Debug)]
pub struct MultiMap<K, V> {
map: HashMap<K, HashSet<V>>,
empty: HashSet<V>, // stays empty over the entire life of the struct (for convenience in the get method)
map: FxHashMap<K, FxHashSet<V>>,
empty: FxHashSet<V>, // stays empty over the entire life of the struct (for convenience in the get method)
}
impl<K, V> MultiMap<K, V>
@ -19,13 +19,13 @@ where
/// Creates an empty multimap
pub fn new() -> MultiMap<K, V> {
MultiMap {
map: HashMap::new(),
empty: HashSet::new(),
map: FxHashMap::default(),
empty: FxHashSet::default(),
}
}
/// Gets the set of values associated to the key (which might be empty)
pub fn get<Q>(&self, key: &Q) -> &HashSet<V>
pub fn get<Q>(&self, key: &Q) -> &FxHashSet<V>
where
K: std::borrow::Borrow<Q>,
Q: Eq + Hash,
@ -59,7 +59,7 @@ where
}
/// An iterator which groups pairs by key
pub fn iter(&self) -> impl Iterator<Item = (&K, &HashSet<V>)> {
pub fn iter(&self) -> impl Iterator<Item = (&K, &FxHashSet<V>)> {
self.map.iter()
}
@ -107,6 +107,7 @@ where
#[cfg(test)]
mod tests {
use itertools::Itertools;
use std::collections::HashSet;
use super::*;

14
src/tree.rs
View file

@ -2,7 +2,6 @@ use std::{
borrow::Cow,
cell::UnsafeCell,
cmp::{max, min},
collections::HashMap,
fmt::Display,
hash::{Hash, Hasher},
ops::Range,
@ -11,6 +10,7 @@ use std::{
use either::Either;
use itertools::Itertools;
use nu_ansi_term::Color;
use rustc_hash::FxHashMap;
use tree_sitter::{Tree, TreeCursor};
use typed_arena::Arena;
@ -41,7 +41,7 @@ pub struct AstNode<'a> {
/// The children of this node (empty if this is a leaf)
pub children: Vec<&'a AstNode<'a>>,
/// The children indexed by field name
field_to_children: HashMap<&'a str, Vec<&'a AstNode<'a>>>,
field_to_children: FxHashMap<&'a str, Vec<&'a AstNode<'a>>>,
/// The portion of the source code which corresponds to this node
pub source: &'a str,
/// The type of node as returned by tree-sitter
@ -117,7 +117,7 @@ impl<'a> AstNode<'a> {
arena: &'a Arena<AstNode<'a>>,
) -> Result<&'a AstNode<'a>, String> {
let mut children = Vec::new();
let mut field_to_children: HashMap<&'a str, Vec<&'a AstNode<'a>>> = HashMap::new();
let mut field_to_children: FxHashMap<&'a str, Vec<&'a AstNode<'a>>> = FxHashMap::default();
let field_name = cursor.field_name();
let atomic = lang_profile.is_atomic_node_type(cursor.node().grammar_name());
if !atomic && cursor.goto_first_child() {
@ -157,7 +157,7 @@ impl<'a> AstNode<'a> {
children.push(arena.alloc(AstNode {
hash: hasher.finish(),
children: Vec::new(),
field_to_children: HashMap::new(),
field_to_children: FxHashMap::default(),
source: trimmed,
grammar_name: "@virtual_line@",
field_name: None,
@ -410,9 +410,9 @@ impl<'a> AstNode<'a> {
.collect()
};
let field_to_children = if truncate {
HashMap::new()
FxHashMap::default()
} else {
let child_id_map: HashMap<usize, &'b AstNode<'b>> =
let child_id_map: FxHashMap<usize, &'b AstNode<'b>> =
children.iter().map(|child| (child.id, *child)).collect();
self.field_to_children
.iter()
@ -840,7 +840,7 @@ mod tests {
parent: UnsafeCell::new(None),
dfs: UnsafeCell::new(None),
children: node_2.children.to_owned(),
field_to_children: HashMap::new(),
field_to_children: FxHashMap::default(),
byte_range: node_2.byte_range.to_owned(),
..*node_2
};

7
src/tree_builder.rs
View file

@ -3,6 +3,7 @@ use std::collections::{HashMap, HashSet};
use either::Either;
use itertools::Itertools;
use log::debug;
use rustc_hash::FxHashSet;
use crate::{
changeset::ChangeSet,
@ -63,7 +64,7 @@ impl VisitingState<'_> {
}
}
type SuccessorsCursor<'a> = HashSet<(Revision, PCSNode<'a>)>;
type SuccessorsCursor<'a> = FxHashSet<(Revision, PCSNode<'a>)>;
impl<'a, 'b> TreeBuilder<'a, 'b> {
/// Create a tree builder from PCS triples, the class mapping and language-specific settings
@ -451,7 +452,7 @@ impl<'a, 'b> TreeBuilder<'a, 'b> {
visiting_state,
)?;
fn strip_revs<'a>(end: &HashSet<(Revision, PCSNode<'a>)>) -> HashSet<PCSNode<'a>> {
fn strip_revs<'a, S>(end: &HashSet<(Revision, PCSNode<'a>), S>) -> HashSet<PCSNode<'a>> {
end.iter().map(|(_, node)| *node).collect()
}
@ -1031,7 +1032,7 @@ impl<'a, 'b> TreeBuilder<'a, 'b> {
}
}
fn fmt_set(s: &HashSet<(Revision, PCSNode<'_>)>) -> String {
fn fmt_set<S>(s: &HashSet<(Revision, PCSNode<'_>), S>) -> String {
s.iter().map(|(r, n)| format!("({r},{n})")).join(", ")
}