viernes, 11 de enero de 2008

Tag Parsing Improvements

Well, well, first post since the end of SoC 2007... whooops!
The reason I haven't blogged in so long is because I have been working very little on CBinding, just fixing simple bugs and adding small features, nothing really worth mentioning. But I think I have finally done something worth announcing!

First off, to build the class pad from from the output of ctags, one has to do a lot of searching in the outputted tags because the tags are not outputted in a hierarchical manner, they are just outputted as a list of tags and each tag entry is marked with the 'parent' tag (namespace, class, struct etc., if any). My original implementation was to do a linear search every time I needed to find a specific tag and I just left it at that and forgot about it. As you have probably noticed, CBinding takes quite some time parsing the tags, this is especially noticeable when parsing the system tags which tend to be many.

Luckily, ctags outputs sorted tags, so I recently changed the search algorithm from linear to binary, which greatly decreases the time it takes to parse tag files, here are some numbers for parsing one of my project's tags (this includes parsing system tags):
before: 102,640 milliseconds
after: 15,731 milliseconds

Nice! well, to be honest I still think it is rather slow... next I'm going to try to implement some caching to improve this even more.