{"thread":{"id":"45735","subject":"[PATCH v1] diffcore-rename: speed up register_rename_src","startedAt":"2017-04-18T19:44:43Z","lastAt":"2017-04-21T01:20:02Z","messageCount":13,"participants":["git@jeffhostetler.com","Jeff King","Junio C Hamano","Johannes Schindelin","Jeff Hostetler"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"317133","messageId":"20170418194421.22453-2-git@jeffhostetler.com","threadId":"45735","inReplyTo":"20170418194421.22453-1-git@jeffhostetler.com","subject":"[PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-18T19:44:21Z","receivedAt":"2017-04-18T19:44:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach register_rename_src() to see if new file pair\ncan simply be appended to the rename_src[] array before\nperforming the binary search to find the proper insertion\npoint.\n\nThis is a performance optimization.  This routine is called\nduring run_diff_files in status and the caller is iterating\nover the sorted index, so we should expect to be able to\nappend in the normal case.  The existing insert logic is\npreserved so we don't have to assume that, but simply take\nadvantage of it if possible.\n\nUsing t/perf/p0005-status.h (from a parallel patch series),\nwe get the following improvement on a 4.2M file repo:\n\nTest                                            HEAD~1               HEAD\n0005.2: read-tree status br_ballast (4194305)   59.14(31.85+18.79)   55.48(28.52+20.71) -6.2%\n\nOn a 1M file repo:\nTest                                            HEAD~1            HEAD\n0005.2: read-tree status br_ballast (1000001)   8.20(4.82+3.35)   7.91(4.57+3.27) -3.5%\n\nOn a smaller repo, like linux.git (58K files), results are masked\nby normal I/O variance.\n\nTest                                          HEAD~1            HEAD\n0005.2: read-tree status br_ballast (57994)   0.43(0.30+0.13)   0.42(0.31+0.12) -2.3%\n0005.2: read-tree status br_ballast (57994)   0.42(0.32+0.09)   0.43(0.34+0.10) +2.4%\n0005.2: read-tree status br_ballast (57994)   0.44(0.33+0.10)   0.42(0.26+0.16) -4.5%\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n diffcore-rename.c | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex f7444c8..543a409 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -81,6 +81,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \n \tfirst = 0;\n \tlast = rename_src_nr;\n+\n+\tif (last > 0) {\n+\t\tstruct diff_rename_src *src = &(rename_src[last-1]);\n+\t\tint cmp = strcmp(one->path, src->p->one->path);\n+\t\tif (!cmp)\n+\t\t\treturn src;\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = last;\n+\t\t\tgoto append_it;\n+\t\t}\n+\t}\n+\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n \t\tstruct diff_rename_src *src = &(rename_src[next]);\n@@ -94,6 +106,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \t\tfirst = next+1;\n \t}\n \n+append_it:\n \t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n \trename_src_nr++;\n-- \n2.9.3\n\n"},{"id":"317134","messageId":"20170418194421.22453-1-git@jeffhostetler.com","threadId":"45735","inReplyTo":null,"subject":"[PATCH v1] diffcore-rename speedup","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-18T19:44:20Z","receivedAt":"2017-04-18T19:44:48Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nHere is another micro-optimization for very large repositories.\nSpeed up register_rename_src() in diffcore-rename.c\n\nJeff Hostetler (1):\n  diffcore-rename: speed up register_rename_src\n\n diffcore-rename.c | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\n-- \n2.9.3\n\n"},{"id":"317167","messageId":"20170419013214.q35jarvmk5jhqdyi@sigill.intra.peff.net","threadId":"45735","inReplyTo":"20170418194421.22453-2-git@jeffhostetler.com","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-19T01:32:15Z","receivedAt":"2017-04-19T01:32:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 18, 2017 at 07:44:21PM +0000, git@jeffhostetler.com wrote:\n\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Teach register_rename_src() to see if new file pair\n> can simply be appended to the rename_src[] array before\n> performing the binary search to find the proper insertion\n> point.\n\nI guess your perf results show some minor improvement. But I suspect\nthis is because your synthetic repo does not resemble the real world\nvery much. You're saving a few strcmps, but for each of those files\nyou're potentially going to have actually zlib inflate the object\ncontents and do similarity analysis.\n\nSo \"absurd number of files doing 100% exact renames\" is the absolute\nbest case, and it saves a few percent.\n\nI dunno. It is not that much code _here_, but I'm not excited about the\nprospect of sprinkling this same \"check the last one\" optimization all\nover the code base. I wonder if there's some way to generalize it.\n\n-Peff\n"},{"id":"317176","messageId":"xmqqd1c9cdzi.fsf@gitster.mtv.corp.google.com","threadId":"45735","inReplyTo":"20170419013214.q35jarvmk5jhqdyi@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-19T02:45:05Z","receivedAt":"2017-04-19T02:45:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Apr 18, 2017 at 07:44:21PM +0000, git@jeffhostetler.com wrote:\n>\n>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>> \n>> Teach register_rename_src() to see if new file pair\n>> can simply be appended to the rename_src[] array before\n>> performing the binary search to find the proper insertion\n>> point.\n>\n> I guess your perf results show some minor improvement. But I suspect\n> this is because your synthetic repo does not resemble the real world\n> very much. You're saving a few strcmps, but for each of those files\n> you're potentially going to have actually zlib inflate the object\n> contents and do similarity analysis.\n>\n> So \"absurd number of files doing 100% exact renames\" is the absolute\n> best case, and it saves a few percent.\n>\n> I dunno. It is not that much code _here_, but I'm not excited about the\n> prospect of sprinkling this same \"check the last one\" optimization all\n> over the code base. I wonder if there's some way to generalize it.\n\nWhen adding many things, we often just append and then sort at the\nend after we finished adding.  I wonder if recent \"check the last\none and append\" optimization beats that strategy.\n"},{"id":"317180","messageId":"20170419025608.xy5nvso6k6lb5z7g@sigill.intra.peff.net","threadId":"45735","inReplyTo":"xmqqd1c9cdzi.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-19T02:56:08Z","receivedAt":"2017-04-19T02:56:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 18, 2017 at 07:45:05PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > On Tue, Apr 18, 2017 at 07:44:21PM +0000, git@jeffhostetler.com wrote:\n> >\n> >> From: Jeff Hostetler <jeffhost@microsoft.com>\n> >> \n> >> Teach register_rename_src() to see if new file pair\n> >> can simply be appended to the rename_src[] array before\n> >> performing the binary search to find the proper insertion\n> >> point.\n> >\n> > I guess your perf results show some minor improvement. But I suspect\n> > this is because your synthetic repo does not resemble the real world\n> > very much. You're saving a few strcmps, but for each of those files\n> > you're potentially going to have actually zlib inflate the object\n> > contents and do similarity analysis.\n> >\n> > So \"absurd number of files doing 100% exact renames\" is the absolute\n> > best case, and it saves a few percent.\n> >\n> > I dunno. It is not that much code _here_, but I'm not excited about the\n> > prospect of sprinkling this same \"check the last one\" optimization all\n> > over the code base. I wonder if there's some way to generalize it.\n> \n> When adding many things, we often just append and then sort at the\n> end after we finished adding.  I wonder if recent \"check the last\n> one and append\" optimization beats that strategy.\n\nThe big question is whether we need to detect duplicates while we're\nappending to the list, which is hard on an unsorted list.  In this\nfunction, at least, we do detect when the path already exists and return\nthe existing entry. I'm not sure under what circumstances we would see\nsuch a duplicate, though, as each filename should appear only once in\nthe tree diff. I would think.\n\nDoing:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex f7444c86b..56a493d97 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -86,7 +86,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n \t\tstruct diff_rename_src *src = &(rename_src[next]);\n \t\tint cmp = strcmp(one->path, src->p->one->path);\n \t\tif (!cmp)\n-\t\t\treturn src;\n+\t\t\tdie(\"BUG: duplicate rename src: %s\", one->path);\n \t\tif (cmp < 0) {\n \t\t\tlast = next;\n \t\t\tcontinue;\n\npasses the test suite, at least. :)\n\n-Peff\n"},{"id":"317182","messageId":"20170419031839.m2zgwywa2soejiqk@sigill.intra.peff.net","threadId":"45735","inReplyTo":"20170419025608.xy5nvso6k6lb5z7g@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-19T03:18:39Z","receivedAt":"2017-04-19T03:18:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 18, 2017 at 10:56:08PM -0400, Jeff King wrote:\n\n> > When adding many things, we often just append and then sort at the\n> > end after we finished adding.  I wonder if recent \"check the last\n> > one and append\" optimization beats that strategy.\n> \n> The big question is whether we need to detect duplicates while we're\n> appending to the list, which is hard on an unsorted list.  In this\n> function, at least, we do detect when the path already exists and return\n> the existing entry. I'm not sure under what circumstances we would see\n> such a duplicate, though, as each filename should appear only once in\n> the tree diff. I would think.\n> \n> Doing:\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index f7444c86b..56a493d97 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -86,7 +86,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n>  \t\tstruct diff_rename_src *src = &(rename_src[next]);\n>  \t\tint cmp = strcmp(one->path, src->p->one->path);\n>  \t\tif (!cmp)\n> -\t\t\treturn src;\n> +\t\t\tdie(\"BUG: duplicate rename src: %s\", one->path);\n>  \t\tif (cmp < 0) {\n>  \t\t\tlast = next;\n>  \t\t\tcontinue;\n> \n> passes the test suite, at least. :)\n\nMaybe relevant: 4d6be03b9 (diffcore-rename: avoid processing duplicate\ndestinations, 2015-02-26). That's on the dst side, but possibly we\nshould do something similar on the src side.\n\nBTW, I think the return value from register_rename_src() is\nquestionable. It points to a \"struct diff_rename_src\" that may be\nreallocated by further calls to the function. Fortunately nobody\nactually looks at it, let alone saves it, so there's no bug.\n\nWe may want to convert that return value to a void (if not just return\nan int for \"hey, there's a duplicate\", like we do for add_rename_dst()).\n\nAlso, presumably that function could learn the same \"check the last one\"\ntrick that the src side does. Which leads me back to \"surely we can\ngeneralize this\". I don't think bsearch() is quite what we want, because\nits interface doesn't tell us where to put the item when it isn't found.\nBut I think we could make a general bsearch-like function that has\nsimilar semantics to index_name_pos(), with its negative-integer return.\n\nAnd then that would be a general lookup function, and we could easily\nbuild a general \"look up and add\" function around that. And the \"check\nthe last one\" optimization would go in the latter.\n\n-Peff\n"},{"id":"317324","messageId":"alpine.DEB.2.20.1704201231350.3480@virtualbox","threadId":"45735","inReplyTo":"20170419013214.q35jarvmk5jhqdyi@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-04-20T10:40:52Z","receivedAt":"2017-04-20T10:41:20Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Tue, 18 Apr 2017, Jeff King wrote:\n\n> On Tue, Apr 18, 2017 at 07:44:21PM +0000, git@jeffhostetler.com wrote:\n> \n> > From: Jeff Hostetler <jeffhost@microsoft.com>\n> > \n> > Teach register_rename_src() to see if new file pair can simply be\n> > appended to the rename_src[] array before performing the binary search\n> > to find the proper insertion point.\n> \n> I guess your perf results show some minor improvement. But I suspect\n> this is because your synthetic repo does not resemble the real world\n> very much.\n\nPlease note that the synthetic test repo was added *after* coming up with\nthe patch, *after* performance benchmarking on a certain really big\nrepository (it is not hard to guess what use case we are optimizing,\nright?).\n\nIn that light, I would like to register the fact that Jeff's performance\nwork is trying to improve a very real world, that of more than 2,000\ndevelopers in our company [*1*].\n\nCiao,\nJohannes\n\nFootnote *1*: https://twitter.com/GabeAul/status/846189637945110528\n"},{"id":"317346","messageId":"40228c69-7946-3ef1-35de-4cea9b0312e4@jeffhostetler.com","threadId":"45735","inReplyTo":"20170419031839.m2zgwywa2soejiqk@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-20T14:00:04Z","receivedAt":"2017-04-20T14:00:18Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/18/2017 11:18 PM, Jeff King wrote:\n> On Tue, Apr 18, 2017 at 10:56:08PM -0400, Jeff King wrote:\n>\n>>> When adding many things, we often just append and then sort at the\n>>> end after we finished adding.  I wonder if recent \"check the last\n>>> one and append\" optimization beats that strategy.\n>>\n>> The big question is whether we need to detect duplicates while we're\n>> appending to the list, which is hard on an unsorted list.  In this\n>> function, at least, we do detect when the path already exists and return\n>> the existing entry. I'm not sure under what circumstances we would see\n>> such a duplicate, though, as each filename should appear only once in\n>> the tree diff. I would think.\n>>\n>> Doing:\n>>\n>> diff --git a/diffcore-rename.c b/diffcore-rename.c\n>> index f7444c86b..56a493d97 100644\n>> --- a/diffcore-rename.c\n>> +++ b/diffcore-rename.c\n>> @@ -86,7 +86,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n>>  \t\tstruct diff_rename_src *src = &(rename_src[next]);\n>>  \t\tint cmp = strcmp(one->path, src->p->one->path);\n>>  \t\tif (!cmp)\n>> -\t\t\treturn src;\n>> +\t\t\tdie(\"BUG: duplicate rename src: %s\", one->path);\n>>  \t\tif (cmp < 0) {\n>>  \t\t\tlast = next;\n>>  \t\t\tcontinue;\n>>\n>> passes the test suite, at least. :)\n>\n> Maybe relevant: 4d6be03b9 (diffcore-rename: avoid processing duplicate\n> destinations, 2015-02-26). That's on the dst side, but possibly we\n> should do something similar on the src side.\n>\n> BTW, I think the return value from register_rename_src() is\n> questionable. It points to a \"struct diff_rename_src\" that may be\n> reallocated by further calls to the function. Fortunately nobody\n> actually looks at it, let alone saves it, so there's no bug.\n>\n> We may want to convert that return value to a void (if not just return\n> an int for \"hey, there's a duplicate\", like we do for add_rename_dst()).\n>\n> Also, presumably that function could learn the same \"check the last one\"\n> trick that the src side does. Which leads me back to \"surely we can\n> generalize this\". I don't think bsearch() is quite what we want, because\n> its interface doesn't tell us where to put the item when it isn't found.\n> But I think we could make a general bsearch-like function that has\n> similar semantics to index_name_pos(), with its negative-integer return.\n>\n> And then that would be a general lookup function, and we could easily\n> build a general \"look up and add\" function around that. And the \"check\n> the last one\" optimization would go in the latter.\n\n\nI do see your point.  And I do get tired of littering the code with\n\"check the last before binary searching\" tricks.  It would be nice\nif we could better isolate this.  I've tried to follow the path of\nleast change/damage -- don't change functionality, but just short-cut\nwhen possible, so the patches I've pushed up this month have mostly\ntaken that form.\n\nAnd you're right, the gains on this particular patch are relatively\nminor and it is a bit of a contrived case (lots of renames??), but\nit did come up while testing on the Windows repo.  It doesn't happen\noften, but it did happen.\n\nSo I'm OK with rejecting this one.\n\nPerhaps the thing to learn from this (and the other ones) is that\nwe have lots of places where we are building a sorted list by\niterating over a sorted list.  The insert routines are general\npurpose and cannot assume this, so they search first.  Perhaps it\nwould be clearer to have independent _append and _insert functions\nand have the caller explicitly call the appropriate one.  The mainline\niterations on the existing index could just call the _append form\nand never have to worry about searching or the negative-integer\nreturn trick.  Whereas, the random iterations (such as on the\ncommand's arg list), would always call the _insert form.\n\nJeff\n\n"},{"id":"317349","messageId":"20170420155003.cugkol6rbv25lpdi@sigill.intra.peff.net","threadId":"45735","inReplyTo":"alpine.DEB.2.20.1704201231350.3480@virtualbox","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-20T15:50:03Z","receivedAt":"2017-04-20T15:50:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 20, 2017 at 12:40:52PM +0200, Johannes Schindelin wrote:\n\n> > > Teach register_rename_src() to see if new file pair can simply be\n> > > appended to the rename_src[] array before performing the binary search\n> > > to find the proper insertion point.\n> > \n> > I guess your perf results show some minor improvement. But I suspect\n> > this is because your synthetic repo does not resemble the real world\n> > very much.\n> \n> Please note that the synthetic test repo was added *after* coming up with\n> the patch, *after* performance benchmarking on a certain really big\n> repository (it is not hard to guess what use case we are optimizing,\n> right?).\n> \n> In that light, I would like to register the fact that Jeff's performance\n> work is trying to improve a very real world, that of more than 2,000\n> developers in our company [*1*].\n\nSure; I didn't think it came out of thin air. What are the benchmarks on\nthis real-world repository, then?\n\nSpecifically, it looks like this optimization isn't really about the\nnumber of files in the repository so much as the number of\nadditions/deletions in a particular diff (which is what become rename\nsources and destinations).\n\nIs it common to add or delete 4 million tiny files and then run \"git\nstatus\"?\n\nNote that I think the optimization probably _is_ worth doing in the\ngeneral case. These \"is it sorted\" tradeoffs can backfire if we\nsometimes get unsorted input, but I don't think that would ever be the\ncase here. My main complaint is not that it's not worth doing, but that\nI'm not excited about sprinkling these checks ad-hoc throughout the code\nbase.\n\n-Peff\n"},{"id":"317350","messageId":"20170420161359.haolllw4ac5jjqx4@sigill.intra.peff.net","threadId":"45735","inReplyTo":"40228c69-7946-3ef1-35de-4cea9b0312e4@jeffhostetler.com","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-20T16:13:59Z","receivedAt":"2017-04-20T16:14:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 20, 2017 at 10:00:04AM -0400, Jeff Hostetler wrote:\n\n> Perhaps the thing to learn from this (and the other ones) is that\n> we have lots of places where we are building a sorted list by\n> iterating over a sorted list.  The insert routines are general\n> purpose and cannot assume this, so they search first.  Perhaps it\n> would be clearer to have independent _append and _insert functions\n> and have the caller explicitly call the appropriate one.  The mainline\n> iterations on the existing index could just call the _append form\n> and never have to worry about searching or the negative-integer\n> return trick.  Whereas, the random iterations (such as on the\n> command's arg list), would always call the _insert form.\n\nYes. I'd be much happier if your patch was flipping between two\ngeneral-purpose insertion functions. And if that same trick was used on\nthe dst side.\n\nOr even, given that this these functions are called from a single\nlocation that has sorted input, the binary search was just replaced\ncompletely with an append combined with a sort-check.\n\nThat's not the minimal change you were going for, but I think the end\nresult is simpler and more consistent.\n\nE.g., something like this:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex f7444c86b..a5c017198 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -43,26 +43,20 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n }\n \n /*\n- * Returns 0 on success, -1 if we found a duplicate.\n+ * Returns 0 on success, -1 if we found a duplicate or a sorting problem.\n  */\n static int add_rename_dst(struct diff_filespec *two)\n {\n-\tint first = find_rename_dst(two);\n-\n-\tif (first >= 0)\n+\tif (rename_dst_nr > 0 &&\n+\t    strcmp(two->path, rename_dst[rename_dst_nr - 1].two->path) <= 0)\n \t\treturn -1;\n-\tfirst = -first - 1;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n+\trename_dst[rename_dst_nr].two = alloc_filespec(two->path);\n+\tfill_filespec(rename_dst[rename_dst_nr].two,\n+\t\t      two->oid.hash, two->oid_valid, two->mode);\n+\trename_dst[rename_dst_nr].pair = NULL;\n \trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n-\t\tmemmove(rename_dst + first + 1, rename_dst + first,\n-\t\t\t(rename_dst_nr - first - 1) * sizeof(*rename_dst));\n-\trename_dst[first].two = alloc_filespec(two->path);\n-\tfill_filespec(rename_dst[first].two, two->oid.hash, two->oid_valid,\n-\t\t      two->mode);\n-\trename_dst[first].pair = NULL;\n \treturn 0;\n }\n \n@@ -73,36 +67,17 @@ static struct diff_rename_src {\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n+static int register_rename_src(struct diff_filepair *p)\n {\n-\tint first, last;\n-\tstruct diff_filespec *one = p->one;\n-\tunsigned short score = p->score;\n-\n-\tfirst = 0;\n-\tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n-\t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->p->one->path);\n-\t\tif (!cmp)\n-\t\t\treturn src;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n+\tif (rename_src_nr > 0 &&\n+\t    strcmp(p->one->path, rename_src[rename_src_nr - 1].p->one->path) <= 0)\n+\t\treturn -1;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n+\trename_src[rename_src_nr].p = p;\n+\trename_src[rename_src_nr].score = p->score;\n \trename_src_nr++;\n-\tif (first < rename_src_nr)\n-\t\tmemmove(rename_src + first + 1, rename_src + first,\n-\t\t\t(rename_src_nr - first - 1) * sizeof(*rename_src));\n-\trename_src[first].p = p;\n-\trename_src[first].score = score;\n-\treturn &(rename_src[first]);\n+\treturn 0;\n }\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n@@ -468,7 +443,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tcontinue;\n \t\t\telse if (add_rename_dst(p->two) < 0) {\n \t\t\t\twarning(\"skipping rename detection, detected\"\n-\t\t\t\t\t\" duplicate destination '%s'\",\n+\t\t\t\t\t\" duplicate or out-of-order destination '%s'\",\n \t\t\t\t\tp->two->path);\n \t\t\t\tgoto cleanup;\n \t\t\t}\n@@ -486,7 +461,12 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (p->broken_pair && !p->score)\n \t\t\t\tp->one->rename_used++;\n-\t\t\tregister_rename_src(p);\n+\t\t\tif (register_rename_src(p) < 0) {\n+\t\t\t\twarning(\"skipping rename detection, detected\"\n+\t\t\t\t\t\" duplicate or out-of-order source '%s'\",\n+\t\t\t\t\tp->one->path);\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n \t\t}\n \t\telse if (detect_rename == DIFF_DETECT_COPY) {\n \t\t\t/*\n@@ -494,7 +474,12 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t * one, to indicate ourselves as a user.\n \t\t\t */\n \t\t\tp->one->rename_used++;\n-\t\t\tregister_rename_src(p);\n+\t\t\tif (register_rename_src(p) < 0) {\n+\t\t\t\twarning(\"skipping rename detection, detected\"\n+\t\t\t\t\t\" duplicate or out-of-order source '%s'\",\n+\t\t\t\t\tp->one->path);\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n"},{"id":"317361","messageId":"4d400fb6-201e-e1ba-cc3a-935951ab3e14@jeffhostetler.com","threadId":"45735","inReplyTo":"20170420161359.haolllw4ac5jjqx4@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-20T18:08:46Z","receivedAt":"2017-04-20T18:08:53Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/20/2017 12:13 PM, Jeff King wrote:\n> On Thu, Apr 20, 2017 at 10:00:04AM -0400, Jeff Hostetler wrote:\n>\n>> Perhaps the thing to learn from this (and the other ones) is that\n>> we have lots of places where we are building a sorted list by\n>> iterating over a sorted list.  The insert routines are general\n>> purpose and cannot assume this, so they search first.  Perhaps it\n>> would be clearer to have independent _append and _insert functions\n>> and have the caller explicitly call the appropriate one.  The mainline\n>> iterations on the existing index could just call the _append form\n>> and never have to worry about searching or the negative-integer\n>> return trick.  Whereas, the random iterations (such as on the\n>> command's arg list), would always call the _insert form.\n>\n> Yes. I'd be much happier if your patch was flipping between two\n> general-purpose insertion functions. And if that same trick was used on\n> the dst side.\n>\n> Or even, given that this these functions are called from a single\n> location that has sorted input, the binary search was just replaced\n> completely with an append combined with a sort-check.\n>\n> That's not the minimal change you were going for, but I think the end\n> result is simpler and more consistent.\n\nOK, let me take a stab at something like that and\nsee where it takes me.\n\nWRT your earlier comment about how often we add or delete 4M\nfiles and then run status.  The use case that started this was a\n1% sparse-checkout followed by a read-tree (which reset the\nskip-worktree bits) and then status (which thought 99% of the\nworktree had been deleted or maybe renamed).  There are probably\nother ways to get into this state, but that's how this started.\nThe more subtle point is that -- for these obscenely large\nvalues of n -- any time I see an O(n log n) operation that could\nor should be O(n), I want to stop and look at it.\n\n"},{"id":"317363","messageId":"20170420183455.y5oz3hspz3v2g6yr@sigill.intra.peff.net","threadId":"45735","inReplyTo":"4d400fb6-201e-e1ba-cc3a-935951ab3e14@jeffhostetler.com","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-20T18:34:55Z","receivedAt":"2017-04-20T18:35:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 20, 2017 at 02:08:46PM -0400, Jeff Hostetler wrote:\n\n> > That's not the minimal change you were going for, but I think the end\n> > result is simpler and more consistent.\n> \n> OK, let me take a stab at something like that and\n> see where it takes me.\n\nThanks.\n\nI set the patch as a lump, but I think there are a few things going on\nthere:\n\n  - the return value of register_rename_src() is actively dangerous (it\n    points to memory which may be reallocated), so it's good that it\n    goes away in favor of an \"int\"\n\n  - we already refuse to do rename detection when there are duplicate\n    dsts. This adds the same for srcs. I don't know if the same safety\n    rules apply there, but it certainly seems like a reasonable and\n    consistent precaution to say \"this tree looks broken, let's skip\n    rename detection\". But it does mean a potential change in\n    functionality in that corner case.\n\n  - this patch probably adds \"unsorted tree\" to the list of breakages\n    that would cause us to skip rename detection. I don't know if that's\n    actually possible in practice (i.e., do we end up sorting the\n    diffq elsewhere anyway?). I also wondered if it might run afoul of\n    diffcore_order(), but that is applied after rename detection, so\n    we're OK.\n\n> WRT your earlier comment about how often we add or delete 4M\n> files and then run status.  The use case that started this was a\n> 1% sparse-checkout followed by a read-tree (which reset the\n> skip-worktree bits) and then status (which thought 99% of the\n> worktree had been deleted or maybe renamed).  There are probably\n> other ways to get into this state, but that's how this started.\n\nRight, that sounds plausible. I guess I just wondered if this is\nsomething an average developer runs daily, or something that they would\nrun into once a year. Shaving 4s of CPU off of a once-a-year operation\nis less exciting.\n\n> The more subtle point is that -- for these obscenely large\n> values of n -- any time I see an O(n log n) operation that could\n> or should be O(n), I want to stop and look at it.\n\nHeh. I spent a fair bit of time in Git's past turning O(n^2) operations\ninto O(n log n), so I feel your pain. I do think it's important to pay\nattention to whole-operation numbers, though. Quite often you have an\nO(n log n) with a small constant (like a single strcmp) coupled with\nsomething linear but with a huge constant (like loading blob contents),\nand micro-optimizations to the former get drowned out by the latter.\n\n-Peff\n"},{"id":"317444","messageId":"xmqqtw5i7e16.fsf@gitster.mtv.corp.google.com","threadId":"45735","inReplyTo":"20170420183455.y5oz3hspz3v2g6yr@sigill.intra.peff.net","subject":"Re: [PATCH v1] diffcore-rename: speed up register_rename_src","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-21T01:19:49Z","receivedAt":"2017-04-21T01:20:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   - this patch probably adds \"unsorted tree\" to the list of breakages\n>     that would cause us to skip rename detection. I don't know if that's\n>     actually possible in practice (i.e., do we end up sorting the\n>     diffq elsewhere anyway?). I also wondered if it might run afoul of\n>     diffcore_order(), but that is applied after rename detection, so\n>     we're OK.\n\nOne of the frontends (I think it was diff-index) couldn't generate\nsorted output (which is input to diffcore-* machinery) but I think\ndiffq is sorted before getting passed to the diffcore-* machinery in\nthat codepath, so we should be also OK on that front.\n"}]}