git-rev-list: proper lazy reachability

git-rev-list: proper lazy reachability

[Linus Torvalds]

Ok, I just made git-rev-list DTRT when you pass it a "beginning" and 
"end", ie it does proper reachability analysis _without_ parsing the whole 
set of commits. 

It's probably buggy, so don't get too excited, but it seems to give the 
right results for something like

	git-rev-list v2.6.12-rc5 v2.6.12-rc4

which is basically "give me a rev-list of everything that is in rc5 but is 
not in rc4".

So now "git-rev-list a b" should be equivalent to "git-rev-tree a ^b", 
except it's faster, and it doesn't print out anything else.

Because it doesn't need to go all the way back to the root (only far 
enough back to be able to determine that there can be no more unreachable 
entries), it should be constant-time in the total history size. Doesn't 
matter if you've got a million revisions, if you asked for the difference 
between two "close" ones, it will be fast.

Somebody should probably take a look at my simplistic algorithm, since it 
can probably be improved upon and/or fixed for corner-cases.

		Linus

Re: git-rev-list: proper lazy reachability

[Jon Seymour]

On 5/31/05, Linus Torvalds <torvalds@osdl.org> wrote:
> 
> Somebody should probably take a look at my simplistic algorithm, since it
> can probably be improved upon and/or fixed for corner-cases.

Seems reasonable, though I think that in a graph like this:

    A 
  /  |  \ 
B  C  D
|  /   /
E
| \ 
F G

and searching for git-rev-list A ^B

it would actually be better to stop at E (printing A,B,C,D,E), rather
than B because the contemporaneously parallel edits C and D and the
common base E are relevant to evaluating B since they got merged with
B into A from the common starting point E.

In the lingo of my epoch theory, this is searching to the next nearest
epoch boundary past B.

My merge-order patch to rev-list which incorporates epoch theory is
still on its way - it turned out that incrementally finding epoch
boundaries was not quite as simple as I thought it would be. I expect
I'll have a respectable looking patch available this weekend. The
patch I have now works quite well for smaller graphs but fails on
larger graphs because it relies on rational numbers with large
numerators and denominators and these end up overflowing even 64 bit
integers. I think I know how to fix it, but it will take me a few more
days yet.

jon.

-- 
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/

Re: git-rev-list: proper lazy reachability

[Paul Mackerras]

Linus Torvalds writes:

> Ok, I just made git-rev-list DTRT when you pass it a "beginning" and 
> "end", ie it does proper reachability analysis _without_ parsing the whole 
> set of commits. 

I have made gitk use git-rev-list instead of git-rev-tree, but it
still absorbs the whole of git-rev-list's output before drawing
anything.  I'd like to make it draw the commit graph and list
incrementally as it gets the output from git-rev-list, but to do that
I need to know whether git-rev-list could ever print a commit ID
*after* one of its parents.  If it never does that then I can
restructure the code to do the drawing incrementally fairly easily.

Paul.

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Tue, 31 May 2005, Jon Seymour wrote:
>
> On 5/31/05, Linus Torvalds <torvalds@osdl.org> wrote:
> > 
> > Somebody should probably take a look at my simplistic algorithm, since it
> > can probably be improved upon and/or fixed for corner-cases.
> 
> Seems reasonable, though I think that in a graph like this:
> 
>      A 
>   /  |  \ 
> B    C   D
> |  /   /
> E
> | \ 
> F G
> 
> and searching for git-rev-list A ^B it would actually be better to stop
> at E (printing A,B,C,D,E), rather than B because the contemporaneously
> parallel edits C and D and the common base E are relevant to evaluating
> B since they got merged with B into A from the common starting point E.

You're talking about something else - you worry about showing a graph, for 
example.

What git-rev-list A B does is literally for something like a "changelog" -
what commits were added in A that weren't in B, and the list is A, C and
D. Or, more commonly, used for something like

	git-rev-list HEAD v2.6.12-rc5 | git-diff-tree --stdin -v -p drivers/usb

which basically says "what changed since 2.6.12-rc5 in the drivers/usb 
tree"?

