Accidentally Quadratic

A tags file is a classic UNIX format for storing an index of where symbols are defined in a source tree, for ease of finding a symbol definition from within an editor. Both vim and emacs have native support for loading TAGS files and using them to jump to symbol definitions.

When performing tags lookups, vim deduplicates results, to suppress identical matches (perhaps in case you’ve concatenated multiple tags files? I’ll admit to not fully understanding the intent here).

However, historically, it stored the matches in an array, which meant that looking up tags was accidentally quadratic in the number of returned matches. Presumably this escaped notice in part because usually most symbols have only a few definitions, but it was a problem for programmatic use, or in some edge cases of manual search or pathological code bases.

The fix, as it often is on this blog, was to store the results in a hash table, providing duplicate-merging for free.

Interestingly, some earlier developer had noticed that this code could be slow, but instead of fixing it, had added code to check for ^C and abort the entire match, so as to return use of the editor to the user! We may never know if that author didn’t realize there was a relatively-easy fast solution, or just thought it was too much work in C (as of the fix, vim did have a built-in hash table type, but it needed to be extended to support non-NULL-terminated strings).

Thanks to James McCoy for fixing this one as well as bringing it to my attention.