Thanks for the lively discussion of this patch series in v1! I've incorporated the feedback from the previous round, added patches [7/6] and [8/6], expanded the discussion of generation numbers in the design document, and added another speedup for 'git branch --contains'.
One major difference: I renamed the macros from _UNDEF to _INFINITY and _NONE to _ZERO. This communicates their value more clearly, since the previous names were unclear about which was larger than the "real" generation numbers. Patch 2 includes a change to builtin/merge.c and a new test in t5318-commit-graph.sh that exposes a problem I found when testing the previous patch series on my box. The "BUG: bad generation skip" message from "commit.c: use generation to halt paint walk" would halt a fast- forward merge since the HEAD commit was loaded before the core.commitGraph config setting was loaded. It is crucial that all commits that exist in the commit-graph file are loaded from that file or else we will lose our expected inequalities of generation numbers. Thanks, -Stolee -- >8 -- This is the one 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). This section is expanded to describe the interaction with special generation numbers GENERATION_NUMBER_INFINITY (commits not in the commit-graph file) and *_ZERO (commits in a commit-graph file written before generation numbers were implemented). This series makes the computation of generation numbers part of the commit-graph write process. Finally, generation numbers are used to order commits in the priority queue in paint_down_to_common(). This allows a constant-time check in queue_has_nonstale() instead of the previous linear-time check. Further, use generation numbers for '--contains' queries in 'git tag' and 'git branch', providing a significant speedup (at least 95% for some cases). A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively. This patch series depends on v7 of ds/commit-graph. Derrick Stolee (10): object.c: parse commit in graph first merge: check config before loading commits commit: add generation number to struct commmit commit-graph: compute generation numbers commit: use generations in paint_down_to_common() commit.c: use generation to halt paint walk commit-graph.txt: update future work ref-filter: use generation number for --contains commit: use generation numbers for in_merge_bases() commit: add short-circuit to paint_down_to_common() Documentation/technical/commit-graph.txt | 50 +++++++++++++-- alloc.c | 1 + builtin/merge.c | 5 +- commit-graph.c | 48 +++++++++++++++ commit.c | 78 ++++++++++++++++++++---- commit.h | 5 ++ object.c | 4 +- ref-filter.c | 24 ++++++-- t/t5318-commit-graph.sh | 9 +++ 9 files changed, 197 insertions(+), 27 deletions(-) -- 2.17.0