{"thread":{"id":"49081","subject":"[RFC PATCH] packfile: iterate packed objects in pack order","startedAt":"2018-08-08T23:12:17Z","lastAt":"2018-08-10T22:59:21Z","messageCount":4,"participants":["Jonathan Tan","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"354956","messageId":"20180808231210.242120-1-jonathantanmy@google.com","threadId":"49081","inReplyTo":null,"subject":"[RFC PATCH] packfile: iterate packed objects in pack order","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-08-08T23:12:10Z","receivedAt":"2018-08-08T23:12:17Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Many invocations of for_each_object_in_pack() and\nfor_each_packed_object() (which invokes the former) subsequently check\nat least the type of the packed object, necessitating accessing the\npackfile itself. For locality reasons, it is thus better to iterate in\npack order, instead of index order. Teach for_each_object_in_pack() to\niterate in pack order by first creating a reverse index.\n\nThis is based off work by Jeff King.\n\nSigned-off-by: Jonathan Tan \n---\nAfter writing this patch and looking at it further, I'm not sure if this\nis a clear benefit, but here's the patch anyway. In particular,\nbuiltin/fsck.c and builtin/cat-file.c just deal with the OID directly\nand does not access the packfile at all (at least at the time of\ninvoking for_each_packed_object). And revision.c, if we are excluding\npromisor objects, parses each packed promisor object, but it seems\npossible to avoid doing that (replacing the parse_object() by\nlookup_unknown_object() still passes tests).\n---\n packfile.c | 10 +++++++---\n 1 file changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 6974903e5..371b64e9b 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -15,6 +15,7 @@\n #include \"tree-walk.h\"\n #include \"tree.h\"\n #include \"object-store.h\"\n+#include \"pack-revindex.h\"\n \n char *odb_pack_name(struct strbuf *buf,\n \t\t const unsigned char *sha1,\n@@ -1890,14 +1891,17 @@ int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void\n \tuint32_t i;\n \tint r = 0;\n \n+\tload_pack_revindex(p);\n+\n \tfor (i = 0; i < p->num_objects; i++) {\n+\t\tuint32_t pack_nr = p->revindex[i].nr;\n \t\tstruct object_id oid;\n \n-\t\tif (!nth_packed_object_oid(&oid, p, i))\n+\t\tif (!nth_packed_object_oid(&oid, p, pack_nr))\n \t\t\treturn error(\"unable to get sha1 of object %u in %s\",\n-\t\t\t\t i, p->pack_name);\n+\t\t\t\t pack_nr, p->pack_name);\n \n-\t\tr = cb(&oid, p, i, data);\n+\t\tr = cb(&oid, p, pack_nr, data);\n \t\tif (r)\n \t\t\tbreak;\n \t}\n-- \n2.18.0.597.ga71716f1ad-goog\n\n"},{"id":"354960","messageId":"20180808232515.GC21882@sigill.intra.peff.net","threadId":"49081","inReplyTo":"20180808231210.242120-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] packfile: iterate packed objects in pack order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-08T23:25:16Z","receivedAt":"2018-08-08T23:25:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 08, 2018 at 04:12:10PM -0700, Jonathan Tan wrote:\n\n> Many invocations of for_each_object_in_pack() and\n> for_each_packed_object() (which invokes the former) subsequently check\n> at least the type of the packed object, necessitating accessing the\n> packfile itself. For locality reasons, it is thus better to iterate in\n> pack order, instead of index order. Teach for_each_object_in_pack() to\n> iterate in pack order by first creating a reverse index.\n> \n> This is based off work by Jeff King.\n> \n> Signed-off-by: Jonathan Tan \n> ---\n> After writing this patch and looking at it further, I'm not sure if this\n> is a clear benefit, but here's the patch anyway. In particular,\n> builtin/fsck.c and builtin/cat-file.c just deal with the OID directly\n> and does not access the packfile at all (at least at the time of\n> invoking for_each_packed_object). And revision.c, if we are excluding\n> promisor objects, parses each packed promisor object, but it seems\n> possible to avoid doing that (replacing the parse_object() by\n> lookup_unknown_object() still passes tests).\n\nEven if you just use the oid to do a separate lookup in the object\ndatabase, there's still a benefit in accessing the objects in pack\norder. The case in cat-file needs more than this, though, since it\nseparately sorts the output (it has to, because it has to merge and\nde-dup the output from several packs plus loose objects).\n\nWith the patch below on top of yours, I get:\n\n $ time git.v2.18.0 cat-file --batch-all-objects --buffer --batch | wc -c\n 6938365964\n\n real\t0m44.686s\n user\t0m42.932s\n sys\t0m5.283s\n\n $ time git.compile cat-file --batch-all-objects --buffer --batch | wc -c\n 8289859070\n\n real\t0m7.007s\n user\t0m5.542s\n sys\t0m4.005s\n\nBut:\n\n - it needs to de-duplicate using a hashmap (which is why the output is\n so much bigger in the second case)\n\n - it probably needs to be enabled explicitly by the user, since\n cat-file is plumbing and callers may be relying on the existing sort\n order\n\nI can try to pick this up and carry the cat-file bits to completion if\nyou want, but probably not until tomorrow or Friday.\n\n-Peff\n"},{"id":"355056","messageId":"CAGf8dgK_yMEtyh+_chQ+9i2d1Uc9oAXr7Q_8ES5OPF8qF87EHw@mail.gmail.com","threadId":"49081","inReplyTo":"20180808232515.GC21882@sigill.intra.peff.net","subject":"Re: [RFC PATCH] packfile: iterate packed objects in pack order","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-08-09T22:03:24Z","receivedAt":"2018-08-09T22:03:28Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Wed, Aug 8, 2018 at 4:25 PM, Jeff King wrote:\n> Even if you just use the oid to do a separate lookup in the object\n> database, there's still a benefit in accessing the objects in pack\n> order.\n\nYou're probably right, but I don't immediately see what the benefit is.\n\nOn a not completely unrelated note, I just realized that in my patch,\ni should be pack_nr (ordinal in pack order) and pack_nr should be\nindex_nr (ordinal in index order, i.e. alphabetical order). If you run\nwith this, feel free to write your own patch and maybe I'll learn how\naccessing objects in pack order benefits looking up the object\ndatabase through the commit message.\n\n> I can try to pick this up and carry the cat-file bits to completion if\n> you want, but probably not until tomorrow or Friday.\n\nThanks - feel free to do this.\n"},{"id":"355208","messageId":"20180810225918.GA18913@sigill.intra.peff.net","threadId":"49081","inReplyTo":"CAGf8dgK_yMEtyh+_chQ+9i2d1Uc9oAXr7Q_8ES5OPF8qF87EHw@mail.gmail.com","subject":"Re: [RFC PATCH] packfile: iterate packed objects in pack order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T22:59:18Z","receivedAt":"2018-08-10T22:59:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 09, 2018 at 03:03:24PM -0700, Jonathan Tan wrote:\n\n> On Wed, Aug 8, 2018 at 4:25 PM, Jeff King wrote:\n> > Even if you just use the oid to do a separate lookup in the object\n> > database, there's still a benefit in accessing the objects in pack\n> > order.\n> \n> You're probably right, but I don't immediately see what the benefit is.\n> \n> On a not completely unrelated note, I just realized that in my patch,\n> i should be pack_nr (ordinal in pack order) and pack_nr should be\n> index_nr (ordinal in index order, i.e. alphabetical order). If you run\n> with this, feel free to write your own patch and maybe I'll learn how\n> accessing objects in pack order benefits looking up the object\n> database through the commit message.\n\nIt probably would have been more apparent if when I said \"like in the\npatch below\" I actually remembered to paste in the patch. ;)\n\n> > I can try to pick this up and carry the cat-file bits to completion if\n> > you want, but probably not until tomorrow or Friday.\n> \n> Thanks - feel free to do this.\n\nI've got a series which I'll post momentarily which hopefully explains\nwhat's going on, along with various timings.\n\n-Peff\n"}]}