Rollup merge of #37229 - nnethercote:FxHasher, r=nikomatsakis

Replace FNV with a faster hash function.

Hash table lookups are very hot in rustc profiles and the time taken within `FnvHash` itself is a big part of that. Although FNV is a simple hash, it processes its input one byte at a time. In contrast, Firefox has a homespun hash function that is also simple but works on multiple bytes at a time. So I tried it out and the results are compelling:

```
futures-rs-test  4.326s vs  4.212s --> 1.027x faster (variance: 1.001x, 1.007x)
helloworld       0.233s vs  0.232s --> 1.004x faster (variance: 1.037x, 1.016x)
html5ever-2016-  5.397s vs  5.210s --> 1.036x faster (variance: 1.009x, 1.006x)
hyper.0.5.0      5.018s vs  4.905s --> 1.023x faster (variance: 1.007x, 1.006x)
inflate-0.1.0    4.889s vs  4.872s --> 1.004x faster (variance: 1.012x, 1.007x)
issue-32062-equ  0.347s vs  0.335s --> 1.035x faster (variance: 1.033x, 1.019x)
issue-32278-big  1.717s vs  1.622s --> 1.059x faster (variance: 1.027x, 1.028x)
jld-day15-parse  1.537s vs  1.459s --> 1.054x faster (variance: 1.005x, 1.003x)
piston-image-0. 11.863s vs 11.482s --> 1.033x faster (variance: 1.060x, 1.002x)
regex.0.1.30     2.517s vs  2.453s --> 1.026x faster (variance: 1.011x, 1.013x)
rust-encoding-0  2.080s vs  2.047s --> 1.016x faster (variance: 1.005x, 1.005x)
syntex-0.42.2   32.268s vs 31.275s --> 1.032x faster (variance: 1.014x, 1.022x)
syntex-0.42.2-i 17.629s vs 16.559s --> 1.065x faster (variance: 1.013x, 1.021x)
```

(That's a stage1 compiler doing debug builds. Results for a stage2 compiler are similar.)

The attached commit is not in a state suitable for landing because I changed the implementation of FnvHasher without changing its name (because that would have required touching many lines in the compiler). Nonetheless, it is a good place to start discussions.

Profiles show very clearly that this new hash function is a lot faster to compute than FNV. The quality of the new hash function is less clear -- it seems to do better in some cases and worse in others (judging by the number of instructions executed in `Hash{Map,Set}::get`).

CC @brson, @arthurprs

5 files changed, 29 insertions, 29 deletions

diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index e72ac841994..43c97cbe004 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -22,7 +22,7 @@ use rustc_back::PanicStrategy;
 use rustc::session::search_paths::PathKind;
 use rustc::middle;
 use rustc::middle::cstore::{CrateStore, validate_crate_name, ExternCrate};
-use rustc::util::nodemap::{FnvHashMap, FnvHashSet};
+use rustc::util::nodemap::{FxHashMap, FxHashSet};
 use rustc::hir::map::Definitions;
 
 use std::cell::{RefCell, Cell};
@@ -50,7 +50,7 @@ pub struct CrateLoader<'a> {
     pub sess: &'a Session,
     cstore: &'a CStore,
     next_crate_num: CrateNum,
-    foreign_item_map: FnvHashMap<String, Vec<ast::NodeId>>,
+    foreign_item_map: FxHashMap<String, Vec<ast::NodeId>>,
     local_crate_name: String,
 }
 
@@ -148,7 +148,7 @@ impl<'a> CrateLoader<'a> {
             sess: sess,
             cstore: cstore,
             next_crate_num: cstore.next_crate_num(),
-            foreign_item_map: FnvHashMap(),
+            foreign_item_map: FxHashMap(),
             local_crate_name: local_crate_name.to_owned(),
         }
     }
