Re: git pack/unpack over bittorrent - works!

From: Nicolas Pitre <nico@fluxnic.net>
Date: Sep 4, 2010, 06:13 UTC
Message-ID: <alpine.LFD.2.00.1009040153280.19366@xanadu.home>
In-Reply-To: <4C81DC34.2090800@gmail.com>

On Sat, 4 Sep 2010, Artur Skawina wrote:

Show 30 quoted lines

> >> 2) Git doesn't use chained deltas. IOW given commits "A --d1-> B --d2-> C",
> >>    "C" can be represented as a delta against "A" or "B", but _not_ against "d1". 
> >>    (Think of the case where "C" reverts /part of/ "B")
> > 
> > Git does use chained deltas indeed.  But deltas are used only at the 
> > object level within a pack file.  Any blob object can be represented as 
> > a delta against any other blob in the pack, regardless of the commit(s) 
> > those blob objects belong to.  Same thing for tree objects.  So you can 
> > have deltas going in total random directions if you look them from a 
> > commit perspective.  So "C" can have some of its objects being deltas 
> > against objects from "B", or "A", or any other commit for that matter, 
> > or even objects belonging to the same commit "C". And some other objects 
> > from "B" can delta against objects from "C" too. There is simply no 
> > restrictions at all on the actual delta direction.  The only rule is 
> > that an object may only delta against another object of the same type.
> > 
> > Of course we don't try to delta each object against all the other 
> > available objects as that would be a O(n^2) operation (imagine with n = 
> > 1.7 million objects).  So we use many heuristics to make this delta 
> > packing efficient without taking an infinite amount of time.
> > 
> > For example, if we have objects X and Y that need to be packed together 
> > and sent to a client over the net, and we find that Y is already a delta 
> > against X in one pack that exists locally, then we simply and literally 
> > copy the delta representation of Y from that local pack file and send it 
> > out without recomputing that delta.
> 
> What i meant by 'chained deltas' is a representation that takes delta#1 and
> applies delta#2 to the first delta, and applies the result to the source of
> delta#1. Which could be a more compact representation of eg. a partial revert.

You can have deltas on top of deltas. And they can be in any direction i.e. object #1 can be a delta that only takes half of a bigger object #2, or object #2 can be a delta copying a smaller object #1 and adding more data to it. In the end both representation will take more or less the same amount of space.

> IOW, if I have commits A..Y, ask (via git pull) for commits X and Z, then I'm
> guaranteed to receive them either raw, or as a delta vs commits A..X, right?

In such case you will receive only those new objects that commits X and Z introduced, and those new objects may indeed be encoded either as whole objects, or as deltas against either objects that you already have, or even as deltas against objects that are part of the transfer.

> What I'm really asking is, if a (modified) git-upload-pack skips transferring
> commit X, and just sends me commit Z (possibly as delta vs 'X'), _and_ I 
> obtain commit 'X" in some other way, I will be able to reconstruct 'Z', correct?

Yes. Although it is 'git pack-objects' that decides what objects to send, not 'git-upload-pack'.

Nicolas