Re: [PATCH 00/10] RFC Partial Clone and Fetch

From: Jonathan Nieder <jrnieder@gmail.com>
Date: May 3, 2017, 21:08 UTC
Message-ID: <20170503210850.GG28740@aiede.svl.corp.google.com>
In-Reply-To: <2b1b504a-07c9-81b3-fed2-e9c029a5b284@google.com>

Hi,

Jonathan Tan wrote:

Show 5 quoted lines

> The binary search to lookup a packfile offset from a .idx file
> (which involves disk reads) would take longer for all lookups (not
> just lookups for missing blobs) - I think I prefer keeping the lists
> separate, to avoid pessimizing the (likely) usual case where the
> relevant blobs are all already in local repo storage.

Another relevant operation is looking up objects by offset or index_nr. The current implementation involves building an in-memory reverse index on demand by reading the idx file and sorting it by offset --- see pack-revindex.c::create_pack_revindex. This takes O(n log n) time where n is the size of the idx file.

That said, it could be avoided by storing an on-disk reverse index with the pack. That's something we've been wanting to do anyway.

Thanks, Jonathan