Re: [RFC] log(n)-transmissions common commit handshake

From: Thomas Rast <trast@student.ethz.ch>
Date: Sep 18, 2008, 08:18 UTC
Message-ID: <200809181018.52811.trast@student.ethz.ch>
In-Reply-To: <200809180100.32626.trast@student.ethz.ch>

I wrote:

Show 10 quoted lines

> * Impact/clever use of refs
> 
>   For some reason, current git sends all refs to the server, even if
>   the server should already know about lots of them.  For example, in
>   git.git, emitting v1.6.0.2 covers almost all tags in the repository
>   by simple ancestor scanning.
> 
>   Is there a reason for this behaviour?  Otherwise it would be better
>   to emit them in date order and intelligently handle commons.  (In
>   fact this does not depend on the discussed change.)

As an addendum, I think the following would be a good way to cleverly use refs to reduce work:

Cache a "reduced" DAG which just maps the ref'd commit relationships, i.e., shows the reachability of refs only. This needs to be written out to disk between invocations.

At the start of the protocol, the server announces all its refs. We can use the reduced DAG to infer the minimal set of ref heads we need to announce to have the server know all common ones. We can also mark all the other refs as "common but not announced yet", so that the backwards marking and searching routines know to stop there.

This should reduce the number of refs listed back to the server to only a handful, and at the same time, stop the client from searching backwards through _all_ history (which can take a bit of time, and is one of the weaknesses of my proposal) in most cases.

- Thomas

-- 
Thomas Rast
trast@student.ethz.ch