Re: O(#haves*...) behaviour in "have <sha>" processing in upload-pack

From: Thomas Rast <trast@student.ethz.ch>
Date: Sep 13, 2008, 12:18 UTC
Message-ID: <200809131418.48637.trast@student.ethz.ch>
In-Reply-To: <200809130211.14091.trast@student.ethz.ch>

I wrote:

Show 5 quoted lines

> * Isn't this ok_to_give_up() test moot?  If H is not in our object
>   store, it cannot be of any use in the transfer (of our history to
>   the client).  So if we are going to fake an ACK to stop the client
>   digging on this side of his history, we might as well send it right
>   away.

Never mind this part, it's wrong:

Let B=$(merge-base H W). Suppose H is unknown to the server, but B is known. Then sending a fake ACK as a reply to H will cause

* the client to believe we have everything reachable from H, including
  B, and cease sending any history reachable from H; and thus

* the server to believe that the client does not have B, since it did
  not list this commit in a "have" line.

Sorry for the noise.

- Thomas

-- 
Thomas Rast
trast@student.ethz.ch