@@ -401,7 +401,7 @@ impl<'a> CrateLoader<'a> {
     fn update_extern_crate(&mut self,
                            cnum: CrateNum,
                            mut extern_crate: ExternCrate,
-                           visited: &mut FnvHashSet<(CrateNum, bool)>)
+                           visited: &mut FxHashSet<(CrateNum, bool)>)
     {
         if !visited.insert((cnum, extern_crate.direct)) { return }
 
@@ -442,7 +442,7 @@ impl<'a> CrateLoader<'a> {
         // The map from crate numbers in the crate we're resolving to local crate
         // numbers
         let deps = crate_root.crate_deps.decode(metadata);
-        let map: FnvHashMap<_, _> = deps.enumerate().map(|(crate_num, dep)| {
+        let map: FxHashMap<_, _> = deps.enumerate().map(|(crate_num, dep)| {
             debug!("resolving dep crate {} hash: `{}`", dep.name, dep.hash);
             let (local_cnum, ..) = self.resolve_crate(root,
                                                         &dep.name.as_str(),
@@ -1021,7 +1021,7 @@ impl<'a> middle::cstore::CrateLoader for CrateLoader<'a> {
 
         let extern_crate =
             ExternCrate { def_id: def_id, span: item.span, direct: true, path_len: len };
-        self.update_extern_crate(cnum, extern_crate, &mut FnvHashSet());
+        self.update_extern_crate(cnum, extern_crate, &mut FxHashSet());
         self.cstore.add_extern_mod_stmt_cnum(info.id, cnum);
 
         loaded_macros
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index 58c70f959b7..f452cc23b73 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -21,7 +21,7 @@ use rustc::hir::svh::Svh;
 use rustc::middle::cstore::ExternCrate;
 use rustc_back::PanicStrategy;
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc::util::nodemap::{FnvHashMap, NodeMap, NodeSet, DefIdMap};
+use rustc::util::nodemap::{FxHashMap, NodeMap, NodeSet, DefIdMap};
 
 use std::cell::{RefCell, Cell};
 use std::rc::Rc;
@@ -76,7 +76,7 @@ pub struct CrateMetadata {
     /// hashmap, which gives the reverse mapping.  This allows us to
     /// quickly retrace a `DefPath`, which is needed for incremental
     /// compilation support.
-    pub key_map: FnvHashMap<DefKey, DefIndex>,
+    pub key_map: FxHashMap<DefKey, DefIndex>,
 
     /// Flag if this crate is required by an rlib version of this crate, or in
     /// other words whether it was explicitly linked to. An example of a crate
@@ -94,7 +94,7 @@ pub struct CachedInlinedItem {
 
 pub struct CStore {
     pub dep_graph: DepGraph,
-    metas: RefCell<FnvHashMap<CrateNum, Rc<CrateMetadata>>>,
+    metas: RefCell<FxHashMap<CrateNum, Rc<CrateMetadata>>>,
     /// Map from NodeId's of local extern crate statements to crate numbers
     extern_mod_crate_map: RefCell<NodeMap<CrateNum>>,
     used_crate_sources: RefCell<Vec<CrateSource>>,
@@ -110,15 +110,15 @@ impl CStore {
     pub fn new(dep_graph: &DepGraph) -> CStore {
         CStore {
             dep_graph: dep_graph.clone(),
-            metas: RefCell::new(FnvHashMap()),
-            extern_mod_crate_map: RefCell::new(FnvHashMap()),
+            metas: RefCell::new(FxHashMap()),
+            extern_mod_crate_map: RefCell::new(FxHashMap()),
             used_crate_sources: RefCell::new(Vec::new()),
             used_libraries: RefCell::new(Vec::new()),
             used_link_args: RefCell::new(Vec::new()),
             statically_included_foreign_items: RefCell::new(NodeSet()),
-            visible_parent_map: RefCell::new(FnvHashMap()),
-            inlined_item_cache: RefCell::new(FnvHashMap()),
-            defid_for_inlined_node: RefCell::new(FnvHashMap()),
+            visible_parent_map: RefCell::new(FxHashMap()),
+            inlined_item_cache: RefCell::new(FxHashMap()),
+            defid_for_inlined_node: RefCell::new(FxHashMap()),
         }
     }
 
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index ccd497860de..630b0774424 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -17,7 +17,7 @@ use schema::*;
 
 use rustc::hir::map as hir_map;
 use rustc::hir::map::{DefKey, DefPathData};
-use rustc::util::nodemap::FnvHashMap;
+use rustc::util::nodemap::FxHashMap;
 use rustc::hir;
 use rustc::hir::intravisit::IdRange;
 
@@ -432,7 +432,7 @@ impl<'a, 'tcx> MetadataBlob {
 
     /// Go through each item in the metadata and create a map from that
     /// item's def-key to the item's DefIndex.
-    pub fn load_key_map(&self, index: LazySeq<Index>) -> FnvHashMap<DefKey, DefIndex> {
+    pub fn load_key_map(&self, index: LazySeq<Index>) -> FxHashMap<DefKey, DefIndex> {
         index.iter_enumerated(self.raw_bytes())
             .map(|(index, item)| (item.decode(self).def_key.decode(self), index))
             .collect()
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index fdb117ef81b..fb4fb507296 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -23,7 +23,7 @@ use rustc::traits::specialization_graph;
 use rustc::ty::{self, Ty, TyCtxt};
 
 use rustc::session::config::{self, CrateTypeProcMacro};
-use rustc::util::nodemap::{FnvHashMap, NodeSet};
+use rustc::util::nodemap::{FxHashMap, NodeSet};
 
 use rustc_serialize::{Encodable, Encoder, SpecializedEncoder, opaque};
 use std::hash::Hash;
@@ -52,8 +52,8 @@ pub struct EncodeContext<'a, 'tcx: 'a> {
     reachable: &'a NodeSet,
 
     lazy_state: LazyState,
-    type_shorthands: FnvHashMap<Ty<'tcx>, usize>,
-    predicate_shorthands: FnvHashMap<ty::Predicate<'tcx>, usize>,
+    type_shorthands: FxHashMap<Ty<'tcx>, usize>,
+    predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
 }
 
 macro_rules! encoder_methods {
@@ -200,7 +200,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
                                       variant: &U,
                                       map: M)
                                       -> Result<(), <Self as Encoder>::Error>
-        where M: for<'b> Fn(&'b mut Self) -> &'b mut FnvHashMap<T, usize>,
+        where M: for<'b> Fn(&'b mut Self) -> &'b mut FxHashMap<T, usize>,
               T: Clone + Eq + Hash,
               U: Encodable
     {
@@ -1143,7 +1143,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 
 struct ImplVisitor<'a, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
-    impls: FnvHashMap<DefId, Vec<DefIndex>>,
+    impls: FxHashMap<DefId, Vec<DefIndex>>,
 }
 
 impl<'a, 'tcx, 'v> Visitor<'v> for ImplVisitor<'a, 'tcx> {
@@ -1165,7 +1165,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     fn encode_impls(&mut self) -> LazySeq<TraitImpls> {
         let mut visitor = ImplVisitor {
             tcx: self.tcx,
-            impls: FnvHashMap(),
+            impls: FxHashMap(),
         };
         self.tcx.map.krate().visit_all_items(&mut visitor);
 
diff --git a/src/librustc_metadata/locator.rs b/src/librustc_metadata/locator.rs
index 0461d7ec061..c31b209768c 100644
--- a/src/librustc_metadata/locator.rs
+++ b/src/librustc_metadata/locator.rs
@@ -221,7 +221,7 @@ use rustc::session::Session;
 use rustc::session::filesearch::{FileSearch, FileMatches, FileDoesntMatch};
 use rustc::session::search_paths::PathKind;
 use rustc::util::common;
-use rustc::util::nodemap::FnvHashMap;
+use rustc::util::nodemap::FxHashMap;
 
 use rustc_llvm as llvm;
 use rustc_llvm::{False, ObjectFile, mk_section_iter};
@@ -430,7 +430,7 @@ impl<'a> Context<'a> {
         let rlib_prefix = format!("lib{}", self.crate_name);
         let staticlib_prefix = format!("{}{}", staticpair.0, self.crate_name);
 
-        let mut candidates = FnvHashMap();
+        let mut candidates = FxHashMap();
         let mut staticlibs = vec![];
 
         // First, find all possible candidate rlibs and dylibs purely based on
@@ -469,7 +469,7 @@ impl<'a> Context<'a> {
 
             let hash_str = hash.to_string();
             let slot = candidates.entry(hash_str)
-                .or_insert_with(|| (FnvHashMap(), FnvHashMap()));
+                .or_insert_with(|| (FxHashMap(), FxHashMap()));
             let (ref mut rlibs, ref mut dylibs) = *slot;
             fs::canonicalize(path)
                 .map(|p| {
@@ -492,7 +492,7 @@ impl<'a> Context<'a> {
         // A Library candidate is created if the metadata for the set of
         // libraries corresponds to the crate id and hash criteria that this
         // search is being performed for.
-        let mut libraries = FnvHashMap();
+        let mut libraries = FxHashMap();
         for (_hash, (rlibs, dylibs)) in candidates {
             let mut slot = None;
             let rlib = self.extract_one(rlibs, CrateFlavor::Rlib, &mut slot);
@@ -544,7 +544,7 @@ impl<'a> Context<'a> {
     // be read, it is assumed that the file isn't a valid rust library (no
     // errors are emitted).
     fn extract_one(&mut self,
-                   m: FnvHashMap<PathBuf, PathKind>,
+                   m: FxHashMap<PathBuf, PathKind>,
                    flavor: CrateFlavor,
                    slot: &mut Option<(Svh, MetadataBlob)>)
                    -> Option<(PathBuf, PathKind)> {
@@ -690,8 +690,8 @@ impl<'a> Context<'a> {
         // rlibs/dylibs.
         let sess = self.sess;
         let dylibname = self.dylibname();
-        let mut rlibs = FnvHashMap();
-        let mut dylibs = FnvHashMap();
+        let mut rlibs = FxHashMap();
+        let mut dylibs = FxHashMap();
         {
             let locs = locs.map(|l| PathBuf::from(l)).filter(|loc| {
                 if !loc.exists() {