v2.19.0-rc1 Performance Regression in 'git merge-base'

As I was testing the release candidate, I stumbled across a regression in 'git merge-base' as a result of the switch to generation numbers. The commit message in [PATCH 1/1] describes the topology involved, but you can test it yourself by comparing 'git merge-base v4.8 v4.9' in the Linux kernel. The regression does not show up when running merge-base for tags at least v4.9, which is why I didn't see it when I was testing earlier.

The solution is simple, but also will conflict with ds/reachable in next. I can send a similar patch that applies the same diff into commit-reach.c.

With the integration of generation numbers into most commit walks coming to a close [1], it will be time to re-investigate other options for reachability indexes [2]. As I was digging into the issue with this regression, I discovered a way we can modify our generation numbers and pair them with commit dates to give us a simple-to-compute, immutable two-dimensional reachability index that would be immune to this regression. I will investigate that more and report back, but it is more important to fix this regression now.

Thanks, -Stolee

[1] https://public-inbox.org/git/[email protected]/[PATCH
0/6] Use generation numbers for --topo-order

[2] https://public-inbox.org/git/[email protected]/[RFC] Other chunks for commit-graph, part 2 - reachability indexes

Derrick Stolee (1):
commit: don't use generation numbers if not needed

 commit.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

base-commit: 2f743933341f276111103550fbf383a34dfcfd38
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-28%2Fderrickstolee%2Fmerge-base-regression-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-28/derrickstolee/merge-base-regression-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/28

gitgitgadget