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

> 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 <trast@student.ethz.ch>
> 
> ---
> 
> This is a simple resend of v2, in the hope of attracting some
> discussion or at least encouraging words this time around.