Re: [PATCH 7/7] builtin/merge-tree.c: implement support for `--write-pack`

On Sun, Oct 08, 2023 at 12:04:04PM -0400, Taylor Blau wrote:

I wonder how big a deal this would be in practice for merges. pack-objects will look for deltas between any two candidates objects, but in practice I think most deltas are between objects from multiple commits (across the "time" dimension, if you will) rather than within a single tree (the "space" dimension). And a merge operation is generally creating a single new tree (recursive merging may create intermediate states which would delta, but we don't actually need to keep those intermediate ones. I won't be surprised if we do, though).

We should be able to test that theory by looking at existing deltas. Here's a script which builds an index of blobs and trees to the commits that introduce them:

  git rev-list HEAD |
  git diff-tree --stdin -r -m -t --raw |
  perl -lne '
    if (/^[0-9a-f]/) {
      $commit = $_;
    } elsif (/^:\S+ \S+ \S+ (\S+)/) {
      $h{$1} = $commit;
    }
    END { print "$_ $h{$_}" for keys(%h) }
  ' >commits.db

And then we can see which deltas come from the same commit:

  git cat-file --batch-all-objects --batch-check='%(objectname) %(deltabase)' |
  perl -alne '
    BEGIN {
      open(my $fh, "<", "commits.db");
      %commit = map { chomp; split } <$fh>;
    }
    next if $F[1] =~ /0{40}/; # not a delta
    next unless defined $commit{$F[0]}; # not in index
    print $commit{$F[0]} eq $commit{$F[1]} ? "inner" : "outer", " ", $_;
  '

In git.git, I see 460 "inner" deltas, and 193,081 "outer" ones. The inner ones are mostly small single-file test vectors, which makes sense. It's possible to have a merge result that does conflict resolution in two such files (that would then delta), but it seems like a fairly unlikely case. Numbers for linux.git are similar.

So it might just not be a big issue at all for this use case.

I was going to suggest the same thing. ;) Unfortunately it's a bit tricky to do as we have no room in the file format for an optional flag. You'd have to add a ".mediocre-delta" file or something.

But here's another approach. I recall discussing a while back the idea that we should not necessarily trust the quality of deltas in packs that are pushed (and I think Thomas Gummerer even did some experiments inside GitHub with those, though I don't remember the results). And one way around that is during geometric repacking to consider the biggest/oldest pack as "preferred", reuse its deltas, but always compute from scratch with the others (neither reusing on-disk deltas, nor skipping try_delta() when two objects come from the same pack).

That same strategy would work here (and for incremental fast-import packs, though of course not if your fast-import pack is the "big" one after you do a from-scratch import).

This is a bit of a devil's advocate question, but: would it make sense to implement this as a general of Git's object-writing code, and not tie it to a specific command? That is, what if a user could do:

  git --write-to-pack merge ...

but also:

  git --write-to-pack add ...

and the object-writing code would just write to a pack instead of writing loose objects. That lets the caller decide when it is or is not a good idea to use this mode. And if making loose objects gives bad performance for merges, wouldn't the same be true of other operations which generate many objects?

Possibly it exacerbates the "no deltas" issue from above (though it would depend on the command). The bigger question to me is one of checkpointing. When do we finish off the pack with a .idx and make it available to other readers? We could do it at program exit, but I suspect there are some commands that really want to make objects available sooner (e.g., as soon as "git add" writes an index, we'd want those objects to already be available). Probably every program that writes objects would need to be annotated with a checkpoint call (which would be a noop in loose object mode).

So maybe it's a dumb direction. I dunno.

-Peff