On Fri, Sep 02, 2016 at 06:23:42PM +0200, Johannes Schindelin wrote: > Let's reimplement this with linear complexity (using a hash map to > match the commits' subject lines) for the common case; Sadly, the > fixup/squash feature's design neglected performance considerations, > allowing arbitrary prefixes (read: `fixup! hell` will match the > commit subject `hello world`), which means that we are stuck with > quadratic performance in the worst case.
If the performance of that case matters enough, we can do better than quadratic complexity: maintain a trie of the subjects, allowing prefix lookups. (Or hash all the prefixes, which you can do in linear time on a string: hash next char, save hash, repeat.) However, that would pessimize the normal case of either a complete subject or a sha1, due to the extra time taken constructing the data structure. Probably not worth it, if you assume that most "fixup!" subjects come from `git commit --fixup` or similar automated means.
