From a5f5f6b6892ffe5364e25345c6f5a0113ae33a98 Mon Sep 17 00:00:00 2001
From: Jakub Beránek <berykubik@gmail.com>
Date: Sun, 12 Dec 2021 20:24:56 +0100
Subject: Avoid sorting in hash map stable hashing

---
 compiler/rustc_data_structures/src/stable_hasher.rs | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

(limited to 'compiler/rustc_data_structures')

diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs
index b8ad66901c6..c2218b92a44 100644
--- a/compiler/rustc_data_structures/src/stable_hasher.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher.rs
@@ -42,6 +42,7 @@ impl StableHasher {
 }
 
 impl StableHasherResult for u128 {
+    #[inline]
     fn finish(hasher: StableHasher) -> Self {
         let (_0, _1) = hasher.finalize();
         u128::from(_0) | (u128::from(_1) << 64)
@@ -49,6 +50,7 @@ impl StableHasherResult for u128 {
 }
 
 impl StableHasherResult for u64 {
+    #[inline]
     fn finish(hasher: StableHasher) -> Self {
         hasher.finalize().0
     }
@@ -559,8 +561,16 @@ pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>(
     SK: HashStable<HCX> + Ord,
     F: Fn(&K, &HCX) -> SK,
 {
-    let mut entries: SmallVec<[_; 3]> =
-        map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect();
-    entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
-    entries.hash_stable(hcx, hasher);
+    let hash = map
+        .iter()
+        .map(|(key, value)| {
+            let key = to_stable_hash_key(key, hcx);
+            let mut hasher = StableHasher::new();
+            key.hash_stable(hcx, &mut hasher);
+            value.hash_stable(hcx, &mut hasher);
+            hasher.finish::<u128>()
+        })
+        .reduce(|accum, value| accum.wrapping_mul(value));
+    map.len().hash_stable(hcx, hasher);
+    hash.hash_stable(hcx, hasher);
 }
-- 
cgit 1.4.1-3-g733a5