From: Josiah Boning <jboning@gmail.com>
Date: Sat, 09 Apr 2016 03:55:54 GMT
Subject: git log with ordering option and --first-parent is unnecessarily slow
Message-ID: <CAKdicq8MnZMBV97K5O8Oa1T=PT9DsutmBS+P-bFYitATHH3s+Q@mail.gmail.com>

As measured on linux.git, adding --date-order to a log command can
result in a significant slowdown (~25x here; I've seen ~100x on other
repositories):

    $ time git log --first-parent --max-count=51 master > /dev/null
    real    0m0.024s
    user    0m0.006s
    sys    0m0.016s
    $ time git log --date-order --first-parent --max-count=51 master > /dev/null
    real    0m0.652s
    user    0m0.570s
    sys    0m0.074s

In combination with --first-parent, --date-order (or any other
ordering option) should be a no-op, since --first-parent selects a
linear history. So it seems like there's a significant performance win
available by ignoring ordering options when --first-parent is present.
Would this change be desirable? If so, I'll see about submitting a
patch.

More generally, it seems like it might be possible to identify when
the selected commits are linear and avoid the cost of sorting.

Josiah