Closed lnicola closed 4 years ago
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.
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?
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.
I think this was fixed in 40170885e7.
But it might still be worth failing fast(er) in https://github.com/rust-analyzer/rust-analyzer/commit/40170885e799ebdefb24ed00865cd1c7800af491#diff-7f6e2fc7cf020c4dc17aa7d4f85ee787R149-R162.
I think that work did improved things a bit, though I suspect token sources and toke trees can still be much more efficient
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
.
It looks like the parser is one of the slower parts of rust-analyzer:
Besides the green node hashing for which there is a TODO in
rowan
and the memory allocation,Parser::nth
takes the most time while runningra_cli analysis-stats
, especially once you factor its children fromTextTokenSource
andSubtreeTokenSource
.Note that
nth
is called very often, viacurrent{,2,3}
andat
. Then
ranges from 0 to 2, with an exception of 3 during parameter parsing. Looking atnth
, it seems that:token_source.lookahead_nth(i)
to get the current token kindis_composite
is_composite
callstoken_source.lookahead_nth
fori
,i + 1
,i + 2
n
nth
itself is often called by the parser in a row with 0..3current3
,current2
,current
, which callnth
three, two and one timeThese 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 inis_composite
(the caller already knows it) and only computingsecond
andthird
if they're needed, it might be better to keep track of the current and next three tokens inbump
or somewhere similar.