Compress amount of hashed bytes for `isize` values in StableHasher

2 files changed, 51 insertions, 3 deletions

diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs
index 9c09a7f5f82..1495521ddbb 100644
--- a/compiler/rustc_data_structures/src/stable_hasher.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher.rs
@@ -137,7 +137,35 @@ impl Hasher for StableHasher {
         // platforms. This is important for symbol hashes when cross compiling,
         // for example. Sign extending here is preferable as it means that the
         // same negative number hashes the same on both 32 and 64 bit platforms.
-        self.state.write_i64((i as i64).to_le());
+        let value = (i as i64).to_le() as u64;
+
+        // Cold path
+        #[cold]
+        #[inline(never)]
+        fn hash_value(state: &mut SipHasher128, value: u64) {
+            state.write_u8(0xFF);
+            state.write_u64(value);
+        }
+
+        // `isize` values often seem to have a small (positive) numeric value in practice.
+        // To exploit this, if the value is small, we will hash a smaller amount of bytes.
+        // However, we cannot just skip the leading zero bytes, as that would produce the same hash
+        // e.g. if you hash two values that have the same bit pattern when they are swapped.
+        // See https://github.com/rust-lang/rust/pull/93014 for context.
+        //
+        // Therefore, we employ the following strategy:
+        // 1) When we encounter a value that fits within a single byte (the most common case), we
+        // hash just that byte. This is the most common case that is being optimized. However, we do
+        // not do this for the value 0xFF, as that is a reserved prefix (a bit like in UTF-8).
+        // 2) When we encounter a larger value, we hash a "marker" 0xFF and then the corresponding
+        // 8 bytes. Since this prefix cannot occur when we hash a single byte, when we hash two
+        // `isize`s that fit within a different amount of bytes, they should always produce a different
+        // byte stream for the hasher.
+        if value < 0xFF {
+            self.state.write_u8(value as u8);
+        } else {
+            hash_value(&mut self.state, value);
+        }
     }
 }
 
diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
index 31190363eb6..a84ee3da438 100644
--- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
@@ -39,7 +39,7 @@ fn test_hash_integers() {
     test_isize.hash(&mut h);
 
     // This depends on the hashing algorithm. See note at top of file.
-    let expected = (2736651863462566372, 8121090595289675650);
+    let expected = (1784307454142909076, 11471672289340283879);
 
     assert_eq!(h.finalize(), expected);
 }
@@ -67,7 +67,7 @@ fn test_hash_isize() {
     test_isize.hash(&mut h);
 
     // This depends on the hashing algorithm. See note at top of file.
-    let expected = (14721296605626097289, 11385941877786388409);
+    let expected = (2789913510339652884, 674280939192711005);
 
     assert_eq!(h.finalize(), expected);
 }
@@ -140,3 +140,23 @@ fn test_attribute_permutation() {
     test_type!(i64);
     test_type!(i128);
 }
+
+// Check that the `isize` hashing optimization does not produce the same hash when permuting two
+// values.
+#[test]
+fn test_isize_compression() {
+    fn check_hash(a: u64, b: u64) {
+        let hash_a = hash(&(a as isize, b as isize));
+        let hash_b = hash(&(b as isize, a as isize));
+        assert_ne!(
+            hash_a, hash_b,
+            "The hash stayed the same when permuting values `{a}` and `{b}!",
+        );
+    }
+
+    check_hash(0xAA, 0xAAAA);
+    check_hash(0xFF, 0xFFFF);
+    check_hash(0xAAAA, 0xAAAAAA);
+    check_hash(0xAAAAAA, 0xAAAAAAAA);
+    check_hash(0xFF, 0xFFFFFFFFFFFFFFFF);
+}