compiler/rustc_data_structures/src/fingerprint.rs

   1 use crate::stable_hasher;
   2 use rustc_serialize::{Decodable, Encodable};
   3 use std::hash::{Hash, Hasher};
   4 use std::mem::{self, MaybeUninit};
   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
  65 impl std::fmt::Display for Fingerprint {
  66     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  67         write!(formatter, "{:x}-{:x}", self.0, self.1)
  68     }
  69 }
  70
  71 impl Hash for Fingerprint {
  72     #[inline]
  73     fn hash<H: Hasher>(&self, state: &mut H) {
  74         state.write_fingerprint(self);
  75     }
  76 }
  77
  78 trait FingerprintHasher {
  79     fn write_fingerprint(&mut self, fingerprint: &Fingerprint);
  80 }
  81
  82 impl<H: Hasher> FingerprintHasher for H {
  83     #[inline]
  84     default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
  85         self.write_u64(fingerprint.0);
  86         self.write_u64(fingerprint.1);
  87     }
  88 }
  89
  90 impl FingerprintHasher for crate::unhash::Unhasher {
  91     #[inline]
  92     fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
  93         // Even though both halves of the fingerprint are expected to be good
  94         // quality hash values, let's still combine the two values because the
  95         // Fingerprints in DefPathHash have the StableCrateId portion which is
  96         // the same for all DefPathHashes from the same crate. Combining the
  97         // two halfs makes sure we get a good quality hash in such cases too.
  98         //
  99         // Since `Unhasher` is used only in the context of HashMaps, it is OK
 100         // to combine the two components in an order-independent way (which is
 101         // cheaper than the more robust Fingerprint::to_smaller_hash()). For
 102         // HashMaps we don't really care if Fingerprint(x,y) and
 103         // Fingerprint(y, x) result in the same hash value. Collision
 104         // probability will still be much better than with FxHash.
 105         self.write_u64(fingerprint.0.wrapping_add(fingerprint.1));
 106     }
 107 }
 108
 109 impl stable_hasher::StableHasherResult for Fingerprint {
 110     #[inline]
 111     fn finish(hasher: stable_hasher::StableHasher) -> Self {
 112         let (_0, _1) = hasher.finalize();
 113         Fingerprint(_0, _1)
 114     }
 115 }
 116
 117 impl_stable_hash_via_hash!(Fingerprint);
 118
 119 impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint {
 120     #[inline]
 121     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 122         let bytes: [u8; 16] = unsafe { mem::transmute([self.0.to_le(), self.1.to_le()]) };
 123         s.emit_raw_bytes(&bytes)?;
 124         Ok(())
 125     }
 126 }
 127
 128 impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint {
 129     #[inline]
 130     fn decode(d: &mut D) -> Result<Self, D::Error> {
 131         let mut bytes: [MaybeUninit<u8>; 16] = MaybeUninit::uninit_array();
 132         d.read_raw_bytes(&mut bytes)?;
 133
 134         let [l, r]: [u64; 2] = unsafe { mem::transmute(bytes) };
 135         Ok(Fingerprint(u64::from_le(l), u64::from_le(r)))
 136     }
 137 }
 138
 139 // `PackedFingerprint` wraps a `Fingerprint`. Its purpose is to, on certain
 140 // architectures, behave like a `Fingerprint` without alignment requirements.
 141 // This behavior is only enabled on x86 and x86_64, where the impact of
 142 // unaligned accesses is tolerable in small doses.
 143 //
 144 // This may be preferable to use in large collections of structs containing
 145 // fingerprints, as it can reduce memory consumption by preventing the padding
 146 // that the more strictly-aligned `Fingerprint` can introduce. An application of
 147 // this is in the query dependency graph, which contains a large collection of
 148 // `DepNode`s. As of this writing, the size of a `DepNode` decreases by ~30%
 149 // (from 24 bytes to 17) by using the packed representation here, which
 150 // noticeably decreases total memory usage when compiling large crates.
 151 //
 152 // The wrapped `Fingerprint` is private to reduce the chance of a client
 153 // invoking undefined behavior by taking a reference to the packed field.
 154 #[cfg_attr(any(target_arch = "x86", target_arch = "x86_64"), repr(packed))]
 155 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy, Hash)]
 156 pub struct PackedFingerprint(Fingerprint);
 157
 158 impl std::fmt::Display for PackedFingerprint {
 159     #[inline]
 160     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 161         // Copy to avoid taking reference to packed field.
 162         let copy = self.0;
 163         copy.fmt(formatter)
 164     }
 165 }
 166
 167 impl<E: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint {
 168     #[inline]
 169     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 170         // Copy to avoid taking reference to packed field.
 171         let copy = self.0;
 172         copy.encode(s)
 173     }
 174 }
 175
 176 impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint {
 177     #[inline]
 178     fn decode(d: &mut D) -> Result<Self, D::Error> {
 179         Fingerprint::decode(d).map(PackedFingerprint)
 180     }
 181 }
 182
 183 impl From<Fingerprint> for PackedFingerprint {
 184     #[inline]
 185     fn from(f: Fingerprint) -> PackedFingerprint {
 186         PackedFingerprint(f)
 187     }
 188 }
 189
 190 impl From<PackedFingerprint> for Fingerprint {
 191     #[inline]
 192     fn from(f: PackedFingerprint) -> Fingerprint {
 193         f.0
 194     }
 195 }