compiler/rustc_data_structures/src/fingerprint.rs

   1 use crate::stable_hasher;
   2 use rustc_serialize::{Decodable, Encodable};
   3 use std::convert::TryInto;
   4 use std::hash::{Hash, Hasher};
   5
   6 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)]
   7 #[repr(C)]
   8 pub struct Fingerprint(u64, u64);
   9
  10 impl Fingerprint {
  11     pub const ZERO: Fingerprint = Fingerprint(0, 0);
  12
  13     #[inline]
  14     pub fn new(_0: u64, _1: u64) -> Fingerprint {
  15         Fingerprint(_0, _1)
  16     }
  17
  18     #[inline]
  19     pub fn from_smaller_hash(hash: u64) -> Fingerprint {
  20         Fingerprint(hash, hash)
  21     }
  22
  23     #[inline]
  24     pub fn to_smaller_hash(&self) -> u64 {
  25         // Even though both halves of the fingerprint are expected to be good
  26         // quality hash values, let's still combine the two values because the
  27         // Fingerprints in DefPathHash have the StableCrateId portion which is
  28         // the same for all DefPathHashes from the same crate. Combining the
  29         // two halfs makes sure we get a good quality hash in such cases too.
  30         self.0.wrapping_mul(3).wrapping_add(self.1)
  31     }
  32
  33     #[inline]
  34     pub fn as_value(&self) -> (u64, u64) {
  35         (self.0, self.1)
  36     }
  37
  38     #[inline]
  39     pub fn combine(self, other: Fingerprint) -> Fingerprint {
  40         // See https://stackoverflow.com/a/27952689 on why this function is
  41         // implemented this way.
  42         Fingerprint(
  43             self.0.wrapping_mul(3).wrapping_add(other.0),
  44             self.1.wrapping_mul(3).wrapping_add(other.1),
  45         )
  46     }
  47
  48     // Combines two hashes in an order independent way. Make sure this is what
  49     // you want.
  50     #[inline]
  51     pub fn combine_commutative(self, other: Fingerprint) -> Fingerprint {
  52         let a = u128::from(self.1) << 64 | u128::from(self.0);
  53         let b = u128::from(other.1) << 64 | u128::from(other.0);
  54
  55         let c = a.wrapping_add(b);
  56
  57         Fingerprint((c >> 64) as u64, c as u64)
  58     }
  59
  60     pub fn to_hex(&self) -> String {
  61         format!("{:x}{:x}", self.0, self.1)
  62     }
  63
  64     #[inline]
  65     pub fn to_le_bytes(&self) -> [u8; 16] {
  66         // This seems to optimize to the same machine code as
  67         // `unsafe { mem::transmute(*k) }`. Well done, LLVM! :)
  68         let mut result = [0u8; 16];
  69
  70         let first_half: &mut [u8; 8] = (&mut result[0..8]).try_into().unwrap();
  71         *first_half = self.0.to_le_bytes();
  72
  73         let second_half: &mut [u8; 8] = (&mut result[8..16]).try_into().unwrap();
  74         *second_half = self.1.to_le_bytes();
  75
  76         result
  77     }
  78
  79     #[inline]
  80     pub fn from_le_bytes(bytes: [u8; 16]) -> Fingerprint {
  81         Fingerprint(
  82             u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
  83             u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
  84         )
  85     }
  86 }
  87
  88 impl std::fmt::Display for Fingerprint {
  89     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  90         write!(formatter, "{:x}-{:x}", self.0, self.1)
  91     }
  92 }
  93
  94 impl Hash for Fingerprint {
  95     #[inline]
  96     fn hash<H: Hasher>(&self, state: &mut H) {
  97         state.write_fingerprint(self);
  98     }
  99 }
 100
 101 trait FingerprintHasher {
 102     fn write_fingerprint(&mut self, fingerprint: &Fingerprint);
 103 }
 104
 105 impl<H: Hasher> FingerprintHasher for H {
 106     #[inline]
 107     default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
 108         self.write_u64(fingerprint.0);
 109         self.write_u64(fingerprint.1);
 110     }
 111 }
 112
 113 impl FingerprintHasher for crate::unhash::Unhasher {
 114     #[inline]
 115     fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
 116         // Even though both halves of the fingerprint are expected to be good
 117         // quality hash values, let's still combine the two values because the
 118         // Fingerprints in DefPathHash have the StableCrateId portion which is
 119         // the same for all DefPathHashes from the same crate. Combining the
 120         // two halfs makes sure we get a good quality hash in such cases too.
 121         //
 122         // Since `Unhasher` is used only in the context of HashMaps, it is OK
 123         // to combine the two components in an order-independent way (which is
 124         // cheaper than the more robust Fingerprint::to_smaller_hash()). For
 125         // HashMaps we don't really care if Fingerprint(x,y) and
 126         // Fingerprint(y, x) result in the same hash value. Collision
 127         // probability will still be much better than with FxHash.
 128         self.write_u64(fingerprint.0.wrapping_add(fingerprint.1));
 129     }
 130 }
 131
 132 impl stable_hasher::StableHasherResult for Fingerprint {
 133     #[inline]
 134     fn finish(hasher: stable_hasher::StableHasher) -> Self {
 135         let (_0, _1) = hasher.finalize();
 136         Fingerprint(_0, _1)
 137     }
 138 }
 139
 140 impl_stable_hash_via_hash!(Fingerprint);
 141
 142 impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint {
 143     #[inline]
 144     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 145         s.emit_raw_bytes(&self.to_le_bytes()[..])?;
 146         Ok(())
 147     }
 148 }
 149
 150 impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint {
 151     #[inline]
 152     fn decode(d: &mut D) -> Result<Self, D::Error> {
 153         let mut bytes = [0u8; 16];
 154         d.read_raw_bytes_into(&mut bytes[..])?;
 155         Ok(Fingerprint::from_le_bytes(bytes))
 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: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint {
 188     #[inline]
 189     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 190         // Copy to avoid taking reference to packed field.
 191         let copy = self.0;
 192         copy.encode(s)
 193     }
 194 }
 195
 196 impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint {
 197     #[inline]
 198     fn decode(d: &mut D) -> Result<Self, D::Error> {
 199         Fingerprint::decode(d).map(PackedFingerprint)
 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 }