Re: [PATCH v2] rev-list docs: clarify --topo-order description

[Thomas Rast <trast@student.ethz.ch>]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> On 08/16/2012 10:51 AM, Thomas Rast wrote:
>> I suppose the real problem is that the "true" ordering
>> is completely obvious as the one ordering that does not require
>> preprocessing, but ugly to specify in words.  Perhaps we can bikeshed a
>> little?  How about
>>
>>    By default, commits are shown in an order that coincides with
>>    `--date-order` on well-behaved history, but is faster to compute.
>
> Maybe the problem is not the description of the options, but the
> options themselves.  Why does the behavior default to some mysterious
> order that we don't even want to document?  Only for the sake of
> computational efficiency.  This is the tail wagging the dog.
>
> Why not turn the behavior on its head:
>
> * Change the default behavior to be something well-defined, easy to
> document, and convenient for humans, such as "topological order with
> ties broken by timestamp" or "approximate timestamp order, but
> respecting dependencies".
>
> * Add a new option, --arbitrary-order, that explicitly chooses
> efficiency instead of a defined order.

I think that would be a rather bad decision, largely because (taking my
git.git as an example):

  $ time git log | head -1
  commit e5e6172f9060c958e3f0d679cd7049d4007eed2c

  real    0m0.033s
  user    0m0.026s
  sys     0m0.007s

  $ time git log --date-order | head -1
  commit e5e6172f9060c958e3f0d679cd7049d4007eed2c

  real    0m0.429s
  user    0m0.359s
  sys     0m0.031s

That is, even in medium-sized projects like git.git, any -order option
incurs a significant preprocessing time until git-log can show the first
commit.  It scales linearly with the number of commits in the range, and
in a linux.git lying around here is already around 3.9s for the same
command.

So if --date-order or --topo-order were the default, you'd have a
significant delay even if you just use 'git log' to quickly see the last
few commits.  At least to me, the optimization makes perfect sense.

The right fix would be to dig up Peff's work on generation number
caching, and modify the algorithm to take generation numbers into
account.  Then the default order would magically become the same as
--date-order at no speed loss, *and* we'd get a huge speed boost to 'git
log --graph' startup times.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch