patchrev-list docs: clarify --topo-order description

We said "--date-order" still does not violate the topology, but it was still not clear enough.

Reword the description for both "--date-order" and "--topo-order", and add an illustration to it.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * Let's do this before I forget...; came up in discussion $gmane/203370

 Documentation/rev-list-options.txt | 29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

On Mon, Aug 13, 2012 at 3:21 PM, Junio C Hamano <gitster@pobox.com> wrote:

Thanks! That definitely confused me (and I suppose I stupidly didn't test with a proper range).

It seems likely that those reading the above sentence will continue on to read about --topo-order, but still, do you think the "descendant commits are shown before parents" part belong here instead?

It would help at least me to also know what the output would be without either of --date-order or --topo-order. (Does the default order have a name, by the way?)

Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:

I do not think so. When you are not limited (i.e. limit_list() is not called), you could do something like "git rev-list 4 5" in a history like this:

	--1---5---2---3---4

and get end up getting "5 4 3 2 1", and "2" certainly doesn't get shown before "5" does.

In your series where cherry-pick runs prepare_revision_walk() and makes the outcome sort in reverse, the list has to be limited, so the above is a non-issue, but in the context of this document, we cannot assume that.

On Mon, Aug 13, 2012 at 4:05 PM, Junio C Hamano <gitster@pobox.com> wrote:

Oh, interesting. I had no idea, although that does make sense. Thanks.

Still, the "Even without this option" strongly suggests to me that what follows ("descendant commits are shown before parents") applies to the "By default" case. Would it be correct to say something like "By default, the commits are shown in reverse chronological order. When commit limiting is in effect, descendant commits are shown before parents."? I'm not sure the "commit limiting" section in the man page involves the same options as "limit_list" (I rather think they don't), but I don't know if there's a better term to use in the documentation either.

Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:

I wonder if spelling out that level of detail is unnecessarily overspecifying the behaviour.

In general, I'd prefer to keep the insn to end users to the minimum: i.e. use the default when you do not care too deeply about the order but you want to get commits in the range in reverse time order in general and let the default take care of the detail, and use one of the --foo-order options if a script wants to be more specific about the order. That way we do not have to get our hands tied to an unnecessary degree and keep the door open for us to improve the implementation.

On 08/14/2012 12:21 AM, Junio C Hamano wrote:

Thanks for this change. I was recently trying to figure out the meaning of these ordering options myself, and found the old text confusing.

Is it possible to predict which of the two orders would be taken here? It would be nice for the results to be deterministic. For example, topology "ties" could be broken by choosing the commit with the most recent timestamp.

Michael

Junio C Hamano <gitster@pobox.com> writes:

I don't think that is true in general. Without any -order options, we process commits in date order, which *usually* means topological order, but not always. You can easily verify this:

  $ git init
  $ date
  Tue Aug 14 10:39:49 CEST 2012
  $ echo initial >file
  $ git add file
  $ GIT_COMMITTER_DATE="Tue Aug 14 11:39:49 2012" git commit
  $ echo foo >file
  $ git commit -mfoo file
  $ git checkout -bside HEAD^
  $ echo bar >file
  $ git commit -mbar file
  $ git log --all --oneline
  8c71325 bar
  e5072d7 initial
  1be702c foo

So the --topo-order switch *ensures* that we process commits in topological order even in the face of skewed clocks.

I suspect that

is just a fortunate side effect of the topological sort.

Thomas Rast <trast@student.ethz.ch> writes:

Yes, I *think* that I attempted to show with the illustration.

I am not sure if it is "side effect"; I *think* it was the "primary objective" we added topo-order in the first place.

Junio C Hamano <gitster@pobox.com> writes:

But then the new description is wrong. It claims that children are always before parents, which is not true in the face of clock skew. Or am I missing something?

I won't judge that, since it's waaaay before my time :-)

Thomas Rast <trast@student.ethz.ch> writes:

Ah, you are talking about the "even without this option" part. Yeah, that does not hold true.

It was unclear what "--topo-order" was really about in the documentation. It is not just about "children before parent", but also about "don't mix lineages".

Reword the description for both "--date-order" and "--topo-order", and add an illustration to it.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
  Thomas Rast <trast@student.ethz.ch> writes:

  > But then the new description is wrong.  It claims that children are
  > always before parents, which is not true in the face of clock skew.

  Thanks for sanity-check.  Here is an updated one.

 Documentation/rev-list-options.txt | 31 ++++++++++++++++++++++++-------
 1 file changed, 24 insertions(+), 7 deletions(-)

On Wed, Aug 15, 2012 at 1:02 PM, Junio C Hamano <gitster@pobox.com> wrote:

As I said before, this led me to believe that "the commits are shown in reverse chronological order" when neither of --topo-order or --date-order is passed. I agree that we should avoid specifying more than necessary about the default case. But in this case, what is specified is not exactly true (in the face of clock skew). Or am I misunderstanding or misinterpreting something? I still don't understand the revision walker well enough to be able to provide a better wording, but I think even the rather crude "By default, the order is unspecified." would at least not be as easy to misinterpret (if that's what I did) and is definitely not over-specified. Of course, if someone can think of something better, I'm all for it.

