Re: [PATCH 0/6] PATH WALK I: The path-walk API

On Mon, Nov 04, 2024 at 10:48:49AM -0500, Derrick Stolee wrote:

Adding my two cents, the discussion we had came after reading this post:

  https://www.jonathancreamer.com/how-we-shrunk-our-git-repo-size-by-94-percent/

I think a few of the low-level details in there are confusing, but it seemed to me that most of the improvement he mentions is just about finding better delta candidates. And it seems obvious that our current pack_name_hash() is pretty rudimentary as context-sensitive hashing goes and won't do well for long paths with similar endings.

So just swapping that out for something better seems like an easy thing to do regardless of whether we pursue --path-walk. It doesn't drastically change how we choose delta pairs so it's not much code and it shouldn't conflict with other features. And the risk of making anything worse should be pretty low.

I wouldn't at all be surprised if --path-walk can do better, but if we do the easy thing first then I think it gives us a better idea of the cost/benefit it's providing.

I suspect there's room for both in the long run. You seem to be focused on push size and cost, whereas I think Taylor and I are more interested in overall repo size and cost of serving bitmapped fetches.

The way I look at it is a possible continuum. We want to use pathnames as a way to sort delta candidates near each other, since we expect them to have high locality with respect to delta-able contents. The current name_hash uses a very small bit of that path information and throws away most of it. The other extreme end is holding the whole path. We may want to end up in the middle for two reasons:

  1. Dealing with whole paths might be costly (though I'm not yet
     convinced of that; outside of pathological cases, the number of
     paths in a repo tends to pale in comparison to the number of
     objects, and the per-object costs dominate during repacking).

  2. It's possible that over-emphasizing the path might be a slightly
     worse heuristic (and I think this is a potential danger of
     --path-walk, too). We still want to find candidate pairs that were
     copied or renamed, for example, or that substantially share content
     found in different parts of the tree.

So it would be interesting to be able to see the performance of various points on that line, from full path down to partial paths down to longer hashes down to the current hash. The true extreme end of course is no path info at all, but I think we know that sucks; that's why we implemented the bitmap name-hash extension in the first place.

Good point. This is all heuristics, of course, but I suspect that the order of the path is important, and that foo/bar.c and bar/foo.c are unlikely to be good matches.

Having worked on that feature of bitmaps, I'm not too worried about it. I think we'd just need to:

  - introduce a new bitmap ext with a flag (HASH_CACHE_V2 or something,
    either with the new hash, or with a "version" byte at the start for
    extensibility).

  - when bitmaps are not in use, we're free to use whichever hash we
    want internally. If the new hash is consistently better, we'd
    probably just enable it by default.

  - when packing using on-disk bitmaps, use internally whichever format
    the on-disk file provided. Technically the format could even provide
    both (in which case we'd prefer the new hash), but I don't see much
    point.

  - when writing bitmaps, use whichever hash the command-line options
    asked for. There's an off chance somebody might want to generate a
    .bitmap file whose hashes will be understood by an older version of
    git, in which case they'd use --no-full-name-hash or whatever while
    repacking.

If we're considering full paths, then that is potentially a bit more involved, just because we'd want the format to avoid repeating duplicate paths for each object (plus they're no longer fixed-size). So probably an extension with packed NUL-terminated path strings, plus a set of fixed-length offsets into that block, one per object.

That's interesting. I wonder which cases get worse, and if a larger window size might help. I.e., presumably we are pushing the candidates further away in the sorted delta list.

I'm not sure why a larger hash would be worse in a shallow clone. As you note, with only one version of each path the name-similarity heuristic is not likely to buy you much. But I'd have thought that would be true for the existing name hash as well as a longer one. Maybe this is the "over-emphasizing" case.

-Peff