On Sat, 3 Sep 2016, Josh Triplett wrote:
> 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
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.