On Tue, Nov 17, 2015 at 10:43 PM, Jeff King <peff@xxxxxxxx> 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@xxxxxxxxxx> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html