Intorduced MiniMap - a tiny small storage optimized map implementation

This makes everything about 1% faster in rustc-perf,
mostly negating performance hit of previous commit.

3 files changed, 63 insertions, 2 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 05d3a9c5621..23878f7ade7 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3594,6 +3594,7 @@ dependencies = [
 name = "rustc_infer"
 version = "0.0.0"
 dependencies = [
+ "arrayvec",
  "rustc_ast",
  "rustc_data_structures",
  "rustc_errors",
diff --git a/compiler/rustc_infer/Cargo.toml b/compiler/rustc_infer/Cargo.toml
index 5dba4106c94..a8c1a370cef 100644
--- a/compiler/rustc_infer/Cargo.toml
+++ b/compiler/rustc_infer/Cargo.toml
@@ -21,4 +21,5 @@ rustc_serialize = { path = "../rustc_serialize" }
 rustc_span = { path = "../rustc_span" }
 rustc_target = { path = "../rustc_target" }
 smallvec = { version = "1.0", features = ["union", "may_dangle"] }
+arrayvec = { version = "0.5.1", default-features = false }
 rustc_ast = { path = "../rustc_ast" }
diff --git a/compiler/rustc_infer/src/infer/combine.rs b/compiler/rustc_infer/src/infer/combine.rs
index bff8ed4ad05..68197f75b9f 100644
--- a/compiler/rustc_infer/src/infer/combine.rs
+++ b/compiler/rustc_infer/src/infer/combine.rs
@@ -31,7 +31,9 @@ use super::unify_key::replace_if_possible;
 use super::unify_key::{ConstVarValue, ConstVariableValue};
 use super::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
 use super::{InferCtxt, MiscVariable, TypeTrace};
+use arrayvec::ArrayVec;
 use rustc_data_structures::fx::FxHashMap;
+use std::hash::Hash;
 
 use crate::traits::{Obligation, PredicateObligations};
 
@@ -45,6 +47,63 @@ use rustc_middle::ty::{self, InferConst, ToPredicate, Ty, TyCtxt, TypeFoldable};
 use rustc_middle::ty::{IntType, UintType};
 use rustc_span::DUMMY_SP;
 
+/// Small-storage-optimized implementation of a map
+/// made specifically for caching results.
+///
+/// Stores elements in a small array up to a certain length
+/// and switches to `HashMap` when that length is exceeded.
+enum MiniMap<K, V> {
+    Array(ArrayVec<[(K, V); 8]>),
+    Map(FxHashMap<K, V>),
+}
+
+impl<K: Eq + Hash, V> MiniMap<K, V> {
+    /// Creates an empty `MiniMap`.
+    pub fn new() -> Self {
+        MiniMap::Array(ArrayVec::new())
+    }
+
+    /// Inserts or updates value in the map.
+    pub fn insert(&mut self, key: K, value: V) {
+        match self {
+            MiniMap::Array(array) => {
+                for pair in array.iter_mut() {
+                    if pair.0 == key {
+                        pair.1 = value;
+                        return;
+                    }
+                }
+                if let Err(error) = array.try_push((key, value)) {
+                    let mut map: FxHashMap<K, V> = array.drain(..).collect();
+                    let (key, value) = error.element();
+                    map.insert(key, value);
+                    *self = MiniMap::Map(map);
+                }
+            }
+            MiniMap::Map(map) => {
+                map.insert(key, value);
+            }
+        }
+    }
+
+    /// Return value by key if any.
+    pub fn get(&self, key: &K) -> Option<&V> {
+        match self {
+            MiniMap::Array(array) => {
+                for pair in array {
+                    if pair.0 == *key {
+                        return Some(&pair.1);
+                    }
+                }
+                return None;
+            }
+            MiniMap::Map(map) => {
+                return map.get(key);
+            }
+        }
+    }
+}
+
 #[derive(Clone)]
 pub struct CombineFields<'infcx, 'tcx> {
     pub infcx: &'infcx InferCtxt<'infcx, 'tcx>,
@@ -380,7 +439,7 @@ impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> {
             needs_wf: false,
             root_ty: ty,
             param_env: self.param_env,
-            cache: FxHashMap::default(),
+            cache: MiniMap::new(),
         };
 
         let ty = match generalize.relate(ty, ty) {
@@ -441,7 +500,7 @@ struct Generalizer<'cx, 'tcx> {
 
     param_env: ty::ParamEnv<'tcx>,
 
-    cache: FxHashMap<(Ty<'tcx>, Ty<'tcx>), RelateResult<'tcx, Ty<'tcx>>>,
+    cache: MiniMap<(Ty<'tcx>, Ty<'tcx>), RelateResult<'tcx, Ty<'tcx>>>,
 }
 
 /// Result from a generalization operation. This includes