{"thread":{"id":"45693","subject":"[PATCH v4] unpack-trees: avoid duplicate ODB lookups during checkout","startedAt":"2017-04-14T19:26:13Z","lastAt":"2017-04-14T21:06:12Z","messageCount":4,"participants":["git@jeffhostetler.com","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":4,"patchTotal":null},"messages":[{"id":"316841","messageId":"20170414192554.26683-1-git@jeffhostetler.com","threadId":"45693","inReplyTo":null,"subject":"[PATCH v4] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-14T19:25:53Z","receivedAt":"2017-04-14T19:26:13Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 4 cleans up the buf[] allocation and freeing as\nsuggested on the mailing list.\n\nJeff Hostetler (1):\n  unpack-trees: avoid duplicate ODB lookups during checkout\n\n unpack-trees.c | 38 +++++++++++++++++++++++++++++++++-----\n 1 file changed, 33 insertions(+), 5 deletions(-)\n\n-- \n2.9.3\n\n"},{"id":"316842","messageId":"20170414192554.26683-2-git@jeffhostetler.com","threadId":"45693","inReplyTo":"20170414192554.26683-1-git@jeffhostetler.com","subject":"[PATCH v4] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-14T19:25:54Z","receivedAt":"2017-04-14T19:26:24Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\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 <jeffhost@microsoft.com>\n---\n unpack-trees.c | 38 +++++++++++++++++++++++++++++++++-----\n 1 file changed, 33 insertions(+), 5 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 3a8ee19..07b0f11 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -531,12 +531,18 @@ 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 \t\t\t\t    struct traverse_info *info)\n {\n \tint i, ret, bottom;\n+\tint nr_buf = 0;\n \tstruct tree_desc t[MAX_UNPACK_TREES];\n \tvoid *buf[MAX_UNPACK_TREES];\n \tstruct traverse_info newinfo;\n@@ -553,18 +559,40 @@ 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\telse if (i > 1 && are_same_oid(&names[i], &names[i - 2]))\n+\t\t\tt[i] = t[i - 2];\n+\t\telse {\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[nr_buf++] = fill_tree_descriptor(t+i, sha1);\n+\t\t}\n \t}\n \n \tbottom = switch_cache_bottom(&newinfo);\n \tret = traverse_trees(n, t, &newinfo);\n \trestore_cache_bottom(&newinfo, bottom);\n \n-\tfor (i = 0; i < n; i++)\n+\tfor (i = 0; i < nr_buf; i++)\n \t\tfree(buf[i]);\n \n \treturn ret;\n-- \n2.9.3\n\n"},{"id":"316848","messageId":"20170414195219.qmc4w46t7t6brlp4@sigill.intra.peff.net","threadId":"45693","inReplyTo":"20170414192554.26683-2-git@jeffhostetler.com","subject":"Re: [PATCH v4] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-14T19:52:19Z","receivedAt":"2017-04-14T19:52:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 14, 2017 at 07:25:54PM +0000, git@jeffhostetler.com wrote:\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 && are_same_oid(&names[i], &names[i - 1]))\n> +\t\t\tt[i] = t[i - 1];\n> +\t\telse if (i > 1 && are_same_oid(&names[i], &names[i - 2]))\n> +\t\t\tt[i] = t[i - 2];\n> +\t\telse {\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[nr_buf++] = fill_tree_descriptor(t+i, sha1);\n> +\t\t}\n\nThis looks fine to me.\n\nJust musing (and I do not think we need to go further than your patch),\nwe're slowly walking towards an actual object-content cache. The \"buf\"\narray is now essentially a cache of all oids we've loaded, but it\ndoesn't know its sha1s. So we could actually encapsulate all of the\ncaching:\n\n  struct object_cache {\n\t  int nr_entries;\n\t  struct object_cache_entry {\n\t\t  struct object_id oid;\n\t\t  void *data;\n\t  } cache[MAX_UNPACK_TREES];\n  };\n\nand then ask it \"have you seen oid X\" rather than playing games with\nlooking at \"i - 1\". Of course it would have to do a linear search, so\nthe next step is to replace its array with a hashmap.\n\nAnd now suddenly we have a reusable object-content cache that you could\nuse like:\n\n  struct object_cache = {0};\n  for (...) {\n    /* maybe reads fresh, or maybe gets it from the cache */\n    void *data = read_object_data_cached(&oid, &cache);\n  }\n  /* operation done, release the cache */\n  clear_object_cache(&cache);\n\nwhich would work anywhere you expect to load N objects and see some\noverlap.\n\nOf course it would be nicer still if this all just happened\nautomatically behind the scenes of read_object_data(). But it would have\nto keep an _extra_ copy of each object, since the caller expects to be\nable to free it. We'd probably have to return instead a struct with\nbuffer/size in it along with a reference counter.\n\nI don't think any of that is worth it unless there are spots where we\nreally expect there to be a lot of cases where we hit the same objects\nin rapid succession. I don't think there should be, though. Our usual\n\"caching\" mechanism is to create a \"struct object\", which is enough to\nperform most operations (and has a much smaller memory footprint).\n\nSo again, just musing. I think your patch is fine as-is.\n\n-Peff\n"},{"id":"316858","messageId":"90b76976-b14c-c1e2-bdd8-8bf1964bce3e@jeffhostetler.com","threadId":"45693","inReplyTo":"20170414195219.qmc4w46t7t6brlp4@sigill.intra.peff.net","subject":"Re: [PATCH v4] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-14T21:06:05Z","receivedAt":"2017-04-14T21:06:12Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/14/2017 3:52 PM, Jeff King wrote:\n> On Fri, Apr 14, 2017 at 07:25:54PM +0000, git@jeffhostetler.com wrote:\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 && are_same_oid(&names[i], &names[i - 1]))\n>> +\t\t\tt[i] = t[i - 1];\n>> +\t\telse if (i > 1 && are_same_oid(&names[i], &names[i - 2]))\n>> +\t\t\tt[i] = t[i - 2];\n>> +\t\telse {\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[nr_buf++] = fill_tree_descriptor(t+i, sha1);\n>> +\t\t}\n>\n> This looks fine to me.\n>\n> Just musing (and I do not think we need to go further than your patch),\n> we're slowly walking towards an actual object-content cache. The \"buf\"\n> array is now essentially a cache of all oids we've loaded, but it\n> doesn't know its sha1s. So we could actually encapsulate all of the\n> caching:\n>\n>   struct object_cache {\n> \t  int nr_entries;\n> \t  struct object_cache_entry {\n> \t\t  struct object_id oid;\n> \t\t  void *data;\n> \t  } cache[MAX_UNPACK_TREES];\n>   };\n>\n> and then ask it \"have you seen oid X\" rather than playing games with\n> looking at \"i - 1\". Of course it would have to do a linear search, so\n> the next step is to replace its array with a hashmap.\n>\n> And now suddenly we have a reusable object-content cache that you could\n> use like:\n>\n>   struct object_cache = {0};\n>   for (...) {\n>     /* maybe reads fresh, or maybe gets it from the cache */\n>     void *data = read_object_data_cached(&oid, &cache);\n>   }\n>   /* operation done, release the cache */\n>   clear_object_cache(&cache);\n>\n> which would work anywhere you expect to load N objects and see some\n> overlap.\n>\n> Of course it would be nicer still if this all just happened\n> automatically behind the scenes of read_object_data(). But it would have\n> to keep an _extra_ copy of each object, since the caller expects to be\n> able to free it. We'd probably have to return instead a struct with\n> buffer/size in it along with a reference counter.\n>\n> I don't think any of that is worth it unless there are spots where we\n> really expect there to be a lot of cases where we hit the same objects\n> in rapid succession. I don't think there should be, though. Our usual\n> \"caching\" mechanism is to create a \"struct object\", which is enough to\n> perform most operations (and has a much smaller memory footprint).\n>\n> So again, just musing. I think your patch is fine as-is.\n\n\nThanks for your help on this one.\n\nI think before I tried to do a cache at this layer,\nI would like to look at (or have a brave volunteer\nlook at) the recursive tree traversal.  In my Windows\ntree I have 500K directories, so the full recursive\ntree traversal touches them.  My change cuts the ODB\nlookups (on a \"checkout -b\") from 1M to 500K (roughly),\nbut I still have to do 500K strcmp's to get those\nsavings.  What would be nice would be to have maybe\nan alternate callback -- one which knows the peers\n(and everything under them) are equal and let it short\ncut as much as it can.  The alternate version of the\nabove routine would be able to avoid the strcmp's,\nbut I'm guessing that there would also be savings\nwhen we look within a treenode -- the oidcmp's and\nsome of the n-way parallel sub-treenode-iteration.\nI'm just swag'ing here, but there might be something\nhere.\n\nJeff\n\n\n"}]}