rust-performance: introduce FastHashMap type alias for HashMap

Rust's default hashing is slow, because it is meant for preventing collision
attacks.
For all of the current Rust code, we don't care about those attacks, because
if an person with bad intentions has write access to your repo, you have other
issues.

I've chosen to use the TwoXHash crate because it was made by a reputable member
of the Rust community and has very good benchmarks.

For now it does not seem to improve performance by much for the current code,
but it's something else to not worry about when benchmarking code: in a
previous experiment with copytracing in Rust, it accounted for more than 10%
of the time of the entire script.

Differential Revision: https://phab.mercurial-scm.org/D7116

rust/Cargo.lock

@@ -32,6 +32,15 b' version = "1.3.2"'
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "c2-chacha"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "ppv-lite86 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "cfg-if"
 version = "0.1.10"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -105,6 +114,16 b' version = "0.1.1"'
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "getrandom"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
+ "wasi 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
 dependencies = [
@@ -115,6 +134,7 b' dependencies = ['
  "rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "twox-hash 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
@@ -179,6 +199,11 b' dependencies = ['
 ]
 
 [[package]]
+name = "ppv-lite86"
+version = "0.2.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "python27-sys"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -215,6 +240,18 b' dependencies = ['
 ]
 
 [[package]]
+name = "rand"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_chacha"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -224,6 +261,15 b' dependencies = ['
 ]
 
 [[package]]
+name = "rand_chacha"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "c2-chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_core"
 version = "0.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -237,6 +283,14 b' version = "0.4.2"'
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "rand_core"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_hc"
 version = "0.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -245,6 +299,14 b' dependencies = ['
 ]
 
 [[package]]
+name = "rand_hc"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_isaac"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -373,6 +435,19 b' dependencies = ['
 ]
 
 [[package]]
+name = "twox-hash"
+version = "1.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "wasi"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "winapi"
 version = "0.3.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -397,6 +472,7 b' source = "registry+https://github.com/ru'
 "checksum autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "b671c8fb71b457dd4ae18c4ba1e59aa81793daacc361d82fcd410cef0d491875"
 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
 "checksum byteorder 1.3.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a7c3dd8985a7111efc5c80b44e23ecdd8c007de8ade3b96595387e812b957cf5"
+"checksum c2-chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7d64d04786e0f528460fc884753cf8dddcc466be308f6026f8e355c41a0e4101"
 "checksum cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
 "checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "85532c648315aeb0829ad216a6a29aa3212cf9319bc7f6daf1404aa0bdd1485f"
@@ -406,6 +482,7 b' source = "registry+https://github.com/ru'
 "checksum crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)" = "04973fa96e96579258a5091af6003abde64af786b860f18622b82e026cca60e6"
 "checksum either 1.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3"
 "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
+"checksum getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)" = "473a1265acc8ff1e808cd0a1af8cee3c2ee5200916058a2ca113c29f2d903571"
 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
 "checksum libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)" = "74dfca3d9957906e8d1e6a0b641dc9a59848e793f1da2165889fd4f62d10d79c"
 "checksum memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "88579771288728879b57485cc7d6b07d648c9f0141eb955f8ab7f9d45394468e"
@@ -413,13 +490,18 b' source = "registry+https://github.com/ru'
 "checksum nodrop 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)" = "72ef4a56884ca558e5ddb05a1d1e7e1bfd9a68d9ed024c21704cc98872dae1bb"
 "checksum num-traits 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "6ba9a427cfca2be13aa6f6403b0b7e7368fe982bfa16fccc450ce74c46cd9b32"
 "checksum num_cpus 1.10.1 (registry+https://github.com/rust-lang/crates.io-index)" = "bcef43580c035376c0705c42792c294b66974abbfd2789b511784023f71f3273"
+"checksum ppv-lite86 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e3cbf9f658cdb5000fcf6f362b8ea2ba154b9f146a61c7a20d647034c6b6561b"
 "checksum python27-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "372555e88a6bc8109eb641380240dc8d25a128fc48363ec9075664daadffdd5b"
 "checksum python3-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f3a8ebed3f1201fda179f3960609dbbc10cd8c75e9f2afcb03788278f367d8ea"
 "checksum rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca"
+"checksum rand 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "3ae1b169243eaf61759b8475a998f0a385e42042370f3a7dbaf35246eacc8412"
 "checksum rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef"
