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

From: Josiah Boning <jboning@gmail.com>
Date: Apr 9, 2016, 03:55 UTC
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