Thanks for all the help on v2. Here are a few changes between versions: * Removed the constant-time check in queue_has_nonstale() due to the possibility of a performance hit and no evidence of a performance benefit in typical cases.
* Reordered the commits about loading commits from the commit-graph. This way it is easier to demonstrate the incorrect checks. On my machine, every commit compiles and the test suite passes, but patches 6-8 have the bug that is fixed in patch 9 "merge: check config before loading commits". * The interaction with parse_commit_in_graph() from parse_object() is replaced with a new 'check_graph' parameter in parse_commit_buffer(). This allows us to fill in the graph_pos and generation values for commits that are parsed directly from a buffer. This keeps the existing behavior that a commit parsed this way should match its buffer. * There was discussion about making GENERATION_NUMBER_MAX assignable by an environment variable so we could add tests that exercise the behavior of capping a generation at that value. Perhaps the code around this is simple enough that we do not need to add that complexity. Thanks, -Stolee -- >8 -- This is the one of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph) and lazy-loading trees (ds/lazy-load-trees). 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 short-circuit mechanism to improve performance of `git branch --contains`. Further, use generation numbers for 'git tag --contains), 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 is build on ds/lazy-load-trees. Derrick Stolee (9): commit: add generation number to struct commmit commit-graph: compute generation numbers commit: use generations in paint_down_to_common() commit-graph.txt: update design document ref-filter: use generation number for --contains commit: use generation numbers for in_merge_bases() commit: add short-circuit to paint_down_to_common() commit-graph: always load commit-graph information merge: check config before loading commits Documentation/technical/commit-graph.txt | 30 +++++-- alloc.c | 1 + builtin/merge.c | 5 +- commit-graph.c | 99 +++++++++++++++++++----- commit-graph.h | 8 ++ commit.c | 54 +++++++++++-- commit.h | 7 +- object.c | 2 +- ref-filter.c | 23 +++++- sha1_file.c | 2 +- t/t5318-commit-graph.sh | 9 +++ 11 files changed, 199 insertions(+), 41 deletions(-) base-commit: 7b8a21dba1bce44d64bd86427d3d92437adc4707 -- 2.17.0.39.g685157f7fb
