[Geany-devel] tagmanager changes

[Nick Treleaven]

On 24/04/2012 22:31, Colomban Wendling wrote:
> Le 17/04/2012 18:20, Nick Treleaven a écrit :
> Sorry for the long delays -- and also small activity -- recently.  I
> have/had a lot of non-Geany stuff to do and stuff, the whole story, you
> know.

No problem.

> I finally committed it and pushed it so you can see it, comment, blame,
> flame&  more:  see https://github.com/b4n/geany/tree/wip%2Fctagsmanager
>
> A few points, as they comes to my mind:
>
> * it support asynchronous parsing (though not concurrent parsing);

What's the difference? Also, what does it buy us?

> * it is under the new ctagsmanager/ directory;
> * it uses the same tag parsers tagmanager used, in ctagsmanager/ctags;
> * all types have different names than the tagmanager ones, though
>    currently the API is almost an 1:1 mapping -- and that's maybe a
>    huge mistake?;

I don't understand why tagmanager has to be replaced, why not just 
replace the parts you want to improve? Rewriting it is likely to lead to 
a new set of bugs and be hard to review and merge changes from master.

> * there is 2 backends as of today:
>    - a "simple" one that is simple and that doesn't waste (too much)
>      memory, but that searches in O(n);

Linear searching seems like a bad idea when we currently have O(log n). 
Removing x tags is O(n * x) by the look of it.

>    - a "multi-cache" one that, as its name suggests, maintains multiple
>      caches (sorted tags arrays).  it uses a little more memory and is
>      slower on insertion since it maintains several sorted lists, but a
>      search on an already existing cache is very fast.

Won't this be slow for adding many tags at once? How is this design 
better than tagmanager?

Given my global tags merge change (see below), I think tagmanager needs 
some changes to avoid sorting the workspace tags array each time tags 
are updated, but this is certainly doable.

>    In practice I haven't yet tested anything big enough to see any
>    difference in performances between these two backends, and that's
>    something that probably isn't worth bothering about for now.
>
> * this "backend" abstraction might be really overkill, and maybe we
>    could do better without it?;

I don't see why having two is better. The memory overhead for a pointer 
array is not much vs. the size of the tag structures. Fast searching is 
important.

> * tags (and most types) are reference-counted (so they aren't
>    necessarily duplicated, e.g. in the multicache backend);

I don't really understand src/symbols.c since the real-time parsing 
change, so don't really understand why this is needed.

> * tag matching/finding is done using ctm_data_backend_find() (or a
>    convenience wrapper), which takes 2 functions for performing the
>    search:
>    - a sort function, used to, heh, sort the tags to search and/or the
>      resulting list (the "simple" backend should use it to sort the
>      result; and the "multi-cache" backend uses it to sort the caches)

It doesn't sound a good idea to have to sort the haystack on each 
lookup. Lookup should be very fast, like tagmanager. Adding/removing 
tags is always less important because real-time updates can be disabled 
anyway.

>    - a match function, use to check whether a tag should be included in
>      the results.  Like the sort function it returns a strcmp()-like
>      value, with the only difference that it probably returns 0 for more
>      tags.
>
>    It is somewhat similar to what tagmanager did, but it's more flexible
>    -- and maybe complex, though many sort/match functions would already
>    be provided.
>
> * no pruning is done yet, so there is duplicate in the results;
> * there is an (almost) working scope completeion implementation;
> * ... I don't see anything to add, so I'll stop here :)
>
> All this isn't of course written in stone: if we already redo a lot of
> things, let's get something nice -- though IMO we'll always be better
> than with tagmanager, since each time I wanted to touch it it took me
> hours, and sometimes I even haven't been able to fix the problem
> (thinking of e.g. scope completion...).

I don't really see what the problem understanding it is. I thought scope 
completion was just tm_workspace_find_scoped and related functions, not 
some tagmanager-wide problem.

>> Also, later in the thread he says that performance problems with
>> resorting global and workspace tags cannot be fixed with the design of
>> tagmanager. I've been working yesterday on improving this significantly
>> by merging the new tags each time instead of resorting *all* the tags. I
>> hope to commit this in the next few days.
>
> Cool!  I haven't done any profiling on either tagmanager or may new
> attempt, so I can't tell what's actually slow, but any improvement is
> good to have :)

I finished the global tags merging change:
https://github.com/geany/geany/commit/712cdd6aa0005f65bd77b15c34cd29067864628d

IMO this should make loading global tags fast enough, even for heavy 
use, as the whole array is now only traversed once.

For avoiding resorting of workspace tags when only reparsing one source 
object, we can remove the source object's old tags & merge the new tags. 
This is all O(n) for the workspace array. I haven't looked into 
implementing this yet because now it's clear you're working on a 
competing change.

The other changes I've made were in response to a user's problem with 
generating C tag files, and some changes to the CTags files.

Regards,
Nick