Auto merge of #91660 - llogiq:make-a-hash-of-def-ids, r=nnethercote

manually implement `Hash` for `DefId`

This might speed up hashing for hashers that can work on individual u64s. Just as an experiment, suggested in a reddit thread on `FxHasher`. cc `@nnethercote`

Note that this should not be merged as is without cfg-ing the code path for 64 bits.

3 files changed, 48 insertions, 22 deletions

diff --git a/compiler/rustc_span/src/def_id.rs b/compiler/rustc_span/src/def_id.rs
index 64baf94cc00..6d8fea2030b 100644
--- a/compiler/rustc_span/src/def_id.rs
+++ b/compiler/rustc_span/src/def_id.rs
@@ -7,6 +7,7 @@ use rustc_macros::HashStable_Generic;
 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
 use std::borrow::Borrow;
 use std::fmt;
+use std::hash::{Hash, Hasher};
 
 rustc_index::newtype_index! {
     pub struct CrateNum {
@@ -146,9 +147,6 @@ impl StableCrateId {
     /// Computes the stable ID for a crate with the given name and
     /// `-Cmetadata` arguments.
     pub fn new(crate_name: &str, is_exe: bool, mut metadata: Vec<String>) -> StableCrateId {
-        use std::hash::Hash;
-        use std::hash::Hasher;
-
         let mut hasher = StableHasher::new();
         crate_name.hash(&mut hasher);
 
@@ -205,10 +203,38 @@ impl<D: Decoder> Decodable<D> for DefIndex {
 /// index and a def index.
 ///
 /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
-#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy)]
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Copy)]
+// On below-64 bit systems we can simply use the derived `Hash` impl
+#[cfg_attr(not(target_pointer_width = "64"), derive(Hash))]
+// Note that the order is essential here, see below why
 pub struct DefId {
-    pub krate: CrateNum,
     pub index: DefIndex,
+    pub krate: CrateNum,
+}
+
+// On 64-bit systems, we can hash the whole `DefId` as one `u64` instead of two `u32`s. This
+// improves performance without impairing `FxHash` quality. So the below code gets compiled to a
+// noop on little endian systems because the memory layout of `DefId` is as follows:
+//
+// ```
+//     +-1--------------31-+-32-------------63-+
+//     ! index             ! krate             !
+//     +-------------------+-------------------+
+// ```
+//
+// The order here has direct impact on `FxHash` quality because we have far more `DefIndex` per
+// crate than we have `Crate`s within one compilation. Or in other words, this arrangement puts
+// more entropy in the low bits than the high bits. The reason this matters is that `FxHash`, which
+// is used throughout rustc, has problems distributing the entropy from the high bits, so reversing
+// the order would lead to a large number of collisions and thus far worse performance.
+//
+// On 64-bit big-endian systems, this compiles to a 64-bit rotation by 32 bits, which is still
+// faster than another `FxHash` round.
+#[cfg(target_pointer_width = "64")]
+impl Hash for DefId {
+    fn hash<H: Hasher>(&self, h: &mut H) {
+        (((self.krate.as_u32() as u64) << 32) | (self.index.as_u32() as u64)).hash(h)
+    }
 }
 
 impl DefId {
diff --git a/src/test/ui/coherence/coherence-orphan.stderr b/src/test/ui/coherence/coherence-orphan.stderr
index 051a519ee14..52d2cc88cbe 100644
--- a/src/test/ui/coherence/coherence-orphan.stderr
+++ b/src/test/ui/coherence/coherence-orphan.stderr
@@ -1,15 +1,4 @@
 error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
-  --> $DIR/coherence-orphan.rs:17:1
-   |
-LL | impl !Send for Vec<isize> { }
-   | ^^^^^^^^^^^^^^^----------
-   | |              |
-   | |              `Vec` is not defined in the current crate
-   | impl doesn't use only types from inside the current crate
-   |
-   = note: define and implement a trait or new type instead
-
-error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
   --> $DIR/coherence-orphan.rs:10:1
    |
 LL | impl TheTrait<usize> for isize { }
@@ -21,6 +10,17 @@ LL | impl TheTrait<usize> for isize { }
    |
    = note: define and implement a trait or new type instead
 
+error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
+  --> $DIR/coherence-orphan.rs:17:1
+   |
+LL | impl !Send for Vec<isize> { }
+   | ^^^^^^^^^^^^^^^----------
+   | |              |
+   | |              `Vec` is not defined in the current crate
+   | impl doesn't use only types from inside the current crate
+   |
+   = note: define and implement a trait or new type instead
+
 error: aborting due to 2 previous errors
 
 For more information about this error, try `rustc --explain E0117`.
diff --git a/src/test/ui/methods/method-ambig-two-traits-cross-crate.stderr b/src/test/ui/methods/method-ambig-two-traits-cross-crate.stderr
index ed03b37fde2..4b2597eed3c 100644
--- a/src/test/ui/methods/method-ambig-two-traits-cross-crate.stderr
+++ b/src/test/ui/methods/method-ambig-two-traits-cross-crate.stderr
@@ -4,20 +4,20 @@ error[E0034]: multiple applicable items in scope
 LL | fn main() { 1_usize.me(); }
    |                     ^^ multiple `me` found
    |
-note: candidate #1 is defined in an impl of the trait `Me2` for the type `usize`
+   = note: candidate #1 is defined in an impl of the trait `Me` for the type `usize`
+note: candidate #2 is defined in an impl of the trait `Me2` for the type `usize`
   --> $DIR/method-ambig-two-traits-cross-crate.rs:10:22
    |
 LL | impl Me2 for usize { fn me(&self) -> usize { *self } }
    |                      ^^^^^^^^^^^^^^^^^^^^^
-   = note: candidate #2 is defined in an impl of the trait `Me` for the type `usize`
 help: disambiguate the associated function for candidate #1
    |
-LL | fn main() { Me2::me(&1_usize); }
-   |             ~~~~~~~~~~~~~~~~~
-help: disambiguate the associated function for candidate #2
-   |
 LL | fn main() { Me::me(&1_usize); }
    |             ~~~~~~~~~~~~~~~~
+help: disambiguate the associated function for candidate #2
+   |
+LL | fn main() { Me2::me(&1_usize); }
+   |             ~~~~~~~~~~~~~~~~~
 
 error: aborting due to previous error