HIR - Use maps-of-vectors for impl lists for faster lookup, optimise Trans_Enumerate

13 files changed, 477 insertions, 288 deletions

diff --git a/src/hir/deserialise.cpp b/src/hir/deserialise.cpp
index 35aeacca..9d5b6cd2 100644
--- a/src/hir/deserialise.cpp
+++ b/src/hir/deserialise.cpp
@@ -123,6 +123,20 @@
             }
             return rv;
         }
+        template<typename V>
+        ::std::map< ::HIR::SimplePath,V> deserialise_pathmap()
+        {
+            TRACE_FUNCTION_F("<" << typeid(V).name() << ">");
+            size_t n = m_in.read_count();
+            ::std::map< ::HIR::SimplePath, V>   rv;
+            //rv.reserve(n);
+            for(size_t i = 0; i < n; i ++)
+            {
+                auto s = deserialise_simplepath();
+                rv.insert( ::std::make_pair( mv$(s), D<V>::des(*this) ) );
+            }
+            return rv;
+        }
 
         template<typename T>
         ::std::vector<T> deserialise_vec()
@@ -779,6 +793,9 @@
     DEF_D( ::std::unique_ptr<T>,
         return d.deserialise_ptr<T>(); )
 
+    template<typename T>
+    DEF_D( ::std::vector<T>,
+        return d.deserialise_vec<T>(); )
     template<typename T, typename U>
     struct D< ::std::pair<T,U> > { static ::std::pair<T,U> des(HirDeserialiser& d) {
         auto a = D<T>::des(d);
@@ -817,6 +834,8 @@
 
     template<> DEF_D( ::HIR::ProcMacro, return d.deserialise_procmacro(); )
     template<> DEF_D( ::HIR::TypeImpl, return d.deserialise_typeimpl(); )
+    template<> DEF_D( ::HIR::TraitImpl, return d.deserialise_traitimpl(); )
+    template<> DEF_D( ::HIR::MarkerImpl, return d.deserialise_markerimpl(); )
     template<> DEF_D( ::MacroRulesPtr, return d.deserialise_macrorulesptr(); )
     template<> DEF_D( unsigned int, return static_cast<unsigned int>(d.deserialise_count()); )
 
@@ -1306,24 +1325,12 @@
         rv.m_crate_name = this->m_crate_name;
         rv.m_root_module = deserialise_module();
 
-        rv.m_type_impls = deserialise_vec< ::HIR::TypeImpl>();
+        rv.m_named_type_impls = deserialise_pathmap< ::std::vector<::HIR::TypeImpl>>();
+        rv.m_primitive_type_impls = deserialise_vec< ::HIR::TypeImpl>();
+        rv.m_generic_type_impls = deserialise_vec< ::HIR::TypeImpl>();
 
-        {
-            size_t n = m_in.read_count();
-            for(size_t i = 0; i < n; i ++)
-            {
-                auto p = deserialise_simplepath();
-                rv.m_trait_impls.insert( ::std::make_pair( mv$(p), deserialise_traitimpl() ) );
-            }
-        }
-        {
-            size_t n = m_in.read_count();
-            for(size_t i = 0; i < n; i ++)
-            {
-                auto p = deserialise_simplepath();
-                rv.m_marker_impls.insert( ::std::make_pair( mv$(p), deserialise_markerimpl() ) );
-            }
-        }
+        rv.m_trait_impls = deserialise_pathmap< ::std::vector<::HIR::TraitImpl>>();
+        rv.m_marker_impls = deserialise_pathmap< ::std::vector<::HIR::MarkerImpl>>();
 
         rv.m_exported_macros = deserialise_istrumap< ::MacroRulesPtr>();
         rv.m_lang_items = deserialise_strumap< ::HIR::SimplePath>();
diff --git a/src/hir/from_ast.cpp b/src/hir/from_ast.cpp
index 84980818..cb8438bf 100644
--- a/src/hir/from_ast.cpp
+++ b/src/hir/from_ast.cpp
@@ -1615,6 +1615,7 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
     {
         if( !i.data.is_Impl() ) continue;
         const auto& impl = i.data.as_Impl();
+        const Span  impl_span;
         auto params = LowerHIR_GenericParams(impl.def().params(), nullptr);
 
         TRACE_FUNCTION_F("IMPL " << impl.def());
@@ -1675,7 +1676,7 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
                     )
                 }
 
-                hir_crate.m_trait_impls.insert( ::std::make_pair(mv$(trait_name), ::HIR::TraitImpl {
+                hir_crate.m_trait_impls.insert( ::std::make_pair(mv$(trait_name), ::std::vector<::HIR::TraitImpl>()) ).first->second.push_back( ::HIR::TraitImpl {
                     mv$(params),
                     mv$(trait_args),
                     mv$(type),
@@ -1686,7 +1687,7 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
                     mv$(types),
 
                     LowerHIR_SimplePath(Span(), ast_mod.path())
-                    }) );
+                    } );
             }
             else if( impl.def().type().m_data.is_None() )
             {
@@ -1695,14 +1696,14 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
             else
             {
                 auto type = LowerHIR_Type(impl.def().type());
-                hir_crate.m_marker_impls.insert( ::std::make_pair( mv$(trait_name), ::HIR::MarkerImpl {
+                hir_crate.m_marker_impls.insert( ::std::make_pair(mv$(trait_name), ::std::vector<::HIR::MarkerImpl>()) ).first->second.push_back(::HIR::MarkerImpl {
                     mv$(params),
                     mv$(trait_args),
                     true,
                     mv$(type),
 
                     LowerHIR_SimplePath(Span(), ast_mod.path())
-                    } ) );
+                    } );
             }
         }
         else
@@ -1748,7 +1749,8 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
                 )
             }
 
