[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Tree-sitter integration on feature/tree-sitter
From: |
Yoav Marco |
Subject: |
Re: Tree-sitter integration on feature/tree-sitter |
Date: |
Mon, 09 May 2022 20:50:32 +0300 |
User-agent: |
mu4e 1.6.3; emacs 29.0.50 |
Looking at the code, isn't the while loop in treesit-query-capture
O(n²)? It essentially amounts to
result = nil
while (next capture group is avaliable) {
captures = nil
for (capture in capture group) {
captures = cons(capture, captures)
}
captures = nreverse(captures)
if (captures pass all predicates in their query)
result = nconc(result, captures) // <----- THE OFFENDER
}
A better way to do this would be to call nconc(captures, result) and
nreverse it all at the end instead of at the end of the for loop.
An even faster way would be to add unconditionally to result and roll it
back in case predicates fail. This doesn't use nconc at all:
result = nil
while (next capture group is avaliable) {
prev_result = result;
for (capture in capture group) {
result = cons(capture, result)
}
if (captures *fail* at a predicate)
result = prev_result
}
result = nreverse(result)
Context: I'm still working on profiling query compilation, and from what
I understand of gprof's output (not much) nconc indeed is very slow
here. Seeing nconc in the report is what made me look for nconc usage in
treesit-query-capture.
index % time self children called name
[1] 98.4 1.76 0.13 169+9031282 <cycle 1 as a whole> [1]
1.59 0.00 41385 Fnconc <cycle 1> [2]
0.06 0.05 2432616+3714 process_mark_stack <cycle 1>
[24]
0.08 0.00 147643 re_match_2_internal <cycle 1>
[25]
0.02 0.00 1707+56214 mark_char_table <cycle 1> [32]
0.00 0.02 18 garbage_collect <cycle 1> [33]
...
The thing profiled is calling treesit-font-lock-fontify-region with c
queries accidentally on a go file with 8k lines. Still shouldn't take
the 2.2 seconds that it did, though.
> BTW, I would appreciate for someone to look at the manual and maybe
> touch up a bit, as I’m not a native speaker and might write something
> not very idiomatic/fluent.
One thing I've noticed - the manual node starts by introducing
treesit-available-p, a function that doesn't seem to exist anymore?
- Re: Tree-sitter integration on feature/tree-sitter, (continued)
- Re: Tree-sitter integration on feature/tree-sitter, Theodor Thornhill, 2022/05/14
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/14
- Re: Tree-sitter integration on feature/tree-sitter, Theodor Thornhill, 2022/05/17
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/18
- Re: Tree-sitter integration on feature/tree-sitter, Theodor Thornhill, 2022/05/18
- Re: Tree-sitter integration on feature/tree-sitter, Stephen Leake, 2022/05/08
Re: Tree-sitter integration on feature/tree-sitter, Daniel Martín, 2022/05/14
Re: Tree-sitter integration on feature/tree-sitter,
Yoav Marco <=
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/09
- Re: Tree-sitter integration on feature/tree-sitter, Yoav Marco, 2022/05/10
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/10
- Re: Tree-sitter integration on feature/tree-sitter, Yoav Marco, 2022/05/10
- Re: Tree-sitter integration on feature/tree-sitter, Stefan Monnier, 2022/05/10
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/10
- Re: Tree-sitter integration on feature/tree-sitter, Yuan Fu, 2022/05/10
Re: Tree-sitter integration on feature/tree-sitter, Eli Zaretskii, 2022/05/11
Re: Tree-sitter integration on feature/tree-sitter, Yoav Marco, 2022/05/11