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

Michael Haggerty [off-list ref] writes:

On 08/16/2012 10:51 AM, Thomas Rast wrote:

quoted

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

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

Michael Haggerty [off-list ref] writes:

quoted

On 08/16/2012 10:51 AM, Thomas Rast wrote:

quoted

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/