Tm

Alright, take a week off to start reviewing ;-).

It's not that bad though - the important ones are the first, third and fourth path - the rest is just various cleanups (but also there are some minor fixes of the three patches).

The TmWorkObject removal patch is unfortunately rather big - once I started removing it, I had to do it everywhere at the same time and there were no small compilable steps in between. It was quite a riddle to find what is called when using the virtual methods but I believe it's alright and much clearer to read when the OO stuff is gone. At this time I also removed some of the function parameters which weren't used for the file or workspace object.

The third patch is just a recreation of the already published patch that makes tm_workspace_update() public for plugins. This, together with the plugin updates to use this function, makes big projects (linux kernel with 35000 files, 2300000 tags being my benchmark) actually load - it would take several hours without this patch (my guestimate around 10 hours, never tried though). This is the issue people were most probably hitting in the first place when they experienced some performance problems.

Here is a profile of the current performance when loading a big project - it's basically hanging on getc() and the sort is almost invisible now (no profile for the previous state for obvious reasons):

https://www.dropbox.com/s/guc9lx6nijqqmzd/project_open.svg?dl=0

(Dropbox links, github doesn't like svg.)

The fourth patch is the one everyone is eagerly waiting for - the merge instead of complete resort. First I created a classical merge which was going through the tag arrays, comparing all values and merging when needed - i.e. it required len(workspace_tag_array) comparisons. This already improved performance a bit but the performance was still hanging on tm_tag_compare(). Then I just had a look at the numbers - the tag array has 2300000 entries and we are merging on average just 2300000/35000=65 tags. This means there are large blocks of tags (on average 2300000/65 = 35000 long) where no merge will happen. This lead me to the idea we could use a kind of binary search to find the merge spot - details explained in the patch. The result is really fast - the merge isn't the hot spot any more.

Here are two profiles of document editing (which includes frequent re-parses of the edited file):

https://www.dropbox.com/s/k2lwa5m2hivuns3/editing_before.svg?dl=0
https://www.dropbox.com/s/42rhvtcdjgi3vm7/editing_after.svg?dl=0

The first is before the change - after pressing a character theres about 2s freeze, the second after the change - about 200ms freeze. You can see the merge is almost free now - the "expensive" ones are now tm_tags_remove_file_tags() and tm_tags_extract(). The only thing they do is walking through the tag array, dereferencing the pointer and comparing a single integer. The dereferencing is the slow part here because it means almost constant cache misses and loads of pages from memory (functions just operating on tag array pointers are almost free performance-wise - you don't see tm_tags_prune() or tm_tags_dedup() here at all).

The question is whether to continue optimizing tm_tags_remove_file_tags() and tm_tags_extract() - I think it's not worth it. They take up just about 50% so by eliminating them we'd get a 2x performance improvement but I don't see any easy-to-do non-invasive way to eliminate them.

---

The rest are mostly cleanups and a few minor fixes of the merge. One of the more interesting cleanups is the removal of the union in TMTag - it was really non-obvious which part of the union is used in which context so now it should be much clearer. I have removed some unused functions which don't seem to be useful at all; however, there were a few "this might be useful in the future" unused functions which I kept, moved to the end of the file and added #if 0 guards around them (actually I think they can be removed, they can always be recovered from the git history). There are also some unused debug functions - I just added #ifdef TM_DEBUG around them but these are probably good to keep.