]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::stable_hasher; |
cdc7bbd5 XL |
2 | use rustc_serialize::{Decodable, Encodable}; |
3 | use std::convert::TryInto; | |
1b1a35ee | 4 | use std::hash::{Hash, Hasher}; |
c30ab7b3 | 5 | |
1b1a35ee | 6 | #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)] |
6a06907d | 7 | #[repr(C)] |
7cac9316 | 8 | pub struct Fingerprint(u64, u64); |
c30ab7b3 SL |
9 | |
10 | impl Fingerprint { | |
ff7c6d11 | 11 | pub const ZERO: Fingerprint = Fingerprint(0, 0); |
c30ab7b3 | 12 | |
6a06907d XL |
13 | #[inline] |
14 | pub fn new(_0: u64, _1: u64) -> Fingerprint { | |
15 | Fingerprint(_0, _1) | |
16 | } | |
17 | ||
7cac9316 | 18 | #[inline] |
c30ab7b3 | 19 | pub fn from_smaller_hash(hash: u64) -> Fingerprint { |
7cac9316 | 20 | Fingerprint(hash, hash) |
c30ab7b3 SL |
21 | } |
22 | ||
7cac9316 | 23 | #[inline] |
c30ab7b3 | 24 | pub fn to_smaller_hash(&self) -> u64 { |
6a06907d XL |
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) | |
c30ab7b3 | 31 | } |
476ff2be | 32 | |
abe05a73 XL |
33 | #[inline] |
34 | pub fn as_value(&self) -> (u64, u64) { | |
35 | (self.0, self.1) | |
36 | } | |
37 | ||
041b39d2 XL |
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), | |
dfeec247 | 44 | self.1.wrapping_mul(3).wrapping_add(other.1), |
041b39d2 XL |
45 | ) |
46 | } | |
47 | ||
8faf50e0 XL |
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 { | |
dc9dc135 XL |
52 | let a = u128::from(self.1) << 64 | u128::from(self.0); |
53 | let b = u128::from(other.1) << 64 | u128::from(other.0); | |
8faf50e0 XL |
54 | |
55 | let c = a.wrapping_add(b); | |
56 | ||
57 | Fingerprint((c >> 64) as u64, c as u64) | |
58 | } | |
59 | ||
476ff2be | 60 | pub fn to_hex(&self) -> String { |
7cac9316 | 61 | format!("{:x}{:x}", self.0, self.1) |
476ff2be | 62 | } |
041b39d2 | 63 | |
cdc7bbd5 XL |
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(); | |
2c00a5a8 | 72 | |
cdc7bbd5 XL |
73 | let second_half: &mut [u8; 8] = (&mut result[8..16]).try_into().unwrap(); |
74 | *second_half = self.1.to_le_bytes(); | |
2c00a5a8 | 75 | |
cdc7bbd5 XL |
76 | result |
77 | } | |
2c00a5a8 | 78 | |
cdc7bbd5 XL |
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 | ) | |
2c00a5a8 | 85 | } |
c30ab7b3 SL |
86 | } |
87 | ||
29967ef6 XL |
88 | impl std::fmt::Display for Fingerprint { |
89 | fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
7cac9316 | 90 | write!(formatter, "{:x}-{:x}", self.0, self.1) |
c30ab7b3 SL |
91 | } |
92 | } | |
93 | ||
1b1a35ee XL |
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) { | |
6a06907d XL |
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)); | |
1b1a35ee XL |
129 | } |
130 | } | |
131 | ||
7cac9316 | 132 | impl stable_hasher::StableHasherResult for Fingerprint { |
0731742a | 133 | #[inline] |
e74abb32 | 134 | fn finish(hasher: stable_hasher::StableHasher) -> Self { |
abe05a73 XL |
135 | let (_0, _1) = hasher.finalize(); |
136 | Fingerprint(_0, _1) | |
c30ab7b3 SL |
137 | } |
138 | } | |
476ff2be | 139 | |
b7449926 | 140 | impl_stable_hash_via_hash!(Fingerprint); |
2c00a5a8 | 141 | |
3dfed10e | 142 | impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint { |
cdc7bbd5 | 143 | #[inline] |
3dfed10e | 144 | fn encode(&self, s: &mut E) -> Result<(), E::Error> { |
a2a8927a | 145 | s.emit_raw_bytes(&self.to_le_bytes())?; |
cdc7bbd5 | 146 | Ok(()) |
3dfed10e XL |
147 | } |
148 | } | |
2c00a5a8 | 149 | |
3dfed10e | 150 | impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint { |
cdc7bbd5 | 151 | #[inline] |
3dfed10e | 152 | fn decode(d: &mut D) -> Result<Self, D::Error> { |
cdc7bbd5 | 153 | let mut bytes = [0u8; 16]; |
a2a8927a | 154 | d.read_raw_bytes_into(&mut bytes)?; |
cdc7bbd5 | 155 | Ok(Fingerprint::from_le_bytes(bytes)) |
2c00a5a8 XL |
156 | } |
157 | } | |
fc512014 XL |
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> { | |
5869c6ff | 199 | Fingerprint::decode(d).map(PackedFingerprint) |
fc512014 XL |
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 | } |