# [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} 8 messages from 2013-05-30 to 2013-05-31. Participants: Thomas Rast, Jeff King, Duy Nguyen, Ramkumar Ramachandra. Thread: https://gitlist.dev/t/33994 ## Thomas Rast, 2013-05-30 20:00 Subject: [PATCH 1/2] sha1_file: silence sha1_loose_object_info Message-ID: <2d926e4dbd218b2305f50652c00a5c1d87e81208.1369943791.git.trast@inf.ethz.ch> URL: https://gitlist.dev/e/2d926e4dbd218b2305f50652c00a5c1d87e81208.1369943791.git.trast%40inf.ethz.ch In-Reply-To: <87bo7sbeoc.fsf@linux-k42r.v.cablecom.net> ``` sha1_object_info() returns -1 (OBJ_BAD) if it cannot find the object for some reason, which suggests that it wants the _caller_ to report this error. However, part of its work happens in sha1_loose_object_info, which _does_ report errors itself. This is doubly strange because: * packed_object_info(), which is the other half of the duo, does _not_ report this. * In the event that an object is packed and pruned while sha1_object_info_extended() goes looking for it, we would erroneously show the error -- even though the code of the latter function purports to handle this case gracefully. * A caller might invoke sha1_object_info() to find the type of an object even if that object is not known to exist. Silence this error. The others remain untouched as a corrupt object is a much more grave error than it merely being absent. Signed-off-by: Thomas Rast --- sha1_file.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sha1_file.c b/sha1_file.c index 67e815b..c0f6a0e 100644 --- a/sha1_file.c +++ b/sha1_file.c @@ -2348,7 +2348,7 @@ static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *size map = map_sha1_file(sha1, &mapsize); if (!map) - return error("unable to find %s", sha1_to_hex(sha1)); + return -1; if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0) status = error("unable to unpack %s header", sha1_to_hex(sha1)); -- 1.8.3.506.g4fdeee5 ``` ## Thomas Rast, 2013-05-30 20:00 Subject: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: <5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch> URL: https://gitlist.dev/e/5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast%40inf.ethz.ch In-Reply-To: <2d926e4dbd218b2305f50652c00a5c1d87e81208.1369943791.git.trast@inf.ethz.ch> ``` lookup_commit_reference_gently unconditionally parses the object given to it. This slows down git-describe a lot if you have a repository with large tagged blobs in it: parse_object() will read the entire blob and verify that its sha1 matches, only to then throw it away. Speed it up by checking the type with sha1_object_info() prior to unpacking. The reason that deref_tag() does not need the same fix is a bit subtle: parse_tag_buffer() does not fill the 'tagged' member of the tag struct if the tagged object is a blob. Reported-by: Alex Bennée Signed-off-by: Thomas Rast --- commit.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/commit.c b/commit.c index 888e02a..00e8d4a 100644 --- a/commit.c +++ b/commit.c @@ -31,8 +31,12 @@ static struct commit *check_commit(struct object *obj, struct commit *lookup_commit_reference_gently(const unsigned char *sha1, int quiet) { - struct object *obj = deref_tag(parse_object(sha1), NULL, 0); - + struct object *obj; + int type = sha1_object_info(sha1, NULL); + /* If it's neither tag nor commit, parsing the object is wasted effort */ + if (type != OBJ_TAG && type != OBJ_COMMIT) + return NULL; + obj = deref_tag(parse_object(sha1), NULL, 0); if (!obj) return NULL; return check_commit(obj, sha1, quiet); -- 1.8.3.506.g4fdeee5 ``` ## Jeff King, 2013-05-30 21:22 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: <20130530212223.GA2135@sigill.intra.peff.net> URL: https://gitlist.dev/e/20130530212223.GA2135%40sigill.intra.peff.net In-Reply-To: <5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch> ``` On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote: > lookup_commit_reference_gently unconditionally parses the object given > to it. This slows down git-describe a lot if you have a repository > with large tagged blobs in it: parse_object() will read the entire > blob and verify that its sha1 matches, only to then throw it away. > > Speed it up by checking the type with sha1_object_info() prior to > unpacking. This would speed up the case where we do not end up looking at the object at all, but it will slow down the (presumably common) case where we will in fact find a commit and end up parsing the object anyway. Have you measured the impact of this on normal operations? During a traversal, we spend a measurable amount of time looking up commits in packfiles, and this would presumably double it. This is not the first time I have seen this tradeoff in git. It would be nice if our object access was structured to do incremental examination of the objects (i.e., store the packfile index lookup or partial unpack of a loose object header, and then use that to complete the next step of actually getting the contents). -Peff ``` ## Duy Nguyen, 2013-05-31 00:52 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: URL: https://gitlist.dev/e/CACsJy8BDM%3D1xfZLvLs-G-0xnneaOAvzZOOXjdTZEtsT9PEvHeg%40mail.gmail.com In-Reply-To: <20130530212223.GA2135@sigill.intra.peff.net> ``` On Fri, May 31, 2013 at 4:22 AM, Jeff King wrote: > On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote: > >> lookup_commit_reference_gently unconditionally parses the object given >> to it. This slows down git-describe a lot if you have a repository >> with large tagged blobs in it: parse_object() will read the entire >> blob and verify that its sha1 matches, only to then throw it away. >> >> Speed it up by checking the type with sha1_object_info() prior to >> unpacking. > > This would speed up the case where we do not end up looking at the > object at all, but it will slow down the (presumably common) case where > we will in fact find a commit and end up parsing the object anyway. Perhaps turn "quiet" into a bitmap and only let git-describe do this? -- Duy ``` ## Ramkumar Ramachandra, 2013-05-31 06:43 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: URL: https://gitlist.dev/e/CALkWK0nL4hPio74Hm%2BctObNNFg9%2B%3D9brKXFK2ymGB%3DsPTAk1Hg%40mail.gmail.com In-Reply-To: <5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch> ``` Thomas Rast wrote: > diff --git a/commit.c b/commit.c > index 888e02a..00e8d4a 100644 > --- a/commit.c > +++ b/commit.c > @@ -31,8 +31,12 @@ static struct commit *check_commit(struct object *obj, > struct commit *lookup_commit_reference_gently(const unsigned char *sha1, > int quiet) > { > - struct object *obj = deref_tag(parse_object(sha1), NULL, 0); > - > + struct object *obj; > + int type = sha1_object_info(sha1, NULL); > + /* If it's neither tag nor commit, parsing the object is wasted effort */ > + if (type != OBJ_TAG && type != OBJ_COMMIT) > + return NULL; > + obj = deref_tag(parse_object(sha1), NULL, 0); > if (!obj) > return NULL; > return check_commit(obj, sha1, quiet); As Jeff points out, you've introduced an extra sha1_object_info() call in the common case of tag (which derefs into a commit anyway) and commit slowing things down. So, my main doubt centres around how sha1_object_info() determines the type of the object without actually parsing it. You have to open up the file and look at the fields near the top, no? (or fallback to blob failing that). I am reading it: 1. It calls sha1_loose_object_info() or sha1_packed_object_info(), depending on whether the particular file is in-pack or not. Lets see what is common between them. 2. The loose counterpart seems to call unpack_sha1_header() after mmap'ing the file. This ultimately ends up calling unpack_object_header_buffer(), which is also what the packed counterpart calls. 3. I didn't understand what unpack_object_header_buffer() is doing. And'ing with some magic 0x80 and shifting by 4 bits iteratively? type = (c >> 4) & 7? In contrast, parse_object() first calls lookup_object() to look it up in some hashtable to get the type -- the packfile idx, presumably? Why don't you also do that instead of sha1_object_info()? Or, why don't you wrap parse_object() in an API that doesn't go beyond the first blob check (and not execute parse_object_buffer())? Also, does this patch fix the bug Alex reported? Apologies if I've misunderstood something horribly (which does seem to be the case). Thanks. ``` ## Thomas Rast, 2013-05-31 08:08 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: <87sj138tcp.fsf@linux-k42r.v.cablecom.net> URL: https://gitlist.dev/e/87sj138tcp.fsf%40linux-k42r.v.cablecom.net In-Reply-To: <20130530212223.GA2135@sigill.intra.peff.net> ``` Jeff King writes: > On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote: > >> lookup_commit_reference_gently unconditionally parses the object given >> to it. This slows down git-describe a lot if you have a repository >> with large tagged blobs in it: parse_object() will read the entire >> blob and verify that its sha1 matches, only to then throw it away. >> >> Speed it up by checking the type with sha1_object_info() prior to >> unpacking. > > This would speed up the case where we do not end up looking at the > object at all, but it will slow down the (presumably common) case where > we will in fact find a commit and end up parsing the object anyway. > > Have you measured the impact of this on normal operations? During a > traversal, we spend a measurable amount of time looking up commits in > packfiles, and this would presumably double it. I don't think so, but admittedly I didn't measure it. The reason why it's unlikely is that this is specific to lookup_commit_reference_gently, which according to some grepping is usually done on refs or values that refs might have; e.g. on the old&new sides of a fetch in remote.c, or in many places in the callback of some variant of for_each_ref. Of course if you have a ridiculously large number of refs (and I gather _you_ do), this will hurt somewhat in the usual case, but speed up the case where there is a ref (usually a lightweight tag) directly pointing at a large blob. I'm not sure this can be fixed without the change you outline here: > This is not the first time I have seen this tradeoff in git. It would > be nice if our object access was structured to do incremental > examination of the objects (i.e., store the packfile index lookup or > partial unpack of a loose object header, and then use that to complete > the next step of actually getting the contents). But in any case I see the point, I should try and gather some performance numbers. -- Thomas Rast trast@{inf,student}.ethz.ch ``` ## Thomas Rast, 2013-05-31 08:16 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: <87fvx37edv.fsf@linux-k42r.v.cablecom.net> URL: https://gitlist.dev/e/87fvx37edv.fsf%40linux-k42r.v.cablecom.net In-Reply-To: ``` Ramkumar Ramachandra writes: > Thomas Rast wrote: >> + struct object *obj; >> + int type = sha1_object_info(sha1, NULL); >> + /* If it's neither tag nor commit, parsing the object is wasted effort */ >> + if (type != OBJ_TAG && type != OBJ_COMMIT) >> + return NULL; >> + obj = deref_tag(parse_object(sha1), NULL, 0); [...] > In contrast, parse_object() first calls lookup_object() to look it up > in some hashtable to get the type -- the packfile idx, presumably? > Why don't you also do that instead of sha1_object_info()? Or, why > don't you wrap parse_object() in an API that doesn't go beyond the > first blob check (and not execute parse_object_buffer())? > > Also, does this patch fix the bug Alex reported? > > Apologies if I've misunderstood something horribly (which does seem to > be the case). Yes, it does fix the bug. (It's not really buggy, just slow.) However, you implicitly point out an important point: If we have the object, and it was already parsed (obj->parsed is set), parse_object() is essentially free. But sha1_object_info is not, it will in particular unconditionally dig through long delta chains to discover the base type of an object that has already been unpacked. As for your original questions: lookup_object() is "do we have it in our big object hashtable?" -- the one that holds many[1] objects, that Peff recently sped up. sha1_object_info() and read_object() are in many ways parallel functions that do approximately the following: check all pack indexes for this object if we found a hit: attempt to unpack by recursively going through deltas (for _info, no need to unpack, but we still go through the delta chain because the type of object is determined by the innermost delta base) try to load it as a loose object it could have been repacked and pruned while we were looking, so: reload pack index information try the packs again (search indexes, then unpack) complain [1] blobs in particular are frequently not stored in that hash table, because it is an insert-only table -- Thomas Rast trast@{inf,student}.ethz.ch ``` ## Jeff King, 2013-05-31 16:00 Subject: Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit} Message-ID: <20130531160020.GA1365@sigill.intra.peff.net> URL: https://gitlist.dev/e/20130531160020.GA1365%40sigill.intra.peff.net In-Reply-To: <87sj138tcp.fsf@linux-k42r.v.cablecom.net> ``` On Fri, May 31, 2013 at 10:08:06AM +0200, Thomas Rast wrote: > > Have you measured the impact of this on normal operations? During a > > traversal, we spend a measurable amount of time looking up commits in > > packfiles, and this would presumably double it. > > I don't think so, but admittedly I didn't measure it. > > The reason why it's unlikely is that this is specific to > lookup_commit_reference_gently, which according to some grepping is > usually done on refs or values that refs might have; e.g. on the old&new > sides of a fetch in remote.c, or in many places in the callback of some > variant of for_each_ref. Yeah, I saw that the "_gently" form backs some of the other forms (non-gently, lookup_commit_or_die) and was worried that we would use it as part of the revision traversal to find parents. But we don't, of course; we use lookup_commit, because we would not accept a parent that is a tag pointing to a commit. So I think it probably won't matter in any sane case. > Of course if you have a ridiculously large number of refs (and I gather > _you_ do), this will hurt somewhat in the usual case, but speed up the > case where there is a ref (usually a lightweight tag) directly pointing > at a large blob. In my large-ref cases, there are often a lot of duplicate refs anyway (e.g., many forks of a project having the same tags). So usually the right thing there is to use lookup_object to see if we have the object already anyway. parse_object has this optimization, but we can add it into sha1_object_info, too, if it turns out to be a problem. -Peff ```