So in that situation, you really do _not_ want to see B and E, even if
you'd need those two to make all the connections. Because you've seen B
and E already (they were in v2.6.12-rc5), and if you're looking for a bug
that didn't happen in that release, you really only want to see the new
stuff.

		Linus

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Tue, 31 May 2005, Paul Mackerras wrote:
> 
> I have made gitk use git-rev-list instead of git-rev-tree, but it
> still absorbs the whole of git-rev-list's output before drawing
> anything.  I'd like to make it draw the commit graph and list
> incrementally as it gets the output from git-rev-list, but to do that
> I need to know whether git-rev-list could ever print a commit ID
> *after* one of its parents.  If it never does that then I can
> restructure the code to do the drawing incrementally fairly easily.

You should never see a parent before a child from git-rev-list. I may have 
screwed something up when I move things between the two lists (the 
before/after thing needs to first do the reachability thing on one list, 
and then moves them to the "potential output list"), but I don't think so.

Anyway, at that point it would be a git-rev-list bug, so if you can make
your code notice and complain ("git-rev-list listed parent before child")  
rather than silently show crud, that would help debugging it if it ever 
happened.

		Linus

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Tue, 31 May 2005, Jon Seymour wrote:
> 
>      A 
>   /  |  \ 
> B    C   D
> |  /   /
> E
> | \ 
> F G
> 
> and searching for git-rev-list A ^B it would actually be better to stop
> at E (printing A,B,C,D,E)

Btw, you probably looked at the actual code, so you know this, but maybe 
it wasn't clear to everybody else: the code obviously _will_ look at all 
of ABCDE before it can even decide that it should print out ACD, since it 
really needs to.

What happens is that it walks the tree "time-first" (not depth-first or 
breadth-first, but "most-recent-first"), which tends to approximate what 
we want, and when it sees "B" it will mark all of its children as 
uninteresting since they were clearly seen. So it will actually have 
gotten all the way to E before it can tell that it has seen enough.

The thing that makes git-rev-list preferred over git-rev-tree is that it 
can avoid looking at F and G and older parents, since it's clear by E that 
walking the tree any further would be pointless, and all the commits we 
could look at are already marked uninteresting.

But if somebody wanted to actually show this as a _graph_, what you would 
probably want is actually all of ABCDE, except you'd get the "interesting" 
bit separately (ie ACD would be tagged some way). Then you could show a 
sane graph that is colored by whether something is new or not, for 
example. That's absolutely trivial to do wiyth the new rev-list algorithm, 
in case somebody really cares - it's literally just changing the printout 
to show the entries marked "ignored" with some extra marking.

(Well, slightly more too: you'd have to add the uninteresting commits to
the list, and mark the end object itself as being ignored, but that's two
more trivial lines. Right now the code knows that it won't even add some 
objects to the output list, so..).

		Linus

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Tue, 31 May 2005, Linus Torvalds wrote:
> 
> You should never see a parent before a child from git-rev-list.

Actually, I take that back.

A commit that has several children will see _a_ child before the parent is
shown, but while the time-based ordering means that it _likely_ will order
all children before the parent, now that I think about it, that's not
guaranteed to be true. You could have

	      A
	     / \
	    B   |
	     \ /
	      C
	      |
	      D

and if C has a date that is before B, then git-rev-list would traverse the
tree (and show it) in the order A C B.

In fact, even D might be listed before B is (eg, the person who committed
B had a clock that was set to the last century, and so the date on that
was wrong).

The thing is, since B has such an "old" date, the traversal assumes that
it is old and very low down in the tree, and that it's better off parsing
other commits first, so it will never look more closely at B and notice
that it has a parent that has already been parsed.

So I guess you'll have to wait for the end and do the toposort after all. 
Sorry about the confusion on my part.

		Linus

Re: git-rev-list: proper lazy reachability

[Jon Seymour]

On 6/1/05, Linus Torvalds <torvalds@osdl.org> wrote:
> 
> 
> On Tue, 31 May 2005, Jon Seymour wrote:
> >
> >      A
> >   /  |  \
> > B    C   D
> > |  /   /
> > E
> > | \
> > F G
> >
> > and searching for git-rev-list A ^B it would actually be better to stop
> > at E (printing A,B,C,D,E)
> 
> Btw, you probably looked at the actual code, so you know this, but maybe
> it wasn't clear to everybody else: the code obviously _will_ look at all
> of ABCDE before it can even decide that it should print out ACD, since it
> really needs to.

