On 5/1/2020 10:13 AM, Antonio Russo wrote:

On 4/29/20 7:12 AM, Derrick Stolee wrote:

quoted

On 4/29/2020 4:01 AM, Antonio Russo wrote:

quoted

When used with --graph, instead of displaying the full graph, display a
spanning subgraph produced by a depth-first search of the graph visiting
parents from left to right.  Edges to already visited commits are
discarded.  This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges
that were not rebased onto each other and the user is primarily
interested in the state of the branch being merged into.

My earlier comment to recommend how to fix the test failures intended
to demonstrate that this area of code requires a bit of precision. I
took some time to review this patch, but I find it needs some significant
updates.

tl;dr: The way you manipulate the commit parents seems incorrect to me,
but perhaps there is enough prior art in the way we simplify parents to
make that acceptable. Someone else will need to chime in on that part.

First, thank you for taking the time look at this.  I understand your
hesitation about the "amputation" of the history, but in some sense
that's the point of this option.  I really want to be ignorant of the
details of when the fork branched off.  I would like the reported
history to be appear nearly equivalent to a rebase-and-fastforward only
merge style, which results in a much simpler git log --graph.

quoted

It may be possible to do this "drop edges" entirely inside of graph.c
(the graph rendering code) instead of revision.c, which would automatically
work with the performance gains from the newer topo-walk algorithm.

Non-local information about the commit graph needs to be used to do this
amputation of the history.  We cannot know how many parents we want to
display until we've completely explored all the parents of that node.
Unfortunately, that means that the whole graph needs to be loaded, and I
cannot really see how there would be any gain by doing this in graph.c.

Caveat: there are semi-streaming DFS implementations (i.e., O(n log n)
space) that we might be able to use to get the first line out the door
quicker. I would, however, like to leave that to another patch.

I will also add that, for the tests I've done, all performance penalties
have been insignificant (less than ~5% for showing the first commit),
while there are significant performance _improvements_, e.g., ~40% for
displaying the full tree.

A notable exception is --all, which can be ~50x faster for the full
output, but is often dramatically slower to show anything (i.e., the
first line).

quoted

There are enough deviations from code and test style that this will
need a significant revision regardless.

(Please see forthcoming revision 3).

quoted

quoted

This second revision of the patch sets revs->limited.  This forces the
graph of commits to be loaded, and simplfiy_forks() therefore reliably
traverses it.  This addresses the test failures mentioned before (see [1]).

This will have a significant performance impact on the option, as you will
not see even the first result until the DFS has completed.

First of all, short of using some other, more sophisticated streaming
version of this algorithm, the full DFS must finish before the first
commit having two (or more) parents can be shown.

That said, the performance is not significantly affected:

I ran the following test (2.26.2, with my patch on top of it):
(git lg = git log --graph --pretty=oneline)

 % time git lg -n1 --ignore-merge-bases e896a286df > /dev/null
 0.73s user 0.02s system 99% cpu 0.746 total

 % time git lg -n1 e896a286df > /dev/null
 0.72s user 0.01s system 99% cpu 0.731 total

 For the linux git repo:

 % time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null
 9.25s user 0.39s system 99% cpu 9.646 total

 % time git lg -n1 v5.7-rc3 >/dev/null
 9.02s user 0.35s system 99% cpu 9.378 total

So the performance seems basically unaffected for very limited graphs.
It's also about 40% faster for complicated ones (as mentioned in my
first email):

 % time git lg --ignore-merge-bases e870325ee8 > /dev/null
 0.83s user 0.06s system 99% cpu 0.886 total

 % time git lg e870325ee8 > /dev/null
 1.41s user 0.03s system 99% cpu 1.443 total

 For the linux git repo:

 % time git lg --ignore-merge-bases v5.7-rc3 >/dev/null
 11.86s user 0.62s system 99% cpu 12.489 total

 % time git lg v5.7-rc3 >/dev/null
 21.56s user 0.55s system 99% cpu 22.108 total

First, run `git commit-graph write --reachable` to create a commit-graph
file which has generation numbers. In this case, I get the following:

$ time git log --oneline --graph v5.7-rc3 >/dev/null

real    0m13.548s
user    0m13.348s
sys     0m0.200s

$ time git log --oneline --graph -n 1 v5.7-rc3 >/dev/null

real    0m0.007s
user    0m0.004s
sys     0m0.004s

Notice exactly how much better this gets for the first result with that
file.

This is because the amputated graph is much simpler, and the rest of the
code needs to do much less work.

Passing --all is another beast, and does indeed suffer:

 % time git lg --ignore-merge-bases --all >/dev/null
 4.06s user 0.04s system 99% cpu 4.105 total

 % time git lg --all >/dev/null
 189.59s user 0.04s system 99% cpu 3:09.65 total

 (and for the first line)

 % time git lg -n1 --ignore-merge-bases --all >/dev/null
 3.86s user 0.02s system 99% cpu 3.874 total

 % time git lg -n1 --all >/dev/null
 0.83s user 0.02s system 99% cpu 0.848 total

(If you need to use --all for the Linux git repo, you should not use
--ignore-merge-bases).

I think this is a deficiency in your implementation, not a hard rule
about how these options would need to interact.

Thanks,
-Stolee