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

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Sep 4, 2016, 06:47 UTC
Message-ID: <alpine.DEB.2.20.1609031548540.129229@virtualbox>
In-Reply-To: <20160903180344.truur5ey6j6ah2wh@x>

Hi Josh,

On Sat, 3 Sep 2016, Josh Triplett wrote:

Show 16 quoted lines

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

Right. My reaction to finding our that subject prefixes were allowed, too, was "WTF?". And then: who uses that? And then: that's gonna hurt performance! And then: but I can optimize for the common case!

The point is: only when people specify a strict prefix will the performance be hurt. Meaning that the performance is linear in the most common cases.

That is good enough for me, and probably good enough for the vast majority of the users. If it ain't broke, don't fix it.

In the case that somebody needs strict prefixes to be handled more efficiently, which I do not expect, the "hash all prefixes" approach may work well, but it would slow down the common case, so I'd suggest doing that only as a fallback (i.e. if a fixup! could not be matched up, fall back to hashing the prefixes, re-hashing the commit subjects that were already seen so far). If this needs to be implemented at all, I would also suggest that the person in need of that improvement also needs to take charge of this: I will not spend more time thinking about this.

Ciao, Johannes