Git merge-base walks to stop early on one-sided histories

Git is set to finish many merge-base queries much sooner when one side of the history is a long chain the other side never meets. Kristofer Karlsson of Spotify submitted a patch series that teaches the merge-base paint walk to stop once one side has no exclusive commits left in the queue, after the walk has entered the region where generation numbers make paint final.

A new merge base can appear only when exclusive paint from both tips meets. When one side is exhausted, further walking cannot produce candidates, yet the current code often kept draining deep into the graph. That pattern shows up after repository imports that graft a separate root, and after any merge that introduces a low-generation commit the other side never paints. On git.git with a commit-graph, one measured query dropped from about 72k steps to 45k; a shallow case fell from 110 steps to 7. On the Linux kernel history, merge-base between v4.8 and v4.9 fell from roughly 167k steps to a few thousand, with wall time dropping from tenths of a second into the low hundredths.

Derrick Stolee supplied a criss-cross counterexample that tightened the halt condition, and Elijah Newren had independently found the same idea. The series also documents the algorithm, adds step counting via trace2, and strengthens tests around clock skew, mixed finite and infinite generation tips, and redundant candidate cleanup.

With side-exhaustion in place, Karlsson removes the old fallback that switched the queue from generation order to commit-date order on v1 commit-graphs. That fallback had papered over a performance cliff but broke the single ordering invariant early-exit logic needs. Maintainer Junio C Hamano called the change an important optimization while flagging a stale commit-message mismatch for a follow-up revision. Newren reviewed the documentation and edge-case coverage favorably.