+"checksum rand_chacha 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "03a2a90da8c7523f554344f921aa97283eadf6ac484a6d2a7d0212fa7f8d6853"
 "checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b"
 "checksum rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9c33a3c44ca05fa6f1807d8e6743f3824e8509beca625669633be0acbdf509dc"
+"checksum rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
 "checksum rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4"
+"checksum rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ca3129af7b92a17112d59ad498c6f81eaf463253766b90396d39ea7a39d6613c"
 "checksum rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08"
 "checksum rand_jitter 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "1166d5c91dc97b88d1decc3285bb0a99ed84b05cfd0bc2341bdf2d43fc41e39b"
 "checksum rand_os 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "7b75f676a1e053fc562eafbb47838d67c84801e38fc1ba459e8f180deabd5071"
@@ -435,6 +517,8 b' source = "registry+https://github.com/ru'
 "checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403"
 "checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
 "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b"
+"checksum twox-hash 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3bfd5b7557925ce778ff9b9ef90e3ade34c524b5ff10e239c69a42d546d2af56"
+"checksum wasi 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b89c3ce4ce14bdc6fb6beaf9ec7928ca331de5df7e5ea278375642a2f478570d"
 "checksum winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6"
 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
 "checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"

rust/hg-core/Cargo.toml

@@ -14,5 +14,6 b' lazy_static = "1.3.0"'
 memchr = "2.2.0"
 rand = "0.6.5"
 rand_pcg = "0.1.1"
+rayon = "1.2.0"
 regex = "1.1.0"
-rayon = "1.2.0"
+twox-hash = "1.5.0"

rust/hg-core/src/dirstate.rs

@@ -5,9 +5,8 b''
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
-use crate::{utils::hg_path::HgPathBuf, DirstateParseError};
+use crate::{utils::hg_path::HgPathBuf, DirstateParseError, FastHashMap};
 use std::collections::hash_map;
-use std::collections::HashMap;
 use std::convert::TryFrom;
 
 pub mod dirs_multiset;
@@ -37,9 +36,9 b' pub struct DirstateEntry {'
 /// merge.
 pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
 
-pub type StateMap = HashMap<HgPathBuf, DirstateEntry>;
+pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>;
 pub type StateMapIter<'a> = hash_map::Iter<'a, HgPathBuf, DirstateEntry>;
-pub type CopyMap = HashMap<HgPathBuf, HgPathBuf>;
+pub type CopyMap = FastHashMap<HgPathBuf, HgPathBuf>;
 pub type CopyMapIter<'a> = hash_map::Iter<'a, HgPathBuf, HgPathBuf>;
 
 #[derive(Copy, Clone, Debug, Eq, PartialEq)]

rust/hg-core/src/dirstate/dirs_multiset.rs

@@ -11,16 +11,16 b''
 use crate::utils::hg_path::{HgPath, HgPathBuf};
 use crate::{
     dirstate::EntryState, utils::files, DirstateEntry, DirstateMapError,
+    FastHashMap,
 };
 use std::collections::hash_map::{self, Entry};
