From a5657dbc43d84133bd95e5de178d68634973b1b3 Mon Sep 17 00:00:00 2001
From: Markus Westerlind <markus.westerlind@imperva.com>
Date: Wed, 8 Jan 2020 23:13:56 +0100
Subject: [PATCH] perf: Avoid creating a SmallVec if nothing changes during a
 fold

Not sure if this helps but in theory it should be less work than what
the current micro optimization does for `ty::Predicate` lists.

(It would explain the overhead I am seeing from `perf`.)
---
 src/librustc/ty/structural_impls.rs | 47 ++++++++++++++++++-----------
 1 file changed, 30 insertions(+), 17 deletions(-)

diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index d87296c03dd..385c8eeb4b8 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -803,8 +803,7 @@ fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
-        folder.tcx().intern_existential_predicates(&v)
+        fold_list(*self, folder, |tcx, v| tcx.intern_existential_predicates(v))
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
@@ -814,8 +813,7 @@ fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<Ty<'tcx>> {
     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
-        folder.tcx().intern_type_list(&v)
+        fold_list(*self, folder, |tcx, v| tcx.intern_type_list(v))
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
@@ -825,8 +823,7 @@ fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ProjectionKind> {
     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
-        folder.tcx().intern_projs(&v)
+        fold_list(*self, folder, |tcx, v| tcx.intern_projs(v))
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
@@ -990,17 +987,7 @@ fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Predicate<'tcx>> {
     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
-        // This code is hot enough that it's worth specializing for a list of
-        // length 0. (No other length is common enough to be worth singling
-        // out).
-        if self.len() == 0 {
-            self
-        } else {
-            // Don't bother interning if nothing changed, which is the common
-            // case.
-            let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
-            if v[..] == self[..] { self } else { folder.tcx().intern_predicates(&v) }
-        }
+        fold_list(*self, folder, |tcx, v| tcx.intern_predicates(v))
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
@@ -1073,3 +1060,29 @@ fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> bool {
         false
     }
 }
+
+fn fold_list<'tcx, F, T>(
+    list: &'tcx ty::List<T>,
+    folder: &mut F,
+    intern: impl FnOnce(TyCtxt<'tcx>, &[T]) -> &'tcx ty::List<T>,
+) -> &'tcx ty::List<T>
+where
+    F: TypeFolder<'tcx>,
+    T: TypeFoldable<'tcx> + PartialEq + Copy,
+{
+    let mut iter = list.iter();
+    // Look for the first element that changed
+    if let Some((i, new_t)) = iter.by_ref().enumerate().find_map(|(i, t)| {
+        let new_t = t.fold_with(folder);
+        if new_t == *t { None } else { Some((i, new_t)) }
+    }) {
+        // An element changed, prepare to intern the resulting list
+        let mut new_list = SmallVec::<[_; 8]>::with_capacity(list.len());
+        new_list.copy_from_slice(&list[..i]);
+        new_list.push(new_t);
+        new_list.extend(iter.map(|t| t.fold_with(folder)));
+        intern(folder.tcx(), &new_list)
+    } else {
+        list
+    }
+}
-- 
2.44.0