I did look at the code and concluded that ACD would be displayed and
simply assumed B would also be displayed. Anyway, you are right, for
the purposes you are interested in neither B nor E are interesting.

> 
> But if somebody wanted to actually show this as a _graph_, what you would
> probably want is actually all of ABCDE, except you'd get the "interesting"
> bit separately (ie ACD would be tagged some way). Then you could show a
> sane graph that is colored by whether something is new or not, for
> example. That's absolutely trivial to do wiyth the new rev-list algorithm,
> in case somebody really cares - it's literally just changing the printout
> to show the entries marked "ignored" with some extra marking.

This will also fall pretty naturally out of the --merge-order patch
that I am working on with an appropiate tweak. But I'll shut up about
that until I have code to share...

jon.

Re: git-rev-list: proper lazy reachability

[Matthias Urlichs]

Hi, Linus Torvalds wrote:

> So I guess you'll have to wait for the end and do the toposort after all.

We could add a cache file, listing commit nodes which predate one of
their parents. Hit one of those and you know you need to immediately
examine their parents instead of waiting for them to come up in date order.

There shouldn't be too many of those in any tree.

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
Truth is a statue, and you are all just a bunch of pigeons.

Re: git-rev-list: proper lazy reachability

[Marco Costalba]

Linus Torvalds wrote:
> 
> On Tue, 31 May 2005, Linus Torvalds wrote:
> 
>>You should never see a parent before a child from git-rev-list.
> 
> 
> Actually, I take that back.
> 
...

> 
> The thing is, since B has such an "old" date, the traversal assumes that
> it is old and very low down in the tree, and that it's better off parsing
> other commits first, so it will never look more closely at B and notice
> that it has a parent that has already been parsed.
> 

If this is an exception, and I it is, peraphs can be treated in a special way.

As example, when adding a new parent to the pending list of parents to be processed in time-based
ordering, should be easy to inc a counter if  the last one is always the same, e.g. there is the
same very old node around, and check closer to it if the counter reach some allowed maximum.

I know it's a hack, and is not a solution in the general case, but also the last century developer
clock is very rare, more, it is a warning for a bad commit. 

Do not wait for the end of the toposort its a very big advantage for, e.g. GUI git viewers
launched on big trees with long histories.

Marco Costalba




	

	
		
___________________________________ 
Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB 
http://mail.yahoo.it

Re: git-rev-list: proper lazy reachability

[Marco Costalba]

Linus Torvalds wrote:
> 
> On Tue, 31 May 2005, Linus Torvalds wrote:
> 
>>You should never see a parent before a child from git-rev-list.
> 
> 
> Actually, I take that back.
> 
...

> 
> The thing is, since B has such an "old" date, the traversal assumes that
> it is old and very low down in the tree, and that it's better off parsing
> other commits first, so it will never look more closely at B and notice
> that it has a parent that has already been parsed.
> 

If this is an exception, and I it is, peraphs can be treated in a special way.

As example, when adding a new parent to the pending list of parents to be processed in time-based
ordering, should be easy to inc a counter if  the last one is always the same, e.g. there is the
same very old node around, and check closer to it if the counter reach some allowed maximum.

I know it's a hack, and is not a solution in the general case, but also the last century developer
clock is very rare, more, it is a warning for a bad commit. 

Do not wait for the end of the toposort its a very big advantage for, e.g. GUI git viewers
launched on big trees with long histories.

Marco Costalba







	

	
		
___________________________________ 
Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB 
http://mail.yahoo.it

Re: git-rev-list: proper lazy reachability

[Junio C Hamano]

Linus, what do you think rev-list should do given HEADs from two
forks, like this?

    JC          git-rev-list JC LT ????
     |
     |  LT
     |   |
      \ /
       |
       |
       |

The above is often the shape of my working repository.  I pull
from you, commit a handful on top of your then-HEAD, and when I
am about ready to submit, I pull from you again to find your
HEAD advanced somewhat.

For patch-form submission, I need a list of my commits since I
forked from you.  Also I tend to rebase to your head often,
instead of merging inside my working repository (which makes
later e-mail patch-form submission more work for me), so even
when I am not immediately submitting the changes I have in my
fork, I need that list to forward port my changes.

JIT currently uses this to get this list (as a workaround):

    git-rev-list JC $(merge-base JC LT)

