On Thu, Jan 16, 2025 at 07:53:13AM -0500, Jeff King wrote: > I suspect that the whole bisection count algorithm needs to be rewritten > to all run in a single traversal. I guess if you iterate over the > commits in reverse-topo order, you should be able to just compute each > distance as "d(commit) = 1; d(commit) += d(p) for parents(commit)". But > it's not a problem I've thought a lot about, so I'm probably missing > some subtlety. Oh nevermind, that won't work, as it double-counts commits that are reachable from each parent. Still, it feels like there ought to be a way to compute it with a single traversal. I think this is similar to the reachability bitmap computation, which computes a bitmap for each commit (and then the weight of each commit is the number of set bits, but we've removed the duplicates). We do that in a single traversal these days, but it's pretty complex and heavyweight. So I think there's room for improvement here, but it sounds non-trivial. -Peff
