{"thread":{"id":"45625","subject":"[PATCH v1] WIP unpack-trees: avoid duplicate ODB lookups during checkout","startedAt":"2017-04-06T20:37:46Z","lastAt":"2017-04-07T17:35:43Z","messageCount":8,"participants":["git@jeffhostetler.com","Stefan Beller","René Scharfe","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"316303","messageId":"20170406203732.47714-1-git@jeffhostetler.com","threadId":"45625","inReplyTo":null,"subject":"[PATCH v1] WIP unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T20:37:31Z","receivedAt":"2017-04-06T20:37:46Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nAvoid duplicate ODB lookups for trees during traverse_tree_recursive().\n\nI'm marking this WIP so we can talk about the TODO in the\ncommit message.\n\nJeff Hostetler (1):\n unpack-trees: avoid duplicate ODB lookups during checkout\n\n tree-walk.c | 8 ++++++++\n tree-walk.h | 1 +\n unpack-trees.c | 13 +++++++++----\n 3 files changed, 18 insertions(+), 4 deletions(-)\n\n-- \n2.9.3\n\n"},{"id":"316304","messageId":"20170406203732.47714-2-git@jeffhostetler.com","threadId":"45625","inReplyTo":"20170406203732.47714-1-git@jeffhostetler.com","subject":"[PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T20:37:32Z","receivedAt":"2017-04-06T20:37:48Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach traverse_trees_recursive() to not do redundant ODB\nlookups when both directories refer to the same OID.\n\nIn operations such as read-tree, checkout, and merge when\nthe differences between the commits are relatively small,\nthere will likely be many directories that have the same\nSHA-1. In these cases we can avoid hitting the ODB multiple\ntimes for the same SHA-1.\n\nTODO This change is a first attempt to test that by comparing\nTODO the hashes of name[i] and name[i-i] and simply copying\nTODO the tree-descriptor data. I was thinking of the n=2\nTODO case here. We may want to extend this to the n=3 case.\n\n================\nOn the Windows repo (500K trees, 3.1M files, 450MB index),\nthis reduced the overall time by 0.75 seconds when cycling\nbetween 2 commits with a single file difference.\n\n(avg) before: 22.699\n(avg) after: 21.955\n===============\n\n================\nUsing the p0004-read-tree test (posted earlier this week)\nwith 1M files on Linux:\n\nbefore:\n$ ./p0004-read-tree.sh\n0004.5: switch work1 work2 (1003037) 11.99(8.12+3.32)\n0004.6: switch commit aliases (1003037) 11.95(8.20+3.14)\n\nafter:\n$ ./p0004-read-tree.sh\n0004.5: switch work1 work2 (1003037) 11.17(7.84+2.76)\n0004.6: switch commit aliases (1003037) 11.13(7.82+2.72)\n================\n\nSigned-off-by: Jeff Hostetler \n---\n tree-walk.c | 8 ++++++++\n tree-walk.h | 1 +\n unpack-trees.c | 13 +++++++++----\n 3 files changed, 18 insertions(+), 4 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex ff77605..3b82f0e 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n \treturn buf;\n }\n \n+void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src)\n+{\n+\tvoid *buf = xmalloc(src->size);\n+\tmemcpy(buf, src->buffer, src->size);\n+\tinit_tree_desc(dest, buf, src->size);\n+\treturn buf;\n+}\n+\n static void entry_clear(struct name_entry *a)\n {\n \tmemset(a, 0, sizeof(*a));\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 68bb78b..ca4032b 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry *);\n int tree_entry_gently(struct tree_desc *, struct name_entry *);\n \n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);\n+void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src);\n \n struct traverse_info;\n typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 3a8ee19..50aacad 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tnewinfo.df_conflicts |= df_conflicts;\n \n \tfor (i = 0; i < n; i++, dirmask >>= 1) {\n-\t\tconst unsigned char *sha1 = NULL;\n-\t\tif (dirmask & 1)\n-\t\t\tsha1 = names[i].oid->hash;\n-\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n+\t\tif (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&\n+\t\t\t!hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {\n+\t\t\tbuf[i] = copy_tree_descriptor(&t[i], &t[i-1]);\n+\t\t} else {\n+\t\t\tconst unsigned char *sha1 = NULL;\n+\t\t\tif (dirmask & 1)\n+\t\t\t\tsha1 = names[i].oid->hash;\n+\t\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n+\t\t}\n \t}\n \n \tbottom = switch_cache_bottom(&newinfo);\n-- \n2.9.3\n\n"},{"id":"316312","messageId":"CAGZ79kafbRQo2Of0H162ue5YzL7uA2PDu=sTy0=cEOejGTJhyw@mail.gmail.com","threadId":"45625","inReplyTo":"20170406203732.47714-2-git@jeffhostetler.com","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-06T22:48:07Z","receivedAt":"2017-04-06T22:48:14Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Apr 6, 2017 at 1:37 PM, wrote:\n> From: Jeff Hostetler \n>\n> Teach traverse_trees_recursive() to not do redundant ODB\n> lookups when both directories refer to the same OID.\n\nAnd the reason for this is that omitting the second lookup\nsaves time, i.e. a lookup in the ODB of a sufficiently large\nrepo is slow.\n\nMy kneejerk line of thinking:\n* yes, it sounds good to reduce the number of ODB accesses.\n* But if we consider ODB lookups to be slow and we perform\n a structured access, how about a cache in front of the ODB?\n* We already have that! (sort of..) 9a414486d9 (lookup_object:\n prioritize recently found objects, 2013-05-01)\n* Instead of improving the caching, maybe change the\n size of the problem: We could keep the objects of different types\n in different hash-tables.\n\nobject.c has its own hash table, I presume for historical and\nperformance reasons, this would be split up to multiple hash\ntables.\n\nAdditionally to \"object *lookup_object(*sha1)\", we'd have\na function\n\n\"object *lookup_object(*sha1, enum object_type hint)\"\nwhich looks into the correct the hash table.\n\nIf you were to call just lookup_object with no hint, then you'd\nlook into all the different tables (I guess there is a preferrable\norder in which to look, haven't thought about that).\n\n>\n> In operations such as read-tree, checkout, and merge when\n> the differences between the commits are relatively small,\n> there will likely be many directories that have the same\n> SHA-1. In these cases we can avoid hitting the ODB multiple\n> times for the same SHA-1.\n\nThis would explain partially why there was such a good\nperformance boost in the referenced commit above as we\nimplicitly lookup the same object multiple times.\n\nPeff is really into getting this part faster, c.f.\nhttps://public-inbox.org/git/20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net/\n\n> TODO This change is a first attempt to test that by comparing\n> TODO the hashes of name[i] and name[i-i] and simply copying\n> TODO the tree-descriptor data. I was thinking of the n=2\n> TODO case here. We may want to extend this to the n=3 case.\n\n>\n> ================\n> On the Windows repo (500K trees, 3.1M files, 450MB index),\n> this reduced the overall time by 0.75 seconds when cycling\n> between 2 commits with a single file difference.\n>\n> (avg) before: 22.699\n> (avg) after: 21.955\n> ===============\n\nSo it shaves off 4% of the time needed. it doesn't sound like a\nbreak through, but I guess these small patches add up. :)\n\n> for (i = 0; i < n; i++, dirmask >>= 1) {\n> - const unsigned char *sha1 = NULL;\n> - if (dirmask & 1)\n> - sha1 = names[i].oid->hash;\n> - buf[i] = fill_tree_descriptor(t+i, sha1);\n> + if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&\n> + !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {\n\nWhy do we need to check for dirmask & 1 here?\nThis ought to be covered by the hashcmp already IIUC.\nSo maybe we can pull out the\n if (dirmask & 1)\n sha1 = names[i].oid->hash;\nout of the else when dropping that dirmask check?\n\n\nThanks,\nStefan\n"},{"id":"316315","messageId":"a1e08e20-7fe6-da3c-cd18-74a8bcd266e0@web.de","threadId":"45625","inReplyTo":"20170406203732.47714-2-git@jeffhostetler.com","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-07T00:32:44Z","receivedAt":"2017-04-07T00:33:10Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 06.04.2017 um 22:37 schrieb git@jeffhostetler.com:\n> From: Jeff Hostetler \n> \n> Teach traverse_trees_recursive() to not do redundant ODB\n> lookups when both directories refer to the same OID.\n> \n> In operations such as read-tree, checkout, and merge when\n> the differences between the commits are relatively small,\n> there will likely be many directories that have the same\n> SHA-1. In these cases we can avoid hitting the ODB multiple\n> times for the same SHA-1.\n> \n> TODO This change is a first attempt to test that by comparing\n> TODO the hashes of name[i] and name[i-i] and simply copying\n> TODO the tree-descriptor data. I was thinking of the n=2\n> TODO case here. We may want to extend this to the n=3 case.\n> \n> ================\n> On the Windows repo (500K trees, 3.1M files, 450MB index),\n> this reduced the overall time by 0.75 seconds when cycling\n> between 2 commits with a single file difference.\n> \n> (avg) before: 22.699\n> (avg) after: 21.955\n> ===============\n> \n> ================\n> Using the p0004-read-tree test (posted earlier this week)\n> with 1M files on Linux:\n> \n> before:\n> $ ./p0004-read-tree.sh\n> 0004.5: switch work1 work2 (1003037) 11.99(8.12+3.32)\n> 0004.6: switch commit aliases (1003037) 11.95(8.20+3.14)\n> \n> after:\n> $ ./p0004-read-tree.sh\n> 0004.5: switch work1 work2 (1003037) 11.17(7.84+2.76)\n> 0004.6: switch commit aliases (1003037) 11.13(7.82+2.72)\n> ================\n> \n> Signed-off-by: Jeff Hostetler \n> ---\n> tree-walk.c | 8 ++++++++\n> tree-walk.h | 1 +\n> unpack-trees.c | 13 +++++++++----\n> 3 files changed, 18 insertions(+), 4 deletions(-)\n> \n> diff --git a/tree-walk.c b/tree-walk.c\n> index ff77605..3b82f0e 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n> \treturn buf;\n> }\n> \n> +void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src)\n> +{\n> +\tvoid *buf = xmalloc(src->size);\n> +\tmemcpy(buf, src->buffer, src->size);\n> +\tinit_tree_desc(dest, buf, src->size);\n> +\treturn buf;\n> +}\n> +\n> static void entry_clear(struct name_entry *a)\n> {\n> \tmemset(a, 0, sizeof(*a));\n> diff --git a/tree-walk.h b/tree-walk.h\n> index 68bb78b..ca4032b 100644\n> --- a/tree-walk.h\n> +++ b/tree-walk.h\n> @@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry *);\n> int tree_entry_gently(struct tree_desc *, struct name_entry *);\n> \n> void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);\n> +void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src);\n> \n> struct traverse_info;\n> typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 3a8ee19..50aacad 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n> \tnewinfo.df_conflicts |= df_conflicts;\n> \n> \tfor (i = 0; i < n; i++, dirmask >>= 1) {\n> -\t\tconst unsigned char *sha1 = NULL;\n> -\t\tif (dirmask & 1)\n> -\t\t\tsha1 = names[i].oid->hash;\n> -\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n> +\t\tif (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&\n\nCan .oid even be NULL? (I didn't check, but it's dereferenced in the \nsha1 assignment below, so I guess the answer is no and these two checks \nare not needed.)\n\n> +\t\t\t!hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {\n\nCalling oidcmp would be shorter.\n\n> +\t\t\tbuf[i] = copy_tree_descriptor(&t[i], &t[i-1]);\n\nbuf keeps track of the allocations that need to be freed at the end of \nthe function. I assume these buffers are read-only. Can you use an \nalias here instead of a duplicate by calling init_tree_desc with the \npredecessor's buffer and setting buf[i] to NULL? Or even just copying \nt[i - 1] to t[i] with an assignment? That would be shorter and probably \nalso quicker.\n\n> +\t\t} else {\n> +\t\t\tconst unsigned char *sha1 = NULL;\n> +\t\t\tif (dirmask & 1)\n> +\t\t\t\tsha1 = names[i].oid->hash;\n> +\t\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n> +\t\t}\n> \t}\n> \n> \tbottom = switch_cache_bottom(&newinfo);\n> \n"},{"id":"316321","messageId":"20170407051935.4usaxtmco7lqm4ew@sigill.intra.peff.net","threadId":"45625","inReplyTo":"CAGZ79kafbRQo2Of0H162ue5YzL7uA2PDu=sTy0=cEOejGTJhyw@mail.gmail.com","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-07T05:19:35Z","receivedAt":"2017-04-07T05:19:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 06, 2017 at 03:48:07PM -0700, Stefan Beller wrote:\n\n> On Thu, Apr 6, 2017 at 1:37 PM, wrote:\n> > From: Jeff Hostetler \n> >\n> > Teach traverse_trees_recursive() to not do redundant ODB\n> > lookups when both directories refer to the same OID.\n> \n> And the reason for this is that omitting the second lookup\n> saves time, i.e. a lookup in the ODB of a sufficiently large\n> repo is slow.\n> \n> My kneejerk line of thinking:\n> * yes, it sounds good to reduce the number of ODB accesses.\n> * But if we consider ODB lookups to be slow and we perform\n> a structured access, how about a cache in front of the ODB?\n> * We already have that! (sort of..) 9a414486d9 (lookup_object:\n> prioritize recently found objects, 2013-05-01)\n> * Instead of improving the caching, maybe change the\n> size of the problem: We could keep the objects of different types\n> in different hash-tables.\n\nI don't think this is using lookup_object() at all, though. It goes\nstraight to fill_tree_descriptor(), which will read the object contents\nfrom disk. So our time is going to:\n\n 1. Finding the object in the odb (ideally a binary search in a single\n pack index, but less optimal when there are many packs).\n\n 2. Reconstructing the object. This means zlib-inflating from disk, but\n it may also mean delta reconstruction.\n\nI think there _are_ some caches at play here, though, when you look up\nthe same tree back to back. The pack-mru means that we'll always look in\nthe correct pack first. And in theory the delta base cache means that\nwe'll already have the whole thing reconstructed in memory (though I\nhave often been confused by exactly when we put items into that cache,\nso I might be wrong).\n\nSo in theory, this is not all that different than the \"just allocate and\ncopy the bytes\" optimization that's happening here (though I'm not\nsurprised that doing it at a higher level can produce some speedup).\n\nI think the more interesting optimization is \"just use the same buffer\nwithout bothering to copy\", which is hard for the low-level code to do\n(since it doesn't know what lifetime the caller is expecting). \n\n> object.c has its own hash table, I presume for historical and\n> performance reasons, this would be split up to multiple hash\n> tables.\n\nSo I don't think lookup_object() is really relevant here. But I'm also\nnot sure that multiple hash tables would really buy us much. In theory\nhash tables are O(1), so multiple smaller tables doesn't help (and might\nhurt, since now we have four O(1) lookups to do). Of course that's a\nminor fiction because of collisions, but we keep the load factor on the\nobject.c table pretty low (and that's why things like quadratic probing\nand cuckoo hashing never showed great improvement).\n\n-Peff\n"},{"id":"316349","messageId":"fa94cfb3-ac5e-13f1-4c06-f0f3f1a2d1df@jeffhostetler.com","threadId":"45625","inReplyTo":"20170407051935.4usaxtmco7lqm4ew@sigill.intra.peff.net","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T13:51:40Z","receivedAt":"2017-04-07T13:51:47Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/7/2017 1:19 AM, Jeff King wrote:\n> On Thu, Apr 06, 2017 at 03:48:07PM -0700, Stefan Beller wrote:\n>\n>> On Thu, Apr 6, 2017 at 1:37 PM, wrote:\n>>> From: Jeff Hostetler \n>>>\n>>> Teach traverse_trees_recursive() to not do redundant ODB\n>>> lookups when both directories refer to the same OID.\n>>\n>> And the reason for this is that omitting the second lookup\n>> saves time, i.e. a lookup in the ODB of a sufficiently large\n>> repo is slow.\n>>\n>> My kneejerk line of thinking:\n>> * yes, it sounds good to reduce the number of ODB accesses.\n>> * But if we consider ODB lookups to be slow and we perform\n>> a structured access, how about a cache in front of the ODB?\n>> * We already have that! (sort of..) 9a414486d9 (lookup_object:\n>> prioritize recently found objects, 2013-05-01)\n>> * Instead of improving the caching, maybe change the\n>> size of the problem: We could keep the objects of different types\n>> in different hash-tables.\n>\n> I don't think this is using lookup_object() at all, though. It goes\n> straight to fill_tree_descriptor(), which will read the object contents\n> from disk. So our time is going to:\n>\n> 1. Finding the object in the odb (ideally a binary search in a single\n> pack index, but less optimal when there are many packs).\n>\n> 2. Reconstructing the object. This means zlib-inflating from disk, but\n> it may also mean delta reconstruction.\n>\n> I think there _are_ some caches at play here, though, when you look up\n> the same tree back to back. The pack-mru means that we'll always look in\n> the correct pack first. And in theory the delta base cache means that\n> we'll already have the whole thing reconstructed in memory (though I\n> have often been confused by exactly when we put items into that cache,\n> so I might be wrong).\n\nThis change shaved 500K calls to fill_tree_descriptor() (on the Windows\nsource tree on a \"checkout -b\" to the same commit). I was surprised it\ndidn't give more of a speed up, so some of that caching may be in play\nhere, but it's hard to tell.\n\nAlso, on my repo I have 100GB+ of packfiles, so that may be messing\nwith things a bit.\n\n>\n> So in theory, this is not all that different than the \"just allocate and\n> copy the bytes\" optimization that's happening here (though I'm not\n> surprised that doing it at a higher level can produce some speedup).\n>\n> I think the more interesting optimization is \"just use the same buffer\n> without bothering to copy\", which is hard for the low-level code to do\n> (since it doesn't know what lifetime the caller is expecting).\n\nMy first draft did just borrow the buffer right there in traverse_\nand it seemed to work just fine. I was being cautious and copied it\nproperly in the lower layer. Since the bufs are freed at the bottom\nit felt safe, but I didn't want to overlook anything. I'll switch it\nback.\n\n>\n>> object.c has its own hash table, I presume for historical and\n>> performance reasons, this would be split up to multiple hash\n>> tables.\n>\n> So I don't think lookup_object() is really relevant here. But I'm also\n> not sure that multiple hash tables would really buy us much. In theory\n> hash tables are O(1), so multiple smaller tables doesn't help (and might\n> hurt, since now we have four O(1) lookups to do). Of course that's a\n> minor fiction because of collisions, but we keep the load factor on the\n> object.c table pretty low (and that's why things like quadratic probing\n> and cuckoo hashing never showed great improvement).\n\nI do wonder now about the initial hash table size and any limits\non it, but that is a question for another day.\n\nThanks\nJeff\n\n"},{"id":"316350","messageId":"b2952bdc-cb93-1317-58b1-a06ea4e14ee8@jeffhostetler.com","threadId":"45625","inReplyTo":"a1e08e20-7fe6-da3c-cd18-74a8bcd266e0@web.de","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T13:57:12Z","receivedAt":"2017-04-07T13:57:19Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 8:32 PM, René Scharfe wrote:\n> Am 06.04.2017 um 22:37 schrieb git@jeffhostetler.com:\n>> From: Jeff Hostetler \n>>\n>> Teach traverse_trees_recursive() to not do redundant ODB\n>> lookups when both directories refer to the same OID.\n>>\n>> In operations such as read-tree, checkout, and merge when\n>> the differences between the commits are relatively small,\n>> there will likely be many directories that have the same\n>> SHA-1. In these cases we can avoid hitting the ODB multiple\n>> times for the same SHA-1.\n>>\n>> TODO This change is a first attempt to test that by comparing\n>> TODO the hashes of name[i] and name[i-i] and simply copying\n>> TODO the tree-descriptor data. I was thinking of the n=2\n>> TODO case here. We may want to extend this to the n=3 case.\n>>\n>> ================\n>> On the Windows repo (500K trees, 3.1M files, 450MB index),\n>> this reduced the overall time by 0.75 seconds when cycling\n>> between 2 commits with a single file difference.\n>>\n>> (avg) before: 22.699\n>> (avg) after: 21.955\n>> ===============\n>>\n>> ================\n>> Using the p0004-read-tree test (posted earlier this week)\n>> with 1M files on Linux:\n>>\n>> before:\n>> $ ./p0004-read-tree.sh\n>> 0004.5: switch work1 work2 (1003037) 11.99(8.12+3.32)\n>> 0004.6: switch commit aliases (1003037) 11.95(8.20+3.14)\n>>\n>> after:\n>> $ ./p0004-read-tree.sh\n>> 0004.5: switch work1 work2 (1003037) 11.17(7.84+2.76)\n>> 0004.6: switch commit aliases (1003037) 11.13(7.82+2.72)\n>> ================\n>>\n>> Signed-off-by: Jeff Hostetler \n>> ---\n>> tree-walk.c | 8 ++++++++\n>> tree-walk.h | 1 +\n>> unpack-trees.c | 13 +++++++++----\n>> 3 files changed, 18 insertions(+), 4 deletions(-)\n>>\n>> diff --git a/tree-walk.c b/tree-walk.c\n>> index ff77605..3b82f0e 100644\n>> --- a/tree-walk.c\n>> +++ b/tree-walk.c\n>> @@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc,\n>> const unsigned char *sha1)\n>> return buf;\n>> }\n>> +void *copy_tree_descriptor(struct tree_desc *dest, const struct\n>> tree_desc *src)\n>> +{\n>> + void *buf = xmalloc(src->size);\n>> + memcpy(buf, src->buffer, src->size);\n>> + init_tree_desc(dest, buf, src->size);\n>> + return buf;\n>> +}\n>> +\n>> static void entry_clear(struct name_entry *a)\n>> {\n>> memset(a, 0, sizeof(*a));\n>> diff --git a/tree-walk.h b/tree-walk.h\n>> index 68bb78b..ca4032b 100644\n>> --- a/tree-walk.h\n>> +++ b/tree-walk.h\n>> @@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry\n>> *);\n>> int tree_entry_gently(struct tree_desc *, struct name_entry *);\n>> void *fill_tree_descriptor(struct tree_desc *desc, const unsigned\n>> char *sha1);\n>> +void *copy_tree_descriptor(struct tree_desc *dest, const struct\n>> tree_desc *src);\n>> struct traverse_info;\n>> typedef int (*traverse_callback_t)(int n, unsigned long mask,\n>> unsigned long dirmask, struct name_entry *entry, struct traverse_info *);\n>> diff --git a/unpack-trees.c b/unpack-trees.c\n>> index 3a8ee19..50aacad 100644\n>> --- a/unpack-trees.c\n>> +++ b/unpack-trees.c\n>> @@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n,\n>> unsigned long dirmask,\n>> newinfo.df_conflicts |= df_conflicts;\n>> for (i = 0; i < n; i++, dirmask >>= 1) {\n>> - const unsigned char *sha1 = NULL;\n>> - if (dirmask & 1)\n>> - sha1 = names[i].oid->hash;\n>> - buf[i] = fill_tree_descriptor(t+i, sha1);\n>> + if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&\n>\n> Can .oid even be NULL? (I didn't check, but it's dereferenced in the\n> sha1 assignment below, so I guess the answer is no and these two checks\n> are not needed.)\n\nyes. i think the (dirmask&1) is hiding it for name[i]. i put both in\nthe code above, but it also worked fine just testing both oid's (and\nwithout dirmask).\n\n>\n>> + !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {\n>\n> Calling oidcmp would be shorter.\n\nright.\n\n>\n>> + buf[i] = copy_tree_descriptor(&t[i], &t[i-1]);\n>\n> buf keeps track of the allocations that need to be freed at the end of\n> the function. I assume these buffers are read-only. Can you use an\n> alias here instead of a duplicate by calling init_tree_desc with the\n> predecessor's buffer and setting buf[i] to NULL? Or even just copying\n> t[i - 1] to t[i] with an assignment? That would be shorter and probably\n> also quicker.\n\nYes, my first draft did that. Just being cautious, but i'll switch it\nback since that seems to be the consensus.\n\n>\n>> + } else {\n>> + const unsigned char *sha1 = NULL;\n>> + if (dirmask & 1)\n>> + sha1 = names[i].oid->hash;\n>> + buf[i] = fill_tree_descriptor(t+i, sha1);\n>> + }\n>> }\n>> bottom = switch_cache_bottom(&newinfo);\n>>\n\nThanks\nJeff\n"},{"id":"316368","messageId":"6aa9d888-54e6-4d43-db84-ce4ec4dfaca6@jeffhostetler.com","threadId":"45625","inReplyTo":"CAGZ79kafbRQo2Of0H162ue5YzL7uA2PDu=sTy0=cEOejGTJhyw@mail.gmail.com","subject":"Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T17:35:36Z","receivedAt":"2017-04-07T17:35:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 6:48 PM, Stefan Beller wrote:\n> On Thu, Apr 6, 2017 at 1:37 PM, wrote:\n>> From: Jeff Hostetler \n>>\n>> Teach traverse_trees_recursive() to not do redundant ODB\n>> lookups when both directories refer to the same OID.\n>\n> And the reason for this is that omitting the second lookup\n> saves time, i.e. a lookup in the ODB of a sufficiently large\n> repo is slow.\n>\n> My kneejerk line of thinking:\n> * yes, it sounds good to reduce the number of ODB accesses.\n> * But if we consider ODB lookups to be slow and we perform\n> a structured access, how about a cache in front of the ODB?\n> * We already have that! (sort of..) 9a414486d9 (lookup_object:\n> prioritize recently found objects, 2013-05-01)\n> * Instead of improving the caching, maybe change the\n> size of the problem: We could keep the objects of different types\n> in different hash-tables.\n>\n> object.c has its own hash table, I presume for historical and\n> performance reasons, this would be split up to multiple hash\n> tables.\n>\n> Additionally to \"object *lookup_object(*sha1)\", we'd have\n> a function\n>\n> \"object *lookup_object(*sha1, enum object_type hint)\"\n> which looks into the correct the hash table.\n>\n> If you were to call just lookup_object with no hint, then you'd\n> look into all the different tables (I guess there is a preferrable\n> order in which to look, haven't thought about that).\n>\n>>\n>> In operations such as read-tree, checkout, and merge when\n>> the differences between the commits are relatively small,\n>> there will likely be many directories that have the same\n>> SHA-1. In these cases we can avoid hitting the ODB multiple\n>> times for the same SHA-1.\n>\n> This would explain partially why there was such a good\n> performance boost in the referenced commit above as we\n> implicitly lookup the same object multiple times.\n>\n> Peff is really into getting this part faster, c.f.\n> https://public-inbox.org/git/20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net/\n\nThat looks interesting, but I question the probabilities for\nmy use case here. When walking the trees and files in a single\ncommit, I have no expectation that I'll see the same tree OID\ntwice, so the cache is not really useful and may just add\noverhead. However, in a checkout or merge there is a high\nexpectation of visiting the same tree OID -- and most of the\ntime they are peers -- since commits tend to only change\nisolated parts of the tree. (I'm not going to worry about the\ncase where someone moves an entire sub-tree to somewhere else\nin the tree and violates my peer assertion.)\n\nI did notice that we do 2 independent passes during checkout.\nFirst to compare the old and new commits. Then to compare the\nnew with the worktree. So we touch each tree object 3 times.\n\nMy patch helps the first, but does nothing for the second.\nHopefully the cache is helping it (but I have not measured that).\n\n\n>\n>> TODO This change is a first attempt to test that by comparing\n>> TODO the hashes of name[i] and name[i-i] and simply copying\n>> TODO the tree-descriptor data. I was thinking of the n=2\n>> TODO case here. We may want to extend this to the n=3 case.\n>\n>>\n>> ================\n>> On the Windows repo (500K trees, 3.1M files, 450MB index),\n>> this reduced the overall time by 0.75 seconds when cycling\n>> between 2 commits with a single file difference.\n>>\n>> (avg) before: 22.699\n>> (avg) after: 21.955\n>> ===============\n>\n> So it shaves off 4% of the time needed. it doesn't sound like a\n> break through, but I guess these small patches add up. :)\n\nAgreed, but on the Windows source repo, it can take 30 seconds to\ndo a \"checkout -b\" (without changing the actual HEAD commit).\nThat's just for the housekeeping of ensuring you get a clean\nworktree. If I can knock off 5% here with minimal impact\nand without changing any file formats, I'll take it.\n\nAnd if I can just repeat that n times... :-)\n\n>\n>> for (i = 0; i < n; i++, dirmask >>= 1) {\n>> - const unsigned char *sha1 = NULL;\n>> - if (dirmask & 1)\n>> - sha1 = names[i].oid->hash;\n>> - buf[i] = fill_tree_descriptor(t+i, sha1);\n>> + if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&\n>> + !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {\n>\n> Why do we need to check for dirmask & 1 here?\n> This ought to be covered by the hashcmp already IIUC.\n> So maybe we can pull out the\n> if (dirmask & 1)\n> sha1 = names[i].oid->hash;\n> out of the else when dropping that dirmask check?\n\nI was wondering about the test in the else clause.\nJust now I put a quick assert in there and it went off,\nso I'm not going to change this.\n\nThanks\nJeff\n"}]}