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

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Aug 16, 2012, 16:35 UTC
Message-ID: <502D2137.9000504@alum.mit.edu>
In-Reply-To: <87k3wzujuy.fsf@thomas.inf.ethz.ch>

On 08/16/2012 02:00 PM, Thomas Rast wrote:

Show 48 quoted lines

> 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.

Thanks for timing this; I didn't realize how costly this would be. Just to make it even more obvious that this performance regression would bite in daily life, consider

     $ time git log -1

     real    0m0.013s
     user    0m0.000s
     sys     0m0.004s

     $ time git log -1 --topo-order

     real    0m0.334s
     user    0m0.316s
     sys     0m0.012s

Ouch.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/