Ordering of git-rev-list

Question 1

By default, the commits are ordered in reverse chronological order. You can get output in a different ordering depending on the options you pass. See the Commit Ordering section in the git-rev-list man page for the other options.

git log orders in reverse chronological order by default, too. However, when you run it with --graph it implies --topo-order.

Lastly, the commit ordering by date is done by commit date, but the default output of git log displays author date. With patches, cherry-picks, and rebases, those two can get out of sync.

Those last two points should explain why your two outputs are ordered differently, and why on the surface git rev-list isn't ordering by date.

Question 2

Is this behavior well-defined?

With Git 2.34 (Q4 2021), the revision traversal API has been optimized by taking advantage of the commit-graph, when available, to determine if a commit is reachable from any of the existing refs.

See commit f559d6d, commit 809ea28, commit bf9c0cb, commit f45022d (09 Aug 2021), and commit 29ef1f2 (05 Aug 2021) by Patrick Steinhardt (pks-t).
^{(Merged by Junio C Hamano -- gitster -- in commit a5619d4, 03 Sep 2021)}

connected: do not sort input revisions

^{Signed-off-by: Patrick Steinhardt}

In order to compute whether objects reachable from a set of tips are all connected, we do a revision walk with these tips as positive references and --not --all.
--not --all will cause the revision walk to load all preexisting references as uninteresting, which can be very expensive in repositories with many references.

Benchmarking the git-rev-list command highlights that by far the most expensive single phase is initial sorting of the input revisions: after all references have been loaded, we first sort commits by author date.
In a real-world repository with about 2.2 million references, it makes up about 40% of the total runtime of git-rev-list.

Ultimately, the connectivity check shouldn't really bother about the order of input revisions at all.
We only care whether we can actually walk all objects until we hit the cut-off point.
So sorting the input is a complete waste of time.

Introduce a new "--unsorted-input" flag to git-rev-list which will cause it to not sort the commits and adjust the connectivity check to always pass the flag.
This results in the following speedups, executed in a clone of gitlab-org/gitlab:
Benchmark #1: git rev-list  --objects --quiet --not --all --not $(cat newrev)
  Time (mean ± σ):      7.639 s ±  0.065 s    [User: 7.304 s, System: 0.335 s]
  Range (min … max):    7.543 s …  7.742 s    10 runs

Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
  Time (mean ± σ):      4.995 s ±  0.044 s    [User: 4.657 s, System: 0.337 s]
  Range (min … max):    4.909 s …  5.048 s    10 runs

Summary
  'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
    1.53 ± 0.02 times faster than 'git rev-list  --objects --quiet --not --all --not $newrev'
Note that not all refs are visible to clients.

rev-list-options now includes in its man page:

--unsorted-input

Show commits in the order they were given on the command line instead of sorting them in reverse chronological order by commit time. Cannot be combined with --no-walk or --no-walk=sorted.

rev-list-options now includes in its man page:

Cannot be combined with --graph. Cannot be combined with --unsorted-input if sorted or no argument was given.

2018:

Git 2.16 (Q1 2018) will allow git describe to give an object a human readable name based on an available ref when used as git describe <blob>.
(See more at "Which commit has this blob?")

In that context, git rev-list adds a new order.
See commit ce5b6f9 by Stefan Beller (stefanbeller).

revision.h: introduce blob/tree walking in order of the commits

The functionality to list tree objects in the order they were seen while traversing the commits will be used in one of the next commits, where we teach git describe to describe not only commits, but blobs, too.

That means the git rev-list man page has a new object traversal order:

--in-commit-order::
Print tree and blob ids in order of the commits.
The tree and blob ids are printed after they are first referenced by a commit.

Ordering of git-rev-list

`connected`: do not sort input revisions

`--unsorted-input`

`revision.h`: introduce blob/tree walking in order of the commits

Ordering of git-rev-list

connected: do not sort input revisions

--unsorted-input

revision.h: introduce blob/tree walking in order of the commits

`connected`: do not sort input revisions

`--unsorted-input`

`revision.h`: introduce blob/tree walking in order of the commits