[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Tree-sitter integration on feature/tree-sitter
From: |
Yuan Fu |
Subject: |
Re: Tree-sitter integration on feature/tree-sitter |
Date: |
Mon, 9 May 2022 13:51:46 -0700 |
> On May 9, 2022, at 10:50 AM, Yoav Marco <yoavm448@gmail.com> wrote:
>
> 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.
Thanks for looking at this! I pushed your proposed fix, could you try your
profile again and see if it works?
>
>> 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?
It’s defined in treesit.el, have you required it before checking for that
function?
Yuan
Re: Tree-sitter integration on feature/tree-sitter, Daniel Martín, 2022/05/14
Re: Tree-sitter integration on feature/tree-sitter, Yoav Marco, 2022/05/09
- Re: Tree-sitter integration on feature/tree-sitter,
Yuan Fu <=
- 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
Re: Tree-sitter integration on feature/tree-sitter, Eli Zaretskii, 2022/05/11