{"thread":{"id":"31726","subject":"[PATCH 1/4] peel_ref: use faster deref_tag_noverify","startedAt":"2012-10-04T07:56:09Z","lastAt":"2012-10-04T21:59:33Z","messageCount":14,"participants":["Jeff King","Nazri Ramliy","Ævar Arnfjörð Bjarmason","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"200525","messageId":"20121004075609.GA1355@sigill.intra.peff.net","threadId":"31726","inReplyTo":"CACBZZX5Sm++Wjyoue-qk7TjwxUM3QihXfWGtEHhOq=VtkgvNbQ@mail.gmail.com","subject":"[PATCH 0/4] optimizing upload-pack ref peeling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T07:56:09Z","receivedAt":"2012-10-04T07:56:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 01:54:47AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > Hmm. It seems like we should not need to open the tags at all. The main\n> > reason is to produce the \"peeled\" advertisement just after it. But for a\n> > packed ref with a modern version of git that supports the \"peeled\"\n> > extension, we should already have that information.\n> \n> B.t.w. do you plan to submit this as a non-hack, I'd like to have it\n> in git.git, so if you're not going to I could pick it up and clean it\n> up a bit. But I think it would be better coming from you.\n\nHere's a cleaned-up version. I realized that peel_ref actually is quite\nclose to what we want; the key thing is that when you are calling it\nfrom a for_each_ref loop it will not only use peeled information from\npacked-refs (if available), but it will also short-circuit the ref\nlookup for non-packed refs. So it really does what we want.\n\nI put some timings into the final patch. The results are very satisfying\nfrom a pure numbers standpoint. However, I'm not 100% sure this is all\nthat useful a benchmark. The repos where you get a noticeable benefit\nare quite big, so I suspect the time to send the advertisements out over\nthe wire will dominate. Still, a CPU second saved is a CPU second\nearned.\n\nAnd the series actually ends up making the code cleaner and shares some\nof the optimizations I put into upload-pack with other users of\npeel_ref. So I think I'd be inclined to use it, even if the speedup\ndoesn't help that much in practice. We'll see what others think.\n\n  [1/4]: peel_ref: use faster deref_tag_noverify\n  [2/4]: peel_ref: do not return a null sha1\n  [3/4]: peel_ref: check object type before loading\n  [4/4]: upload-pack: use peel_ref for ref advertisements\n\n-Peff\n"},{"id":"200490","messageId":"20121004075815.GA31325@sigill.intra.peff.net","threadId":"31726","inReplyTo":"20121004075609.GA1355@sigill.intra.peff.net","subject":"[PATCH 1/4] peel_ref: use faster deref_tag_noverify","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T07:58:15Z","receivedAt":"2012-10-04T07:58:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are asked to peel a ref to a sha1, we internally call\nderef_tag, which will recursively parse each tagged object\nuntil we reach a non-tag. This has the benefit that we will\nverify our ability to load and parse the pointed-to object.\n\nHowever, there is a performance downside: we may not need to\nload that object at all (e.g., if we are listing peeled\nsimply listing peeled refs), or it may be a large object\nthat should follow a streaming code path (e.g., an annotated\ntag of a large blob).\n\nIt makes more sense for peel_ref to choose the fast thing\nrather than performing the extra check, for two reasons:\n\n  1. We will already sometimes short-circuit the tag parsing\n     in favor of a peeled entry from a packed-refs file. So\n     we are already favoring speed in some cases, and it is\n     not wise for a caller to rely on peel_ref to detect\n     corruption.\n\n  2. We already silently ignore much larger corruptions,\n     like a ref that points to a non-existent object, or a\n     tag object that exists but is corrupted.\n\n  2. peel_ref is not the right place to check for such a\n     database corruption. It is returning only the sha1\n     anyway, not the actual object. Any callers which use\n     that sha1 to load an object will soon discover the\n     corruption anyway, so we are really just pushing back\n     the discovery to later in the program.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThis is basically bringing the optimization from 90108a2 (upload-pack:\navoid parsing tag destinations, 2012-01-06) to users of peel_ref.\n\n refs.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/refs.c b/refs.c\nindex da74a2b..0a916a0 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1225,7 +1225,7 @@ fallback:\n fallback:\n \to = parse_object(base);\n \tif (o && o->type == OBJ_TAG) {\n-\t\to = deref_tag(o, refname, 0);\n+\t\to = deref_tag_noverify(o);\n \t\tif (o) {\n \t\t\thashcpy(sha1, o->sha1);\n \t\t\treturn 0;\n-- \n1.8.0.rc0.10.g8dd2a92\n"},{"id":"200508","messageId":"20121004080019.GB31325@sigill.intra.peff.net","threadId":"31726","inReplyTo":"20121004075609.GA1355@sigill.intra.peff.net","subject":"[PATCH 2/4] peel_ref: do not return a null sha1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T08:00:19Z","receivedAt":"2012-10-04T08:00:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The idea of the peel_ref function is to dereference tag\nobjects recursively until we hit a non-tag, and return the\nsha1. Conceptually, it should return 0 if it is successful\n(and fill in the sha1), or -1 if there was nothing to peel.\n\nHowever, the current behavior is much more confusing. For a\nregular loose ref, the behavior is as described above. But\nthere is an optimization to reuse the peeled-ref value for a\nref that came from a packed-refs file. If we have such a\nref, we return its peeled value, even if that peeled value\nis null (indicating that we know the ref definitely does\n_not_ peel).\n\nIt might seem like such information is useful to the caller,\nwho would then know not to bother loading and trying to peel\nthe object. Except that they should not bother loading and\ntrying to peel the object _anyway_, because that fallback is\nalready handled by peel_ref. In other words, the whole point\nof calling this function is that it handles those details\ninternally, and you either get a sha1, or you know that it\nis not peel-able.\n\nThis patch catches the null sha1 case internally and\nconverts it into a -1 return value (i.e., there is nothing\nto peel). This simplifies callers, which do not need to\nbother checking themselves.\n\nTwo callers are worth noting:\n\n  - in pack-objects, a comment indicates that there is a\n    difference between non-peelable tags and unannotated\n    tags. But that is not the case (before or after this\n    patch). Whether you get a null sha1 has to do with\n    internal details of how peel_ref operated.\n\n  - in show-ref, if peel_ref returns a failure, the caller\n    tries to decide whether to try peeling manually based on\n    whether the REF_ISPACKED flag is set. But this doesn't\n    make any sense. If the flag is set, that does not\n    necessarily mean the ref came from a packed-refs file\n    with the \"peeled\" extension. But it doesn't matter,\n    because even if it didn't, there's no point in trying to\n    peel it ourselves, as peel_ref would already have done\n    so. In other words, the fallback peeling is guaranteed\n    to fail.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nSorry for the long-winded explanation. I'd love it if somebody could\neyeball the code and make sure what I wrote above is correct. I was\nmightily confused at first by the way that some of the callers treated\nthe return value. I think it is simply a case of code growing crufty as\nfeatures were added (originally the packed-refs optimization did not\nexist, and was bolted on later), but I may have mis-read something.\n\n builtin/describe.c     |  2 +-\n builtin/pack-objects.c |  1 -\n builtin/show-ref.c     | 23 +++--------------------\n refs.c                 |  2 ++\n 4 files changed, 6 insertions(+), 22 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 9fe11ed..04c185b 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -144,7 +144,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \tif (!all && !might_be_tag)\n \t\treturn 0;\n \n-\tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n+\tif (!peel_ref(path, peeled)) {\n \t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n \t\thashcpy(peeled, sha1);\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5e14064..f069462 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2033,7 +2033,6 @@ static int add_ref_tag(const char *path, const unsigned char *sha1, int flag, vo\n \n \tif (!prefixcmp(path, \"refs/tags/\") && /* is a tag? */\n \t    !peel_ref(path, peeled)        && /* peelable? */\n-\t    !is_null_sha1(peeled)          && /* annotated tag? */\n \t    locate_object_entry(peeled))      /* object packed? */\n \t\tadd_object_entry(sha1, OBJ_TAG, NULL, 0);\n \treturn 0;\ndiff --git a/builtin/show-ref.c b/builtin/show-ref.c\nindex 4eb016d..8d9b76a 100644\n--- a/builtin/show-ref.c\n+++ b/builtin/show-ref.c\n@@ -28,7 +28,6 @@ static int show_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \n static int show_ref(const char *refname, const unsigned char *sha1, int flag, void *cbdata)\n {\n-\tstruct object *obj;\n \tconst char *hex;\n \tunsigned char peeled[20];\n \n@@ -79,25 +78,9 @@ match:\n \tif (!deref_tags)\n \t\treturn 0;\n \n-\tif ((flag & REF_ISPACKED) && !peel_ref(refname, peeled)) {\n-\t\tif (!is_null_sha1(peeled)) {\n-\t\t\thex = find_unique_abbrev(peeled, abbrev);\n-\t\t\tprintf(\"%s %s^{}\\n\", hex, refname);\n-\t\t}\n-\t}\n-\telse {\n-\t\tobj = parse_object(sha1);\n-\t\tif (!obj)\n-\t\t\tdie(\"git show-ref: bad ref %s (%s)\", refname,\n-\t\t\t    sha1_to_hex(sha1));\n-\t\tif (obj->type == OBJ_TAG) {\n-\t\t\tobj = deref_tag(obj, refname, 0);\n-\t\t\tif (!obj)\n-\t\t\t\tdie(\"git show-ref: bad tag at ref %s (%s)\", refname,\n-\t\t\t\t    sha1_to_hex(sha1));\n-\t\t\thex = find_unique_abbrev(obj->sha1, abbrev);\n-\t\t\tprintf(\"%s %s^{}\\n\", hex, refname);\n-\t\t}\n+\tif (!peel_ref(refname, peeled)) {\n+\t\thex = find_unique_abbrev(peeled, abbrev);\n+\t\tprintf(\"%s %s^{}\\n\", hex, refname);\n \t}\n \treturn 0;\n }\ndiff --git a/refs.c b/refs.c\nindex 0a916a0..f672ad9 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1202,6 +1202,8 @@ int peel_ref(const char *refname, unsigned char *sha1)\n \tif (current_ref && (current_ref->name == refname\n \t\t|| !strcmp(current_ref->name, refname))) {\n \t\tif (current_ref->flag & REF_KNOWS_PEELED) {\n+\t\t\tif (is_null_sha1(current_ref->u.value.peeled))\n+\t\t\t    return -1;\n \t\t\thashcpy(sha1, current_ref->u.value.peeled);\n \t\t\treturn 0;\n \t\t}\n-- \n1.8.0.rc0.10.g8dd2a92\n"},{"id":"200523","messageId":"20121004080253.GC31325@sigill.intra.peff.net","threadId":"31726","inReplyTo":"20121004075609.GA1355@sigill.intra.peff.net","subject":"[PATCH 3/4] peel_ref: check object type before loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T08:02:53Z","receivedAt":"2012-10-04T08:02:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The point of peel_ref is to dereference tags; if the base\nobject is not a tag, then we can return early without even\nloading the object into memory.\n\nThis patch accomplishes that by checking sha1_object_info\nfor the type. For a packed object, we can get away with just\nlooking in the pack index. For a loose object, we only need\nto inflate the first couple of header bytes.\n\nThis is a bit of a gamble; if we do find a tag object, then\nwe will end up loading the content anyway, and the extra\nlookup will have been wasteful. However, if it is not a tag\nobject, then we save loading the object entirely. Depending\non the ratio of non-tags to tags in the input, this can be a\nminor win or minor loss.\n\nHowever, it does give us one potential major win: if a ref\npoints to a large blob (e.g., via an unannotated tag), then\nwe can avoid looking at it entirely.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThis optimization is the one that gave me the most pause. While\nupload-pack does call peel_ref on everything, the other callers all\nconstrain themselves to refs/tags/. So for many projects, we will be\ncalling it mostly on annotated tags, and it may be a very small net\nloss. But in practice, it will not matter for most projects with a sane\nnumber of normal tags, and saving even one accidental giant blob load\ncan have a huge impact.\n\n refs.c | 11 +++++++++--\n 1 file changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex f672ad9..02e47b1 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1225,8 +1225,15 @@ fallback:\n \t}\n \n fallback:\n-\to = parse_object(base);\n-\tif (o && o->type == OBJ_TAG) {\n+\to = lookup_unknown_object(base);\n+\tif (o->type == OBJ_NONE) {\n+\t\tint type = sha1_object_info(base, NULL);\n+\t\tif (type < 0)\n+\t\t\treturn -1;\n+\t\to->type = type;\n+\t}\n+\n+\tif (o->type == OBJ_TAG) {\n \t\to = deref_tag_noverify(o);\n \t\tif (o) {\n \t\t\thashcpy(sha1, o->sha1);\n-- \n1.8.0.rc0.10.g8dd2a92\n"},{"id":"200501","messageId":"20121004080333.GD31325@sigill.intra.peff.net","threadId":"31726","inReplyTo":"20121004075609.GA1355@sigill.intra.peff.net","subject":"[PATCH 4/4] upload-pack: use peel_ref for ref advertisements","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T08:03:33Z","receivedAt":"2012-10-04T08:03:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When upload-pack advertises refs, we attempt to peel tags\nand advertise the peeled version. We currently hand-roll the\ntag dereferencing, and use as many optimizations as we can\nto avoid loading non-tag objects into memory.\n\nNot only has peel_ref recently learned these optimizations,\ntoo, but it also contains an even more important one: it\nhas access to the \"peeled\" data from the pack-refs file.\nThat means we can avoid not only loading annotated tags\nentirely, but also avoid doing any kind of object lookup at\nall.\n\nThis cut the CPU time to advertise refs by 50% in the\nlinux-2.6 repo, as measured by:\n\n  echo 0000 | git-upload-pack . >/dev/null\n\nbest-of-five, warm cache, objects and refs fully packed:\n\n  [before]             [after]\n  real    0m0.026s     real    0m0.013s\n  user    0m0.024s     user    0m0.008s\n  sys     0m0.000s     sys     0m0.000s\n\nThose numbers are irrelevantly small compared to an actual\nfetch. Here's a larger repo (400K refs, of which 12K are\nunique, and of which only 107 are unique annotated tags):\n\n  [before]             [after]\n  real    0m0.704s     real    0m0.596s\n  user    0m0.600s     user    0m0.496s\n  sys     0m0.096s     sys     0m0.092s\n\nThis shows only a 15% speedup (mostly because it has fewer\nactual tags to parse), but a larger absolute value (100ms,\nwhich isn't a lot compared to a real fetch, but this\nadvertisement happens on every fetch, even if the client is\njust finding out they are completely up to date).\n\nIn truly pathological cases, where you have a large number\nof unique annotated tags, it can make an even bigger\ndifference. Here are the numbers for a linux-2.6 repository\nthat has had every seventh commit tagged (so about 50K\ntags):\n\n  [before]             [after]\n  real    0m0.443s     real    0m0.097s\n  user    0m0.416s     user    0m0.080s\n  sys     0m0.024s     sys     0m0.012s\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n upload-pack.c | 14 +++-----------\n 1 file changed, 3 insertions(+), 11 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 2e90ccb..6142421 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -727,12 +727,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \t\t\" include-tag multi_ack_detailed\";\n \tstruct object *o = lookup_unknown_object(sha1);\n \tconst char *refname_nons = strip_namespace(refname);\n-\n-\tif (o->type == OBJ_NONE) {\n-\t\to->type = sha1_object_info(sha1, NULL);\n-\t\tif (o->type < 0)\n-\t\t    die(\"git upload-pack: cannot find object %s:\", sha1_to_hex(sha1));\n-\t}\n+\tunsigned char peeled[20];\n \n \tif (capabilities)\n \t\tpacket_write(1, \"%s %s%c%s%s agent=%s\\n\",\n@@ -747,11 +742,8 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n \t\to->flags |= OUR_REF;\n \t\tnr_our_refs++;\n \t}\n-\tif (o->type == OBJ_TAG) {\n-\t\to = deref_tag_noverify(o);\n-\t\tif (o)\n-\t\t\tpacket_write(1, \"%s %s^{}\\n\", sha1_to_hex(o->sha1), refname_nons);\n-\t}\n+\tif (!peel_ref(refname, peeled))\n+\t\tpacket_write(1, \"%s %s^{}\\n\", sha1_to_hex(peeled), refname_nons);\n \treturn 0;\n }\n \n-- \n1.8.0.rc0.10.g8dd2a92\n"},{"id":"200502","messageId":"20121004080438.GA31305@sigill.intra.peff.net","threadId":"31726","inReplyTo":"20121004075609.GA1355@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] optimizing upload-pack ref peeling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T08:04:38Z","receivedAt":"2012-10-04T08:04:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 03:56:09AM -0400, Jeff King wrote:\n\n>   [1/4]: peel_ref: use faster deref_tag_noverify\n>   [2/4]: peel_ref: do not return a null sha1\n>   [3/4]: peel_ref: check object type before loading\n>   [4/4]: upload-pack: use peel_ref for ref advertisements\n\nI included my own timings in the final one, but my \"pathological\" case\nat the end is a somewhat made-up attempt to emulate what you described.\nCan you double-check that this series still has a nice impact on your\nreal-world repository?\n\n-Peff\n"},{"id":"200521","messageId":"CACBZZX6hoXdP5fV8NSmkEOvm1eayyCH+vSJYSpd=ZL0XjC68HQ@mail.gmail.com","threadId":"31726","inReplyTo":"20121004080438.GA31305@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] optimizing upload-pack ref peeling","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2012-10-04T09:01:26Z","receivedAt":"2012-10-04T09:01:26Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Oct 4, 2012 at 10:04 AM, Jeff King <peff@peff.net> wrote:\n> On Thu, Oct 04, 2012 at 03:56:09AM -0400, Jeff King wrote:\n>\n>>   [1/4]: peel_ref: use faster deref_tag_noverify\n>>   [2/4]: peel_ref: do not return a null sha1\n>>   [3/4]: peel_ref: check object type before loading\n>>   [4/4]: upload-pack: use peel_ref for ref advertisements\n>\n> I included my own timings in the final one, but my \"pathological\" case\n> at the end is a somewhat made-up attempt to emulate what you described.\n> Can you double-check that this series still has a nice impact on your\n> real-world repository?\n\nIt does, here's best of five for, all compiled with -g -O3:\n\nv1.7.8:\n\n    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)\n    3.49MB 0:00:00 [ 5.3MB/s] [  <=>\n\n           ]\n\n    real    0m0.660s\n    user    0m0.604s\n    sys     0m0.248s\n\nmaster without your patches:\n\n    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)\n    3.49MB 0:00:00 [10.2MB/s] [  <=>\n\n           ]\n\n    real    0m0.344s\n    user    0m0.300s\n    sys     0m0.172s\n\nmaster with your patches:\n\n    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)\n    3.49MB 0:00:00 [31.8MB/s] [  <=>\n\n           ]\n\n    real    0m0.113s\n    user    0m0.088s\n    sys     0m0.088s\n"},{"id":"200520","messageId":"CAEY4ZpMiQn61ZD8-Gbcr8zKW=LRQZKwFb7kwVeAJ3tPrvkRbWQ@mail.gmail.com","threadId":"31726","inReplyTo":"CACBZZX6hoXdP5fV8NSmkEOvm1eayyCH+vSJYSpd=ZL0XjC68HQ@mail.gmail.com","subject":"Re: [PATCH 0/4] optimizing upload-pack ref peeling","fromName":"Nazri Ramliy","fromEmail":"ayiehere@gmail.com","sentAt":"2012-10-04T12:14:52Z","receivedAt":"2012-10-04T12:14:52Z","isPatch":true,"sender":{"key":"ayiehere@gmail.com","avatar":"https://avatars.githubusercontent.com/u/164756?v=4"},"body":"On Thu, Oct 4, 2012 at 5:01 PM, Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n>     $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)\n\nTotally off-topic, but ...\n\nThanks for making me look up what pv is. I remember checking it out\nquiet sometime\nago and have forgotten about it altogether.\n\nNow I can replace my poorly written, half-assed attempt at a shell script to do\nsomething similar to what pv is already capable of!\n\nNazri.\n"},{"id":"200562","messageId":"7vk3v6yu1g.fsf@alter.siamese.dyndns.org","threadId":"31726","inReplyTo":"20121004075815.GA31325@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] peel_ref: use faster deref_tag_noverify","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-04T18:24:43Z","receivedAt":"2012-10-04T18:24:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> When we are asked to peel a ref to a sha1, we internally call\n> deref_tag, which will recursively parse each tagged object\n> until we reach a non-tag. This has the benefit that we will\n> verify our ability to load and parse the pointed-to object.\n>\n> However, there is a performance downside: we may not need to\n> load that object at all (e.g., if we are listing peeled\n> simply listing peeled refs),...\n\nBoth correct.\n\nI checked the existing callsites and nobody seems to assume that it\ncan use the pointed-to object without checking because peel_ref has\nalready checked, so it makes sense.\n"},{"id":"200558","messageId":"7vfw5uytoy.fsf@alter.siamese.dyndns.org","threadId":"31726","inReplyTo":"20121004080019.GB31325@sigill.intra.peff.net","subject":"Re: [PATCH 2/4] peel_ref: do not return a null sha1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-04T18:32:13Z","receivedAt":"2012-10-04T18:32:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The idea of the peel_ref function is to dereference tag\n> objects recursively until we hit a non-tag, and return the\n> sha1. Conceptually, it should return 0 if it is successful\n> (and fill in the sha1), or -1 if there was nothing to peel.\n>\n> However, the current behavior is much more confusing. For a\n> regular loose ref, the behavior is as described above. But\n> there is an optimization to reuse the peeled-ref value for a\n> ref that came from a packed-refs file. If we have such a\n> ref, we return its peeled value, even if that peeled value\n> is null (indicating that we know the ref definitely does\n> _not_ peel).\n>\n> It might seem like such information is useful to the caller,\n> who would then know not to bother loading and trying to peel\n> the object. Except that they should not bother loading and\n> trying to peel the object _anyway_, because that fallback is\n> already handled by peel_ref. In other words, the whole point\n> of calling this function is that it handles those details\n> internally, and you either get a sha1, or you know that it\n> is not peel-able.\n>\n> This patch catches the null sha1 case internally and\n> converts it into a -1 return value (i.e., there is nothing\n> to peel). This simplifies callers, which do not need to\n> bother checking themselves.\n>\n> Two callers are worth noting:\n>\n>   - in pack-objects, a comment indicates that there is a\n>     difference between non-peelable tags and unannotated\n>     tags. But that is not the case (before or after this\n>     patch). Whether you get a null sha1 has to do with\n>     internal details of how peel_ref operated.\n\nYeah, this is what I was wondering while reviewing [1/4].\n\nWe traditionally said both HEAD^0 and HEAD^0^0 peel to HEAD, but\nthis at least at the internal API level redefines them to \"these do\nnot peel at all and is a failure\".  In other words, peel_ref(ref,\nsha1) that returns 0 is a way to see if ref points at a real tag\nobject, and if the function returns non-zero, the caller cannot tell\nif the failure is because it was a valid commit or a corrupt object.\n\nThe check !is_null_sha1(peeled) always looked fishy to me.  Good\nriddance.\n"},{"id":"200569","messageId":"7vbogiys47.fsf@alter.siamese.dyndns.org","threadId":"31726","inReplyTo":"20121004080253.GC31325@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] peel_ref: check object type before loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-04T19:06:16Z","receivedAt":"2012-10-04T19:06:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The point of peel_ref is to dereference tags; if the base\n> object is not a tag, then we can return early without even\n> loading the object into memory.\n>\n> This patch accomplishes that by checking sha1_object_info\n> for the type. For a packed object, we can get away with just\n> looking in the pack index. For a loose object, we only need\n> to inflate the first couple of header bytes.\n\nWe look at the pack index and have to follow its delta chain down to\nthe base to find its type; if the object is deeply deltified, this\ncertainly is an overall loss.\n\nThe only case sha1_object_info() could work well for an object near\nthe tip of a deep delta chain is to find its size, as the diff-delta\nencodes the size of the base and the size of the result of applying\nthe delta to the base, so you do not have to follow the chain when\nyou are only interested in the final size.\n\nBut alas nobody calls sha1_object_info() for only size but not type\n(there are some callers that are interested in only type but not\nsize).\n\n> This is a bit of a gamble; if we do find a tag object, then\n> we will end up loading the content anyway, and the extra\n> lookup will have been wasteful. However, if it is not a tag\n> object, then we save loading the object entirely. Depending\n> on the ratio of non-tags to tags in the input, this can be a\n> minor win or minor loss.\n>\n> However, it does give us one potential major win: if a ref\n> points to a large blob (e.g., via an unannotated tag), then\n> we can avoid looking at it entirely.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> This optimization is the one that gave me the most pause. While\n> upload-pack does call peel_ref on everything, the other callers all\n> constrain themselves to refs/tags/. So for many projects, we will be\n> calling it mostly on annotated tags, and it may be a very small net\n> loss. But in practice, it will not matter for most projects with a sane\n> number of normal tags, and saving even one accidental giant blob load\n> can have a huge impact.\n\nI may be missing something, but the above description is not\nconvincing to me.  When was the last time you pointed a blob\ndirectly with a ref, whether large or small, and whether within\nrefs/tags or outside?\n\n>\n>  refs.c | 11 +++++++++--\n>  1 file changed, 9 insertions(+), 2 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index f672ad9..02e47b1 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -1225,8 +1225,15 @@ fallback:\n>  \t}\n>  \n>  fallback:\n> -\to = parse_object(base);\n> -\tif (o && o->type == OBJ_TAG) {\n> +\to = lookup_unknown_object(base);\n> +\tif (o->type == OBJ_NONE) {\n> +\t\tint type = sha1_object_info(base, NULL);\n> +\t\tif (type < 0)\n> +\t\t\treturn -1;\n> +\t\to->type = type;\n> +\t}\n> +\n> +\tif (o->type == OBJ_TAG) {\n>  \t\to = deref_tag_noverify(o);\n>  \t\tif (o) {\n>  \t\t\thashcpy(sha1, o->sha1);\n"},{"id":"200545","messageId":"20121004194150.GA13955@sigill.intra.peff.net","threadId":"31726","inReplyTo":"7vbogiys47.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] peel_ref: check object type before loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T19:41:50Z","receivedAt":"2012-10-04T19:41:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 12:06:16PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > The point of peel_ref is to dereference tags; if the base\n> > object is not a tag, then we can return early without even\n> > loading the object into memory.\n> >\n> > This patch accomplishes that by checking sha1_object_info\n> > for the type. For a packed object, we can get away with just\n> > looking in the pack index. For a loose object, we only need\n> > to inflate the first couple of header bytes.\n> \n> We look at the pack index and have to follow its delta chain down to\n> the base to find its type; if the object is deeply deltified, this\n> certainly is an overall loss.\n\nYes. Although in practice I would expect most things pointed to by refs\nto not be delta'd. And indeed, comparing \"git index-pack -v\" to \"git\nfor-each-ref\" in my git.git repository yields 950 non-delta tips and\nonly 42 delta (and those are mostly rebased commit objects). In my\nlinux-2.6 repo, I have 0 delta ref tips (probably because I do not\nactually do kernel work, but keep it around for querying).\n\nThe numbers I mentioned in 926f1dd (which did this exact same\noptimization for upload-pack) showed a slight improvement in practice.\nBecause keep in mind that the alternative to this multi-step delta\nlookup for the type is to load the object. Which will do the _same_\nlookup, but will also have to actually compute the delta.\n\nSo the only real loss is that you have to repeat the lookup (or in the\ncase of a loose object, re-open and re-inflate the first 32 bytes). The\nbest way to do this would be to have sha1_object_info return some kind\nof handle to the object where we could get the meta info cheaply, and\nthen reuse the handle to get the actual object data later (so for a\npacked object, cache the actual pack location; for a loose object, keep\nthe descriptor and zlib stream open).\n\nOf course, the speed up in 926f1dd probably won't matter anymore because\nthe whole point of this series is to avoid touching the object at all.\nSo hitting sha1_object_info in peel_ref is already the slow path. On\nmost objects, an optimization like this will not be noticeable either\nway. The interesting thing is that we can avoid touching a large or\nexpensive object at all.\n\n> > This optimization is the one that gave me the most pause. While\n> > upload-pack does call peel_ref on everything, the other callers all\n> > constrain themselves to refs/tags/. So for many projects, we will be\n> > calling it mostly on annotated tags, and it may be a very small net\n> > loss. But in practice, it will not matter for most projects with a sane\n> > number of normal tags, and saving even one accidental giant blob load\n> > can have a huge impact.\n> \n> I may be missing something, but the above description is not\n> convincing to me.  When was the last time you pointed a blob\n> directly with a ref, whether large or small, and whether within\n> refs/tags or outside?\n\nNot often (though you have such a ref in git.git). I started down this\nroad because just applying patch 4/4 produces a regression in the test\nsuite. t1050 tries to clone a tag pointing to a large object with\nGIT_ALLOC_LIMIT set. Using peel_ref regresses this to actually load the\nwhole object into memory.\n\nThat particular regression is fixed by 1/1 (because it's an annotated\ntag pointing to the large object). This would fix the same case if it\nwere an unannotated tag.\n\nNow is that a real-world test? No, I'm not sure it is. But I consider it\na win for large-object git[1] every time we can avoid loading an object,\nbecause it only takes one unnecessary load to ruin the user experience.\nSo even if it's unlikely, if it isn't hurting the regular code path, I\nthink it's worth doing (and I'm not sure it is hurting; my numbers\nshowed that it be helping, though I suspect it is doing nothing after my\n4/4).\n\n-Peff\n\n[1] One thing I've been toying is with \"external alternates\"; dumping\n    your large objects in some realtively slow data store (e.g., a\n    RESTful HTTP service). You could cache and cheaply query a list of\n    \"sha1 / size / type\" for each object from the store, but getting the\n    actual objects would be much more expensive. But again, it would\n    depend on whether you would actually have such a store directly\n    accessible by a ref.\n"},{"id":"200570","messageId":"7vd30yx94r.fsf@alter.siamese.dyndns.org","threadId":"31726","inReplyTo":"20121004194150.GA13955@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] peel_ref: check object type before loading","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-04T20:41:40Z","receivedAt":"2012-10-04T20:41:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> [1] One thing I've been toying is with \"external alternates\"; dumping\n>     your large objects in some realtively slow data store (e.g., a\n>     RESTful HTTP service). You could cache and cheaply query a list of\n>     \"sha1 / size / type\" for each object from the store, but getting the\n>     actual objects would be much more expensive. But again, it would\n>     depend on whether you would actually have such a store directly\n>     accessible by a ref.\n\nYeah, that actually has been another thing we were discussing\nlocally, without coming to something concrete enough to present to\nthe list.\n\nThe basic idea is to mark such paths with attributes, and use a\nvariant of smudge/clean filter that is _not_ a filter (as we do not\nwant to have the interface to this external helper to be \"we feed\nthe whole big blob to you\").  Instead, these smudgex/cleanx things\nwork on a pathname.\n\n - Your in-tree objects store a blob that records a description of\n   the large thing.  Call such a blob a surrogate.  \"clone\", \"fetch\"\n   and \"push\" all deal only with surrogates so your in-history data\n   will stay small.\n\n - When checking out, the attributes mechanism kicks in and runs the\n   \"not filter\" variant of smudge with the data in the surrogate.\n\n   The surrogate records how to get the real thing from where, and\n   how to validate what you got is correct.  A hand-wavy example may\n   look like this:\n\n   \tget: download http://cdn.example.com/67def20\n        sha1sum: f84667def209e4a84e37e8488a08e9eca3f208c1\n\n   to tell you to download a single URL with whatever means suitable\n   for your platform (perhaps curl or wget), and verify the result\n   by running sha1sum.  Or it may involve\n\n\tget: git-fetch git://git.example.com/images.git/ master\n        object: 85a094f22f02c54c740448f6716da608a5e89a80\n\n   to tell you to \"git fetch\" from the given git-reachable resource\n   into some place and grab the object via \"git cat-file\", possibly\n   streaming it out.  The details do not matter at this point in the\n   design process.\n\n   The smudgex helper is responsible for caching previously fetched\n   large contents, maintaining association between the surrogate\n   blob and its real data, so that once the real thing is\n   downloaded, and the contents of the path needs to change to\n   something else (e.g. user checks out a different branch) and\n   then change to the previous thing again (e.g. user comes back to\n   the original branch), it does not download it again.\n\n - When checking if the working tree is clean relative to the index,\n   the smudgex/cleanx helper will be consulted.  It will be given\n   the surrogate data in the index and the path in the working tree.\n   We may want to allow the helper implementation to give a read-only\n   hardlink directly into helper's cache storage, so that it can\n   consult its database of surrogate-to-real mapping and perform\n   this verification cheaply by inode comparison, or something.\n\n - When running \"git add\" a modified large stuff prepared in the\n   working tree, cleanx helper is called to prepare a new surrogate,\n   and that is what is registered in the index.  The helper is also\n   responsible for storing the new large stuff away and arrange it\n   to be retrievable when others see and use this surrogate.\n\nThe initial scope of supporting something like that in core-git\nwould be to add the necessary infrastracture to arrange such smudgex\nand cleanx helpers are called when a path is marked as a surrogate\nin the attribute system, and supply a sample helper.\n"},{"id":"200559","messageId":"20121004215933.GA17358@sigill.intra.peff.net","threadId":"31726","inReplyTo":"7vd30yx94r.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] peel_ref: check object type before loading","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-10-04T21:59:33Z","receivedAt":"2012-10-04T21:59:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2012 at 01:41:40PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > [1] One thing I've been toying is with \"external alternates\"; dumping\n> >     your large objects in some realtively slow data store (e.g., a\n> >     RESTful HTTP service). You could cache and cheaply query a list of\n> >     \"sha1 / size / type\" for each object from the store, but getting the\n> >     actual objects would be much more expensive. But again, it would\n> >     depend on whether you would actually have such a store directly\n> >     accessible by a ref.\n> \n> Yeah, that actually has been another thing we were discussing\n> locally, without coming to something concrete enough to present to\n> the list.\n> \n> The basic idea is to mark such paths with attributes, and use a\n> variant of smudge/clean filter that is _not_ a filter (as we do not\n> want to have the interface to this external helper to be \"we feed\n> the whole big blob to you\").  Instead, these smudgex/cleanx things\n> work on a pathname.\n\nThere are a few ways that smudge/clean filters are not up to the task\ncurrently. One is definitely the efficiency of the interface.\n\nAnother is that this distinction is not \"canonical in-repo versus\nworking tree representation\".  Yes, part of it is about what you store\nin the repo versus what you checkout. But you may also want to diff or\nmerge these large items. Almost certainly not with the internal text\ntools, but you might want to feed the _real_ blobs (not the fake\nsurrogates) to external tools, and smudge and clean are not a natural\nfit for that. If you teach the external tools to dereference the\nsurrogates, it would work. I think you could also get around it by\ngiving these smudgex/cleanx filters slightly different semantics.\n\nBut the thing I most dislike about a solution like this is that the\nrepresentation pollutes git's data model. That is, git stores a blob\nrepresenting the surrogate, and that is the official sha1 that goes into\nthe tree. That means your surrogate decisions are locked into history\nforever, which has a few implications:\n\n  1. If I store a surrogate and you store the real blob, we do not get\n     the same tree (and in fact get conflicts).\n\n  2. Once I store a blob, I can never revise my decision not to store\n     that blob in every subsequent clone without rewriting history. I\n     can convert it into a surrogate, but old versions of that blob will\n     always be required for object connectivity.\n\n  3. If your surrogate contains more than just the sha1 (e.g., if it\n     points to http://cdn.example.com), your history is forever tied to\n     that (and you are stuck with configuring run-time redirects if your\n     URL changes).\n\nMy thinking was to make it all happen below the git object level, at the\nsame level as packs and loose objects. This is more invasive to git, but\nmuch more flexible.\n\nThe basic implementation is pretty straightforward. You configure one or\nmore helpers which have two operations: provide a list of sha1s, and\nfetch a single sha1. Whenever an object lookup fails in the packs and\nloose objects, we check the helper lists.  We can cache the lists in\nsome mmap'able format similar to a pack index, so we can do quick checks\nfor object existence, type, and size. And if the lookup actually needs\nthe object, we fetch and cache (where the caching policy would all be\ndetermined by the external script).\n\nThe real challenges are:\n\n  1. It is expensive to meet normal reachability guarantees. So you\n     would not want a remote to delta against a blob that you _could_\n     get, but do not have.\n\n  2. You need to tell remotes that you can access some objects in a\n     different way, and not to send them as part of an object transfer.\n\n  3. Many commands need to be taught not to load objects carelessly. For\n     the most part, we do well with this because it's already expensive\n     to load large objects from disk. I think we've got most of them on\n     the diff code path, but I wouldn't be surprised if one or two more\n     crop up. Fsck would need to learn to handle these objects\n     differently.\n\nItem (3) is really just about trying it and seeing where the problems\ncome up. For items (1) and (2), we'd need a protocol extension.\n\nHaving the receiver send something like \"I have these blobs from my external\nsource, don't send them\" is a nice idea, but it doesn't scale well (you\nhave to advertise the whole list for each transfer, because the receiver\ndoesn't know which ones are actually referenced).\n\nHaving the receiver say \"I have access to external database $FOO, go check\nthe list of objects there and don't send anything it has\" unnecessarily\nties the sender to the external database (i.e., they have to implement\n$FOO for it to work).\n\nSomething simple like \"do not send blobs larger than N bytes, nor make\ndeltas against such blobs\" would work. It does mean that your value of N\nreally needs to match up with what goes into your external database, but\nI don't think that will be a huge problem in practice (after the\ntransfer you can do a consistency check that between the fetched objects\nand the external db, you have everything).\n\n> [details on smudgex/cleanx]\n\nAll of what you wrote seems very sane; I think the real question is\nwhether this should be \"above\" or \"below\" git's user-visible data model\nlayer.\n\n-Peff\n"}]}