Re: [PATCH 9/9] rebase -i: rearrange fixup/squash lines using the rebase--helper

From: Josh Triplett <josh@joshtriplett.org>
Date: Sep 3, 2016, 18:03 UTC
Message-ID: <20160903180344.truur5ey6j6ah2wh@x>
In-Reply-To: <3810bd4bddb3b850a78e5d960207157de64a2e56.1472833365.git.johannes.schindelin@gmx.de>

On Fri, Sep 02, 2016 at 06:23:42PM +0200, Johannes Schindelin wrote:

Show 6 quoted lines

> 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.