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

[Josiah Boning <jboning@gmail.com>]

On Fri, Apr 8, 2016 at 10:01 PM, Jeff King wrote:
> 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.

> 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