{"thread":{"id":"52607","subject":"[PATCH] unpack-trees: correctly compute result count","startedAt":"2020-01-10T01:59:35Z","lastAt":"2020-01-10T19:33:34Z","messageCount":5,"participants":["Derrick Stolee via GitGitGadget","Jeff King","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"389561","messageId":"pull.520.git.1578621570180.gitgitgadget@gmail.com","threadId":"52607","inReplyTo":null,"subject":"[PATCH] unpack-trees: correctly compute result count","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-01-10T01:59:30Z","receivedAt":"2020-01-10T01:59:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The clear_ce_flags_dir() method processes the cache entries within\na common directory. The returned int is the number of cache entries\nprocessed by that directory. When using the sparse-checkout feature\nin cone mode, we can skip the pattern matching for entries in the\ndirectories that are entirely included or entirely excluded.\n\neb42feca (unpack-trees: hash less in cone mode, 2019-11-21)\nintroduced this performance feature. The old mechanism relied on\nthe counts returned by calling clear_ce_flags_1(), but the new\nmechanism calculated the number of rows by subtracting \"cache_end\"\nfrom \"cache\" to find the size of the range. However, the equation\nis wrong because it divides by sizeof(struct cache_entry *). This\nis not how pointer arithmetic works!\n\nA coverity build of Git for Windows in preparation for the 2.25.0\nrelease found this issue with the warning, \"Pointer differences,\nsuch as cache_end - cache, are automatically scaled down by the\nsize (8 bytes) of the pointed-to type (struct cache_entry *).\nMost likely, the division by sizeof(struct cache_entry *) is\nextraneous and should be eliminated.\" This warning is correct.\n\nThis leaves us with the question \"how did this even work?\" The\nproblem that occurs with this incorrect pointer arithmetic is\na performance-only bug, and a very slight one at that. Since\nthe entry count returned by clear_ce_flags_dir() is reduced by\na factor of 8, the loop in clear_ce_flags_1() will re-process\nentries from those directories.\n\nBy inserting global counters into unpack-tree.c and tracing\nthem with trace2_data_intmax() (in a private change, for\ntesting), I was able to see count how many times the loop inside\nclear_ce_flags_1() processed an entry and how many times\nclear_ce_flags_dir() was called. Each of these are reduced by at\nleast a factor of 8 with the current change. A factor larger\nthan 8 happens when multiple levels of directories are repeated.\n\nSpecifically, in the Linux kernel repo, the command\n\n\tgit sparse-checkout set LICENSES\n\nrestricts the working directory to only the files at root and\nin the LICENSES directory. Here are the measured counts:\n\nclear_ce_flags_1 loop blocks:\n\tBefore: 11,520\n\tAfter: 1,621\n\nclear_ce_flags_dir calls:\n\tBefore: 7,048\n\tAfter: 606\n\nWhile these are dramatic counts, the time spent in\nclear_ce_flags_1() is under one millisecond in each case, so\nthe improvement is not measurable as an end-to-end time.\n\nReported-by: Johannes Schindelin \nSigned-off-by: Derrick Stolee \n---\n unpack-trees: correctly compute result count\n \n Here is a very small fix to the cone-mode pattern-matching in\n unpack-trees.c. Johannes found this while running a Coverity scan for\n other issues. He alerted me to the problem and I could immediately see \n my error here. In creating this patch, most of my time was spent asking\n \"how did this work before?\" and \"why didn't this hurt performance?\"\n Hopefully my commit message explains this thoroughly enough.\n \n As for making it into the release, I don't know. The change is small, it\n has a very limited scope, but this flaw is also not really hurting\n anything in a major way.\n \n Thanks, -Stolee\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-520%2Fderrickstolee%2Funpack-trees-division-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-520/derrickstolee/unpack-trees-division-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/520\n\n unpack-trees.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 2399b6818b..3dba7f9f09 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1305,14 +1305,14 @@ static int clear_ce_flags_dir(struct index_state *istate,\n \n \tif (pl->use_cone_patterns && orig_ret == MATCHED_RECURSIVE) {\n \t\tstruct cache_entry **ce = cache;\n-\t\trc = (cache_end - cache) / sizeof(struct cache_entry *);\n+\t\trc = cache_end - cache;\n \n \t\twhile (ce < cache_end) {\n \t\t\t(*ce)->ce_flags &= ~clear_mask;\n \t\t\tce++;\n \t\t}\n \t} else if (pl->use_cone_patterns && orig_ret == NOT_MATCHED) {\n-\t\trc = (cache_end - cache) / sizeof(struct cache_entry *);\n+\t\trc = cache_end - cache;\n \t} else {\n \t\trc = clear_ce_flags_1(istate, cache, cache_end - cache,\n \t\t\t\t prefix,\n\nbase-commit: 7a6a90c6ec48fc78c83d7090d6c1b95d8f3739c0\n-- \ngitgitgadget\n"},{"id":"389572","messageId":"20200110103729.GA470836@coredump.intra.peff.net","threadId":"52607","inReplyTo":"pull.520.git.1578621570180.gitgitgadget@gmail.com","subject":"Re: [PATCH] unpack-trees: correctly compute result count","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-10T10:37:29Z","receivedAt":"2020-01-10T10:37:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 10, 2020 at 01:59:30AM +0000, Derrick Stolee via GitGitGadget wrote:\n\n> Here is a very small fix to the cone-mode pattern-matching in\n> unpack-trees.c. Johannes found this while running a Coverity scan for\n> other issues. He alerted me to the problem and I could immediately see \n> my error here. In creating this patch, most of my time was spent asking\n> \"how did this work before?\" and \"why didn't this hurt performance?\"\n> Hopefully my commit message explains this thoroughly enough.\n\nYes, it makes perfect sense (and as soon as I saw the explanation of the\nproblem, my immediate response was also \"wait, how did this even work\").\n\nAnd the patch itself looks good.\n\n> As for making it into the release, I don't know. The change is small, it\n> has a very limited scope, but this flaw is also not really hurting\n> anything in a major way.\n\nI could go either way.\n\nThis counts as something small and obvious enough that I'd consider\nslipping it in at the last minute if it were fixing a bad bug. But given\nhow minor the bug is, being conservative makes sense to me, if only\nbecause it's good to exercise our release discipline muscles. :)\n\n-Peff\n"},{"id":"389574","messageId":"d9a465bf-843b-2a8f-66c0-73fb706dbfc0@gmail.com","threadId":"52607","inReplyTo":"20200110103729.GA470836@coredump.intra.peff.net","subject":"Re: [PATCH] unpack-trees: correctly compute result count","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-01-10T11:24:19Z","receivedAt":"2020-01-10T11:24:23Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/10/2020 5:37 AM, Jeff King wrote:\n> On Fri, Jan 10, 2020 at 01:59:30AM +0000, Derrick Stolee via GitGitGadget wrote:\n>>\n>> As for making it into the release, I don't know. The change is small, it\n>> has a very limited scope, but this flaw is also not really hurting\n>> anything in a major way.\n> \n> I could go either way.\n> \n> This counts as something small and obvious enough that I'd consider\n> slipping it in at the last minute if it were fixing a bad bug. But given\n> how minor the bug is, being conservative makes sense to me, if only\n> because it's good to exercise our release discipline muscles. :)\n\nPerhaps this should be an example for future release windows.\n\nThanks,\n-Stolee\n\n"},{"id":"389575","messageId":"40ff5504-9cdc-a97f-9dbf-84529d6596ce@gmail.com","threadId":"52607","inReplyTo":"d9a465bf-843b-2a8f-66c0-73fb706dbfc0@gmail.com","subject":"Re: [PATCH] unpack-trees: correctly compute result count","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-01-10T11:30:24Z","receivedAt":"2020-01-10T11:30:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/10/2020 6:24 AM, Derrick Stolee wrote:\n> On 1/10/2020 5:37 AM, Jeff King wrote:\n>> On Fri, Jan 10, 2020 at 01:59:30AM +0000, Derrick Stolee via GitGitGadget wrote:\n>>>\n>>> As for making it into the release, I don't know. The change is small, it\n>>> has a very limited scope, but this flaw is also not really hurting\n>>> anything in a major way.\n>>\n>> I could go either way.\n>>\n>> This counts as something small and obvious enough that I'd consider\n>> slipping it in at the last minute if it were fixing a bad bug. But given\n>> how minor the bug is, being conservative makes sense to me, if only\n>> because it's good to exercise our release discipline muscles. :)\n> \n> Perhaps this should be an example for future release windows.\n\n(Forgive me for fat-fingering and accidentally using \"gmx.net\" instead\nof \"gmx.de\" for Johannes' email address. Fixed in this message.)\n\n-Stolee\n"},{"id":"389591","messageId":"xmqqftgnm7i0.fsf@gitster-ct.c.googlers.com","threadId":"52607","inReplyTo":"20200110103729.GA470836@coredump.intra.peff.net","subject":"Re: [PATCH] unpack-trees: correctly compute result count","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-01-10T19:33:27Z","receivedAt":"2020-01-10T19:33:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Jan 10, 2020 at 01:59:30AM +0000, Derrick Stolee via GitGitGadget wrote:\n>\n>> Here is a very small fix to the cone-mode pattern-matching in\n>> unpack-trees.c. Johannes found this while running a Coverity scan for\n>> other issues. He alerted me to the problem and I could immediately see \n>> my error here. In creating this patch, most of my time was spent asking\n>> \"how did this work before?\" and \"why didn't this hurt performance?\"\n>> Hopefully my commit message explains this thoroughly enough.\n>\n> Yes, it makes perfect sense (and as soon as I saw the explanation of the\n> problem, my immediate response was also \"wait, how did this even work\").\n>\n> And the patch itself looks good.\n>\n>> As for making it into the release, I don't know. The change is small, it\n>> has a very limited scope, but this flaw is also not really hurting\n>> anything in a major way.\n>\n> I could go either way.\n>\n> This counts as something small and obvious enough that I'd consider\n> slipping it in at the last minute if it were fixing a bad bug. But given\n> how minor the bug is, being conservative makes sense to me, if only\n> because it's good to exercise our release discipline muscles. :)\n\nHeh.\n\nOn one hand, it is obvious, even to a mindless compiler, that the\nauthor meant to count how many elements of cache[] array have been\nprocessed in the loop, so it is clear that the patch makes the code\nreflect the author's original intention better.\n\nOn the other hand, the code that reflects the author's original\nintention has never been tested in the field---it could be possible\nthat the author thought cache[0] thru cache_end[0] have been\nprocessed, but for some subtlety, only a very early part of the\nrange was correctly processed, and returning smaller range may have\nbeen hiding that subtle bug ;-)\n\nI do not see any such subtle bug in this particular case, so I am\nsomewhat tempted to say \"it is clear that the 'fix' makes the code\ndo what the author wanted to do, *and* what the author wanted to do\nseems sane, so let's apply it\".\n\nHaving said that, the earlier part of the patch, i.e.\n\n \tif (pl->use_cone_patterns && orig_ret == MATCHED_RECURSIVE) {\n \t\tstruct cache_entry **ce = cache;\n-\t\trc = (cache_end - cache) / sizeof(struct cache_entry *);\n+\t\trc = cache_end - cache;\n \n \t\twhile (ce < cache_end) {\n \t\t\t(*ce)->ce_flags &= ~clear_mask;\n \t\t\tce++;\n \t\t}\n\nwouldn't have been needed any fix if it were actually *counting*,\nwhich is what clear_ce_flags_dir() promises its callers it does,\ninstead of cheating with a subtraction. i.e.\n\n\tif (... RECURSIVE) {\n\t\trc = 0;\n\t\twhile (ce < cache_end) {\n\t\t\tclear;\n\t\t\tce++;\n\t\t\trc++;\n\t\t}\n\t}\n\nand that may have been more future-proof way, in that the body of\nthe while loop may in the future decide to leave early etc. and\nactually counting how far the processing progressed would be less\nerror prone.\n\nALso, the computation of cache_end earlier in the function looks\nsuspiciously similar to the code Emily recently touched to avoid\nsegfaulting against inconsistent index state, where it used\nthe entry count in the cache_tree structure (when it is valid) to\ndetermine how many entries to skip over. We may want to see if we\ncan apply the same optimization here.\n\nThanks. Will queue but will not merge to 'master' ;-)\n"}]}