{"thread":{"id":"41237","subject":"[PATCH v2] unpack-trees: fix accidentally quadratic behavior","startedAt":"2016-01-21T21:11:48Z","lastAt":"2016-01-21T23:24:20Z","messageCount":3,"participants":["David Turner","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"276511","messageId":"1453410708-23951-1-git-send-email-dturner@twopensource.com","threadId":"41237","inReplyTo":null,"subject":"[PATCH v2] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-21T21:11:48Z","receivedAt":"2016-01-21T21:11:48Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"While unpacking trees (e.g. during git checkout), when we hit a cache\nentry that's past and outside our path, we cut off iteration.\n\nThis provides about a 45% speedup on git checkout between master and\nmaster^20000 on Twitter's monorepo.  Speedup in general will depend on\nrepostitory structure, number of changes, and packfile packing\ndecisions.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\n---\n unpack-trees.c | 13 ++++++++++++-\n 1 file changed, 12 insertions(+), 1 deletion(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 5f541c2..d8e9685 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -695,8 +695,19 @@ static int find_cache_pos(struct traverse_info *info,\n \t\t\t\t++o->cache_bottom;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!ce_in_traverse_path(ce, info))\n+\t\tif (!ce_in_traverse_path(ce, info)) {\n+\t\t\t/*\n+\t\t\t * Check if we can skip future cache checks\n+\t\t\t * (because we're already past all possible\n+\t\t\t * entries in the traverse path).\n+\t\t\t */\n+\t\t\tif (info->prev && info->traverse_path) {\n+\t\t\t\tif (strncmp(ce->name, info->traverse_path,\n+\t\t\t\t\t    info->pathlen) > 0)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n \t\t\tcontinue;\n+\t\t}\n \t\tce_name = ce->name + pfxlen;\n \t\tce_slash = strchr(ce_name, '/');\n \t\tif (ce_slash)\n-- \n2.4.2.749.g730654d-twtrsrc\n"},{"id":"276513","messageId":"20160121213056.GA6664@sigill.intra.peff.net","threadId":"41237","inReplyTo":"1453410708-23951-1-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v2] unpack-trees: fix accidentally quadratic behavior","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-01-21T21:30:56Z","receivedAt":"2016-01-21T21:30:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 21, 2016 at 04:11:48PM -0500, David Turner wrote:\n\n> While unpacking trees (e.g. during git checkout), when we hit a cache\n> entry that's past and outside our path, we cut off iteration.\n> \n> This provides about a 45% speedup on git checkout between master and\n> master^20000 on Twitter's monorepo.  Speedup in general will depend on\n> repostitory structure, number of changes, and packfile packing\n> decisions.\n\nI feel like I'm missing the explanation of the quadratic part. From\nlooking at the patch, my guess is:\n\n  1. We're doing a linear walk in a data structure (a \"struct\n     index_state\").\n\n  2. For each element, we look it up in another structure\n     (\"struct traverse_info\") with a linear search.\n\n     That leaves us at O(m*n), but if we assume both are on the same\n     order of magnitude, that's quadratic.\n\n  3. The fix works by knowing that once a lookup in (2) fails once, it's\n     likely to fail for all the remainder, and we short-cut that case\n     and skip out of (1) completely.\n\nBut that makes me wonder. Aren't we still quadratic in the case that\nce_in_traverse_path() returns true? If so, would we benefit from either:\n\n  a. Improving the complexity of ce_in_traverse_path, to say O(log n),\n     which would give us O(n log n) for the whole operation in all\n     cases?\n\n  b. If both lists are already sorted, maybe doing a list-merge to\n     compare them in O(2n) time?\n\nI'm fairly ignorant of this part of the code, so there's probably a good\nreason why my suggestion is unworkable.\n\n-Peff\n"},{"id":"276525","messageId":"1453418660.16226.53.camel@twopensource.com","threadId":"41237","inReplyTo":"20160121213056.GA6664@sigill.intra.peff.net","subject":"Re: [PATCH v2] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-21T23:24:20Z","receivedAt":"2016-01-21T23:24:20Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Thu, 2016-01-21 at 16:30 -0500, Jeff King wrote:\n> On Thu, Jan 21, 2016 at 04:11:48PM -0500, David Turner wrote:\n> \n> > While unpacking trees (e.g. during git checkout), when we hit a\n> > cache\n> > entry that's past and outside our path, we cut off iteration.\n> > \n> > This provides about a 45% speedup on git checkout between master\n> > and\n> > master^20000 on Twitter's monorepo.  Speedup in general will depend\n> > on\n> > repostitory structure, number of changes, and packfile packing\n> > decisions.\n> \n> I feel like I'm missing the explanation of the quadratic part. From\n> looking at the patch, my guess is:\n> \n>   1. We're doing a linear walk in a data structure (a \"struct\n>      index_state\").\n> \n>   2. For each element, we look it up in another structure\n>      (\"struct traverse_info\") with a linear search.\n> \n>      That leaves us at O(m*n), but if we assume both are on the same\n>      order of magnitude, that's quadratic.\n\nNo, I think, it's the opposite order: we're doing a linear walk over\nthe incoming tree and for each entry, we're calling find_cache_pos.\nfind_cache_pos was doing a linear walk over struct index_state.  But\nthe same algorithmic complexity holds.\n\n>   3. The fix works by knowing that once a lookup in (2) fails once,\n> it's\n>      likely to fail for all the remainder, and we short-cut that case\n>      and skip out of (1) completely.\n> \n> But that makes me wonder. Aren't we still quadratic in the case that\n> ce_in_traverse_path() returns true? \n\nI think that doesn't happen very often, because it requires that the\npaths match up.  \n\n> If so, would we benefit from either:\n> \n>   a. Improving the complexity of ce_in_traverse_path, to say O(log\n> n),\n>      which would give us O(n log n) for the whole operation in all\n>      cases?\n> \n>   b. If both lists are already sorted, maybe doing a list-merge to\n>      compare them in O(2n) time?\n\n(b) appears to be now (roughly) what we're now doing.\n\n> I'm fairly ignorant of this part of the code, so there's probably a\n> good\n> reason why my suggestion is unworkable.\n\nI am also quite ignorant of this part of the code; I just looked at\nperf and did some simple counting.\n"}]}