Re: [PATCH v2] add test to demonstrate that shallow recursive clones fail

[Duy Nguyen <pclouds@gmail.com>]

On Tue, Nov 17, 2015 at 10:43 PM, Jeff King <peff@peff.net> wrote:
> On Tue, Nov 17, 2015 at 09:17:43PM +0100, Duy Nguyen wrote:
>
>> On Mon, Nov 16, 2015 at 8:25 PM, Stefan Beller <sbeller@google.com> wrote:
>> > Instead of having to search all branches for the requested sha1, we could have
>> > some sort of data structure to make it not an O(n) operation (n being
>> > all objects
>> > in the repo).
>> >
>> > Maybe I overestimate the work which needs to be done, because the server has
>> > bitmaps nowadays.
>>
>> Quote from [1]
>>
>> > If we take the kernel history in rev-list and pick two commits that
>> > are roughly ~10,000 commits apart from one another, JGit can compute
>> > the rev-list --objects between these two commits in about 120
>> > milliseconds (git-core should be faster, or at least comparable).
>>
>> I think we should be fine (note that --objects is a lot heavier than
>> commit walking). Though.. I just tried it on git.git. 10k commits
>> (without --objects) take about 200ms with C Git..
>
> A lot of this depends on the endpoints. We can't store bitmaps for every
> commit, so we often have to fall back to traversing from the commit,
> collecting reachable objects until we hit a commit that does have
> bitmaps.
>
> I think the for the purposes of upload-pack and reachability, it might
> be fine to just walk commits, which as you note is much cheaper. The C
> git bitmap code does not currently have a way to say "I only care about
> commits, do not bother filling in the trees and blobs when you have to
> do a fallback traversal". But it would not be hard to add, I think.

Yeah I think that was the 10k commits in Shawn's mail: the number of
commits we may have to walk until we hit a reachability bitmap. It
looks like C Git will create a bitmap every 5k commits, not 10k,
though, if I read the code correctly. The point is reachability test
with the presence of pack bitmaps is not O(n) anymore. Which is
probably good enough for now.
-- 
Duy