Merge #4489

4489: Memory allocation optimization r=matklad a=simonvandel

I did some profiling using DHAT, and this was what I could easily optimize without much knowledge of the codebase.

This speeds up analysis-stats on rust-analyser by ~4% on my local machine.

**Benchmark**
➜  rust-analyzer-base git:(master) hyperfine --min-runs=2 '/home/simon/Documents/rust-analyzer/target/release/rust-analyzer analysis-stats .' '/home/simon/Documents/rust-analyzer-base/target/release/rust-analyzer analysis-stats .'
Benchmark #1: /home/simon/Documents/rust-analyzer/target/release/rust-analyzer analysis-stats .
  Time (mean ± σ):     49.621 s ±  0.317 s    [User: 48.725 s, System: 0.792 s]
  Range (min … max):   49.397 s … 49.846 s    2 runs
 
Benchmark #2: /home/simon/Documents/rust-analyzer-base/target/release/rust-analyzer analysis-stats .
  Time (mean ± σ):     51.764 s ±  0.045 s    [User: 50.882 s, System: 0.756 s]
  Range (min … max):   51.733 s … 51.796 s    2 runs
 
Summary
  '/home/simon/Documents/rust-analyzer/target/release/rust-analyzer analysis-stats .' ran
    1.04 ± 0.01 times faster than '/home/simon/Documents/rust-analyzer-base/target/release/rust-analyzer analysis-stats .'

Co-authored-by: Simon Vandel Sillesen <[email protected]>

5 files changed, 27 insertions, 16 deletions

diff --git a/crates/ra_mbe/src/mbe_expander/transcriber.rs b/crates/ra_mbe/src/mbe_expander/transcriber.rs
index 4b173edd3..7c9bb4d00 100644
--- a/crates/ra_mbe/src/mbe_expander/transcriber.rs
+++ b/crates/ra_mbe/src/mbe_expander/transcriber.rs
@@ -1,4 +1,4 @@
-//! Transcraber takes a template, like `fn $ident() {}`, a set of bindings like
+//! Transcriber takes a template, like `fn $ident() {}`, a set of bindings like
 //! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}`
 
 use ra_syntax::SmolStr;
@@ -53,7 +53,8 @@ impl Bindings {
 pub(super) fn transcribe(template: &tt::Subtree, bindings: &Bindings) -> ExpandResult<tt::Subtree> {
     assert!(template.delimiter == None);
     let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() };
-    expand_subtree(&mut ctx, template)
+    let mut arena: Vec<tt::TokenTree> = Vec::new();
+    expand_subtree(&mut ctx, template, &mut arena)
 }
 
 #[derive(Debug)]
@@ -73,8 +74,13 @@ struct ExpandCtx<'a> {
     nesting: Vec<NestingState>,
 }
 