I am wondering if this "since they forked" is usually what the
user wants.  If that is the case then it would be great if I did
not have to do the "merge-base" part outside.

Current "proper lazy reachability" version, btw, does something
very unexpected for my use pattern.  If you have more than one
commits between the fork point and LT HEAD in the above picture,
everything from the beginning of time to JC is given, or
something silly like that.

Re: git-rev-list: proper lazy reachability

[Thomas Glanzmann]

Hello Junio,
I pull the REMOTE_HEAD including objects but don't merge. After that I
run:

system("git-rev-tree HEAD REMOTE_HEAD | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v ");

for bitkeeper I used the merge base approach (but at that time I only
knew that this gives me any deltas in the current tree not in the remote
tree, but didn't know how it worked).

bkparentdiff is aliased to `bk rset -hr`bk repogca`,+ | grep -v ^BitKeeper | bk gnupatch -du -e -h -T'

	Thomas

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Sat, 4 Jun 2005, Junio C Hamano wrote:
>
> Linus, what do you think rev-list should do given HEADs from two
> forks, like this?
> 
>     JC          git-rev-list JC LT ????
>      |
>      |  LT
>      |   |
>       \ /
>        |
>        |
>        |

Ahh. Ok, I'll fix it. Indeed, I think it should give everything up to the 
merge base.

> Current "proper lazy reachability" version, btw, does something
> very unexpected for my use pattern.  If you have more than one
> commits between the fork point and LT HEAD in the above picture,
> everything from the beginning of time to JC is given, or
> something silly like that.

Yes. The whole thing is written to literally expect to see the "stop here" 
thing, and that's when it starts poisoning the well.

Does this fix it for you (untested, of course)?

		Linus
---
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -160,6 +160,8 @@ int main(int argc, char **argv)
 		end = lookup_commit_reference(sha1[1]);
 		if (!end || parse_commit(end) < 0)
 			die("bad ending commit object");
+		end->object.flags |= UNINTERESTING;
+		commit_list_insert(end, &list);
 	}
 
 	commit_list_insert(commit, &list);

Re: git-rev-list: proper lazy reachability

[Linus Torvalds]

On Sat, 4 Jun 2005, Linus Torvalds wrote:
> 
> Does this fix it for you (untested, of course)?

Btw, as shown by this patch, the lazy git-rev-list algorithm is actually
_supposed_ to be able to handle a lot more complicated cases than what the 
command line interface allows.

In other words, maybe I should have used the same syntax as for 
git-rev-tree, because it _can_ handle things like "show me all revisions 
that are reachable from a or b, but are _not_ reachable from c or d or e.

Is that useful? I dunno. It might be useful for somebody like Jeff, who
has lots of different heads, and he could say "ok, show me what is in all
my network driver heads, but isn't in linus' tree".

Would people prefer to have "git-rev-list" take arguments like

	git-rev-list a b ^c ^d

the way git-rev-tree does?

		Linus

Re: git-rev-list: proper lazy reachability

[Junio C Hamano]

>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:

LT> On Sat, 4 Jun 2005, Linus Torvalds wrote:

>> Does this fix it for you (untested, of course)?

Will check later.

LT> Would people prefer to have "git-rev-list" take arguments like
LT> 	git-rev-list a b ^c ^d
LT> the way git-rev-tree does?

I do not expect myself to maintain many heads like Jeff, I
cannot comment on how well that "many heads" feature would work
in practice, but I would vote "a ^b" syntax to match
git-rev-tree.

Re: git-rev-list: proper lazy reachability

[Junio C Hamano]

>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:

LT> Yes. The whole thing is written to literally expect to see the "stop here" 
LT> thing, and that's when it starts poisoning the well.

LT> Does this fix it for you (untested, of course)?

Yes, it does.

Re: git-rev-list: proper lazy reachability

[Petr Baudis]

Dear diary, on Sat, Jun 04, 2005 at 05:51:13PM CEST, I got a letter
where Linus Torvalds <torvalds@osdl.org> told me that...
> Would people prefer to have "git-rev-list" take arguments like
> 
> 	git-rev-list a b ^c ^d
> 
> the way git-rev-tree does?

Yes, please. I think that usage is more consistent and more flexible.

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor