Parsing seems slow

[lnicola]

It looks like the parser is one of the slower parts of rust-analyzer:

6.01%  <rowan::green::GreenNode as core::hash::Hash>::hash
4.49%  _int_malloc
4.34%  ra_parser::parser::Parser::nth
3.66%  ra_syntax::syntax_node::SyntaxTreeBuilder::finish_node
3.64%  <ra_syntax::parsing::text_token_source::TextTokenSource as ra_parser::TokenSource>::lookahead_nth
3.51%  _int_free
3.04%  malloc
2.82%  ra_parser::event::process
2.71%  alloc::sync::Arc<T>::drop_slow
2.67%  ra_mbe::subtree_source::SubtreeTokenSource::get
2.43%  <smol_str::SmolStr as core::hash::Hash>::hash
1.98%  __memmove_avx_unaligned_erms
1.72%  <rowan::cursor::SyntaxNode as core::ops::drop::Drop>::drop
1.68%  unlink_chunk.isra.0
1.54%  <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T,I>>::from_iter
1.45%  malloc_consolidate
1.43%  ra_syntax::parsing::text_tree_sink::TextTreeSink::do_token
1.42%  ra_rustc_lexer::<impl ra_rustc_lexer::cursor::Cursor>::advance_token
1.25%  rowan::cursor::FreeList::try_push
1.21%  <rowan::cursor::SyntaxNodeChildren as core::iter::traits::iterator::Iterator>::next
1.19%  realloc
0.99%  <core::iter::adapters::Map<I,F> as core::iter::traits::iterator::Iterator>::next
0.93%  <ra_mbe::subtree_source::SubtreeTokenSource as ra_parser::TokenSource>::lookahead_nth

Besides the green node hashing for which there is a TODO in rowan and the memory allocation, Parser::nth takes the most time while running ra_cli analysis-stats, especially once you factor its children from TextTokenSource and SubtreeTokenSource.

Note that nth is called very often, via current{,2,3} and at. The n ranges from 0 to 2, with an exception of 3 during parameter parsing. Looking at nth, it seems that:

• it calls token_source.lookahead_nth(i) to get the current token kind
• it passes the kind to is_composite
• is_composite calls token_source.lookahead_nth for i, i + 1, i + 2
• the things above happen in a loop from 0 to n
• nth itself is often called by the parser in a row with 0..3
• there's also current3, current2, current, which call nth three, two and one time
• these functions are themselves called in a row:

    if let Some(t) = p.current3() {
        // ...
    }
    if let Some(t) = p.current2() {
        // ...
    }
    match p.current() {
        // ...
    }

These cause token_source.lookahead_nth to be called a large number of times, and that function in itself is not necessarily inexpensive.

While there is some low-hanging fruit like avoiding the first lookahead in is_composite (the caller already knows it) and only computing second and third if they're needed, it might be better to keep track of the current and next three tokens in bump or somewhere similar.

[lnicola]

I tried making the "low-hanging fruit" change mentioned above. The profile now looks like this:

6.40%  <rowan::green::GreenNode as core::hash::Hash>::hash
4.65%  _int_malloc
3.89%  ra_syntax::syntax_node::SyntaxTreeBuilder::finish_node
3.74%  _int_free
3.73%  ra_parser::parser::Parser::nth
3.24%  malloc
2.91%  ra_parser::event::process
2.88%  alloc::sync::Arc<T>::drop_slow
2.60%  <smol_str::SmolStr as core::hash::Hash>::hash
2.09%  __memmove_avx_unaligned_erms
1.81%  <rowan::cursor::SyntaxNode as core::ops::drop::Drop>::drop
1.66%  <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T,I>>::from_iter
1.66%  unlink_chunk.isra.0
1.58%  ra_syntax::parsing::text_tree_sink::TextTreeSink::do_token
1.54%  malloc_consolidate
1.49%  <ra_syntax::parsing::text_token_source::TextTokenSource as ra_parser::TokenSource>::lookahead_nth
1.47%  ra_rustc_lexer::<impl ra_rustc_lexer::cursor::Cursor>::advance_token
1.46%  ra_mbe::subtree_source::SubtreeTokenSource::get
1.34%  rowan::cursor::FreeList::try_push
1.26%  <rowan::cursor::SyntaxNodeChildren as core::iter::traits::iterator::Iterator>::next
1.25%  realloc
1.09%  <core::iter::adapters::Map<I,F> as core::iter::traits::iterator::Iterator>::next
0.98%  ra_parser::parser::Marker::complete
0.91%  <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop
0.90%  smol_str::SmolStr::new
0.90%  ra_parser::parser::Parser::do_bump
0.83%  cfree@GLIBC_2.2.5
0.80%  <core::iter::adapters::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
0.70%  drop_bomb::RealBomb::new
0.67%  indexmap::map::IndexMap<K,V,S>::insert
0.64%  <ra_mbe::syntax_bridge::TtTreeSink as ra_parser::TreeSink>::token
0.62%  rowan::cursor::NodeData::new
0.60%  alloc::sync::Arc<T>::drop_slow
0.58%  <ra_syntax::parsing::text_tree_sink::TextTreeSink as ra_parser::TreeSink>::start_node
0.53%  ra_syntax::parsing::lexer::tokenize
0.52%  ra_hir::nameres::collector::DefCollector<&DB>::update_recursive
0.51%  <ra_syntax::algo::visit::VisCtx<V,N,F> as ra_syntax::algo::visit::VisitorCtx>::accept
0.48%  ra_mbe::mbe_expander::expand_tt

SubtreeTokenSource::lookahead_nth is gone, and TextTokenSource::lookahead_nth is down from 3.64% to 1.49%. The total run time went down a couple of seconds:

After #1638:

Database loaded, 255 roots, 236.176803ms
Crates in this dir: 27
Total modules found: 282
Total declarations: 9642
Total functions: 3287
Total expressions: 64620
Expressions of unknown type: 9107 (14%)
Expressions of partially unknown type: 3425 (5%)
Analysis: 22.562328486s, 0b allocated 0b resident
target/release/ra_cli analysis-stats  23.12s user 0.57s system 100% cpu 23.659 total

With this change:

Database loaded, 255 roots, 244.805985ms
Crates in this dir: 27
Total modules found: 282
Total declarations: 9648
Total functions: 3291
Total expressions: 64762
Expressions of unknown type: 9119 (14%)
Expressions of partially unknown type: 3431 (5%)
Analysis: 19.997281073s, 0b allocated 0b resident
target/release/ra_cli analysis-stats  20.59s user 0.48s system 100% cpu 21.036 total

diff --git i/crates/ra_parser/src/parser.rs w/crates/ra_parser/src/parser.rs
index 159ed50df..393586561 100644
--- i/crates/ra_parser/src/parser.rs
+++ w/crates/ra_parser/src/parser.rs
@@ -6,7 +6,7 @@ use crate::{
     event::Event,
     ParseError,
     SyntaxKind::{self, EOF, ERROR, TOMBSTONE},
-    TokenSet, TokenSource, T,
+    Token, TokenSet, TokenSource, T,
 };
 
 /// `Parser` struct provides the low-level API for
@@ -87,8 +87,9 @@ impl<'t> Parser<'t> {
         let mut i = 0;
 
         loop {
-            let mut kind = self.token_source.lookahead_nth(i).kind;
-            if let Some((composited, step)) = self.is_composite(kind, i) {
+            let token = self.token_source.lookahead_nth(i);
+            let mut kind = token.kind;
+            if let Some((composited, step)) = self.is_composite(token, i) {
                 kind = composited;
                 i += step;
             } else {
@@ -250,32 +251,47 @@ impl<'t> Parser<'t> {
     }
 
     /// helper function for check if it is composite.
-    fn is_composite(&self, kind: SyntaxKind, n: usize) -> Option<(SyntaxKind, usize)> {
+    fn is_composite(&self, first: Token, n: usize) -> Option<(SyntaxKind, usize)> {
         // We assume the dollars will not occuried between
         // mult-byte tokens
 
-        let first = self.token_source.lookahead_nth(n);
+        let jn1 = first.is_jointed_to_next;
+        if !jn1 && first.kind != T![-] {
+            return None;
+        }
+
         let second = self.token_source.lookahead_nth(n + 1);
+        if first.kind == T![-] && second.kind == T![>] {
+            return Some((T![->], 2));
+        }
+        if !jn1 {
+            return None;
+        }
+
+        match (first.kind, second.kind) {
+            (T![:], T![:]) => return Some((T![::], 2)),
+            (T![=], T![=]) => return Some((T![==], 2)),
+            (T![=], T![>]) => return Some((T![=>], 2)),
+            (T![!], T![=]) => return Some((T![!=], 2)),
+            _ => {}
+        }
+
+        if first.kind != T![.] || second.kind != T![.] {
+            return None;
+        }
+
         let third = self.token_source.lookahead_nth(n + 2);
 
-        let jn1 = first.is_jointed_to_next;
-        let la2 = second.kind;
         let jn2 = second.is_jointed_to_next;
         let la3 = third.kind;
 
-        match kind {
-            T![.] if jn1 && la2 == T![.] && jn2 && la3 == T![.] => Some((T![...], 3)),
-            T![.] if jn1 && la2 == T![.] && la3 == T![=] => Some((T![..=], 3)),
-            T![.] if jn1 && la2 == T![.] => Some((T![..], 2)),
-
-            T![:] if jn1 && la2 == T![:] => Some((T![::], 2)),
-            T![=] if jn1 && la2 == T![=] => Some((T![==], 2)),
-            T![=] if jn1 && la2 == T![>] => Some((T![=>], 2)),
-
-            T![!] if jn1 && la2 == T![=] => Some((T![!=], 2)),
-            T![-] if la2 == T![>] => Some((T![->], 2)),
-            _ => None,
+        if jn2 && la3 == T![.] {
+            return Some((T![...], 3));
         }
+        if la3 == T![=] {
+            return Some((T![..=], 3));
+        }
+        return Some((T![..], 2));
     }
 
     fn eat_dollars(&mut self) {

I'm not opening a PR because I'm not convinced it's the right approach.

[matklad]

Don’t have time for a thorough review right now, but it might be the case that we want to use a different design altogether for the token sources. Maybe we even should move look ahead management into the parser itself?

[lnicola]

Related, perhaps ra_cli analysis-stats should print the parsing time; it's a little more than half of the whole run in my quick test.

[lnicola]

I think this was fixed in 4017088.

But it might still be worth failing fast(er) in 4017088#diff-7f6e2fc7cf020c4dc17aa7d4f85ee787R149-R162.

[matklad]

I think that work did improved things a bit, though I suspect token sources and toke trees can still be much more efficient

[lnicola]

The issue is mostly about the cascade lookaheads, we should probably file another one for other optimizations.

By the way, batch analysis is still almost twice as fast with RA_LRU_CAP=0.