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.