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. -Peff -- 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