{"thread":{"id":"41232","subject":"[PATCH] unpack-trees: fix accidentally quadratic behavior","startedAt":"2016-01-21T04:05:56Z","lastAt":"2016-01-21T21:06:18Z","messageCount":6,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"276483","messageId":"1453349156-12553-1-git-send-email-dturner@twopensource.com","threadId":"41232","inReplyTo":null,"subject":"[PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-21T04:05:56Z","receivedAt":"2016-01-21T04:05:56Z","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 \n---\n unpack-trees.c | 19 ++++++++++++++++++-\n 1 file changed, 18 insertions(+), 1 deletion(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 5f541c2..b18a611 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -695,8 +695,25 @@ 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\tint prefix_cmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n+\t\t\t\tif (prefix_cmp > 0)\n+\t\t\t\t\tbreak;\n+\t\t\t\telse if (prefix_cmp == 0 &&\n+\t\t\t\t\t ce_namelen(ce) >= info->pathlen &&\n+\t\t\t\t\t strcmp(ce->name + info->pathlen,\n+\t\t\t\t\t\t info->name.path) > 0) {\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\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":"276487","messageId":"xmqq60ynzfyq.fsf@gitster.mtv.corp.google.com","threadId":"41232","inReplyTo":"1453349156-12553-1-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-01-21T04:58:21Z","receivedAt":"2016-01-21T04:58:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\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>\n> Signed-off-by: David Turner \n> ---\n\nI haven't thought things through, but does this get fooled by the\nsomewhat strange ordering rules of tree entries (i.e. a subtree\nsorts as if its name is suffixed with a '/' in a tree object)?\n\nOther than that, I like this. \"We know the list is sorted, and\nafter seeing this entry we know there is nothing that will match\" is\nan obvious optimization that we already use elsewhere.\n\nThanks.\n\n> unpack-trees.c | 19 ++++++++++++++++++-\n> 1 file changed, 18 insertions(+), 1 deletion(-)\n>\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 5f541c2..b18a611 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -695,8 +695,25 @@ 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\tint prefix_cmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n> +\t\t\t\tif (prefix_cmp > 0)\n> +\t\t\t\t\tbreak;\n> +\t\t\t\telse if (prefix_cmp == 0 &&\n> +\t\t\t\t\t ce_namelen(ce) >= info->pathlen &&\n> +\t\t\t\t\t strcmp(ce->name + info->pathlen,\n> +\t\t\t\t\t\t info->name.path) > 0) {\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\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"},{"id":"276502","messageId":"1453403398.16226.40.camel@twopensource.com","threadId":"41232","inReplyTo":"xmqq60ynzfyq.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-21T19:09:58Z","receivedAt":"2016-01-21T19:09:58Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote:\n> David Turner writes:\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> > Signed-off-by: David Turner \n> > ---\n> \n> I haven't thought things through, but does this get fooled by the\n> somewhat strange ordering rules of tree entries (i.e. a subtree\n> sorts as if its name is suffixed with a '/' in a tree object)?\n> \n> Other than that, I like this. \"We know the list is sorted, and\n> after seeing this entry we know there is nothing that will match\" is\n> an obvious optimization that we already use elsewhere.\n> \n> Thanks.\n\nI think this is correct, because we first do the more complicated check\n(ce_in_traverse_path), and only check the ordering once that has\nfailed. The tests all pass, so this should be good.\n"},{"id":"276505","messageId":"xmqqpowuyall.fsf@gitster.mtv.corp.google.com","threadId":"41232","inReplyTo":"1453403398.16226.40.camel@twopensource.com","subject":"Re: [PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-01-21T19:51:50Z","receivedAt":"2016-01-21T19:51:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\n\n> On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote:\n>> David Turner writes:\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>> > Signed-off-by: David Turner \n>> > ---\n>> \n>> I haven't thought things through, but does this get fooled by the\n>> somewhat strange ordering rules of tree entries (i.e. a subtree\n>> sorts as if its name is suffixed with a '/' in a tree object)?\n>> \n>> Other than that, I like this. \"We know the list is sorted, and\n>> after seeing this entry we know there is nothing that will match\" is\n>> an obvious optimization that we already use elsewhere.\n>> \n>> Thanks.\n>\n> I think this is correct, because we first do the more complicated check\n> (ce_in_traverse_path), and only check the ordering once that has\n> failed. \n\nBut the patch does this:\n\n> +\t\t\tif (info->prev && info->traverse_path) {\n> +\t\t\t\tint prefix_cmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n> +\t\t\t\tif (prefix_cmp > 0)\n> +\t\t\t\t\tbreak;\n> +\t\t\t\telse if (prefix_cmp == 0 &&\n> +\t\t\t\t\t ce_namelen(ce) >= info->pathlen &&\n> +\t\t\t\t\t strcmp(ce->name + info->pathlen,\n> +\t\t\t\t\t\t info->name.path) > 0) {\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> +\t\t\t}\n> \t\t\tcontinue;\n\nThe first break is correct, but I am not sure about the \"else if\"\npart. Shouldn't it be doing something similar to the logic to \"keep\nlooking\" that talks about \"t-i\", \"t\" and \"t/a\" at the end of the\nloop?\n\n> The tests all pass, so this should be good.\n\nPlease don't ever say that again. The existing tests do not cover\nall corner cases, and they fundamentally cannot cover the corner\ncases future changes may introduce.\n\nSaying \"Even test X breaks, so it is clearly broken. Why did you\nsend it out without testing?\" is OK, though.\n"},{"id":"276509","messageId":"1453409984.16226.46.camel@twopensource.com","threadId":"41232","inReplyTo":"xmqqpowuyall.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-21T20:59:44Z","receivedAt":"2016-01-21T20:59:44Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Thu, 2016-01-21 at 11:51 -0800, Junio C Hamano wrote:\n> David Turner writes:\n> \n> > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote:\n> > > David Turner writes:\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\n> > > > master\n> > > > and\n> > > > master^20000 on Twitter's monorepo. Speedup in general will\n> > > > depend\n> > > > on\n> > > > repostitory structure, number of changes, and packfile packing\n> > > > decisions.\n> > > > \n> > > > Signed-off-by: David Turner \n> > > > ---\n> > > \n> > > I haven't thought things through, but does this get fooled by the\n> > > somewhat strange ordering rules of tree entries (i.e. a subtree\n> > > sorts as if its name is suffixed with a '/' in a tree object)?\n> > > \n> > > Other than that, I like this. \"We know the list is sorted, and\n> > > after seeing this entry we know there is nothing that will match\"\n> > > is\n> > > an obvious optimization that we already use elsewhere.\n> > > \n> > > Thanks.\n> > \n> > I think this is correct, because we first do the more complicated\n> > check\n> > (ce_in_traverse_path), and only check the ordering once that has\n> > failed. \n> \n> But the patch does this:\n> \n> > +\t\t\tif (info->prev && info->traverse_path) {\n> > +\t\t\t\tint prefix_cmp = strncmp(ce->name,\n> > info->traverse_path, info->pathlen);\n> > +\t\t\t\tif (prefix_cmp > 0)\n> > +\t\t\t\t\tbreak;\n> > +\t\t\t\telse if (prefix_cmp == 0 &&\n> > +\t\t\t\t\t ce_namelen(ce) >= info\n> > ->pathlen &&\n> > +\t\t\t\t\t strcmp(ce->name + info\n> > ->pathlen,\n> > +\t\t\t\t\t\t info->name.path)\n> > > 0) {\n> > +\t\t\t\t\tbreak;\n> > +\t\t\t\t}\n> > +\t\t\t}\n> > \t\t\tcontinue;\n> \n> The first break is correct, but I am not sure about the \"else if\"\n> part. Shouldn't it be doing something similar to the logic to \"keep\n> looking\" that talks about \"t-i\", \"t\" and \"t/a\" at the end of the\n> loop?\n\nRather than doing more complicated logic, let's just do the first\ncheck; it seems about as fast for our repo, and I think will usually be\nso. does that seem reasonable to you?\n\n> > The tests all pass, so this should be good.\n> \n> Please don't ever say that again. \n\nOK.\n"},{"id":"276510","messageId":"xmqqbn8ey75h.fsf@gitster.mtv.corp.google.com","threadId":"41232","inReplyTo":"1453409984.16226.46.camel@twopensource.com","subject":"Re: [PATCH] unpack-trees: fix accidentally quadratic behavior","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-01-21T21:06:18Z","receivedAt":"2016-01-21T21:06:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\n\n>> The first break is correct, but I am not sure about the \"else if\"\n>> part. Shouldn't it be doing something similar to the logic to \"keep\n>> looking\" that talks about \"t-i\", \"t\" and \"t/a\" at the end of the\n>> loop?\n>\n> Rather than doing more complicated logic, let's just do the first\n> check; it seems about as fast for our repo, and I think will usually be\n> so. does that seem reasonable to you?\n\nVery reasonable. I was mostly afraid of leaving the loop\nprematurely and giving a wrong answer to the caller.\n"}]}