{"thread":{"id":"45678","subject":"[PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","startedAt":"2017-04-13T15:59:11Z","lastAt":"2017-04-14T19:33:06Z","messageCount":5,"participants":["git@jeffhostetler.com","Junio C Hamano","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"316724","messageId":"20170413155852.4281-1-git@jeffhostetler.com","threadId":"45678","inReplyTo":null,"subject":"[PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-13T15:58:51Z","receivedAt":"2017-04-13T15:59:11Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nVersion 3 uses a structure copy rather than memcpy and adds a comment.\n\nJeff Hostetler (1):\n unpack-trees: avoid duplicate ODB lookups during checkout\n\n unpack-trees.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\n-- \n2.9.3\n\n"},{"id":"316725","messageId":"20170413155852.4281-2-git@jeffhostetler.com","threadId":"45678","inReplyTo":"20170413155852.4281-1-git@jeffhostetler.com","subject":"[PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-13T15:58:52Z","receivedAt":"2017-04-13T15:59:12Z","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 and checkout, there will\nlikely be many peer directories that have the same OID when\nthe differences between the commits are relatively small.\nIn these cases we can avoid hitting the ODB multiple times\nfor the same OID.\n\nThis patch handles n=2 and n=3 cases and simply copies the\ndata rather than repeating the fill_tree_descriptor().\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================\nOn Linux using p0006-read-tree-checkout.sh with linux.git:\n\nTest HEAD^ HEAD\n-------------------------------------------------------------------------------------------------------\n0006.2: read-tree br_base br_ballast (57994) 0.24(0.20+0.03) 0.24(0.22+0.01) +0.0%\n0006.3: switch between br_base br_ballast (57994) 10.58(6.23+2.86) 10.67(5.94+2.87) +0.9%\n0006.4: switch between br_ballast br_ballast_plus_1 (57994) 0.60(0.44+0.17) 0.57(0.44+0.14) -5.0%\n0006.5: switch between aliases (57994) 0.59(0.48+0.13) 0.57(0.44+0.15) -3.4%\n================\n\nSigned-off-by: Jeff Hostetler \n---\n unpack-trees.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 3a8ee19..a674423 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -531,6 +531,11 @@ static int switch_cache_bottom(struct traverse_info *info)\n \treturn ret;\n }\n \n+static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)\n+{\n+\treturn name_j->oid && name_k->oid && !oidcmp(name_j->oid, name_k->oid);\n+}\n+\n static int traverse_trees_recursive(int n, unsigned long dirmask,\n \t\t\t\t unsigned long df_conflicts,\n \t\t\t\t struct name_entry *names,\n@@ -553,11 +558,35 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tnewinfo.pathlen += tree_entry_len(p) + 1;\n \tnewinfo.df_conflicts |= df_conflicts;\n \n+\t/*\n+\t * Fetch the tree from the ODB for each peer directory in the\n+\t * n commits.\n+\t *\n+\t * For 2- and 3-way traversals, we try to avoid hitting the\n+\t * ODB twice for the same OID. This should yield a nice speed\n+\t * up in checkouts and merges when the commits are similar.\n+\t *\n+\t * We don't bother doing the full O(n^2) search for larger n,\n+\t * because wider traversals don't happen that often and we\n+\t * avoid the search setup.\n+\t *\n+\t * When 2 peer OIDs are the same, we just copy the tree\n+\t * descriptor data. This implicitly borrows the buffer\n+\t * data from the earlier cell.\n+\t */\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 && are_same_oid(&names[i], &names[i - 1])) {\n+\t\t\tt[i] = t[i - 1];\n+\t\t\tbuf[i] = NULL;\n+\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i - 2])) {\n+\t\t\tt[i] = t[i - 2];\n+\t\t\tbuf[i] = NULL;\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":"316800","messageId":"xmqqtw5roqcc.fsf@gitster.mtv.corp.google.com","threadId":"45678","inReplyTo":"20170413155852.4281-2-git@jeffhostetler.com","subject":"Re: [PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-13T23:11:31Z","receivedAt":"2017-04-13T23:11:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"git@jeffhostetler.com writes:\n\n> +\t/*\n> +\t * Fetch the tree from the ODB for each peer directory in the\n> +\t * n commits.\n> +\t *\n> +\t * For 2- and 3-way traversals, we try to avoid hitting the\n> +\t * ODB twice for the same OID. This should yield a nice speed\n> +\t * up in checkouts and merges when the commits are similar.\n> +\t *\n> +\t * We don't bother doing the full O(n^2) search for larger n,\n> +\t * because wider traversals don't happen that often and we\n> +\t * avoid the search setup.\n> +\t *\n> +\t * When 2 peer OIDs are the same, we just copy the tree\n> +\t * descriptor data. This implicitly borrows the buffer\n> +\t * data from the earlier cell.\n\nThis \"borrowing\" made me worried, but it turns out that this is\nperfectly OK.\n\nfill_tree_descriptor() uses read_sha1_file() to give a tree_desc its\nown copy of the tree object data, so the code that calls into the\ntree traversal API is responsible for freeing the buffer returned\nfrom fill_tree_descriptor(). The updated code avoids double freeing\nby setting buf[i] to NULL for borrowing [i].\n\n> +\t */\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 && are_same_oid(&names[i], &names[i - 1])) {\n> +\t\t\tt[i] = t[i - 1];\n> +\t\t\tbuf[i] = NULL;\n> +\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i - 2])) {\n> +\t\t\tt[i] = t[i - 2];\n> +\t\t\tbuf[i] = NULL;\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"},{"id":"316804","messageId":"20170414005924.sfu4csdxaoafipsv@sigill.intra.peff.net","threadId":"45678","inReplyTo":"xmqqtw5roqcc.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-14T00:59:25Z","receivedAt":"2017-04-14T00:59:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 13, 2017 at 04:11:31PM -0700, Junio C Hamano wrote:\n\n> git@jeffhostetler.com writes:\n> \n> > +\t/*\n> > +\t * Fetch the tree from the ODB for each peer directory in the\n> > +\t * n commits.\n> > +\t *\n> > +\t * For 2- and 3-way traversals, we try to avoid hitting the\n> > +\t * ODB twice for the same OID. This should yield a nice speed\n> > +\t * up in checkouts and merges when the commits are similar.\n> > +\t *\n> > +\t * We don't bother doing the full O(n^2) search for larger n,\n> > +\t * because wider traversals don't happen that often and we\n> > +\t * avoid the search setup.\n> > +\t *\n> > +\t * When 2 peer OIDs are the same, we just copy the tree\n> > +\t * descriptor data. This implicitly borrows the buffer\n> > +\t * data from the earlier cell.\n> \n> This \"borrowing\" made me worried, but it turns out that this is\n> perfectly OK.\n> \n> fill_tree_descriptor() uses read_sha1_file() to give a tree_desc its\n> own copy of the tree object data, so the code that calls into the\n> tree traversal API is responsible for freeing the buffer returned\n> from fill_tree_descriptor(). The updated code avoids double freeing\n> by setting buf[i] to NULL for borrowing [i].\n\nYeah, I think that logic is fine. We could also keep a separate counter\nfor the size of buf, like:\n\n buf[nr_buf++] = fill_tree_descriptor(t+i, sha1);\n\nand then just count from zero to nr_buf in the freeing loop. I don't\nthink it matters much either way (the free(NULL) calls are presumably\ncheap).\n\n-Peff\n"},{"id":"316843","messageId":"3746703d-54e0-a855-8511-94a573a182a8@jeffhostetler.com","threadId":"45678","inReplyTo":"20170414005924.sfu4csdxaoafipsv@sigill.intra.peff.net","subject":"Re: [PATCH v3] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-14T19:32:58Z","receivedAt":"2017-04-14T19:33:06Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/13/2017 8:59 PM, Jeff King wrote:\n> On Thu, Apr 13, 2017 at 04:11:31PM -0700, Junio C Hamano wrote:\n>\n>> git@jeffhostetler.com writes:\n>>\n>>> +\t/*\n>>> +\t * Fetch the tree from the ODB for each peer directory in the\n>>> +\t * n commits.\n>>> +\t *\n>>> +\t * For 2- and 3-way traversals, we try to avoid hitting the\n>>> +\t * ODB twice for the same OID. This should yield a nice speed\n>>> +\t * up in checkouts and merges when the commits are similar.\n>>> +\t *\n>>> +\t * We don't bother doing the full O(n^2) search for larger n,\n>>> +\t * because wider traversals don't happen that often and we\n>>> +\t * avoid the search setup.\n>>> +\t *\n>>> +\t * When 2 peer OIDs are the same, we just copy the tree\n>>> +\t * descriptor data. This implicitly borrows the buffer\n>>> +\t * data from the earlier cell.\n>>\n>> This \"borrowing\" made me worried, but it turns out that this is\n>> perfectly OK.\n>>\n>> fill_tree_descriptor() uses read_sha1_file() to give a tree_desc its\n>> own copy of the tree object data, so the code that calls into the\n>> tree traversal API is responsible for freeing the buffer returned\n>> from fill_tree_descriptor(). The updated code avoids double freeing\n>> by setting buf[i] to NULL for borrowing [i].\n>\n> Yeah, I think that logic is fine. We could also keep a separate counter\n> for the size of buf, like:\n>\n> buf[nr_buf++] = fill_tree_descriptor(t+i, sha1);\n>\n> and then just count from zero to nr_buf in the freeing loop. I don't\n> think it matters much either way (the free(NULL) calls are presumably\n> cheap).\n\nAgreed. I don't think this matters one way or the other, but\nI'll go ahead and do this while it is fresh.\nThanks,\nJeff\n\n"}]}