]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::stable_hasher; |
923072b8 | 2 | use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; |
cdc7bbd5 | 3 | use std::convert::TryInto; |
1b1a35ee | 4 | use std::hash::{Hash, Hasher}; |
c30ab7b3 | 5 | |
5099ac24 FG |
6 | #[cfg(test)] |
7 | mod tests; | |
8 | ||
1b1a35ee | 9 | #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)] |
6a06907d | 10 | #[repr(C)] |
7cac9316 | 11 | pub struct Fingerprint(u64, u64); |
c30ab7b3 SL |
12 | |
13 | impl Fingerprint { | |
ff7c6d11 | 14 | pub const ZERO: Fingerprint = Fingerprint(0, 0); |
c30ab7b3 | 15 | |
6a06907d XL |
16 | #[inline] |
17 | pub fn new(_0: u64, _1: u64) -> Fingerprint { | |
18 | Fingerprint(_0, _1) | |
19 | } | |
20 | ||
7cac9316 | 21 | #[inline] |
c30ab7b3 | 22 | pub fn from_smaller_hash(hash: u64) -> Fingerprint { |
7cac9316 | 23 | Fingerprint(hash, hash) |
c30ab7b3 SL |
24 | } |
25 | ||
7cac9316 | 26 | #[inline] |
c30ab7b3 | 27 | pub fn to_smaller_hash(&self) -> u64 { |
6a06907d XL |
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 halfs makes sure we get a good quality hash in such cases too. | |
33 | self.0.wrapping_mul(3).wrapping_add(self.1) | |
c30ab7b3 | 34 | } |
476ff2be | 35 | |
abe05a73 XL |
36 | #[inline] |
37 | pub fn as_value(&self) -> (u64, u64) { | |
38 | (self.0, self.1) | |
39 | } | |
40 | ||
041b39d2 XL |
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), | |
dfeec247 | 47 | self.1.wrapping_mul(3).wrapping_add(other.1), |
041b39d2 XL |
48 | ) |
49 | } | |
50 | ||
8faf50e0 XL |
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 { | |
dc9dc135 XL |
55 | let a = u128::from(self.1) << 64 | u128::from(self.0); |
56 | let b = u128::from(other.1) << 64 | u128::from(other.0); | |
8faf50e0 XL |
57 | |
58 | let c = a.wrapping_add(b); | |
59 | ||
5099ac24 | 60 | Fingerprint(c as u64, (c >> 64) as u64) |
8faf50e0 XL |
61 | } |
62 | ||
476ff2be | 63 | pub fn to_hex(&self) -> String { |
7cac9316 | 64 | format!("{:x}{:x}", self.0, self.1) |
476ff2be | 65 | } |
041b39d2 | 66 | |
cdc7bbd5 XL |
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(); | |
2c00a5a8 | 75 | |
cdc7bbd5 XL |
76 | let second_half: &mut [u8; 8] = (&mut result[8..16]).try_into().unwrap(); |
77 | *second_half = self.1.to_le_bytes(); | |
2c00a5a8 | 78 | |
cdc7bbd5 XL |
79 | result |
80 | } | |
2c00a5a8 | 81 | |
cdc7bbd5 XL |
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 | ) | |
2c00a5a8 | 88 | } |
c30ab7b3 SL |
89 | } |
90 | ||
29967ef6 XL |
91 | impl std::fmt::Display for Fingerprint { |
92 | fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
7cac9316 | 93 | write!(formatter, "{:x}-{:x}", self.0, self.1) |
c30ab7b3 SL |
94 | } |
95 | } | |
96 | ||
1b1a35ee XL |
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) { | |
6a06907d XL |
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 halfs 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)); | |
1b1a35ee XL |
132 | } |
133 | } | |
134 | ||
7cac9316 | 135 | impl stable_hasher::StableHasherResult for Fingerprint { |
0731742a | 136 | #[inline] |
e74abb32 | 137 | fn finish(hasher: stable_hasher::StableHasher) -> Self { |
abe05a73 XL |
138 | let (_0, _1) = hasher.finalize(); |
139 | Fingerprint(_0, _1) | |
c30ab7b3 SL |
140 | } |
141 | } | |
476ff2be | 142 | |
b7449926 | 143 | impl_stable_hash_via_hash!(Fingerprint); |
2c00a5a8 | 144 | |
923072b8 | 145 | impl<E: Encoder> Encodable<E> for Fingerprint { |
cdc7bbd5 | 146 | #[inline] |
923072b8 FG |
147 | fn encode(&self, s: &mut E) { |
148 | s.emit_raw_bytes(&self.to_le_bytes()); | |
3dfed10e XL |
149 | } |
150 | } | |
2c00a5a8 | 151 | |
923072b8 | 152 | impl<D: Decoder> Decodable<D> for Fingerprint { |
cdc7bbd5 | 153 | #[inline] |
5099ac24 | 154 | fn decode(d: &mut D) -> Self { |
5e7ed085 | 155 | Fingerprint::from_le_bytes(d.read_raw_bytes(16).try_into().unwrap()) |
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 | ||
923072b8 | 187 | impl<E: Encoder> Encodable<E> for PackedFingerprint { |
fc512014 | 188 | #[inline] |
923072b8 | 189 | fn encode(&self, s: &mut E) { |
fc512014 XL |
190 | // Copy to avoid taking reference to packed field. |
191 | let copy = self.0; | |
923072b8 | 192 | copy.encode(s); |
fc512014 XL |
193 | } |
194 | } | |
195 | ||
923072b8 | 196 | impl<D: Decoder> Decodable<D> for PackedFingerprint { |
fc512014 | 197 | #[inline] |
5099ac24 FG |
198 | fn decode(d: &mut D) -> Self { |
199 | Self(Fingerprint::decode(d)) | |
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 | } |