libgit2/libgit2 — pull request #1424 by phkelley (2013-03-19 19:19:40+00:00)
Title: Reduce the number of unnecessary objects in pushed packs

Right now if you have 100 files in your working copy and edit just 1 of them in a commit, then push that commit, all 100 files are sent up as part of the pushed packfile.

A naive algorithm would fix this by saying, "For each object enqueued in the packbuilder, check to see if it's reachable from one of the remote's refs. If so, then the remote already has it, so we don't need to send it." This brute force approach is expensive but it covers the case where a blob with OID `1234abcd` existed early in the history of the remote repository and was deleted, but is now being added again in a commit being pushed. The object would be identified as unnecessary and the packfile would not include it.

@ethomson and I decided to try a faster approach which is less accurate. I have no idea if this is what core Git does. The proposed algorithm is:
1. If a commit has no parents, then include its tree and everything it points to, recursively.
2. If a commit has parents, then diff the commit's tree with the tree of each parent. Only the differences are enqueued in the packbuilder.

This takes advantage of the fact that the packbuilder's queue is hash table, so you can add the same OID over and over again. The tree-differ is also smart enough not to recurse into subtrees that have the same OID.

I feel safe saying is that the algorithm proposed here isn't absolutely terrible. But I would not be surprised at all if someone out there has a better strategy -- either in terms of runtime or in terms of what scenarios it covers. For example, this strategy doesn't cover the scenario when you move a blob from one place in your repository to another (a rename without a content change).