-fn expand_subtree(ctx: &mut ExpandCtx, template: &tt::Subtree) -> ExpandResult<tt::Subtree> {
-    let mut buf: Vec<tt::TokenTree> = Vec::new();
+fn expand_subtree(
+    ctx: &mut ExpandCtx,
+    template: &tt::Subtree,
+    arena: &mut Vec<tt::TokenTree>,
+) -> ExpandResult<tt::Subtree> {
+    // remember how many elements are in the arena now - when returning, we want to drain exactly how many elements we added. This way, the recursive uses of the arena get their own "view" of the arena, but will reuse the allocation
+    let start_elements = arena.len();
     let mut err = None;
     for op in parse_template(template) {
         let op = match op {
@@ -85,25 +91,27 @@ fn expand_subtree(ctx: &mut ExpandCtx, template: &tt::Subtree) -> ExpandResult<t
             }
         };
         match op {
-            Op::TokenTree(tt @ tt::TokenTree::Leaf(..)) => buf.push(tt.clone()),
+            Op::TokenTree(tt @ tt::TokenTree::Leaf(..)) => arena.push(tt.clone()),
             Op::TokenTree(tt::TokenTree::Subtree(tt)) => {
-                let ExpandResult(tt, e) = expand_subtree(ctx, tt);
+                let ExpandResult(tt, e) = expand_subtree(ctx, tt, arena);
                 err = err.or(e);
-                buf.push(tt.into());
+                arena.push(tt.into());
             }
             Op::Var { name, kind: _ } => {
                 let ExpandResult(fragment, e) = expand_var(ctx, name);
                 err = err.or(e);
-                push_fragment(&mut buf, fragment);
+                push_fragment(arena, fragment);
             }
             Op::Repeat { subtree, kind, separator } => {
-                let ExpandResult(fragment, e) = expand_repeat(ctx, subtree, kind, separator);
+                let ExpandResult(fragment, e) = expand_repeat(ctx, subtree, kind, separator, arena);
                 err = err.or(e);
-                push_fragment(&mut buf, fragment)
+                push_fragment(arena, fragment)
             }
         }
     }
-    ExpandResult(tt::Subtree { delimiter: template.delimiter, token_trees: buf }, err)
+    // drain the elements added in this instance of expand_subtree
+    let tts = arena.drain(start_elements..arena.len()).collect();
+    ExpandResult(tt::Subtree { delimiter: template.delimiter, token_trees: tts }, err)
 }
 
 fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> ExpandResult<Fragment> {
@@ -155,6 +163,7 @@ fn expand_repeat(
     template: &tt::Subtree,
     kind: RepeatKind,
     separator: Option<Separator>,
+    arena: &mut Vec<tt::TokenTree>,
 ) -> ExpandResult<Fragment> {
     let mut buf: Vec<tt::TokenTree> = Vec::new();
     ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
@@ -165,7 +174,7 @@ fn expand_repeat(
     let mut counter = 0;
 
     loop {
-        let ExpandResult(mut t, e) = expand_subtree(ctx, template);
+        let ExpandResult(mut t, e) = expand_subtree(ctx, template, arena);
         let nesting_state = ctx.nesting.last_mut().unwrap();
         if nesting_state.at_end || !nesting_state.hit {
             break;
diff --git a/crates/ra_parser/src/lib.rs b/crates/ra_parser/src/lib.rs
index e08ad4dae..eeb8ad66b 100644
--- a/crates/ra_parser/src/lib.rs
+++ b/crates/ra_parser/src/lib.rs
@@ -25,7 +25,7 @@ pub(crate) use token_set::TokenSet;
 pub use syntax_kind::SyntaxKind;
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct ParseError(pub String);
+pub struct ParseError(pub Box<String>);
 
 /// `TokenSource` abstracts the source of the tokens parser operates on.
 ///
diff --git a/crates/ra_parser/src/parser.rs b/crates/ra_parser/src/parser.rs
index faa63d53f..4f59b0a23 100644
--- a/crates/ra_parser/src/parser.rs
+++ b/crates/ra_parser/src/parser.rs
@@ -192,7 +192,7 @@ impl<'t> Parser<'t> {
     /// structured errors with spans and notes, like rustc
     /// does.
     pub(crate) fn error<T: Into<String>>(&mut self, message: T) {
-        let msg = ParseError(message.into());
+        let msg = ParseError(Box::new(message.into()));
         self.push_event(Event::Error { msg })
     }
 
diff --git a/crates/ra_syntax/src/syntax_node.rs b/crates/ra_syntax/src/syntax_node.rs
index f9d379abf..e566af7e8 100644
--- a/crates/ra_syntax/src/syntax_node.rs
+++ b/crates/ra_syntax/src/syntax_node.rs
@@ -70,6 +70,6 @@ impl SyntaxTreeBuilder {
     }
 
     pub fn error(&mut self, error: ra_parser::ParseError, text_pos: TextSize) {
-        self.errors.push(SyntaxError::new_at_offset(error.0, text_pos))
+        self.errors.push(SyntaxError::new_at_offset(*error.0, text_pos))
     }
 }
diff --git a/crates/ra_tt/src/buffer.rs b/crates/ra_tt/src/buffer.rs
index 14b3f707d..5967f44cd 100644
--- a/crates/ra_tt/src/buffer.rs
+++ b/crates/ra_tt/src/buffer.rs
@@ -42,7 +42,9 @@ impl<'t> TokenBuffer<'t> {
         buffers: &mut Vec<Box<[Entry<'t>]>>,
         next: Option<EntryPtr>,
     ) -> usize {
-        let mut entries = vec![];
+        // Must contain everything in tokens and then the Entry::End
+        let start_capacity = tokens.len() + 1;
+        let mut entries = Vec::with_capacity(start_capacity);
         let mut children = vec![];
 
         for (idx, tt) in tokens.iter().enumerate() {