On Thu, Mar 27, 2025 at 02:32:43AM -0400, Jeff King wrote: > The pathspec-trie stuff is, I think, still a reasonable idea for general > use. But IIRC, the rewritten blame-tree you guys worked on does not > benefit from it, because it ditches pathspecs entirely (both because > they're too slow without the tries, but also because it's important to > continually narrow the pathspec while traversing). That trie code was > never run in production, I think (and I see there is a patch to narrow > the pathspec while traversing; I suspect that likewise was never used). Yeah, the rewritten blame-tree code uses changed-path Bloom filters to narrow the set of revisions that we need to actually compute tree-diffs for. The general idea is that we have a set of paths that we have yet to blame, and those are the "interesting" ones. IOW, if a changed-path Bloom filter tells us that we are at some revision where there is maybe a change to one or more unblamed paths, we need to compute a tree-diff. But if the Bloom filter says "no", then we can skip the tree-diff at that layer entirely. > The max-depth diff code is also in theory a reasonable thing to have in > general. But it is awkward to use, and not really necessary for > blame-tree. There we really only care about recursing vs not recursing, > but the usual "recursive" flag for diffing isn't enough (we have to > recurse down to the tree of interest, but may not want to go further). I > don't remember how that is handled in your blame-tree rewrites. I think that's mostly true, but the blame-tree caching stuff that Stolee worked on many years ago and mentioned below does require it IIRC. > So yeah. I don't know if all of this is really a very good starting > point. Taylor, if you can share the current code that GitHub is running, > I think that would be beneficial for the community. Sure. You can fetch from the 'tb/blame-tree' branch from my tree (which is located at 'git@xxxxxxxxxx:ttaylorr/git.git'). I owe a huge "thank you" to Victoria Dye, who split out the various topics from GitHub's fork into individual rebased branches. There were many more patches on top that came after Victoria's split above, and I applied those manually. The commit structure probably needs significant clean-up and polishing before it's ready for serious review, since this is more-or-less a raw dump of the work on GitHub's side over more than a decade. It also doesn't pass the tests in t9932 (and the test number should probably also be reworked, it's in the t99xx range so that inclusion in GitHub's fork doesn't cause collisions with new tests when we merge upstream). To that end, I removed everybody's Signed-off-by in case I have mangled their work in some way unintentionally. Thanks, Taylor