-            hir_crate.m_type_impls.push_back( ::HIR::TypeImpl {
+            // Sorted later on
+            hir_crate.m_generic_type_impls.push_back( ::HIR::TypeImpl {
                 mv$(params),
                 mv$(type),
                 mv$(methods),
@@ -1769,14 +1771,14 @@ void LowerHIR_Module_Impls(const ::AST::Module& ast_mod,  ::HIR::Crate& hir_crat
         auto trait_name = mv$(trait.m_path);
         auto trait_args = mv$(trait.m_params);
 
-        hir_crate.m_marker_impls.insert( ::std::make_pair( mv$(trait_name), ::HIR::MarkerImpl {
+        hir_crate.m_marker_impls.insert( ::std::make_pair(mv$(trait_name), ::std::vector<::HIR::MarkerImpl>()) ).first->second.push_back(::HIR::MarkerImpl {
             mv$(params),
             mv$(trait_args),
             false,
             mv$(type),
 
             LowerHIR_SimplePath(Span(), ast_mod.path())
-            } ) );
+            } );
     }
 }
 
diff --git a/src/hir/hir.hpp b/src/hir/hir.hpp
index 3f045dd2..12b874a7 100644
--- a/src/hir/hir.hpp
+++ b/src/hir/hir.hpp
@@ -527,11 +527,17 @@ public:
 
     Module  m_root_module;
 
-    /// Impl blocks on just a type
-    ::std::vector< ::HIR::TypeImpl > m_type_impls;
+    /// Impl blocks on just a type, split into three groups
+    // - Named type (sorted on the path)
+    // - Primitive types
+    // - Unsorted (generics, and everything before outer type resolution)
+    ::std::map<::HIR::SimplePath, ::std::vector<::HIR::TypeImpl>> m_named_type_impls;
+    ::std::vector< ::HIR::TypeImpl> m_primitive_type_impls;
+    ::std::vector< ::HIR::TypeImpl> m_generic_type_impls;
+
     /// Impl blocks
-    ::std::multimap< ::HIR::SimplePath, ::HIR::TraitImpl > m_trait_impls;
-    ::std::multimap< ::HIR::SimplePath, ::HIR::MarkerImpl > m_marker_impls;
+    ::std::map< ::HIR::SimplePath, ::std::vector<::HIR::TraitImpl> > m_trait_impls;
+    ::std::map< ::HIR::SimplePath, ::std::vector<::HIR::MarkerImpl> > m_marker_impls;
 
     /// Macros exported by this crate
     ::std::unordered_map< RcString, ::MacroRulesPtr >  m_exported_macros;
diff --git a/src/hir/hir_ops.cpp b/src/hir/hir_ops.cpp
index 32c70a72..a484b5eb 100644
--- a/src/hir/hir_ops.cpp
+++ b/src/hir/hir_ops.cpp
@@ -15,9 +15,9 @@
 #include <mir/main_bindings.hpp>
 
 namespace {
-    bool matches_genericpath(const ::HIR::GenericParams& params, const ::HIR::GenericPath& left, const ::HIR::GenericPath& right, ::HIR::t_cb_resolve_type ty_res, bool expand_generic);
+    bool matches_genericpath(const ::HIR::GenericPath& left, const ::HIR::GenericPath& right, ::HIR::t_cb_resolve_type ty_res, bool expand_generic);
 
-    bool matches_type_int(const ::HIR::GenericParams& params, const ::HIR::TypeRef& left,  const ::HIR::TypeRef& right_in, ::HIR::t_cb_resolve_type ty_res, bool expand_generic)
+    bool matches_type_int(const ::HIR::TypeRef& left,  const ::HIR::TypeRef& right_in, ::HIR::t_cb_resolve_type ty_res, bool expand_generic)
     {
         assert(! left.m_data.is_Infer() );
         const auto& right = (right_in.m_data.is_Infer() || (right_in.m_data.is_Generic() && expand_generic) ? ty_res(right_in) : right_in);
@@ -97,7 +97,7 @@ namespace {
                 return false;
                 ),
             (Generic,
-                return matches_genericpath(params, ple, pre, ty_res, expand_generic);
+                return matches_genericpath( ple, pre, ty_res, expand_generic);
                 )
             )
             ),
@@ -105,7 +105,7 @@ namespace {
             throw "";
             ),
         (TraitObject,
-            if( !matches_genericpath(params, le.m_trait.m_path, re.m_trait.m_path, ty_res, expand_generic) )
+            if( !matches_genericpath(le.m_trait.m_path, re.m_trait.m_path, ty_res, expand_generic) )
                 return false;
             if( le.m_markers.size() != re.m_markers.size() )
                 return false;
@@ -113,7 +113,7 @@ namespace {
             {
                 const auto& lm = le.m_markers[i];
                 const auto& rm = re.m_markers[i];
-                if( !matches_genericpath(params, lm, rm, ty_res, expand_generic) )
+                if( !matches_genericpath(lm, rm, ty_res, expand_generic) )
                     return false;
             }
             return true;
@@ -122,32 +122,32 @@ namespace {
             throw "Unexpected ErasedType in matches_type_int";
             ),
         (Array,
-            if( ! matches_type_int(params, *le.inner, *re.inner, ty_res, expand_generic) )
+            if( ! matches_type_int(*le.inner, *re.inner, ty_res, expand_generic) )
                 return false;
             if( le.size_val != re.size_val )
                 return false;
             return true;
             ),
         (Slice,
-            return matches_type_int(params, *le.inner, *re.inner, ty_res, expand_generic);
+            return matches_type_int(*le.inner, *re.inner, ty_res, expand_generic);
             ),
         (Tuple,
             if( le.size() != re.size() )
                 return false;
             for( unsigned int i = 0; i < le.size(); i ++ )
-                if( !matches_type_int(params, le[i], re[i], ty_res, expand_generic) )
+                if( !matches_type_int(le[i], re[i], ty_res, expand_generic) )
                     return false;
             return true;
             ),
         (Borrow,
             if( le.type != re.type )
                 return false;
-            return matches_type_int(params, *le.inner, *re.inner, ty_res, expand_generic);
+            return matches_type_int(*le.inner, *re.inner, ty_res, expand_generic);
             ),
         (Pointer,
             if( le.type != re.type )
                 return false;
-            return matches_type_int(params, *le.inner, *re.inner, ty_res, expand_generic);
+            return matches_type_int(*le.inner, *re.inner, ty_res, expand_generic);
             ),
         (Function,
             if( le.is_unsafe != re.is_unsafe )
@@ -157,9 +157,9 @@ namespace {
             if( le.m_arg_types.size() != re.m_arg_types.size() )
                 return false;
             for( unsigned int i = 0; i < le.m_arg_types.size(); i ++ )
-                if( !matches_type_int(params, le.m_arg_types[i], re.m_arg_types[i], ty_res, expand_generic) )
+                if( !matches_type_int(le.m_arg_types[i], re.m_arg_types[i], ty_res, expand_generic) )
                     return false;
-            return matches_type_int(params, *le.m_rettype, *re.m_rettype, ty_res, expand_generic);
+            return matches_type_int(*le.m_rettype, *re.m_rettype, ty_res, expand_generic);
             ),
         (Closure,
             return le.node == re.node;
@@ -167,7 +167,7 @@ namespace {
         )
         return false;
     }
-    bool matches_genericpath(const ::HIR::GenericParams& params, const ::HIR::GenericPath& left, const ::HIR::GenericPath& right, ::HIR::t_cb_resolve_type ty_res, bool expand_generic)
+    bool matches_genericpath(const ::HIR::GenericPath& left, const ::HIR::GenericPath& right, ::HIR::t_cb_resolve_type ty_res, bool expand_generic)
     {
         if( left.m_path.m_crate_name != right.m_path.m_crate_name )
             return false;
@@ -188,7 +188,7 @@ namespace {
             }
             for( unsigned int i = 0; i < right.m_params.m_types.size(); i ++ )
             {
-                if( ! matches_type_int(params, left.m_params.m_types[i], right.m_params.m_types[i], ty_res, expand_generic) )
+                if( ! matches_type_int(left.m_params.m_types[i], right.m_params.m_types[i], ty_res, expand_generic) )
                     return false;
             }
         }
@@ -196,23 +196,6 @@ namespace {
     }
 }
 
-//::HIR::TypeRef HIR::Function::make_ty(const Span& sp, const ::HIR::PathParams& params) const
-//{
-//    // TODO: Obtain function type for this function (i.e. a type that is specifically for this function)
-//    auto fcn_ty_data = ::HIR::FunctionType {
-//        m_is_unsafe,
-//        m_abi,
-//        box$( monomorphise_type(sp, m_params, params,  m_return) ),
-//        {}
-//        };
-//    fcn_ty_data.m_arg_types.reserve( m_args.size() );
-//    for(const auto& arg : m_args)
-//    {
-//        fcn_ty_data.m_arg_types.push_back( monomorphise_type(sp, m_params, params,  arg.second) );
-//    }
-//    return ::HIR::TypeRef( mv$(fcn_ty_data) );
-//}
-
 namespace {
     bool is_unbounded_infer(const ::HIR::TypeRef& type) {
         if( const auto* e = type.m_data.opt_Infer() ) {
@@ -234,21 +217,21 @@ bool ::HIR::TraitImpl::matches_type(const ::HIR::TypeRef& type, ::HIR::t_cb_reso
     if( is_unbounded_infer(type) || TU_TEST1(type.m_data, Path, .binding.is_Unbound()) ) {
         return false;
     }
-    return matches_type_int(m_params, m_type, type, ty_res, true);
+    return matches_type_int(m_type, type, ty_res, true);
 }
 bool ::HIR::TypeImpl::matches_type(const ::HIR::TypeRef& type, ::HIR::t_cb_resolve_type ty_res) const
 {
     if( is_unbounded_infer(type) || TU_TEST1(type.m_data, Path, .binding.is_Unbound()) ) {
         return false;
     }
-    return matches_type_int(m_params, m_type, type, ty_res, true);
+    return matches_type_int(m_type, type, ty_res, true);
 }
 bool ::HIR::MarkerImpl::matches_type(const ::HIR::TypeRef& type, ::HIR::t_cb_resolve_type ty_res) const
 {
     if( is_unbounded_infer(type) || TU_TEST1(type.m_data, Path, .binding.is_Unbound()) ) {
         return false;
     }
-    return matches_type_int(m_params, m_type, type, ty_res, true);
+    return matches_type_int(m_type, type, ty_res, true);
 }
 
 namespace {
@@ -954,13 +937,15 @@ bool ::HIR::TraitImpl::overlaps_with(const Crate& crate, const ::HIR::TraitImpl&
 
 bool ::HIR::Crate::find_trait_impls(const ::HIR::SimplePath& trait, const ::HIR::TypeRef& type, t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::TraitImpl&)> callback) const
 {
-    auto its = this->m_trait_impls.equal_range( trait );
-    for( auto it = its.first; it != its.second; ++ it )
+    auto it = this->m_trait_impls.find( trait );
+    if( it != this->m_trait_impls.end() )
     {
-        const auto& impl = it->second;
-        if( impl.matches_type(type, ty_res) ) {
-            if( callback(impl) ) {
-                return true;
+        for(const auto& impl : it->second)
+        {
+            if( impl.matches_type(type, ty_res) ) {
+                if( callback(impl) ) {
+                    return true;
+                }
             }
         }
     }
@@ -974,13 +959,15 @@ bool ::HIR::Crate::find_trait_impls(const ::HIR::SimplePath& trait, const ::HIR:
 }
 bool ::HIR::Crate::find_auto_trait_impls(const ::HIR::SimplePath& trait, const ::HIR::TypeRef& type, t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::MarkerImpl&)> callback) const
 {
-    auto its = this->m_marker_impls.equal_range( trait );
-    for( auto it = its.first; it != its.second; ++ it )
+    auto it = this->m_marker_impls.find( trait );
+    if( it != this->m_marker_impls.end() )
     {
-        const auto& impl = it->second;
-        if( impl.matches_type(type, ty_res) ) {
-            if( callback(impl) ) {
-                return true;
+        for(const auto& impl : it->second)
+        {
+            if( impl.matches_type(type, ty_res) ) {
+                if( callback(impl) ) {
+                    return true;
+                }
             }
         }
     }
@@ -992,21 +979,90 @@ bool ::HIR::Crate::find_auto_trait_impls(const ::HIR::SimplePath& trait, const :
     }
     return false;
 }
-bool ::HIR::Crate::find_type_impls(const ::HIR::TypeRef& type, t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::TypeImpl&)> callback) const
+namespace
 {
-    // TODO: Restrict which crate is searched based on the type.
-    for( const auto& impl : this->m_type_impls )
+    bool find_type_impls_list(const ::std::vector<HIR::TypeImpl>& impl_list, const ::HIR::TypeRef& type, ::HIR::t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::TypeImpl&)> callback)
     {
-        if( impl.matches_type(type, ty_res) ) {
-            if( callback(impl) ) {
-                return true;
+        for(const auto& impl : impl_list)
+        {
+            if( impl.matches_type(type, ty_res) )
+            {
+                if( callback(impl) )
+                {
+                    return true;
+                }
             }
         }
+        return false;
+    }
+    bool find_type_impls_int(const ::HIR::Crate& crate, const ::HIR::SimplePath* sort_path, const ::HIR::TypeRef& type, ::HIR::t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::TypeImpl&)> callback)
+    {
+        // 1. Find named impls (associated with named types)
+        if( sort_path )
+        {
+            // TODO: This fails if the type is marked as #[fundamental]
+            //if( sort_path->m_crate_name != crate.m_crate_name ) {
+            //    return false;
+            //}
+
+            auto impl_list_it = crate.m_named_type_impls.find(*sort_path);
+            if( impl_list_it != crate.m_named_type_impls.end() )
+            {
+                if( find_type_impls_list(impl_list_it->second, type, ty_res, callback) )
+                    return true;
+            }
+        }
+        // - If this type has no associated path, look in the primitives list
+        else
+        {
+            if( find_type_impls_list(crate.m_primitive_type_impls, type, ty_res, callback) )
+                return true;
+        }
+
+        // 2. Search fully generic list?
+        if( find_type_impls_list(crate.m_generic_type_impls, type, ty_res, callback) )
+            return true;
+
+        return false;
+    }
+}
+bool ::HIR::Crate::find_type_impls(const ::HIR::TypeRef& type, t_cb_resolve_type ty_res, ::std::function<bool(const ::HIR::TypeImpl&)> callback) const
+{
+    const ::HIR::SimplePath*    path = nullptr;
+    // - Generic paths get sorted
+    if( TU_TEST1(type.m_data, Path, .path.m_data.is_Generic()) )
+    {
+        path = &type.m_data.as_Path().path.m_data.as_Generic().m_path;
+    }
+    // - So do trait objects
+    else if( type.m_data.is_TraitObject() )
+    {
+        path = &type.m_data.as_TraitObject().m_trait.m_path.m_path;
+    }
+    else
+    {
+        // Keep as nullptr, will search primitive list
+    }
+
+    if( path )
+    {
+        DEBUG(type << ", path=" << *path);
+    }
+    else
+    {
+        DEBUG(type << ", no path");
+    }
+
+    // > Current crate
+    if( find_type_impls_int(*this, path, type, ty_res, callback) )
+    {
+        return true;
     }
     for( const auto& ec : this->m_ext_crates )
     {
         //DEBUG("- " << ec.first);
-        if( ec.second.m_data->find_type_impls(type, ty_res, callback) ) {
+        if( find_type_impls_int(*ec.second.m_data, path, type, ty_res, callback) )
+        {
             return true;
         }
     }
diff --git a/src/hir/serialise.cpp b/src/hir/serialise.cpp
index fc53e245..83e6d016 100644
--- a/src/hir/serialise.cpp
+++ b/src/hir/serialise.cpp
@@ -39,6 +39,16 @@
             }
         }
         template<typename V>
+        void serialise_pathmap(const ::std::map< ::HIR::SimplePath,V>& map)
+        {
+            m_out.write_count(map.size());
+            for(const auto& v : map) {
+                DEBUG("- " << v.first);
+                serialise(v.first);
+                serialise(v.second);
+            }
+        }
+        template<typename V>
         void serialise_strmap(const ::std::unordered_map<RcString,V>& map)
         {
             m_out.write_count(map.size());
@@ -87,6 +97,11 @@
                 serialise(i);
         }
         template<typename T>
+        void serialise(const ::std::vector<T>& vec)
+        {
+            serialise_vec(vec);
+        }
+        template<typename T>
         void serialise(const ::HIR::VisEnt<T>& e)
         {
             m_out.write_bool(e.publicity.is_global());  // At this stage, we only care if the item is visible outside the crate or not
@@ -299,20 +314,13 @@
             m_out.write_string(crate.m_crate_name);
             serialise_module(crate.m_root_module);
 
-            m_out.write_count(crate.m_type_impls.size());
-            for(const auto& impl : crate.m_type_impls) {
-                serialise_typeimpl(impl);
-            }
-            m_out.write_count(crate.m_trait_impls.size());
-            for(const auto& tr_impl : crate.m_trait_impls) {
-                serialise_simplepath(tr_impl.first);
-                serialise_traitimpl(tr_impl.second);
-            }
-            m_out.write_count(crate.m_marker_impls.size());
-            for(const auto& tr_impl : crate.m_marker_impls) {
-                serialise_simplepath(tr_impl.first);
-                serialise_markerimpl(tr_impl.second);
-            }
+            //std::map<HIR::SimplePath,std::vector<TypeImpl>>
+            serialise_pathmap(crate.m_named_type_impls);
+            serialise_vec(crate.m_primitive_type_impls);
+            serialise_vec(crate.m_generic_type_impls);
+
+            serialise_pathmap(crate.m_trait_impls);
+            serialise_pathmap(crate.m_marker_impls);
 
             serialise_strmap(crate.m_exported_macros);
             {
@@ -373,6 +381,10 @@
             }
             // m_src_module doesn't matter after typeck
         }
+        void serialise(const ::HIR::TypeImpl& impl)
+        {
+            serialise_typeimpl(impl);
+        }
         void serialise_traitimpl(const ::HIR::TraitImpl& impl)
         {
             TRACE_FUNCTION_F("impl" << impl.m_params.fmt_args() << " ?" << impl.m_trait_args << " for " << impl.m_type);
@@ -410,6 +422,10 @@
             }
             // m_src_module doesn't matter after typeck
         }
+        void serialise(const ::HIR::TraitImpl& impl)
+        {
+            serialise_traitimpl(impl);
+        }
         void serialise_markerimpl(const ::HIR::MarkerImpl& impl)
         {
             serialise_generics(impl.m_params);
@@ -417,6 +433,10 @@
             m_out.write_bool(impl.is_positive);
             serialise_type(impl.m_type);
         }
+        void serialise(const ::HIR::MarkerImpl& impl)
+        {
+            serialise_markerimpl(impl);
+        }
 
         void serialise(const ::HIR::TypeRef& ty) {
             serialise_type(ty);
diff --git a/src/hir/visitor.cpp b/src/hir/visitor.cpp
index f23bae88..8bf674b3 100644
--- a/src/hir/visitor.cpp
+++ b/src/hir/visitor.cpp
@@ -16,17 +16,34 @@ void ::HIR::Visitor::visit_crate(::HIR::Crate& crate)
 {
     this->visit_module(::HIR::ItemPath(crate.m_crate_name), crate.m_root_module );
 
-    for( auto& ty_impl : crate.m_type_impls )
+    for( auto& ty_impl_group : crate.m_named_type_impls )
+    {
+        for( auto& ty_impl : ty_impl_group.second )
+        {
+            this->visit_type_impl(ty_impl);
+        }
+    }
+    for( auto& ty_impl : crate.m_primitive_type_impls )
     {
         this->visit_type_impl(ty_impl);
     }
-    for( auto& impl : crate.m_trait_impls )
+    for( auto& ty_impl : crate.m_generic_type_impls )
     {
-        this->visit_trait_impl(impl.first, impl.second);
+        this->visit_type_impl(ty_impl);
     }
-    for( auto& impl : crate.m_marker_impls )
+    for( auto& impl_group : crate.m_trait_impls )
     {
-        this->visit_marker_impl(impl.first, impl.second);
+        for( auto& impl : impl_group.second )
+        {
+            this->visit_trait_impl(impl_group.first, impl);
+        }
+    }
+    for( auto& impl_group : crate.m_marker_impls )
+    {
+        for( auto& impl : impl_group.second )
+        {
+            this->visit_marker_impl(impl_group.first, impl);
+        }
     }
 }
 
diff --git a/src/hir_conv/resolve_ufcs_outer.cpp b/src/hir_conv/resolve_ufcs_outer.cpp
index a8accf4d..285f6e55 100644
--- a/src/hir_conv/resolve_ufcs_outer.cpp
+++ b/src/hir_conv/resolve_ufcs_outer.cpp
@@ -13,6 +13,7 @@
 #include <hir/expr.hpp>
 #include <hir/visitor.hpp>
 #include <hir_typeck/common.hpp>    // monomorphise_genericpath_needed
+#include <algorithm>
 
 namespace {
     class Visitor:
@@ -342,4 +343,46 @@ void ConvertHIR_ResolveUFCS_Outer(::HIR::Crate& crate)
 {
     Visitor exp { crate };
     exp.visit_crate( crate );
+
+    // Sort impls!
+    auto new_end = ::std::remove_if(crate.m_generic_type_impls.begin(), crate.m_generic_type_impls.end(), [&crate](::HIR::TypeImpl& ty_impl) {
+        const auto& type = ty_impl.m_type;
+        const ::HIR::SimplePath*    path = nullptr;
+        // - Generic paths get sorted
+        if( TU_TEST1(type.m_data, Path, .path.m_data.is_Generic()) )
+        {
+            path = &type.m_data.as_Path().path.m_data.as_Generic().m_path;
+        }
+        // - So do trait objects
+        else if( type.m_data.is_TraitObject() )
+        {
+            path = &type.m_data.as_TraitObject().m_trait.m_path.m_path;
+        }
+        else
+        {
+            // Keep as nullptr, will search primitive list
+        }
+
+        if( path )
+        {
+            auto it = crate.m_named_type_impls.find(*path);
+            if( it == crate.m_named_type_impls.end() )
+            {
+                it = crate.m_named_type_impls.insert( ::std::make_pair(*path, ::std::vector<::HIR::TypeImpl>()) ).first;
+            }
+            it->second.push_back(mv$(ty_impl));
+        }
+        else if( type.m_data.is_Path() || type.m_data.is_Generic() )
+        {
+            return false;
+        }
+        else
+        {
+            crate.m_primitive_type_impls.push_back(mv$(ty_impl));
+        }
+        return true;
+        });
+    crate.m_generic_type_impls.erase(new_end, crate.m_generic_type_impls.end());
+
+    DEBUG("Impl counts: " << crate.m_named_type_impls.size() << " path groups, " << crate.m_primitive_type_impls.size() << " primitive, " << crate.m_generic_type_impls.size() << " ungrouped");
 }
diff --git a/src/hir_expand/closures.cpp b/src/hir_expand/closures.cpp
index 94f272f8..b4ab564c 100644
--- a/src/hir_expand/closures.cpp
+++ b/src/hir_expand/closures.cpp
@@ -46,6 +46,48 @@ namespace {
         return rv;
     }
 
+    void push_new_impls(const Span& sp, ::HIR::Crate& crate, out_impls_t new_trait_impls)
+    {
+        for(auto& impl : new_trait_impls)
+        {
+            switch(impl.first)
+            {
+            case ::HIR::ExprNode_Closure::Class::Once:
+                crate.m_trait_impls[crate.get_lang_item_path(sp, "fn_once")].push_back( mv$(impl.second) );
+                break;
+            case ::HIR::ExprNode_Closure::Class::Mut:
+                crate.m_trait_impls[crate.get_lang_item_path(sp, "fn_mut" )].push_back( mv$(impl.second) );
+                break;
+            case ::HIR::ExprNode_Closure::Class::Shared:
+                crate.m_trait_impls[crate.get_lang_item_path(sp, "fn"     )].push_back( mv$(impl.second) );
+                break;
+            case ::HIR::ExprNode_Closure::Class::NoCapture: {
+                assert(impl.second.m_methods.size() == 1);
+                assert(impl.second.m_types.empty());
+                assert(impl.second.m_constants.empty());
+                // NOTE: This should always have a name
+                const auto& path = impl.second.m_type.m_data.as_Path().path.m_data.as_Generic().m_path;
+                DEBUG("Adding type impl " << path);
+                auto list_it = crate.m_named_type_impls.insert( ::std::make_pair(path, ::std::vector<::HIR::TypeImpl>()) ).first;
+                list_it->second.push_back( ::HIR::TypeImpl {
+                    mv$(impl.second.m_params),
+                    mv$(impl.second.m_type),
+                    make_map1(
+                        impl.second.m_methods.begin()->first,
+                        ::HIR::TypeImpl::VisImplEnt< ::HIR::Function> { ::HIR::Publicity::new_global(), false,  mv$(impl.second.m_methods.begin()->second.data) }
+                        ),
+                    {},
+                    mv$(impl.second.m_src_module)
+                    } );
+                } break;
+            case ::HIR::ExprNode_Closure::Class::Unknown:
+                BUG(Span(), "Encountered Unkown closure type in new impls");
+                break;
+            }
+        }
+        new_trait_impls.resize(0);
+    }
+
     /// Mutate the contents of a closure to update captures, variables, and types
     class ExprVisitor_Mutate:
         public ::HIR::ExprVisitorDef
@@ -1190,37 +1232,8 @@ namespace {
 
             ::HIR::Visitor::visit_crate(crate);
 
-            for(auto& impl : m_new_trait_impls)
-            {
-                switch(impl.first)
-                {
-                case ::HIR::ExprNode_Closure::Class::Once:
-                    crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn_once"), mv$(impl.second)) );
-                    break;
-                case ::HIR::ExprNode_Closure::Class::Mut:
-                    crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn_mut" ), mv$(impl.second)) );
-                    break;
-                case ::HIR::ExprNode_Closure::Class::Shared:
-                    crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn"     ), mv$(impl.second)) );
-                    break;
-                case ::HIR::ExprNode_Closure::Class::NoCapture:
-                    assert(impl.second.m_methods.size() == 1);
-                    assert(impl.second.m_types.empty());
-                    assert(impl.second.m_constants.empty());
-                    crate.m_type_impls.push_back( ::HIR::TypeImpl {
-                        mv$(impl.second.m_params),
-                        mv$(impl.second.m_type),
-                        make_map1(impl.second.m_methods.begin()->first, ::HIR::TypeImpl::VisImplEnt< ::HIR::Function> { ::HIR::Publicity::new_global(), false,  mv$(impl.second.m_methods.begin()->second.data) }),
-                        {},
-                        mv$(impl.second.m_src_module)
-                        } );
-                    break;
-                case ::HIR::ExprNode_Closure::Class::Unknown:
-                    BUG(Span(), "Encountered Unkown closure type in new impls");
-                    break;
-                }
-            }
-            m_new_trait_impls.resize(0);
+            push_new_impls(sp, crate, mv$(m_new_trait_impls));
+            m_new_trait_impls.clear();
         }
 
         void visit_module(::HIR::ItemPath p, ::HIR::Module& mod) override
@@ -1399,34 +1412,8 @@ void HIR_Expand_Closures_Expr(const ::HIR::Crate& crate_ro, ::HIR::ExprPtr& exp)
             m.second.data.m_code.m_state->stage = ::HIR::ExprState::Stage::Typecheck;
         }
         impl.second.m_src_module = exp.m_state->m_mod_path;
-        switch(impl.first)
-        {
-        case ::HIR::ExprNode_Closure::Class::Once:
-            crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn_once"), mv$(impl.second)) );
-            break;
-        case ::HIR::ExprNode_Closure::Class::Mut:
-            crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn_mut" ), mv$(impl.second)) );
-            break;
-        case ::HIR::ExprNode_Closure::Class::Shared:
-            crate.m_trait_impls.insert( ::std::make_pair(crate.get_lang_item_path(sp, "fn"     ), mv$(impl.second)) );
-            break;
-        case ::HIR::ExprNode_Closure::Class::NoCapture:
-            assert(impl.second.m_methods.size() == 1);
-            assert(impl.second.m_types.empty());
-            assert(impl.second.m_constants.empty());
-            crate.m_type_impls.push_back( ::HIR::TypeImpl {
-                mv$(impl.second.m_params),
-                mv$(impl.second.m_type),
-                make_map1(impl.second.m_methods.begin()->first, ::HIR::TypeImpl::VisImplEnt< ::HIR::Function> { ::HIR::Publicity::new_global(), false,  mv$(impl.second.m_methods.begin()->second.data) }),
-                {},
-                mv$(impl.second.m_src_module)
-                } );
-            break;
-        case ::HIR::ExprNode_Closure::Class::Unknown:
-            BUG(Span(), "Encountered Unkown closure type in new impls");
-            break;
-        }
     }
+    push_new_impls(sp, crate, mv$(new_trait_impls));
 }
 
 void HIR_Expand_Closures(::HIR::Crate& crate)
diff --git a/src/hir_typeck/outer.cpp b/src/hir_typeck/outer.cpp
index c2b216d4..38c6f652 100644
--- a/src/hir_typeck/outer.cpp
+++ b/src/hir_typeck/outer.cpp
@@ -506,26 +506,25 @@ namespace {
             )
             else {
                 // 1. Search for applicable inherent methods (COMES FIRST!)
-                for( const auto& impl : this->crate.m_type_impls )
-                {
-                    if( !impl.matches_type(*e.type) ) {
-                        continue ;
-                    }
+                if( this->crate.find_type_impls(*e.type, [](const auto& ty)->const auto&{return ty;}, [&](const auto& impl) {
                     DEBUG("- matched inherent impl " << *e.type);
                     // Search for item in this block
                     switch( pc )
                     {
                     case ::HIR::Visitor::PathContext::VALUE:
                         if( impl.m_methods.find(e.item) == impl.m_methods.end() ) {
-                            continue ;
+                            return false;
                         }
                         // Found it, just keep going (don't care about details here)
                         break;
                     case ::HIR::Visitor::PathContext::TRAIT:
                     case ::HIR::Visitor::PathContext::TYPE:
-                        continue ;
+                        return false;
                     }
 
+                    return true;
+                    }) )
+                {
                     auto new_data = ::HIR::Path::Data::make_UfcsInherent({ mv$(e.type), mv$(e.item), mv$(e.params)} );
                     p.m_data = mv$(new_data);
                     DEBUG("- Resolved, replace with " << p);
diff --git a/src/trans/auto_impls.cpp b/src/trans/auto_impls.cpp
index ea10c8e2..ced322a4 100644
--- a/src/trans/auto_impls.cpp
+++ b/src/trans/auto_impls.cpp
@@ -202,7 +202,7 @@ void Trans_AutoImpl_Clone(State& state, ::HIR::TypeRef ty)
     impl.m_methods.insert(::std::make_pair( RcString::new_interned("clone"), ::HIR::TraitImpl::ImplEnt< ::HIR::Function> { false, ::std::move(fcn) } ));
 
     // Add impl to the crate
-    state.crate.m_trait_impls.insert(::std::make_pair( state.lang_Clone, ::std::move(impl) ));
+    state.crate.m_trait_impls[state.lang_Clone].push_back( ::std::move(impl) );
 }
 
 void Trans_AutoImpls(::HIR::Crate& crate, TransList& trans_list)
@@ -227,18 +227,19 @@ void Trans_AutoImpls(::HIR::Crate& crate, TransList& trans_list)
         Trans_AutoImpl_Clone(state, mv$(ty));
     }
 
-    const auto impl_range = crate.m_trait_impls.equal_range( state.lang_Clone );
+    auto impl_list_it = crate.m_trait_impls.find(state.lang_Clone);
     for(const auto& ty : state.done_list)
     {
+        assert(impl_list_it != crate.m_trait_impls.end());
         // TODO: Find a way of turning a set into a vector so items can be erased.
 
         auto p = ::HIR::Path(ty.clone(), ::HIR::GenericPath(state.lang_Clone), "clone");
         //DEBUG("add_function(" << p << ")");
         auto e = trans_list.add_function(::std::move(p));
 
-        auto it = ::std::find_if( impl_range.first, impl_range.second, [&](const auto& i){ return i.second.m_type == ty; });
-        assert( it->second.m_methods.size() == 1 );
-        e->ptr = &it->second.m_methods.begin()->second.data;
+        auto it = ::std::find_if( impl_list_it->second.begin(), impl_list_it->second.end(), [&](const auto& i){ return i.m_type == ty; });
+        assert( it->m_methods.size() == 1 );
+        e->ptr = &it->m_methods.begin()->second.data;
     }
 }
 
diff --git a/src/trans/enumerate.cpp b/src/trans/enumerate.cpp
index dfc566c0..7ef605b9 100644
--- a/src/trans/enumerate.cpp
+++ b/src/trans/enumerate.cpp
@@ -48,6 +48,7 @@ namespace {
 TransList Trans_Enumerate_CommonPost(EnumState& state);
 void Trans_Enumerate_Types(EnumState& state);
 void Trans_Enumerate_FillFrom_Path(EnumState& state, const ::HIR::Path& path, const Trans_Params& pp);
+void Trans_Enumerate_FillFrom_PathMono(EnumState& state, ::HIR::Path path);
 void Trans_Enumerate_FillFrom(EnumState& state, const ::HIR::Function& function, const Trans_Params& pp);
 void Trans_Enumerate_FillFrom(EnumState& state, const ::HIR::Static& stat, TransList_Static& stat_out, Trans_Params pp={});
 void Trans_Enumerate_FillFrom_VTable (EnumState& state, ::HIR::Path vtable_path, const Trans_Params& pp);
@@ -176,100 +177,125 @@ TransList Trans_Enumerate_Public(::HIR::Crate& crate)
 
     // Impl blocks
     StaticTraitResolve resolve { crate };
-    for(auto& impl : crate.m_trait_impls)
+    for(auto& impl_group : crate.m_trait_impls)
     {
-        const auto& impl_ty = impl.second.m_type;
-        TRACE_FUNCTION_F("Impl " << impl.first << impl.second.m_trait_args << " for " << impl_ty);
-        if( impl.second.m_params.m_types.size() == 0 )
+        const auto& trait_path = impl_group.first;
+        for(auto& impl : impl_group.second)
         {
-            auto cb_monomorph = monomorphise_type_get_cb(sp, &impl_ty, &impl.second.m_trait_args, nullptr);
-
-            // Emit each method/static (in the trait itself)
-            const auto& trait = crate.get_trait_by_path(sp, impl.first);
-            for(const auto& vi : trait.m_values)
+            const auto& impl_ty = impl.m_type;
+            TRACE_FUNCTION_F("Impl " << trait_path << impl.m_trait_args << " for " << impl_ty);
+            if( impl.m_params.m_types.size() == 0 )
             {
-                TRACE_FUNCTION_F("Item " << vi.first << " : " << vi.second.tag_str());
-                // Constant, no codegen
-                if( vi.second.is_Constant() )
-                    ;
-                // Generic method, no codegen
-                else if( vi.second.is_Function() && vi.second.as_Function().m_params.m_types.size() > 0 )
-                    ;
-                // VTable, magic
-                else if( vi.first == "vtable#" )
-                    ;
-                else
+                auto cb_monomorph = monomorphise_type_get_cb(sp, &impl_ty, &impl.m_trait_args, nullptr);
+
+                // Emit each method/static (in the trait itself)
+                const auto& trait = crate.get_trait_by_path(sp, trait_path);
+                for(const auto& vi : trait.m_values)
                 {
-                    // Check bounds before queueing for codegen
-                    if( vi.second.is_Function() )
+                    TRACE_FUNCTION_F("Item " << vi.first << " : " << vi.second.tag_str());
+                    // Constant, no codegen
+                    if( vi.second.is_Constant() )
+                        ;
+                    // Generic method, no codegen
+                    else if( vi.second.is_Function() && vi.second.as_Function().m_params.m_types.size() > 0 )
+                        ;
+                    // VTable, magic
+                    else if( vi.first == "vtable#" )
+                        ;
+                    else
                     {
-                        bool rv = true;
-                        for(const auto& b : vi.second.as_Function().m_params.m_bounds)
+                        // Check bounds before queueing for codegen
+                        if( vi.second.is_Function() )
                         {
-                            if( !b.is_TraitBound() )    continue;
-                            const auto& be = b.as_TraitBound();
+                            bool rv = true;
+                            for(const auto& b : vi.second.as_Function().m_params.m_bounds)
+                            {
+                                if( !b.is_TraitBound() )    continue;
+                                const auto& be = b.as_TraitBound();
 
-                            auto b_ty_mono = monomorphise_type_with(sp, be.type, cb_monomorph); resolve.expand_associated_types(sp, b_ty_mono);
-                            auto b_tp_mono = monomorphise_traitpath_with(sp, be.trait, cb_monomorph, false);
-                            for(auto& ty : b_tp_mono.m_path.m_params.m_types) {
-                                resolve.expand_associated_types(sp, ty);
-                            }
-                            for(auto& assoc_bound : b_tp_mono.m_type_bounds) {
-                                resolve.expand_associated_types(sp, assoc_bound.second);
-                            }
+                                auto b_ty_mono = monomorphise_type_with(sp, be.type, cb_monomorph); resolve.expand_associated_types(sp, b_ty_mono);
+                                auto b_tp_mono = monomorphise_traitpath_with(sp, be.trait, cb_monomorph, false);
+                                for(auto& ty : b_tp_mono.m_path.m_params.m_types) {
+                                    resolve.expand_associated_types(sp, ty);
+                                }
+                                for(auto& assoc_bound : b_tp_mono.m_type_bounds) {
+                                    resolve.expand_associated_types(sp, assoc_bound.second);
+                                }
 
-                            rv = resolve.find_impl(sp, b_tp_mono.m_path.m_path, b_tp_mono.m_path.m_params, b_ty_mono, [&](const auto& impl, bool) {
-                                return true;
-                                });
+                                rv = resolve.find_impl(sp, b_tp_mono.m_path.m_path, b_tp_mono.m_path.m_params, b_ty_mono, [&](const auto& impl, bool) {
+                                    return true;
+                                    });
+                                if( !rv )
+                                    break;
+                            }
                             if( !rv )
-                                break;
+                                continue ;
                         }
-                        if( !rv )
-                            continue ;
+                        auto path = ::HIR::Path(impl_ty.clone(), ::HIR::GenericPath(trait_path, impl.m_trait_args.clone()), vi.first);
+                        Trans_Enumerate_FillFrom_PathMono(state, mv$(path));
+                        //state.enum_fcn(mv$(path), fcn.second.data, {});
                     }
-                    auto p = ::HIR::Path(impl_ty.clone(), ::HIR::GenericPath(impl.first, impl.second.m_trait_args.clone()), vi.first);
-                    Trans_Enumerate_FillFrom_Path(state, p, {});
+                }
+                for(auto& m : impl.m_methods)
+                {
+                    if( m.second.data.m_params.m_types.size() > 0 )
+                        m.second.data.m_save_code = true;
                 }
             }
-            for(auto& m : impl.second.m_methods)
+            else
             {
-                if( m.second.data.m_params.m_types.size() > 0 )
+                for(auto& m : impl.m_methods)
+                {
                     m.second.data.m_save_code = true;
-            }
-        }
-        else
-        {
-            for(auto& m : impl.second.m_methods)
-            {
-                m.second.data.m_save_code = true;
+                }
             }
         }
     }
-    for(auto& impl : crate.m_type_impls)
+    struct H1
     {
-        if( impl.m_params.m_types.size() == 0 )
+        static void enumerate_type_impl(EnumState& state, ::HIR::TypeImpl& impl)
         {
-            for(auto& fcn : impl.m_methods)
+            TRACE_FUNCTION_F("impl" << impl.m_params.fmt_args() << " " << impl.m_type);
+            if( impl.m_params.m_types.size() == 0 )
             {
-                if( fcn.second.data.m_params.m_types.size() == 0 )
+                for(auto& fcn : impl.m_methods)
                 {
-                    auto p = ::HIR::Path(impl.m_type.clone(), fcn.first);
-                    Trans_Enumerate_FillFrom_Path(state, p, {});
+                    DEBUG("fn " << fcn.first << fcn.second.data.m_params.fmt_args());
+                    if( fcn.second.data.m_params.m_types.size() == 0 )
+                    {
+                        auto path = ::HIR::Path(impl.m_type.clone(), fcn.first);
+                        state.enum_fcn(mv$(path), fcn.second.data, {});
+                    }
+                    else
+                    {
+                        fcn.second.data.m_save_code = true;
+                    }
                 }
-                else
+            }
+            else
+            {
+                for(auto& m : impl.m_methods)
                 {
-                    fcn.second.data.m_save_code = true;
+                    m.second.data.m_save_code = true;
                 }
             }
         }
-        else
+    };
+    for(auto& impl_grp : crate.m_named_type_impls)
+    {
+        for(auto& impl : impl_grp.second)
         {
-            for(auto& m : impl.m_methods)
-            {
-                m.second.data.m_save_code = true;
-            }
+            H1::enumerate_type_impl(state, impl);
         }
     }
+    for(auto& impl : crate.m_primitive_type_impls)
+    {
+        H1::enumerate_type_impl(state, impl);
+    }
+    for(auto& impl : crate.m_generic_type_impls)
+    {
+        H1::enumerate_type_impl(state, impl);
+    }
 
     auto rv = Trans_Enumerate_CommonPost(state);
 
@@ -407,7 +433,8 @@ TransList Trans_Enumerate_CommonPost(EnumState& state)
     return mv$(state.rv);
 }
 
-namespace {
+namespace
+{
     struct PtrComp
     {
         template<typename T>
@@ -420,7 +447,8 @@ namespace {
         ::StaticTraitResolve    m_resolve;
         ::std::vector< ::std::pair< ::HIR::TypeRef, bool> >& out_list;
 
-        ::std::map< ::HIR::TypeRef, bool > visited;
+        // TODO: Have a list of indexes into `out_list`, sorted by typeref ordering
+        ::std::vector<size_t>   visited_map;
         ::std::set< const ::HIR::TypeRef*, PtrComp> active_set;
 
         TypeVisitor(const ::HIR::Crate& crate, ::std::vector< ::std::pair< ::HIR::TypeRef, bool > >& out_list):
@@ -429,6 +457,11 @@ namespace {
             out_list(out_list)
         {}
 
+        ~TypeVisitor()
+        {
+            DEBUG("Visited a total of " << visited_map.size());
+        }
+
         void visit_struct(const ::HIR::GenericPath& path, const ::HIR::Struct& item) {
             static Span sp;
             ::HIR::TypeRef  tmp;
@@ -506,16 +539,16 @@ namespace {
         {
             // If the type has already been visited, AND either this is a shallow visit, or the previous wasn't
             {
-                auto it = visited.find(ty);
-                if( it != visited.end() )
+                auto idx_it = ::std::lower_bound(visited_map.begin(), visited_map.end(), ty, [&](size_t i, const ::HIR::TypeRef& t){ return out_list[i].first < t; });
+                if( idx_it != visited_map.end() && out_list[*idx_it].first == ty)
                 {
+                    auto it = &out_list[*idx_it];
                     if( it->second == false || mode == Mode::Shallow )
                     {
                         // Return early
                         return ;
                     }
                     DEBUG("-- " << ty << " already visited as shallow");
-                    it->second = false;
                 }
             }
             TRACE_FUNCTION_F(ty << " - " << (mode == Mode::Shallow ? "Shallow" : (mode == Mode::Normal ? "Normal" : "Deep")));
@@ -635,37 +668,30 @@ namespace {
 
             bool shallow = (mode == Mode::Shallow);
             {
-                auto rv = visited.insert( ::std::make_pair(ty.clone(), shallow) );
-                if( !rv.second && ! shallow )
+                auto idx_it = ::std::lower_bound(visited_map.begin(), visited_map.end(), ty, [&](size_t i, const ::HIR::TypeRef& t){ return out_list[i].first < t; });
+                if( idx_it == visited_map.end() || out_list[*idx_it].first != ty )
                 {
-                    rv.first->second = false;
+                    // Add a new entry
+                    visited_map.insert(idx_it, out_list.size());
+                }
+                else
+                {
+                    // Previous visit was shallow, but this one isn't
+                    // - Update the entry to the to-be-pushed entry with shallow=false
+                    if( !shallow && out_list[*idx_it].second )
+                    {
+                        *idx_it = out_list.size();
+                    }
                 }
             }
             out_list.push_back( ::std::make_pair(ty.clone(), shallow) );
             DEBUG("Add type " << ty << (shallow ? " (Shallow)": ""));
         }
-    };
-}
-
-// Enumerate types required for the enumerated items
-void Trans_Enumerate_Types(EnumState& state)
-{
-    static Span sp;
-    TypeVisitor tv { state.crate, state.rv.m_types };
 
-    unsigned int types_count = 0;
-    bool constructors_added;
-    do
-    {
-        // Visit all functions that haven't been type-visited yet
-        for(unsigned int i = 0; i < state.fcns_to_type_visit.size(); i++)
+        void __attribute__ ((noinline)) visit_function(const ::HIR::Path& path, const ::HIR::Function& fcn, const Trans_Params& pp)
         {
-            auto* p = state.fcns_to_type_visit[i];
-            auto& fcn_path = ::std::find_if(state.rv.m_functions.begin(), state.rv.m_functions.end(), [&](const auto&x){ return x.second.get() == p; })->first;
-            TRACE_FUNCTION_F("Function " << fcn_path);
-            assert(p->ptr);
-            const auto& fcn = *p->ptr;
-            const auto& pp = p->pp;
+            Span    sp;
+            auto& tv = *this;
 
             ::HIR::TypeRef   tmp;
             auto monomorph = [&](const auto& ty)->const auto& {
@@ -909,8 +935,35 @@ void Trans_Enumerate_Types(EnumState& state)
                 }
             }
         }
+    };  // struct TypeVisitor
+} // namespace <empty>
+
+// Enumerate types required for the enumerated items
+void Trans_Enumerate_Types(EnumState& state)
+{
+    static Span sp;
+    TypeVisitor tv { state.crate, state.rv.m_types };
+
+    unsigned int types_count = 0;
+    bool constructors_added;
+    do
+    {
+        // Visit all functions that haven't been type-visited yet
+        for(unsigned int i = 0; i < state.fcns_to_type_visit.size(); i++)
+        {
+            auto* p = state.fcns_to_type_visit[i];
+            assert(p->path);
+            assert(p->ptr);
+            auto& fcn_path = *p->path;
+            const auto& fcn = *p->ptr;
+            const auto& pp = p->pp;
+
+            TRACE_FUNCTION_F("Function " << fcn_path);
+            tv.visit_function(fcn_path, fcn, pp);
+        }
         state.fcns_to_type_visit.clear();
         // TODO: Similarly restrict revisiting of statics.
+        // - Challenging, as they're stored as a std::map
         for(const auto& ent : state.rv.m_statics)
         {
             TRACE_FUNCTION_F("Enumerate static " << ent.first);
@@ -957,22 +1010,16 @@ void Trans_Enumerate_Types(EnumState& state)
             if( ty.m_data.is_Path() )
             {
                 const auto& te = ty.m_data.as_Path();
-                const ::HIR::TraitMarkings* markings_ptr = nullptr;
-                TU_MATCHA( (te.binding), (tpb),
-                (Unbound,   ),
-                (Opaque,   ),
-                (ExternType, markings_ptr = &tpb->m_markings; ),
-                (Struct, markings_ptr = &tpb->m_markings; ),
-                (Union,  markings_ptr = &tpb->m_markings; ),
-                (Enum,   markings_ptr = &tpb->m_markings; )
-                )
-                ASSERT_BUG(Span(), markings_ptr, "Path binding not set correctly - " << ty);
+                ASSERT_BUG(sp, te.path.m_data.is_Generic(), "Non-Generic type path after enumeration - " << ty);
+                const auto& gp = te.path.m_data.as_Generic();
+                const ::HIR::TraitMarkings* markings_ptr = te.binding.get_trait_markings();
+                ASSERT_BUG(sp, markings_ptr, "Path binding not set correctly - " << ty);
 
                 // If the type has a drop impl, and it's either defined in this crate or has params (and thus was monomorphised)
-                if( markings_ptr->has_drop_impl && (te.path.m_data.as_Generic().m_path.m_crate_name == state.crate.m_crate_name || te.path.m_data.as_Generic().m_params.has_params()) )
+                if( markings_ptr->has_drop_impl && (gp.m_path.m_crate_name == state.crate.m_crate_name || gp.m_params.has_params()) )
                 {
                     // Add the Drop impl to the codegen list
-                    Trans_Enumerate_FillFrom_Path(state,  ::HIR::Path( ty.clone(), state.crate.get_lang_item_path(sp, "drop"), "drop"), {});
+                    Trans_Enumerate_FillFrom_PathMono(state,  ::HIR::Path( ty.clone(), state.crate.get_lang_item_path(sp, "drop"), "drop"));
                     constructors_added = true;
                 }
             }
@@ -982,7 +1029,7 @@ void Trans_Enumerate_Types(EnumState& state)
                 // Reqire drop glue for inner type.
                 // - Should that already exist?
                 // Requires box_free lang item
-                Trans_Enumerate_FillFrom_Path(state, ::HIR::GenericPath( state.crate.get_lang_item_path(sp, "box_free"), { ity->clone() } ), {});;
+                Trans_Enumerate_FillFrom_PathMono(state, ::HIR::GenericPath( state.crate.get_lang_item_path(sp, "box_free"), { ity->clone() } ));
             }
         }
         types_count = state.rv.m_types.size();
@@ -1278,24 +1325,27 @@ namespace MIR {
 
 void Trans_Enumerate_FillFrom_Path(EnumState& state, const ::HIR::Path& path, const Trans_Params& pp)
 {
-    TRACE_FUNCTION_F(path);
-    Span    sp;
     auto path_mono = pp.monomorph(state.crate, path);
-    DEBUG("- " << path_mono);
+    Trans_Enumerate_FillFrom_PathMono(state, mv$(path_mono));
+}
+void Trans_Enumerate_FillFrom_PathMono(EnumState& state, ::HIR::Path path_mono)
+{
+    TRACE_FUNCTION_F(path_mono);
+    Span    sp;
     // TODO: If already in the list, return early
-    if( state.rv.m_functions.count(path) ) {
+    if( state.rv.m_functions.count(path_mono) ) {
         DEBUG("> Already done function");
         return ;
     }
-    if( state.rv.m_statics.count(path) ) {
+    if( state.rv.m_statics.count(path_mono) ) {
         DEBUG("> Already done static");
         return ;
     }
-    if( state.rv.m_constants.count(path) ) {
+    if( state.rv.m_constants.count(path_mono) ) {
         DEBUG("> Already done constant");
         return ;
     }
-    if( state.rv.m_vtables.count(path) ) {
+    if( state.rv.m_vtables.count(path_mono) ) {
         DEBUG("> Already done vtable");
         return ;
     }
@@ -1315,7 +1365,7 @@ void Trans_Enumerate_FillFrom_Path(EnumState& state, const ::HIR::Path& path, co
         sub_pp.self_type = pe.type->clone();
         ),
     (UfcsUnknown,
-        BUG(sp, "UfcsUnknown - " << path);
+        BUG(sp, "UfcsUnknown - " << path_mono);
         )
     )
     // Get the item type
@@ -1368,8 +1418,7 @@ void Trans_Enumerate_FillFrom_Path(EnumState& state, const ::HIR::Path& path, co
                 auto enum_impl = [&](const ::HIR::TypeRef& ity) {
                     if( !resolve.type_is_copy(sp, ity) )
                     {
-                        auto p = ::HIR::Path(ity.clone(), pe.trait.clone(), pe.item);
-                        Trans_Enumerate_FillFrom_Path(state, p, {});
+                        Trans_Enumerate_FillFrom_PathMono(state, ::HIR::Path(ity.clone(), pe.trait.clone(), pe.item));
                     }
                     };
                 if( const auto* te = inner_ty.m_data.opt_Tuple() ) {
@@ -1599,7 +1648,7 @@ void Trans_Enumerate_FillFrom_VTable(EnumState& state, ::HIR::Path vtable_path,
     {
         DEBUG("- " << m.second.first << " = " << m.second.second << " :: " << m.first);
         auto gpath = monomorphise_genericpath_with(sp, m.second.second, monomorph_cb_trait, false);
-        Trans_Enumerate_FillFrom_Path(state, ::HIR::Path(type.clone(), mv$(gpath), m.first), {});
+        Trans_Enumerate_FillFrom_PathMono(state, ::HIR::Path(type.clone(), mv$(gpath), m.first));
     }
 }
 
diff --git a/src/trans/trans_list.cpp b/src/trans/trans_list.cpp
index 54ae8011..3d8aa86f 100644
--- a/src/trans/trans_list.cpp
+++ b/src/trans/trans_list.cpp
@@ -15,7 +15,7 @@ TransList_Function* TransList::add_function(::HIR::Path p)
     {
         DEBUG("Function " << rv.first->first);
         assert( !rv.first->second );
-        rv.first->second.reset( new TransList_Function {} );
+        rv.first->second.reset( new TransList_Function(rv.first->first) );
         return &*rv.first->second;
     }
     else
diff --git a/src/trans/trans_list.hpp b/src/trans/trans_list.hpp
index df550925..7009111f 100644
--- a/src/trans/trans_list.hpp
+++ b/src/trans/trans_list.hpp
@@ -49,12 +49,14 @@ struct CachedFunction {
 };
 struct TransList_Function
 {
+    const ::HIR::Path*  path;   // Pointer into the list (std::map pointers are stable)
     const ::HIR::Function*  ptr;
     Trans_Params    pp;
     // If `pp.has_types` is true, the below is valid
     CachedFunction  monomorphised;
 
-    TransList_Function():
+    TransList_Function(const ::HIR::Path& path):
+        path(&path),
         ptr(nullptr)
     {}
 };