-use std::collections::HashMap;
 
 // could be encapsulated if we care API stability more seriously
 pub type DirsMultisetIter<'a> = hash_map::Keys<'a, HgPathBuf, u32>;
 
 #[derive(PartialEq, Debug)]
 pub struct DirsMultiset {
-    inner: HashMap<HgPathBuf, u32>,
+    inner: FastHashMap<HgPathBuf, u32>,
 }
 
 impl DirsMultiset {
@@ -28,11 +28,11 b' impl DirsMultiset {'
     ///
     /// If `skip_state` is provided, skips dirstate entries with equal state.
     pub fn from_dirstate(
-        vec: &HashMap<HgPathBuf, DirstateEntry>,
+        vec: &FastHashMap<HgPathBuf, DirstateEntry>,
         skip_state: Option<EntryState>,
     ) -> Self {
         let mut multiset = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
 
         for (filename, DirstateEntry { state, .. }) in vec {
@@ -52,7 +52,7 b' impl DirsMultiset {'
     /// Initializes the multiset from a manifest.
     pub fn from_manifest(vec: &Vec<HgPathBuf>) -> Self {
         let mut multiset = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
 
         for filename in vec {
@@ -127,7 +127,6 b' impl DirsMultiset {'
 #[cfg(test)]
 mod tests {
     use super::*;
-    use std::collections::HashMap;
 
     #[test]
     fn test_delete_path_path_not_found() {
@@ -243,13 +242,13 b' mod tests {'
     fn test_dirsmultiset_new_empty() {
         let new = DirsMultiset::from_manifest(&vec![]);
         let expected = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
         assert_eq!(expected, new);
 
-        let new = DirsMultiset::from_dirstate(&HashMap::new(), None);
+        let new = DirsMultiset::from_dirstate(&FastHashMap::default(), None);
         let expected = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
         assert_eq!(expected, new);
     }

rust/hg-core/src/dirstate/dirstate_map.rs

@@ -13,16 +13,16 b' use crate::{'
         hg_path::{HgPath, HgPathBuf},
     },
     CopyMap, DirsMultiset, DirstateEntry, DirstateError, DirstateMapError,
-    DirstateParents, DirstateParseError, StateMap,
+    DirstateParents, DirstateParseError, FastHashMap, StateMap,
 };
 use core::borrow::Borrow;
-use std::collections::{HashMap, HashSet};
+use std::collections::HashSet;
 use std::convert::TryInto;
 use std::iter::FromIterator;
 use std::ops::Deref;
 use std::time::Duration;
 
-pub type FileFoldMap = HashMap<HgPathBuf, HgPathBuf>;
+pub type FileFoldMap = FastHashMap<HgPathBuf, HgPathBuf>;
 
 const NULL_ID: [u8; 20] = [0; 20];
 const MTIME_UNSET: i32 = -1;
@@ -327,7 +327,7 b' impl DirstateMap {'
         if let Some(ref file_fold_map) = self.file_fold_map {
             return file_fold_map;
         }
-        let mut new_file_fold_map = FileFoldMap::new();
+        let mut new_file_fold_map = FileFoldMap::default();
         for (filename, DirstateEntry { state, .. }) in self.state_map.borrow()
         {
             if *state == EntryState::Removed {

rust/hg-core/src/dirstate/parsers.rs

@@ -157,13 +157,12 b' pub fn pack_dirstate('
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::utils::hg_path::HgPathBuf;
-    use std::collections::HashMap;
+    use crate::{utils::hg_path::HgPathBuf, FastHashMap};
 
     #[test]
     fn test_pack_dirstate_empty() {
-        let mut state_map: StateMap = HashMap::new();
-        let copymap = HashMap::new();
+        let mut state_map: StateMap = FastHashMap::default();
+        let copymap = FastHashMap::default();
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
@@ -194,7 +193,7 b' mod tests {'
         .collect();
         let mut state_map = expected_state_map.clone();
 
-        let copymap = HashMap::new();
+        let copymap = FastHashMap::default();
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
@@ -230,7 +229,7 b' mod tests {'
         .cloned()
         .collect();
         let mut state_map = expected_state_map.clone();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
@@ -270,7 +269,7 b' mod tests {'
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
@@ -284,8 +283,8 b' mod tests {'
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,
@@ -341,7 +340,7 b' mod tests {'
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
@@ -359,8 +358,8 b' mod tests {'
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,
@@ -388,7 +387,7 b' mod tests {'
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
@@ -402,8 +401,8 b' mod tests {'
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,

rust/hg-core/src/discovery.rs

@@ -11,12 +11,11 b''
 //! `mercurial.setdiscovery`
 
 use super::{Graph, GraphError, Revision, NULL_REVISION};
-use crate::ancestors::MissingAncestors;
-use crate::dagops;
+use crate::{ancestors::MissingAncestors, dagops, FastHashMap};
 use rand::seq::SliceRandom;
 use rand::{thread_rng, RngCore, SeedableRng};
 use std::cmp::{max, min};
-use std::collections::{HashMap, HashSet, VecDeque};
+use std::collections::{HashSet, VecDeque};
 
 type Rng = rand_pcg::Pcg32;
 
@@ -25,7 +24,7 b' pub struct PartialDiscovery<G: Graph + C'
     graph: G, // plays the role of self._repo
     common: MissingAncestors<G>,
     undecided: Option<HashSet<Revision>>,
-    children_cache: Option<HashMap<Revision, Vec<Revision>>>,
+    children_cache: Option<FastHashMap<Revision, Vec<Revision>>>,
     missing: HashSet<Revision>,
     rng: Rng,
     respect_size: bool,
@@ -61,7 +60,7 b' fn update_sample<I>('
 where
     I: Iterator<Item = Revision>,
 {
-    let mut distances: HashMap<Revision, u32> = HashMap::new();
+    let mut distances: FastHashMap<Revision, u32> = FastHashMap::default();
     let mut visit: VecDeque<Revision> = heads.into_iter().collect();
     let mut factor: u32 = 1;
     let mut seen: HashSet<Revision> = HashSet::new();
@@ -328,7 +327,8 b' impl<G: Graph + Clone> PartialDiscovery<'
         }
         self.ensure_undecided()?;
 
-        let mut children: HashMap<Revision, Vec<Revision>> = HashMap::new();
+        let mut children: FastHashMap<Revision, Vec<Revision>> =
+            FastHashMap::default();
         for &rev in self.undecided.as_ref().unwrap() {
             for p in ParentsIterator::graph_parents(&self.graph, rev)? {
                 children.entry(p).or_insert_with(|| Vec::new()).push(rev);

rust/hg-core/src/filepatterns.rs

@@ -7,10 +7,11 b''
 
 //! Handling of Mercurial-specific patterns.
 
-use crate::{utils::SliceExt, LineNumber, PatternError, PatternFileError};
+use crate::{
+    utils::SliceExt, FastHashMap, LineNumber, PatternError, PatternFileError,
+};
 use lazy_static::lazy_static;
 use regex::bytes::{NoExpand, Regex};
-use std::collections::HashMap;
 use std::fs::File;
 use std::io::Read;
 use std::path::{Path, PathBuf};
@@ -214,8 +215,8 b' pub fn build_single_regex('
 }
 
 lazy_static! {
-    static ref SYNTAXES: HashMap<&'static [u8], &'static [u8]> = {
-        let mut m = HashMap::new();
+    static ref SYNTAXES: FastHashMap<&'static [u8], &'static [u8]> = {
+        let mut m = FastHashMap::default();
 
         m.insert(b"re".as_ref(), b"relre:".as_ref());
         m.insert(b"regexp".as_ref(), b"relre:".as_ref());

rust/hg-core/src/lib.rs

@@ -24,6 +24,8 b' use crate::utils::hg_path::HgPathBuf;'
 pub use filepatterns::{
     build_single_regex, read_pattern_file, PatternSyntax, PatternTuple,
 };
+use std::collections::HashMap;
+use twox_hash::RandomXxHashBuilder64;
 
 /// Mercurial revision numbers
 ///
@@ -53,6 +55,11 b' pub trait Graph {'
 
 pub type LineNumber = usize;
 
+/// Rust's default hasher is too slow because it tries to prevent collision
+/// attacks. We are not concerned about those: if an ill-minded person has
+/// write access to your repository, you have other issues.
+pub type FastHashMap<K, V> = HashMap<K, V, RandomXxHashBuilder64>;
+
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),

rust/hg-cpython/src/parsers.rs

@@ -15,9 +15,9 b' use cpython::{'
 };
 use hg::{
     pack_dirstate, parse_dirstate, utils::hg_path::HgPathBuf,
-    DirstatePackError, DirstateParents, DirstateParseError, PARENT_SIZE,
+    DirstatePackError, DirstateParents, DirstateParseError, FastHashMap,
+    PARENT_SIZE,
 };
-use std::collections::HashMap;
 use std::convert::TryInto;
 
 use crate::dirstate::{extract_dirstate, make_dirstate_tuple};
@@ -29,8 +29,8 b' fn parse_dirstate_wrapper('
     copymap: PyDict,
     st: PyBytes,
 ) -> PyResult<PyTuple> {
-    let mut dirstate_map = HashMap::new();
-    let mut copies = HashMap::new();
+    let mut dirstate_map = FastHashMap::default();
+    let mut copies = FastHashMap::default();
 
     match parse_dirstate(&mut dirstate_map, &mut copies, st.data(py)) {
         Ok(parents) => {
@@ -85,7 +85,7 b' fn pack_dirstate_wrapper('
 
     let mut dirstate_map = extract_dirstate(py, &dmap)?;
 
-    let copies: Result<HashMap<HgPathBuf, HgPathBuf>, PyErr> = copymap
+    let copies: Result<FastHashMap<HgPathBuf, HgPathBuf>, PyErr> = copymap
         .items(py)
         .iter()
         .map(|(key, value)| {