compiler/rustc_data_structures/src/fingerprint.rs

   1 use crate::stable_hasher;
   2 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
   3 use std::convert::TryInto;
   4 use std::hash::{Hash, Hasher};
   5
   6 #[cfg(test)]
   7 mod tests;
   8
   9 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)]
  10 #[repr(C)]
  11 pub struct Fingerprint(u64, u64);
  12
  13 impl Fingerprint {
  14     pub const ZERO: Fingerprint = Fingerprint(0, 0);
  15
  16     #[inline]
  17     pub fn new(_0: u64, _1: u64) -> Fingerprint {
  18         Fingerprint(_0, _1)
  19     }
  20
  21     #[inline]
  22     pub fn from_smaller_hash(hash: u64) -> Fingerprint {
  23         Fingerprint(hash, hash)
  24     }
  25
  26     #[inline]
  27     pub fn to_smaller_hash(&self) -> u64 {
  28         // Even though both halves of the fingerprint are expected to be good
  29         // quality hash values, let's still combine the two values because the
  30         // Fingerprints in DefPathHash have the StableCrateId portion which is
  31         // the same for all DefPathHashes from the same crate. Combining the
  32         // two halves makes sure we get a good quality hash in such cases too.
  33         self.0.wrapping_mul(3).wrapping_add(self.1)
  34     }
  35
  36     #[inline]
  37     pub fn as_value(&self) -> (u64, u64) {
  38         (self.0, self.1)
  39     }
  40
  41     #[inline]
  42     pub fn combine(self, other: Fingerprint) -> Fingerprint {
  43         // See https://stackoverflow.com/a/27952689 on why this function is
  44         // implemented this way.
  45         Fingerprint(
  46             self.0.wrapping_mul(3).wrapping_add(other.0),
  47             self.1.wrapping_mul(3).wrapping_add(other.1),
  48         )
  49     }
  50
  51     // Combines two hashes in an order independent way. Make sure this is what
  52     // you want.
  53     #[inline]
  54     pub fn combine_commutative(self, other: Fingerprint) -> Fingerprint {
  55         let a = u128::from(self.1) << 64 | u128::from(self.0);
  56         let b = u128::from(other.1) << 64 | u128::from(other.0);
  57
  58         let c = a.wrapping_add(b);
  59
  60         Fingerprint(c as u64, (c >> 64) as u64)
  61     }
  62
  63     pub fn to_hex(&self) -> String {
  64         format!("{:x}{:x}", self.0, self.1)
  65     }
  66
  67     #[inline]
  68     pub fn to_le_bytes(&self) -> [u8; 16] {
  69         // This seems to optimize to the same machine code as
  70         // `unsafe { mem::transmute(*k) }`. Well done, LLVM! :)
  71         let mut result = [0u8; 16];
  72
  73         let first_half: &mut [u8; 8] = (&mut result[0..8]).try_into().unwrap();
  74         *first_half = self.0.to_le_bytes();
  75
  76         let second_half: &mut [u8; 8] = (&mut result[8..16]).try_into().unwrap();
  77         *second_half = self.1.to_le_bytes();
  78
  79         result
  80     }
  81
  82     #[inline]
  83     pub fn from_le_bytes(bytes: [u8; 16]) -> Fingerprint {
  84         Fingerprint(
  85             u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
  86             u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
  87         )
  88     }
  89 }
  90
  91 impl std::fmt::Display for Fingerprint {
  92     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  93         write!(formatter, "{:x}-{:x}", self.0, self.1)
  94     }
  95 }
  96
  97 impl Hash for Fingerprint {
  98     #[inline]
  99     fn hash<H: Hasher>(&self, state: &mut H) {
 100         state.write_fingerprint(self);
 101     }
 102 }
 103
 104 trait FingerprintHasher {
 105     fn write_fingerprint(&mut self, fingerprint: &Fingerprint);
 106 }
 107
 108 impl<H: Hasher> FingerprintHasher for H {
 109     #[inline]
 110     default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
 111         self.write_u64(fingerprint.0);
 112         self.write_u64(fingerprint.1);
 113     }
 114 }
 115
 116 impl FingerprintHasher for crate::unhash::Unhasher {
 117     #[inline]
 118     fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
 119         // Even though both halves of the fingerprint are expected to be good
 120         // quality hash values, let's still combine the two values because the
 121         // Fingerprints in DefPathHash have the StableCrateId portion which is
 122         // the same for all DefPathHashes from the same crate. Combining the
 123         // two halves makes sure we get a good quality hash in such cases too.
 124         //
 125         // Since `Unhasher` is used only in the context of HashMaps, it is OK
 126         // to combine the two components in an order-independent way (which is
 127         // cheaper than the more robust Fingerprint::to_smaller_hash()). For
 128         // HashMaps we don't really care if Fingerprint(x,y) and
 129         // Fingerprint(y, x) result in the same hash value. Collision
 130         // probability will still be much better than with FxHash.
 131         self.write_u64(fingerprint.0.wrapping_add(fingerprint.1));
 132     }
 133 }
 134
 135 impl stable_hasher::StableHasherResult for Fingerprint {
 136     #[inline]
 137     fn finish(hasher: stable_hasher::StableHasher) -> Self {
 138         let (_0, _1) = hasher.finalize();
 139         Fingerprint(_0, _1)
 140     }
 141 }
 142
 143 impl_stable_hash_via_hash!(Fingerprint);
 144
 145 impl<E: Encoder> Encodable<E> for Fingerprint {
 146     #[inline]
 147     fn encode(&self, s: &mut E) {
 148         s.emit_raw_bytes(&self.to_le_bytes());
 149     }
 150 }
 151
 152 impl<D: Decoder> Decodable<D> for Fingerprint {
 153     #[inline]
 154     fn decode(d: &mut D) -> Self {
 155         Fingerprint::from_le_bytes(d.read_raw_bytes(16).try_into().unwrap())
 156     }
 157 }
 158
 159 // `PackedFingerprint` wraps a `Fingerprint`. Its purpose is to, on certain
 160 // architectures, behave like a `Fingerprint` without alignment requirements.
 161 // This behavior is only enabled on x86 and x86_64, where the impact of
 162 // unaligned accesses is tolerable in small doses.
 163 //
 164 // This may be preferable to use in large collections of structs containing
 165 // fingerprints, as it can reduce memory consumption by preventing the padding
 166 // that the more strictly-aligned `Fingerprint` can introduce. An application of
 167 // this is in the query dependency graph, which contains a large collection of
 168 // `DepNode`s. As of this writing, the size of a `DepNode` decreases by ~30%
 169 // (from 24 bytes to 17) by using the packed representation here, which
 170 // noticeably decreases total memory usage when compiling large crates.
 171 //
 172 // The wrapped `Fingerprint` is private to reduce the chance of a client
 173 // invoking undefined behavior by taking a reference to the packed field.
 174 #[cfg_attr(any(target_arch = "x86", target_arch = "x86_64"), repr(packed))]
 175 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy, Hash)]
 176 pub struct PackedFingerprint(Fingerprint);
 177
 178 impl std::fmt::Display for PackedFingerprint {
 179     #[inline]
 180     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 181         // Copy to avoid taking reference to packed field.
 182         let copy = self.0;
 183         copy.fmt(formatter)
 184     }
 185 }
 186
 187 impl<E: Encoder> Encodable<E> for PackedFingerprint {
 188     #[inline]
 189     fn encode(&self, s: &mut E) {
 190         // Copy to avoid taking reference to packed field.
 191         let copy = self.0;
 192         copy.encode(s);
 193     }
 194 }
 195
 196 impl<D: Decoder> Decodable<D> for PackedFingerprint {
 197     #[inline]
 198     fn decode(d: &mut D) -> Self {
 199         Self(Fingerprint::decode(d))
 200     }
 201 }
 202
 203 impl From<Fingerprint> for PackedFingerprint {
 204     #[inline]
 205     fn from(f: Fingerprint) -> PackedFingerprint {
 206         PackedFingerprint(f)
 207     }
 208 }
 209
 210 impl From<PackedFingerprint> for Fingerprint {
 211     #[inline]
 212     fn from(f: PackedFingerprint) -> Fingerprint {
 213         f.0
 214     }
 215 }