Regardless of the above comment about the patch context, what your patch actually changes looks good. Thanks again.

Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:

We could remove it if you find it confusing.

I think the original motivation that line was added was to help people who see "git log" (without any frills) output for the first time not to be alarmed when they see newer things first: "In general, the "time" flows from bottom to top", but the "time" in that sentence is not necessarily the timestamp of either committer nor author field.

Junio C Hamano <gitster@pobox.com> writes:

Just to clarify, I am not defending the current wording that I did not touch in my patch with the above. I am just giving historical background to help _other_ people (including you) to come up with a better wording, as I do not think of a better replacement myself.

Junio C Hamano <gitster@pobox.com> writes:

I tend to agree with Martin, the existing header for the list

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

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

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.

That way the easiest thing to type is also the most convenient, whereas when you care about efficiency and *don't* care about order (i.e., mainly in scripts) you can explicitly request the high-performance option.

Michael

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

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@student.ethz.ch> writes:

You are correct to point out that introducing "--arbitrary-order" and force sorting by default is stupid for one reason, but forgot to stress the other equally important reason, I think. Even though you came close to it here:

you may not have fully internalized that other reason yourself, I suspect, for the reason I mention in my last two paragraphs below.

When you run "git log", you are asking only to see "the last few" commits. The size of "few" actually depends on the occasion and the user, but the important thing to notice is that the definition of "the last" is fuzzily defined. In such a request over a history like this:

      ---A---B---C---D
                      \
    ---1---2---3---4---* = HEAD

the user does not care the exact order, as long as the ones "closer" (again, a fuzzy definition) to HEAD come out earlier than the ones "farther" (and all of them have to come out eventually but that goes without saying).

In the case of the above sample history, even with clock skews, the ones labeled with alphabets appear in the expected order among themselves, and the ones labeled with numbers also do, with or without sorting. And all three orders match the use case of "git log" to view "the last few" commits just fine. When we have the default, topo and date orders, all of which would give us output suitable for the purpose of showing "the last few", picking the one with the least latency is the right thing to do.

In other words, latency is important, but a short-latency solution is acceptable and preferred only if it gives a reasonable result. Giving useless output with small latency is not what we are aiming to do.

