Re: [RFC PATCH v2] fetch-pack: log(n)-transmission find_common()

On Thu, 23 Oct 2008, Thomas Rast wrote:

Replaces the existing simple history search with a more sophisticated
algorithm:

1) Walk history with exponentially increasing stride lengths; i.e.,
   send the 1st commit, then the 2nd after that, then the 4th after
   that, and so on.

2) Bisect the resulting intervals.

Combined with tracking the "outstanding haves" so that we can detect
which sha1s were never ACKed by upload-pack (and hence not common),
this gives O(log(n)) required "have" lines.

Unfortunately this cannot work if the server sends fake ACKs, so we
introduce a capability 'exp-stride' which instructs upload-pack to
disable ok_to_give_up().  (Which incidentally saves the server a lot
of work.)

Signed-off-by: Thomas Rast <redacted>

---

This is a simple resend of v2, in the hope of attracting some
discussion or at least encouraging words this time around.

OK, I gave this a quick try, and fetch operations appear to make their 
mind about what to do quicker.  Some fetch requests which used to take 
up to 5 seconds are somewhat faster.  I have no formal measurements 
though.


Nicolas