Re: Tree-sitter integration on feature/tree-sitter

[Yuan Fu <casouri@gmail.com>]

> 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