I think you are totally wrong here, unless you are talking about a generation number that is different from what I recall from the older discussion. Think of the sample history above, and imagine that the numbered ones are based on the current 'master', but that the alphabet ones are based on an ancient maintenance release that is 1000 generations behind (think of me running the command after finishing the day's integration cycle, sitting at the tip of 'pu', where the last topic merged is meant to be eventually merged to maint-1.7.9). All of the commits depicted in the picture will have the commit timestamps in the past few hours. Ancestors of A and 1, not drawn in the picture, were made yesterday or before.

The current "default" output will give all of the depicted commits before showing the older commits that are not in the picture, and that is absolutely the right thing to do when you ask "git log" to view "the last few" commits. Imagine what you will see if you used generation numbers instead of the commit timestamp. You will see commits on the maintenance topic that can later be merged to an older codebase, only after you saw all the development history on the master branch since 1.7.9 release. I do not think we want to call such an output "the right fix".

Junio C Hamano <gitster@pobox.com> writes:

Hrm, now you're making me feel like I missed something. But my reasoning goes roughly like this.

Consider the commit graph as a DAG, where the parent pointers are directed edges from child to parent. Thus, tip commits are sources and root commits are sinks. One way to get a valid topo ordering, knowing the complete DAG, is:

  while there are vertices left:
    remove any source and emit it

(You can also generate it from the sinks instead; I haven't actually checked what the code currently does. But for the following, we need to start from the sources.)

To implement this efficiently, one usually keeps track of the set S of sources, and inserts vertices that (by removal of their last in-neighbour) have become a source.

The distinction between topo-order and date-order is the preference given in the choice of source. IIUC, date-order prefers the newest source by committer date (using a priority queue or such for S), and topo-order prefers the source(s) which were parents of the vertex removed in the previous iteration (using a stack for S).

The problem with this algorithm is that it requires knowledge of the DAG[1]. So with --topo-order, git dutifully loads the whole commit graph, and then runs the algorithm, leading to the discussed startup delay.

However, suppose we knew generation numbers. I haven't actually looked into the old threads again, but my understanding was that they are numbers g(C) attached to each commit C such that

  g(C) = 1 + max(g(P) for P a parent of C)   for non-root commits

  g(C) = 0                                   for root commits

They are invariant given the commit, so they can be cached. And they allow us to infer something about ancestry: if g(C)<=g(D), then C cannot possibly be a descendant of D.

The topo order algorithm can be modified to take advantage of them, in order to provide incremental processing:

  Let S be the set of tentative sources

  Let U be the set of vertices whose out-edges are no known yet
    (i.e., the set of commits which haven't been loaded yet)

  Let max g(U) denote "max g(C) taken over all C in U".

  Fill S and U from the revisions given:
    load all positive revisions, let's call this set P
    put all zero-indegree members of P in S
    put all parents of members of P in U (as far as they are not also
    members of P, and therefore loaded already)

  while there are any vertices left:

    pick any tentative source C from S that we "want to emit"

    # Ascertain that no unknown commit (from U or further beyond) can be
    # a descendant of C
    while there is a D in U such that g(D) > g(C):
      load D
      remove D from U
      add the parents of D to U if they were not already loaded
      possibly remove some elements of S if their indegree became nonzero

    if C was removed from S:
      continue

    remove C from the graph and emit it

I hope I got that right. The order of commits is still entirely determined by the choice of "any tentative source", but the algorithm should now stream nicely once the generation numbers are known.

Footnotes: 

[1] If there are any parent pointers not yet followed, they may in fact wind up (over at least one more commit) pointing to the commit you wanted to emit next, making that an invalid choice.

Thomas Rast <trast@inf.ethz.ch> writes:

[...]

By the way, this does bump the runtime of the algorithm a bit, depending on the data structure used for U. Recall that ordinary topo-sort with a stack for S (i.e., --topo-order) runs linearly with the number of vertices.

If we use a priority queue for U, which lets us get at the highest-generation unknown commits easily, it potentially goes to n log n if U reaches linear size at some point.

That shouldn't hurt too much of course, since on the one hand it should rarely actually get that big, and OTOH --date-order has n log n runtime anyway (using a priority queue for S).

Thanks for challenging me on my "it should work" feeling. It was quite interesting to actually think it through and write down a workable algorithm.

Thomas Rast <trast@inf.ethz.ch> writes:

That matches the definition of generation number I remember from the old discussion. Now look at the illustration in this discussion again:

      ---A---B---C---D
                      \
    ---1---2---3---4---* = HEAD

and an excerpt from the message you are respoding to:

  Think of the sample history above, and imagine
  that the numbered ones are based on the current 'master', but that
  the alphabet ones are based on an ancient maintenance release that
  is 1000 generations behind (think of me running the command after
  finishing the day's integration cycle, sitting at the tip of 'pu',
  where the last topic merged is meant to be eventually merged to
  maint-1.7.9).  All of the commits depicted in the picture will have
  the commit timestamps in the past few hours.  Ancestors of A and 1,
  not drawn in the picture, were made yesterday or before.

The numbered commits 1 2 3 4 are building on top of recent "master", while alphabetized A B C D are building on aged maintenance track. The difference in generation numbers between 1 and 2, 2 and 3,... A and B, B and C, C and D are all one, and HEAD (the tip of 'pu') would have generation number of commit 4 plus 1, as commit 4's generation number would be a thousand or more ahead of that of commit D. And there are a thousand ancestors of '1' with larger generation numbers than 'D'.

When the user runs "git log" (i.e. the casual "the last few commit" macthes), the expectation of the user is "I want to see what I did recently". If you substituted the commit timestamp with such a generation number, how would that expectation satisified?

Generation numbers is a clean solution to avoid giving an incorrect range result when there are clock skews (cf. the use of SLOP in revision.c::still_interesting()), but it is not a good substitute when the user is more interested in absolutely correct topology (in other words, the user is more interested in both rougly wallclock time order and seeing the result soon --- which brings us back to the original "short latency is vastly preferred _as long as_ it produces the result the user wants to see").

Junio C Hamano <gitster@pobox.com> writes:

[...]

Umm, have you looked at the algorithm I proposed?

It does not substitute the generation numbers for anything, let alone the date. It merely uses them to determine a point where it knows "enough" of the history to be able to emit the next commit; that is, where it can use the generation numbers to prove that no unknown commit can be a descendant of what it wants to emit next.

It does *not* have to use the generation numbers in the final ordering of the commits. That final order is determined by how the algorithm chooses the next candidate commit. If you use a stack, it winds up being --topo-order. If you use a date-ordered priority queue, it becomes --date-order.

So really, this is only about modifying the algorithm that generates the existing order to allow for streaming output as it reads through history.

Thomas Rast <trast@student.ethz.ch> writes:

Sorry, I thought you were optimizing sort_in_topological_order() found in commit.c, not the callchain that forms get_revision() in revision.c.

Thomas Rast <trast@inf.ethz.ch> writes:

Thanks for an intereseting read.

Even though generation numbers are not always a good subsitute for timestamps depending on the use (see the other message), the algorithm to compute "topo-order" can take advantage of the generation numbers when they are available, as you illustrated in your message.

We may want to think about adding a new field to the commit object, with a fallback mechanism to an external "cache" that is generated on-demand.

Once the mechanism is in place so that any caller of parse_commit() can depend on having a reliable .generation field in the commit object it receives from the function, we can start updating various traversal algorithms to take advantage of this new information.

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

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

Junio C Hamano <gitster@pobox.com> writes:

[...]

Ack, thanks.