Re: git log with ordering option and --first-parent is unnecessarily slow

From: Josiah Boning <jboning@gmail.com>
Date: Apr 9, 2016, 05:42 UTC
Message-ID: <CAKdicq_uNFcy0_SPephHX9KhEouYdk0ddj4g0y4nAiD90+eH3A@mail.gmail.com>
In-Reply-To: <20160409050116.GB25151@sigill.intra.peff.net>

On Fri, Apr 8, 2016 at 10:01 PM, Jeff King wrote:

Show 9 quoted lines

> I do agree that --date-order on a linear parent walk cannot change the
> ordering (which guarantees child-before-parent), and is a noop.  But
> note that not all first-parent invocations are strictly linear. For
> example:
>
>   git log --first-parent --date-order master next
>
> which starts from two tips. We'd still want to order commits from the
> two lists according to --date-order.

Ah, indeed; multiple tips certainly count as a nonlinearity.

Show 5 quoted lines

> I suppose we could catch the single-tip, first-parent case and ignore
> any ordering options which imply child-before-parent (which is currently
> all of them). But I did not think too hard if there are any other corner
> cases. This sounds like a case of "doctor, it hurts when I do this". Why
> do you want to add --date-order in such a case, when it is a noop?

It hurt when I did that, so I stopped. In my case, the git log command was written when the repositories involved were much smaller, so the delay was not so noticeable. Today I found and fixed the invocation--but it still seems nice to fix at the git level, if that's possible without adding much complexity.

> It's not the cost of sorting. It's the cost of accessing the commits (if
> you profile, you should see most time spent in zlib). So figuring out
> that the case is linear will require roughly the same expense.

I'm imagining that while traversing the commit graph, one could keep an is_linear flag, which is set initially if starting from a single tip, and becomes unset when a merge commit is encountered. If is_linear is still true when the entire requested range or the desired number of commit sare accumulated, then there's no need to sort.

This is, as a disclaimer, the guesswork of someone not familiar with the codebase. I'll go read the source before imagining further :)

Josiah