From: H. Peter Anvin <hpa@zytor.com>
Date: Fri, 01 Jul 2005 01:24:05 GMT
Subject: Re: "git-send-pack"
Message-ID: <42C49B35.3050204@zytor.com>
In-Reply-To: <Pine.LNX.4.58.0506301656570.14331@ppc970.osdl.org>

Linus Torvalds wrote:
> 
> On Thu, 30 Jun 2005, H. Peter Anvin wrote:
> 
>>In your linux-2.6 tree, there are currently 54,204 objects, and that is 
>>after less than one full 2.6.x kernel release cycle.  That's a megabyte 
>>of SHA1s.
> 
> 
> But that's _all_ objects. There are "only" 4040 commit objects (which are
> always the starting point for a search). 
> 

Well, there are objects that reference commit objects (e.g. tag 
objects), not the other way around, but your point is well taken.

> So streaming out the commit objects a few hundred at a time is actually 
> a very simple strategy. 
> 
> Also, note that the server is usually _more_ ahead than the client is, and 
> the server is the one that potentially has lots of commits that the 
> client doesn't have. Not the other way around. So if the client makes a 
> list of it's top commits, it almost certainly won't have to make a very 
> long list until the server can tell it "ok, stop, I've seen it".

Well, what I proposed was pretty much that except to have the client 
(receiver) start first.

I prefer calling it sender and receiver, because in the case of upload 
and download you have different sides being the "server".

> Yeah, maybe we want to limit the "burst" to 70 sha1's, since that will fit 
> in a regular-sized ethernet packet, but whatever - you'd burst out your 
> commits "latest first", so you'd never even get to the current 4040 unless 
> you've literally done the kind of work we've done in the git tree for the 
> last 3 months _and_you've_not_pulled_from_that_server_in_the_whole_time_.

Well, in the common case (sender has a superset of receiver), what I 
proposed would converge on the first iteration.  I'm not even convinced 
that the algorithm *ever* needs to iterate.

	-hpa