{"thread":{"id":"33994","subject":"[PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","startedAt":"2013-05-30T20:00:22Z","lastAt":"2013-05-31T16:00:20Z","messageCount":8,"participants":["Thomas Rast","Jeff King","Duy Nguyen","Ramkumar Ramachandra"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"219044","messageId":"2d926e4dbd218b2305f50652c00a5c1d87e81208.1369943791.git.trast@inf.ethz.ch","threadId":"33994","inReplyTo":"87bo7sbeoc.fsf@linux-k42r.v.cablecom.net","subject":"[PATCH 1/2] sha1_file: silence sha1_loose_object_info","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-05-30T20:00:22Z","receivedAt":"2013-05-30T20:00:22Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"sha1_object_info() returns -1 (OBJ_BAD) if it cannot find the object\nfor some reason, which suggests that it wants the _caller_ to report\nthis error. However, part of its work happens in\nsha1_loose_object_info, which _does_ report errors itself. This is\ndoubly strange because:\n\n* packed_object_info(), which is the other half of the duo, does _not_\n report this.\n\n* In the event that an object is packed and pruned while\n sha1_object_info_extended() goes looking for it, we would\n erroneously show the error -- even though the code of the latter\n function purports to handle this case gracefully.\n\n* A caller might invoke sha1_object_info() to find the type of an\n object even if that object is not known to exist.\n\nSilence this error. The others remain untouched as a corrupt object\nis a much more grave error than it merely being absent.\n\nSigned-off-by: Thomas Rast \n---\n sha1_file.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 67e815b..c0f6a0e 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2348,7 +2348,7 @@ static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *size\n \n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (!map)\n-\t\treturn error(\"unable to find %s\", sha1_to_hex(sha1));\n+\t\treturn -1;\n \tif (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)\n \t\tstatus = error(\"unable to unpack %s header\",\n \t\t\t sha1_to_hex(sha1));\n-- \n1.8.3.506.g4fdeee5\n"},{"id":"219043","messageId":"5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch","threadId":"33994","inReplyTo":"2d926e4dbd218b2305f50652c00a5c1d87e81208.1369943791.git.trast@inf.ethz.ch","subject":"[PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-05-30T20:00:23Z","receivedAt":"2013-05-30T20:00:23Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"lookup_commit_reference_gently unconditionally parses the object given\nto it. This slows down git-describe a lot if you have a repository\nwith large tagged blobs in it: parse_object() will read the entire\nblob and verify that its sha1 matches, only to then throw it away.\n\nSpeed it up by checking the type with sha1_object_info() prior to\nunpacking.\n\nThe reason that deref_tag() does not need the same fix is a bit\nsubtle: parse_tag_buffer() does not fill the 'tagged' member of the\ntag struct if the tagged object is a blob.\n\nReported-by: Alex Bennée \nSigned-off-by: Thomas Rast \n---\n commit.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 888e02a..00e8d4a 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -31,8 +31,12 @@ static struct commit *check_commit(struct object *obj,\n struct commit *lookup_commit_reference_gently(const unsigned char *sha1,\n \t\t\t\t\t int quiet)\n {\n-\tstruct object *obj = deref_tag(parse_object(sha1), NULL, 0);\n-\n+\tstruct object *obj;\n+\tint type = sha1_object_info(sha1, NULL);\n+\t/* If it's neither tag nor commit, parsing the object is wasted effort */\n+\tif (type != OBJ_TAG && type != OBJ_COMMIT)\n+\t\treturn NULL;\n+\tobj = deref_tag(parse_object(sha1), NULL, 0);\n \tif (!obj)\n \t\treturn NULL;\n \treturn check_commit(obj, sha1, quiet);\n-- \n1.8.3.506.g4fdeee5\n"},{"id":"219046","messageId":"20130530212223.GA2135@sigill.intra.peff.net","threadId":"33994","inReplyTo":"5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-30T21:22:23Z","receivedAt":"2013-05-30T21:22:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote:\n\n> lookup_commit_reference_gently unconditionally parses the object given\n> to it. This slows down git-describe a lot if you have a repository\n> with large tagged blobs in it: parse_object() will read the entire\n> blob and verify that its sha1 matches, only to then throw it away.\n> \n> Speed it up by checking the type with sha1_object_info() prior to\n> unpacking.\n\nThis would speed up the case where we do not end up looking at the\nobject at all, but it will slow down the (presumably common) case where\nwe will in fact find a commit and end up parsing the object anyway.\n\nHave you measured the impact of this on normal operations? During a\ntraversal, we spend a measurable amount of time looking up commits in\npackfiles, and this would presumably double it.\n\nThis is not the first time I have seen this tradeoff in git. It would\nbe nice if our object access was structured to do incremental\nexamination of the objects (i.e., store the packfile index lookup or\npartial unpack of a loose object header, and then use that to complete\nthe next step of actually getting the contents).\n\n-Peff\n"},{"id":"219050","messageId":"CACsJy8BDM=1xfZLvLs-G-0xnneaOAvzZOOXjdTZEtsT9PEvHeg@mail.gmail.com","threadId":"33994","inReplyTo":"20130530212223.GA2135@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-05-31T00:52:09Z","receivedAt":"2013-05-31T00:52:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 31, 2013 at 4:22 AM, Jeff King wrote:\n> On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote:\n>\n>> lookup_commit_reference_gently unconditionally parses the object given\n>> to it. This slows down git-describe a lot if you have a repository\n>> with large tagged blobs in it: parse_object() will read the entire\n>> blob and verify that its sha1 matches, only to then throw it away.\n>>\n>> Speed it up by checking the type with sha1_object_info() prior to\n>> unpacking.\n>\n> This would speed up the case where we do not end up looking at the\n> object at all, but it will slow down the (presumably common) case where\n> we will in fact find a commit and end up parsing the object anyway.\n\nPerhaps turn \"quiet\" into a bitmap and only let git-describe do this?\n--\nDuy\n"},{"id":"219058","messageId":"CALkWK0nL4hPio74Hm+ctObNNFg9+=9brKXFK2ymGB=sPTAk1Hg@mail.gmail.com","threadId":"33994","inReplyTo":"5cc40825d5b4fb3382e4c054c49adf5e6b6fe110.1369943791.git.trast@inf.ethz.ch","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-05-31T06:43:00Z","receivedAt":"2013-05-31T06:43:00Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Thomas Rast wrote:\n> diff --git a/commit.c b/commit.c\n> index 888e02a..00e8d4a 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -31,8 +31,12 @@ static struct commit *check_commit(struct object *obj,\n> struct commit *lookup_commit_reference_gently(const unsigned char *sha1,\n> int quiet)\n> {\n> - struct object *obj = deref_tag(parse_object(sha1), NULL, 0);\n> -\n> + struct object *obj;\n> + int type = sha1_object_info(sha1, NULL);\n> + /* If it's neither tag nor commit, parsing the object is wasted effort */\n> + if (type != OBJ_TAG && type != OBJ_COMMIT)\n> + return NULL;\n> + obj = deref_tag(parse_object(sha1), NULL, 0);\n> if (!obj)\n> return NULL;\n> return check_commit(obj, sha1, quiet);\n\nAs Jeff points out, you've introduced an extra sha1_object_info() call\nin the common case of tag (which derefs into a commit anyway) and\ncommit slowing things down.\n\nSo, my main doubt centres around how sha1_object_info() determines the\ntype of the object without actually parsing it. You have to open up\nthe file and look at the fields near the top, no? (or fallback to blob\nfailing that). I am reading it:\n\n1. It calls sha1_loose_object_info() or sha1_packed_object_info(),\ndepending on whether the particular file is in-pack or not. Lets see\nwhat is common between them.\n\n2. The loose counterpart seems to call unpack_sha1_header() after\nmmap'ing the file. This ultimately ends up calling\nunpack_object_header_buffer(), which is also what the packed\ncounterpart calls.\n\n3. I didn't understand what unpack_object_header_buffer() is doing.\nAnd'ing with some magic 0x80 and shifting by 4 bits iteratively? type\n= (c >> 4) & 7?\n\nIn contrast, parse_object() first calls lookup_object() to look it up\nin some hashtable to get the type -- the packfile idx, presumably?\nWhy don't you also do that instead of sha1_object_info()? Or, why\ndon't you wrap parse_object() in an API that doesn't go beyond the\nfirst blob check (and not execute parse_object_buffer())?\n\nAlso, does this patch fix the bug Alex reported?\n\nApologies if I've misunderstood something horribly (which does seem to\nbe the case).\n\nThanks.\n"},{"id":"219082","messageId":"87sj138tcp.fsf@linux-k42r.v.cablecom.net","threadId":"33994","inReplyTo":"20130530212223.GA2135@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-05-31T08:08:06Z","receivedAt":"2013-05-31T08:08:06Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote:\n>\n>> lookup_commit_reference_gently unconditionally parses the object given\n>> to it. This slows down git-describe a lot if you have a repository\n>> with large tagged blobs in it: parse_object() will read the entire\n>> blob and verify that its sha1 matches, only to then throw it away.\n>> \n>> Speed it up by checking the type with sha1_object_info() prior to\n>> unpacking.\n>\n> This would speed up the case where we do not end up looking at the\n> object at all, but it will slow down the (presumably common) case where\n> we will in fact find a commit and end up parsing the object anyway.\n>\n> Have you measured the impact of this on normal operations? During a\n> traversal, we spend a measurable amount of time looking up commits in\n> packfiles, and this would presumably double it.\n\nI don't think so, but admittedly I didn't measure it.\n\nThe reason why it's unlikely is that this is specific to\nlookup_commit_reference_gently, which according to some grepping is\nusually done on refs or values that refs might have; e.g. on the old&new\nsides of a fetch in remote.c, or in many places in the callback of some\nvariant of for_each_ref.\n\nOf course if you have a ridiculously large number of refs (and I gather\n_you_ do), this will hurt somewhat in the usual case, but speed up the\ncase where there is a ref (usually a lightweight tag) directly pointing\nat a large blob.\n\nI'm not sure this can be fixed without the change you outline here:\n\n> This is not the first time I have seen this tradeoff in git. It would\n> be nice if our object access was structured to do incremental\n> examination of the objects (i.e., store the packfile index lookup or\n> partial unpack of a loose object header, and then use that to complete\n> the next step of actually getting the contents).\n\nBut in any case I see the point, I should try and gather some\nperformance numbers.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"219085","messageId":"87fvx37edv.fsf@linux-k42r.v.cablecom.net","threadId":"33994","inReplyTo":"CALkWK0nL4hPio74Hm+ctObNNFg9+=9brKXFK2ymGB=sPTAk1Hg@mail.gmail.com","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-05-31T08:16:44Z","receivedAt":"2013-05-31T08:16:44Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Ramkumar Ramachandra writes:\n\n> Thomas Rast wrote:\n>> + struct object *obj;\n>> + int type = sha1_object_info(sha1, NULL);\n>> + /* If it's neither tag nor commit, parsing the object is wasted effort */\n>> + if (type != OBJ_TAG && type != OBJ_COMMIT)\n>> + return NULL;\n>> + obj = deref_tag(parse_object(sha1), NULL, 0);\n[...]\n> In contrast, parse_object() first calls lookup_object() to look it up\n> in some hashtable to get the type -- the packfile idx, presumably?\n> Why don't you also do that instead of sha1_object_info()? Or, why\n> don't you wrap parse_object() in an API that doesn't go beyond the\n> first blob check (and not execute parse_object_buffer())?\n>\n> Also, does this patch fix the bug Alex reported?\n>\n> Apologies if I've misunderstood something horribly (which does seem to\n> be the case).\n\nYes, it does fix the bug. (It's not really buggy, just slow.)\n\nHowever, you implicitly point out an important point: If we have the\nobject, and it was already parsed (obj->parsed is set), parse_object()\nis essentially free. But sha1_object_info is not, it will in particular\nunconditionally dig through long delta chains to discover the base type\nof an object that has already been unpacked.\n\n\nAs for your original questions: lookup_object() is \"do we have it in our\nbig object hashtable?\" -- the one that holds many[1] objects, that Peff\nrecently sped up.\n\nsha1_object_info() and read_object() are in many ways parallel functions\nthat do approximately the following:\n\n check all pack indexes for this object\n if we found a hit:\n attempt to unpack by recursively going through deltas\n (for _info, no need to unpack, but we still go through the delta\n chain because the type of object is determined by the innermost\n delta base)\n try to load it as a loose object\n it could have been repacked and pruned while we were looking, so:\n reload pack index information\n try the packs again (search indexes, then unpack)\n complain\n\n\n[1] blobs in particular are frequently not stored in that hash table,\nbecause it is an insert-only table\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"219103","messageId":"20130531160020.GA1365@sigill.intra.peff.net","threadId":"33994","inReplyTo":"87sj138tcp.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH 2/2] lookup_commit_reference_gently: do not read non-{tag,commit}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-31T16:00:20Z","receivedAt":"2013-05-31T16:00:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 31, 2013 at 10:08:06AM +0200, Thomas Rast wrote:\n\n> > Have you measured the impact of this on normal operations? During a\n> > traversal, we spend a measurable amount of time looking up commits in\n> > packfiles, and this would presumably double it.\n> \n> I don't think so, but admittedly I didn't measure it.\n> \n> The reason why it's unlikely is that this is specific to\n> lookup_commit_reference_gently, which according to some grepping is\n> usually done on refs or values that refs might have; e.g. on the old&new\n> sides of a fetch in remote.c, or in many places in the callback of some\n> variant of for_each_ref.\n\nYeah, I saw that the \"_gently\" form backs some of the other forms\n(non-gently, lookup_commit_or_die) and was worried that we would use it\nas part of the revision traversal to find parents. But we don't, of\ncourse; we use lookup_commit, because we would not accept a parent that\nis a tag pointing to a commit.\n\nSo I think it probably won't matter in any sane case.\n\n> Of course if you have a ridiculously large number of refs (and I gather\n> _you_ do), this will hurt somewhat in the usual case, but speed up the\n> case where there is a ref (usually a lightweight tag) directly pointing\n> at a large blob.\n\nIn my large-ref cases, there are often a lot of duplicate refs anyway\n(e.g., many forks of a project having the same tags). So usually the\nright thing there is to use lookup_object to see if we have the object\nalready anyway. parse_object has this optimization, but we can add it\ninto sha1_object_info, too, if it turns out to be a problem.\n\n-Peff\n"}]}