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 <simon.vandel@gmail.com>

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 4b173edd3f9..7c9bb4d00e1 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 e08ad4dae67..eeb8ad66bd1 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 faa63d53f2c..4f59b0a2356 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 f9d379abf3c..e566af7e87a 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 14b3f707df3..5967f44cd08 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() {