compiler/rustc_data_structures/src/fingerprint.rs

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