Derrick Stolee <sto...@gmail.com> writes: > On 4/3/2018 2:03 PM, Brandon Williams wrote: >> On 04/03, Derrick Stolee wrote: >>> This is the first of several "small" patches that follow the serialized >>> Git commit graph patch (ds/commit-graph). >>> >>> As described in Documentation/technical/commit-graph.txt, the generation >>> number of a commit is one more than the maximum generation number among >>> its parents (trivially, a commit with no parents has generation number >>> one). [...] >>> A more substantial refactoring of revision.c is required before making >>> 'git log --graph' use generation numbers effectively. >> >> log --graph should benefit a lot more from this correct? I know we've >> talked a bit about negotiation and I wonder if these generation numbers >> should be able to help out a little bit with that some day. > > 'log --graph' should be a HUGE speedup, when it is refactored. Since > the topo-order can "stream" commits to the pager, it can be very > responsive to return the graph in almost all conditions. (The case > where generation numbers are not enough is when filters reduce the set > of displayed commits to be very sparse, so many commits are walked > anyway.)
I wonder if next big speedup would be to store [some] topological ordering of commits in the commit graph... It could be done for example in two chunks: a mapping to position in topological order, and list of commits sorted in topological order. Note also that FELINE index uses (or can use -- but it is supposedly the optimal choice) position of vertex/node in topological order as one of the two values in the pair that composes FELINE index. > If we have generic "can X reach Y?" queries, then we can also use > generation numbers there to great effect (by not walking commits Z > with gen(Z) <= gen(Y)). Perhaps I should look at that "git branch > --contains" thread for ideas. This is something that is shown in the Google Colab [Jupyter] Notebook I have mentioned: https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg https://drive.google.com/file/d/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg/view?usp=sharing > For negotiation, there are some things we can do here. VSTS uses > generation numbers as a heuristic for determining "all wants connected > to haves" which is a condition for halting negotiation. The idea is > very simple, and I'd be happy to discuss it on a separate thread. Nice. How much speedup it gives? Best regards, -- Jakub Narębski
