{"thread":{"id":"57574","subject":"[PATCH 0/3] Fix use of 'cache_bottom' in sparse index","startedAt":"2022-03-16T20:12:09Z","lastAt":"2022-03-21T20:53:11Z","messageCount":12,"participants":["Victoria Dye via GitGitGadget","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"451511","messageId":"pull.1179.git.1647461522.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":null,"subject":"[PATCH 0/3] Fix use of 'cache_bottom' in sparse index","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-16T20:11:59Z","receivedAt":"2022-03-16T20:12:09Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"An issue was found by @stolee after experimenting with the structure of the\ntest repo used in 't/t1092-sparse-checkout-compatibility.sh' (patch [1/3])\nand finding that certain commands (namely those that internally performed a\n\"cache diff\") failed when a sparse directory appeared lexicographically\nbefore the in-cone directory. The root cause was traced to the\n'unpack_trees_options.cache_bottom' variable, which was not being advanced\nproperly for sparse directories. The result was entries being\ndouble-unpacked or improperly unpacked by 'unpack_trees', causing failures\nin tests using 'git reset -- <pathspec>' and 'git diff --staged --\n<pathspec>' using pathspecs.\n\nThe 'cache_bottom' was handled differently in sparse indexes in the first\nplace based on the reasoning laid out in 17a1bb570b (unpack-trees: preserve\ncache_bottom, 2021-07-14). In short, the 'cache_bottom' advancement in\n'mark_ce_used(...)' was disabled for sparse directories because\n'unpack_callback(...)' would advance the 'cache_bottom' based on the number\nof index entries matching or inside the tree being unpacked. If the tree was\na sparse directory, 'cache_bottom' would appropriately advance by 1, and\ntherefore didn't need the extra advancement in 'mark_ce_used(...)'. However,\nthis was insufficient to properly advance the 'cache_bottom' for two\nreasons:\n\n 1. 'unpack_callback(...)' would only advance the 'cache_bottom' for sparse\n    directories if the operation in progress was a \"cache diff\" (true for\n    'git diff --staged' and 'git reset --mixed', but not - for instance -\n    'git reset --hard' or 'git read-tree -m').\n 2. If sparse directories were unpacked with 'unpack_index_entry(...)'\n    (e.g., in 'git reset -- <pathspec>'), the cache tree-based advancement\n    of 'cache_bottom' would not happen.\n\nLuckily, the first did not appear to have any behavioral impact. However,\nthe latter led to incorrect values being returned by 'next_cache_entry(...)'\ndepending on the structure of the index, causing the test failures observed\nin 't1092'.\n\nTo fix this, the 'cache_bottom' advancement is reinstated in\n'mark_ce_used(...)', and instead it is disabled in 'unpack_callback(...)' if\nthe tree in question is a sparse directory. This corrects both the\nnon-\"cache diff\" cases and the 'unpack_index_entry(...)' cases while\npreventing the double-advancement 17a1bb570b originally intended to avoid\n(patch [2/3]).\n\nFinally, now that the cache bottom is advanced properly, we can revert the\n\"performance improvement\" introduced in f2a454e0a5 (unpack-trees: improve\nperformance of next_cache_entry, 2021-11-29) that mitigated performance\nissues arising in 'next_cache_entry(...)' from the non-advancing\n'cache_bottom' (patch [3/3]). The performance results in\n'p2000-sparse-operations.sh' showed expected variability around 0% change in\nexecution time (+/= 0.04s, depending on the command), with example results\nfor potentially-affected commands below.\n\n'git reset'                      master            this_series                  \n------------------------------------------------------------------------\nfull-v3                          0.51(0.21+0.27)   0.50(0.21+0.25) -2.0%\nfull-v4                          0.51(0.22+0.27)   0.50(0.21+0.24) -2.0%\nsparse-v3                        0.30(0.04+0.55)   0.28(0.04+0.50) -6.7%\nsparse-v4                        0.31(0.04+0.51)   0.29(0.04+0.51) -6.5%\n\n'git reset -- does-not-exist'    master            this_series                  \n------------------------------------------------------------------------\nfull-v3                          0.54(0.23+0.27)   0.55(0.22+0.28) +1.9%\nfull-v4                          0.56(0.25+0.26)   0.54(0.24+0.26) -3.6%\nsparse-v3                        0.31(0.04+0.54)   0.31(0.04+0.50) +0.0%\nsparse-v4                        0.31(0.04+0.52)   0.31(0.04+0.50) +0.0%\n\n'git diff --cached'              master            this_series    \n-------------------------------------------------------------------------\nfull-v3                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\nfull-v4                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\nsparse-v3                        0.05(0.01+0.02)   0.05(0.01+0.03) +0.0%\nsparse-v4                        0.04(0.01+0.02)   0.04(0.01+0.02) +0.0%\n\n\nThanks! -Victoria\n\nVictoria Dye (3):\n  t1092: add sparse directory before cone in test repo\n  unpack-trees: increment cache_bottom for sparse directories\n  Revert \"unpack-trees: improve performance of next_cache_entry\"\n\n t/t1092-sparse-checkout-compatibility.sh |  6 +++-\n unpack-trees.c                           | 39 +++++++++---------------\n 2 files changed, 19 insertions(+), 26 deletions(-)\n\n\nbase-commit: 1a4874565fa3b6668042216189551b98b4dc0b1b\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1179%2Fvdye%2Fbugfix%2Fsparse-index-cache-bottom-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1179/vdye/bugfix/sparse-index-cache-bottom-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1179\n-- \ngitgitgadget\n"},{"id":"451512","messageId":"726b947bcbfa8ff10dba0241460cbf1a0cbcd7e4.1647461522.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.git.1647461522.gitgitgadget@gmail.com","subject":"[PATCH 1/3] t1092: add sparse directory before cone in test repo","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-16T20:12:00Z","receivedAt":"2022-03-16T20:12:10Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nAdd a sparse directory 'before/' containing files 'a' and 'b' to the test\nrepo used in 't/t1092-sparse-checkout-compatibility.sh'. This is meant to\nensure that no sparse index integrations rely on the in-cone path(s) being\nlexicographically first in the repo.\n\nUnfortunately, some existing tests do not handle this repo architecture\nproperly:\n\n* 'add outside sparse cone'\n* 'status/add: outside sparse cone'\n* 'reset with pathspecs inside sparse definition'\n\nAll three of these are due to the incorrect handling of the\n'unpack_trees_options.cache_bottom' when performing a cache diff via\n'unpack_trees'. This will be corrected in a future patch; in the meantime,\nmark the tests with 'test_expect_failure'.\n\nFinally, update the 'ls-files' test to include the 'before/' directory in\nits expected results.\n\nCo-authored-by: Derrick Stolee <derrickstolee@github.com>\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n t/t1092-sparse-checkout-compatibility.sh | 12 ++++++++----\n 1 file changed, 8 insertions(+), 4 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 2a04b532f91..11141221b4d 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -16,7 +16,9 @@ test_expect_success 'setup' '\n \t\techo \"after deep\" >e &&\n \t\techo \"after folder1\" >g &&\n \t\techo \"after x\" >z &&\n-\t\tmkdir folder1 folder2 deep x &&\n+\t\tmkdir folder1 folder2 deep before x &&\n+\t\techo \"before deep\" >before/a &&\n+\t\techo \"before deep again\" >before/b &&\n \t\tmkdir deep/deeper1 deep/deeper2 deep/before deep/later &&\n \t\tmkdir deep/deeper1/deepest &&\n \t\tmkdir deep/deeper1/deepest2 &&\n@@ -312,7 +314,7 @@ test_expect_success 'deep changes during checkout' '\n \ttest_all_match git checkout base\n '\n \n-test_expect_success 'add outside sparse cone' '\n+test_expect_failure 'add outside sparse cone' '\n \tinit_repos &&\n \n \trun_on_sparse mkdir folder1 &&\n@@ -354,7 +356,7 @@ test_expect_success 'commit including unstaged changes' '\n \ttest_all_match git status --porcelain=v2\n '\n \n-test_expect_success 'status/add: outside sparse cone' '\n+test_expect_failure 'status/add: outside sparse cone' '\n \tinit_repos &&\n \n \t# folder1 is at HEAD, but outside the sparse cone\n@@ -565,7 +567,7 @@ test_expect_success 'checkout and reset (keep)' '\n \ttest_all_match test_must_fail git reset --keep deepest\n '\n \n-test_expect_success 'reset with pathspecs inside sparse definition' '\n+test_expect_failure 'reset with pathspecs inside sparse definition' '\n \tinit_repos &&\n \n \twrite_script edit-contents <<-\\EOF &&\n@@ -1311,6 +1313,7 @@ test_expect_success 'ls-files' '\n \n \tcat >expect <<-\\EOF &&\n \ta\n+\tbefore/\n \tdeep/\n \te\n \tfolder1-\n@@ -1358,6 +1361,7 @@ test_expect_success 'ls-files' '\n \n \tcat >expect <<-\\EOF &&\n \ta\n+\tbefore/\n \tdeep/\n \te\n \tfolder1-\n-- \ngitgitgadget\n\n"},{"id":"451513","messageId":"8ebfebcc3473e6a5d1052b14b3e9d43036cb6857.1647461522.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.git.1647461522.gitgitgadget@gmail.com","subject":"[PATCH 2/3] unpack-trees: increment cache_bottom for sparse directories","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-16T20:12:01Z","receivedAt":"2022-03-16T20:12:21Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nCorrect tracking of the 'cache_bottom' for cases where sparse directories\nare present in the index.\n\nBACKGROUND\n----------\nThe 'unpack_trees_options.cache_bottom' is a variable that tracks the\nin-progress \"bottom\" of the cache as 'unpack_trees()' iterates through the\ncontents of the index. Most importantly, this value informs the sequential\nreturn values of 'next_cache_entry()' which, in the \"diff cache\" usage of\n'unpack_callback()', are either unpacked as-is or are passed into the diff\nmachinery.\n\nThe 'cache_bottom' is intended to track the position of the first entry in\nthe index that has not yet been diffed or unpacked. It is advanced in two\nmain ways: either it is incremented when an index entry is marked as \"used\"\n(in 'mark_ce_used()'), indicating that it was unpacked or diffed, or when a\ndirectory is unpacked, in which case it is increased by an amount equaling\nthe number of index entries inside that tree.\n\nIn 17a1bb570b (unpack-trees: preserve cache_bottom, 2021-07-14), it was\nidentified that sparse directories posed a problem to the above\n'cache_bottom' advancement logic - because a sparse directory was both an\nindex entry that could be \"used\" and a directory that can be unpacked, the\n'cache_bottom' would be incremented too many times. To solve this problem,\nthe 'mark_ce_used()' advancement of 'cache_bottom' was skipped for sparse\ndirectories.\n\nINCORRECT CACHE_BOTTOM TRACKING\n-------------------------------\nSkipping the 'cache_bottom' advancement for sparse directories in\n'mark_ce_used()' breaks down in two cases:\n\n1. When the 'unpack_trees()' operation is *not* a \"cache diff\" (because the\n   directory contents-based incrementing of 'cache_bottom' does not happen).\n2. When a cache diff is performed with a pathspec (because\n   'unpack_index_entry()' will unpack a sparse directory not matched by the\n   pathspec without performing the directory contents-based increment).\n\nThe former luckily does not appear to affect 'git' behavior, likely because\n'cache_bottom' is largely unused (non-\"cache diff\" 'unpack_trees()' uses\n'find_index_entry()' - rather than 'next_cache_entry()' - to find the index\nentries to unpack).\n\nThe latter, however, causes 'cache_bottom' to \"lag behind\" its intended\nposition by an amount equal to the number of sparse directories unpacked so\nfar with 'unpack_index_entry()'. If a repository is structured such that any\nsparse directories are ordered lexicographically *after* any\npathspec-matching directories, though, this issue won't present any adverse\nbehavior.\n\nThis was the case with the 't1092-sparse-checkout-compatibility.sh' tests\nbefore the addition of the 'before/' sparse directory (ordered *before* the\nin-cone 'deep/' directory), therefore sidestepping the issue. Once the\n'before/' directory was added, though, 'cache_bottom' began to lag behind\nits intended position, causing 'next_cache_entry()' to return index entries\nit had already processed and, ultimately, an incorrect diff.\n\nCORRECTING CACHE_BOTTOM\n-----------------------\nThe problems observed in 't1092' come from 'cache_bottom' lagging behind in\ncases where the cache tree-based advancement doesn't occur. To solve this,\nthen, the fix in 17a1bb570b is \"reversed\"; rather than skipping\n'cache_bottom' advancement in 'mark_ce_used()', we skip the directory\ncontents-based advancement for sparse directories. Now, every index entry\ncan be accounted for in 'cache_bottom':\n\n* if you're working with a single index entry, 'cache_bottom' is incremented\n  in 'mark_ce_used()'\n* if you're working with a directory that contains index entries (but is not\n  one itself), 'cache_bottom' is incremented by the number of entries in\n  that directory.\n\nFinally, change the 'test_expect_failure' tests in 't1092' failing due to\nthis bug back to 'test_expect_success'.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n t/t1092-sparse-checkout-compatibility.sh |  6 +++---\n unpack-trees.c                           | 16 ++++++++--------\n 2 files changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 11141221b4d..e9533832aab 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -314,7 +314,7 @@ test_expect_success 'deep changes during checkout' '\n \ttest_all_match git checkout base\n '\n \n-test_expect_failure 'add outside sparse cone' '\n+test_expect_success 'add outside sparse cone' '\n \tinit_repos &&\n \n \trun_on_sparse mkdir folder1 &&\n@@ -356,7 +356,7 @@ test_expect_success 'commit including unstaged changes' '\n \ttest_all_match git status --porcelain=v2\n '\n \n-test_expect_failure 'status/add: outside sparse cone' '\n+test_expect_success 'status/add: outside sparse cone' '\n \tinit_repos &&\n \n \t# folder1 is at HEAD, but outside the sparse cone\n@@ -567,7 +567,7 @@ test_expect_success 'checkout and reset (keep)' '\n \ttest_all_match test_must_fail git reset --keep deepest\n '\n \n-test_expect_failure 'reset with pathspecs inside sparse definition' '\n+test_expect_success 'reset with pathspecs inside sparse definition' '\n \tinit_repos &&\n \n \twrite_script edit-contents <<-\\EOF &&\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 96525d2ec26..aac927faf08 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -595,13 +595,6 @@ static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)\n {\n \tce->ce_flags |= CE_UNPACKED;\n \n-\t/*\n-\t * If this is a sparse directory, don't advance cache_bottom.\n-\t * That will be advanced later using the cache-tree data.\n-\t */\n-\tif (S_ISSPARSEDIR(ce->ce_mode))\n-\t\treturn;\n-\n \tif (o->cache_bottom < o->src_index->cache_nr &&\n \t    o->src_index->cache[o->cache_bottom] == ce) {\n \t\tint bottom = o->cache_bottom;\n@@ -1442,7 +1435,14 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \t\t\t * it does not do any look-ahead, so this is safe.\n \t\t\t */\n \t\t\tif (matches) {\n-\t\t\t\to->cache_bottom += matches;\n+\t\t\t\t/*\n+\t\t\t\t * Only increment the cache_bottom if the\n+\t\t\t\t * directory isn't a sparse directory index\n+\t\t\t\t * entry (if it is, it was already incremented)\n+\t\t\t\t * in 'mark_ce_used()'\n+\t\t\t\t */\n+\t\t\t\tif (!src[0] || !S_ISSPARSEDIR(src[0]->ce_mode))\n+\t\t\t\t\to->cache_bottom += matches;\n \t\t\t\treturn mask;\n \t\t\t}\n \t\t}\n-- \ngitgitgadget\n\n"},{"id":"451514","messageId":"ec6b9686e8f388a3edc42c9b51372cf062ae5699.1647461522.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.git.1647461522.gitgitgadget@gmail.com","subject":"[PATCH 3/3] Revert \"unpack-trees: improve performance of next_cache_entry\"","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-16T20:12:02Z","receivedAt":"2022-03-16T20:12:24Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nThis reverts commit f2a454e0a5 (unpack-trees: improve performance of\nnext_cache_entry, 2021-11-29).\n\nThe \"hint\" value was originally needed to improve performance in 'git reset\n-- <pathspec>' caused by 'cache_bottom' lagging behind its correct value\nwhen using a sparse index. The 'cache_bottom' tracking has since been\ncorrected, removing the need for an additional \"pseudo-cache_bottom\"\ntracking variable.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n unpack-trees.c | 23 ++++++-----------------\n 1 file changed, 6 insertions(+), 17 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex aac927faf08..7e5715c42b3 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -644,24 +644,17 @@ static void mark_ce_used_same_name(struct cache_entry *ce,\n \t}\n }\n \n-static struct cache_entry *next_cache_entry(struct unpack_trees_options *o, int *hint)\n+static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n {\n \tconst struct index_state *index = o->src_index;\n \tint pos = o->cache_bottom;\n \n-\tif (*hint > pos)\n-\t\tpos = *hint;\n-\n \twhile (pos < index->cache_nr) {\n \t\tstruct cache_entry *ce = index->cache[pos];\n-\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n-\t\t\t*hint = pos + 1;\n+\t\tif (!(ce->ce_flags & CE_UNPACKED))\n \t\t\treturn ce;\n-\t\t}\n \t\tpos++;\n \t}\n-\n-\t*hint = pos;\n \treturn NULL;\n }\n \n@@ -1373,13 +1366,12 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \n \t/* Are we supposed to look at the index too? */\n \tif (o->merge) {\n-\t\tint hint = -1;\n \t\twhile (1) {\n \t\t\tint cmp;\n \t\t\tstruct cache_entry *ce;\n \n \t\t\tif (o->diff_index_cached)\n-\t\t\t\tce = next_cache_entry(o, &hint);\n+\t\t\t\tce = next_cache_entry(o);\n \t\t\telse\n \t\t\t\tce = find_cache_entry(info, p);\n \n@@ -1706,7 +1698,7 @@ static int verify_absent(const struct cache_entry *,\n int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)\n {\n \tstruct repository *repo = the_repository;\n-\tint i, hint, ret;\n+\tint i, ret;\n \tstatic struct cache_entry *dfc;\n \tstruct pattern_list pl;\n \tint free_pattern_list = 0;\n@@ -1795,15 +1787,13 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tinfo.pathspec = o->pathspec;\n \n \t\tif (o->prefix) {\n-\t\t\thint = -1;\n-\n \t\t\t/*\n \t\t\t * Unpack existing index entries that sort before the\n \t\t\t * prefix the tree is spliced into.  Note that o->merge\n \t\t\t * is always true in this case.\n \t\t\t */\n \t\t\twhile (1) {\n-\t\t\t\tstruct cache_entry *ce = next_cache_entry(o, &hint);\n+\t\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n \t\t\t\tif (!ce)\n \t\t\t\t\tbreak;\n \t\t\t\tif (ce_in_traverse_path(ce, &info))\n@@ -1824,9 +1814,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \n \t/* Any left-over entries in the index? */\n \tif (o->merge) {\n-\t\thint = -1;\n \t\twhile (1) {\n-\t\t\tstruct cache_entry *ce = next_cache_entry(o, &hint);\n+\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n \t\t\tif (!ce)\n \t\t\t\tbreak;\n \t\t\tif (unpack_index_entry(ce, o) < 0)\n-- \ngitgitgadget\n"},{"id":"451515","messageId":"xmqq5yodlkc9.fsf@gitster.g","threadId":"57574","inReplyTo":"pull.1179.git.1647461522.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Fix use of 'cache_bottom' in sparse index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-03-16T20:21:26Z","receivedAt":"2022-03-16T20:21:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> ...\n> To fix this, the 'cache_bottom' advancement is reinstated in\n> 'mark_ce_used(...)', and instead it is disabled in 'unpack_callback(...)' if\n> the tree in question is a sparse directory. This corrects both the\n> non-\"cache diff\" cases and the 'unpack_index_entry(...)' cases while\n> preventing the double-advancement 17a1bb570b originally intended to avoid\n> (patch [2/3]).\n\n;-).\n"},{"id":"451565","messageId":"pull.1179.v2.git.1647532536.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.git.1647461522.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] Fix use of 'cache_bottom' in sparse index","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-17T15:55:33Z","receivedAt":"2022-03-17T15:55:43Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"An issue was found by @stolee after experimenting with the structure of the\ntest repo used in 't/t1092-sparse-checkout-compatibility.sh' (patch [1/3])\nand finding that certain commands (namely those that internally performed a\n\"cache diff\") failed when a sparse directory appeared lexicographically\nbefore the in-cone directory. The root cause was traced to the\n'unpack_trees_options.cache_bottom' variable, which was not being advanced\nproperly for sparse directories. The result was entries being\ndouble-unpacked or improperly unpacked by 'unpack_trees', causing failures\nin tests using 'git reset -- <pathspec>' and 'git diff --staged --\n<pathspec>' using pathspecs.\n\nThe 'cache_bottom' was handled differently in sparse indexes in the first\nplace based on the reasoning laid out in 17a1bb570b (unpack-trees: preserve\ncache_bottom, 2021-07-14). In short, the 'cache_bottom' advancement in\n'mark_ce_used(...)' was disabled for sparse directories because\n'unpack_callback(...)' would advance the 'cache_bottom' based on the number\nof index entries matching or inside the tree being unpacked. If the tree was\na sparse directory, 'cache_bottom' would appropriately advance by 1, and\ntherefore didn't need the extra advancement in 'mark_ce_used(...)'. However,\nthis was insufficient to properly advance the 'cache_bottom' for two\nreasons:\n\n 1. 'unpack_callback(...)' would only advance the 'cache_bottom' for sparse\n    directories if the operation in progress was a \"cache diff\" (true for\n    'git diff --staged' and 'git reset --mixed', but not - for instance -\n    'git reset --hard' or 'git read-tree -m').\n 2. If sparse directories were unpacked with 'unpack_index_entry(...)'\n    (e.g., in 'git reset -- <pathspec>'), the cache tree-based advancement\n    of 'cache_bottom' would not happen.\n\nLuckily, the first did not appear to have any behavioral impact. However,\nthe latter led to incorrect values being returned by 'next_cache_entry(...)'\ndepending on the structure of the index, causing the test failures observed\nin 't1092'.\n\nTo fix this, the 'cache_bottom' advancement is reinstated in\n'mark_ce_used(...)', and instead it is disabled in 'unpack_callback(...)' if\nthe tree in question is a sparse directory. This corrects both the\nnon-\"cache diff\" cases and the 'unpack_index_entry(...)' cases while\npreventing the double-advancement 17a1bb570b originally intended to avoid\n(patch [2/3]).\n\nFinally, now that the cache bottom is advanced properly, we can revert the\n\"performance improvement\" introduced in f2a454e0a5 (unpack-trees: improve\nperformance of next_cache_entry, 2021-11-29) that mitigated performance\nissues arising in 'next_cache_entry(...)' from the non-advancing\n'cache_bottom' (patch [3/3]). The performance results in\n'p2000-sparse-operations.sh' showed expected variability around 0% change in\nexecution time (+/= 0.04s, depending on the command), with example results\nfor potentially-affected commands below.\n\n'git reset'                      master            this_series                  \n------------------------------------------------------------------------\nfull-v3                          0.51(0.21+0.27)   0.50(0.21+0.25) -2.0%\nfull-v4                          0.51(0.22+0.27)   0.50(0.21+0.24) -2.0%\nsparse-v3                        0.30(0.04+0.55)   0.28(0.04+0.50) -6.7%\nsparse-v4                        0.31(0.04+0.51)   0.29(0.04+0.51) -6.5%\n\n'git reset -- does-not-exist'    master            this_series                  \n------------------------------------------------------------------------\nfull-v3                          0.54(0.23+0.27)   0.55(0.22+0.28) +1.9%\nfull-v4                          0.56(0.25+0.26)   0.54(0.24+0.26) -3.6%\nsparse-v3                        0.31(0.04+0.54)   0.31(0.04+0.50) +0.0%\nsparse-v4                        0.31(0.04+0.52)   0.31(0.04+0.50) +0.0%\n\n'git diff --cached'              master            this_series    \n-------------------------------------------------------------------------\nfull-v3                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\nfull-v4                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\nsparse-v3                        0.05(0.01+0.02)   0.05(0.01+0.03) +0.0%\nsparse-v4                        0.04(0.01+0.02)   0.04(0.01+0.02) +0.0%\n\n\n\nChanges since V1\n================\n\n * Rebase on top of 'master' (to take changes from 'vd/sparse-read-tree')\n * Add 'before/' to expected index results in 't1092' test 'root directory\n   cannot be sparse'\n\nThanks! -Victoria\n\nVictoria Dye (3):\n  t1092: add sparse directory before cone in test repo\n  unpack-trees: increment cache_bottom for sparse directories\n  Revert \"unpack-trees: improve performance of next_cache_entry\"\n\n t/t1092-sparse-checkout-compatibility.sh |  7 ++++-\n unpack-trees.c                           | 39 +++++++++---------------\n 2 files changed, 20 insertions(+), 26 deletions(-)\n\n\nbase-commit: 74cc1aa55f30ed76424a0e7226ab519aa6265061\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1179%2Fvdye%2Fbugfix%2Fsparse-index-cache-bottom-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1179/vdye/bugfix/sparse-index-cache-bottom-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1179\n\nRange-diff vs v1:\n\n 1:  726b947bcbf ! 1:  d1491d299a9 t1092: add sparse directory before cone in test repo\n     @@ Commit message\n          'unpack_trees'. This will be corrected in a future patch; in the meantime,\n          mark the tests with 'test_expect_failure'.\n      \n     -    Finally, update the 'ls-files' test to include the 'before/' directory in\n     -    its expected results.\n     +    Finally, update the 'ls-files' and 'root directory cannot be sparse' tests\n     +    to include the 'before/' directory in their expected index contents.\n      \n          Co-authored-by: Derrick Stolee <derrickstolee@github.com>\n          Signed-off-by: Victoria Dye <vdye@github.com>\n     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'setup' '\n       \t\tmkdir deep/deeper1 deep/deeper2 deep/before deep/later &&\n       \t\tmkdir deep/deeper1/deepest &&\n       \t\tmkdir deep/deeper1/deepest2 &&\n     +@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'root directory cannot be sparse' '\n     + \n     + \t# Verify sparse directories still present, root directory is not sparse\n     + \tcat >expect <<-EOF &&\n     ++\tbefore/\n     + \tfolder1/\n     + \tfolder2/\n     + \tx/\n      @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'deep changes during checkout' '\n       \ttest_all_match git checkout base\n       '\n 2:  8ebfebcc347 = 2:  cf8dc50c300 unpack-trees: increment cache_bottom for sparse directories\n 3:  ec6b9686e8f = 3:  d74b304f560 Revert \"unpack-trees: improve performance of next_cache_entry\"\n\n-- \ngitgitgadget\n"},{"id":"451566","messageId":"d1491d299a94a7f776b2e20b4ff586f544487443.1647532536.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.v2.git.1647532536.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] t1092: add sparse directory before cone in test repo","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-17T15:55:34Z","receivedAt":"2022-03-17T15:55:45Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nAdd a sparse directory 'before/' containing files 'a' and 'b' to the test\nrepo used in 't/t1092-sparse-checkout-compatibility.sh'. This is meant to\nensure that no sparse index integrations rely on the in-cone path(s) being\nlexicographically first in the repo.\n\nUnfortunately, some existing tests do not handle this repo architecture\nproperly:\n\n* 'add outside sparse cone'\n* 'status/add: outside sparse cone'\n* 'reset with pathspecs inside sparse definition'\n\nAll three of these are due to the incorrect handling of the\n'unpack_trees_options.cache_bottom' when performing a cache diff via\n'unpack_trees'. This will be corrected in a future patch; in the meantime,\nmark the tests with 'test_expect_failure'.\n\nFinally, update the 'ls-files' and 'root directory cannot be sparse' tests\nto include the 'before/' directory in their expected index contents.\n\nCo-authored-by: Derrick Stolee <derrickstolee@github.com>\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n t/t1092-sparse-checkout-compatibility.sh | 13 +++++++++----\n 1 file changed, 9 insertions(+), 4 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex dcc0a30d4ad..dcd7061fb3b 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -16,7 +16,9 @@ test_expect_success 'setup' '\n \t\techo \"after deep\" >e &&\n \t\techo \"after folder1\" >g &&\n \t\techo \"after x\" >z &&\n-\t\tmkdir folder1 folder2 deep x &&\n+\t\tmkdir folder1 folder2 deep before x &&\n+\t\techo \"before deep\" >before/a &&\n+\t\techo \"before deep again\" >before/b &&\n \t\tmkdir deep/deeper1 deep/deeper2 deep/before deep/later &&\n \t\tmkdir deep/deeper1/deepest &&\n \t\tmkdir deep/deeper1/deepest2 &&\n@@ -254,6 +256,7 @@ test_expect_success 'root directory cannot be sparse' '\n \n \t# Verify sparse directories still present, root directory is not sparse\n \tcat >expect <<-EOF &&\n+\tbefore/\n \tfolder1/\n \tfolder2/\n \tx/\n@@ -337,7 +340,7 @@ test_expect_success 'deep changes during checkout' '\n \ttest_all_match git checkout base\n '\n \n-test_expect_success 'add outside sparse cone' '\n+test_expect_failure 'add outside sparse cone' '\n \tinit_repos &&\n \n \trun_on_sparse mkdir folder1 &&\n@@ -379,7 +382,7 @@ test_expect_success 'commit including unstaged changes' '\n \ttest_all_match git status --porcelain=v2\n '\n \n-test_expect_success 'status/add: outside sparse cone' '\n+test_expect_failure 'status/add: outside sparse cone' '\n \tinit_repos &&\n \n \t# folder1 is at HEAD, but outside the sparse cone\n@@ -590,7 +593,7 @@ test_expect_success 'checkout and reset (keep)' '\n \ttest_all_match test_must_fail git reset --keep deepest\n '\n \n-test_expect_success 'reset with pathspecs inside sparse definition' '\n+test_expect_failure 'reset with pathspecs inside sparse definition' '\n \tinit_repos &&\n \n \twrite_script edit-contents <<-\\EOF &&\n@@ -1444,6 +1447,7 @@ test_expect_success 'ls-files' '\n \n \tcat >expect <<-\\EOF &&\n \ta\n+\tbefore/\n \tdeep/\n \te\n \tfolder1-\n@@ -1491,6 +1495,7 @@ test_expect_success 'ls-files' '\n \n \tcat >expect <<-\\EOF &&\n \ta\n+\tbefore/\n \tdeep/\n \te\n \tfolder1-\n-- \ngitgitgadget\n\n"},{"id":"451567","messageId":"cf8dc50c300a08f54d0cf69c82d4d979922a8143.1647532536.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.v2.git.1647532536.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] unpack-trees: increment cache_bottom for sparse directories","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-17T15:55:35Z","receivedAt":"2022-03-17T15:55:52Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nCorrect tracking of the 'cache_bottom' for cases where sparse directories\nare present in the index.\n\nBACKGROUND\n----------\nThe 'unpack_trees_options.cache_bottom' is a variable that tracks the\nin-progress \"bottom\" of the cache as 'unpack_trees()' iterates through the\ncontents of the index. Most importantly, this value informs the sequential\nreturn values of 'next_cache_entry()' which, in the \"diff cache\" usage of\n'unpack_callback()', are either unpacked as-is or are passed into the diff\nmachinery.\n\nThe 'cache_bottom' is intended to track the position of the first entry in\nthe index that has not yet been diffed or unpacked. It is advanced in two\nmain ways: either it is incremented when an index entry is marked as \"used\"\n(in 'mark_ce_used()'), indicating that it was unpacked or diffed, or when a\ndirectory is unpacked, in which case it is increased by an amount equaling\nthe number of index entries inside that tree.\n\nIn 17a1bb570b (unpack-trees: preserve cache_bottom, 2021-07-14), it was\nidentified that sparse directories posed a problem to the above\n'cache_bottom' advancement logic - because a sparse directory was both an\nindex entry that could be \"used\" and a directory that can be unpacked, the\n'cache_bottom' would be incremented too many times. To solve this problem,\nthe 'mark_ce_used()' advancement of 'cache_bottom' was skipped for sparse\ndirectories.\n\nINCORRECT CACHE_BOTTOM TRACKING\n-------------------------------\nSkipping the 'cache_bottom' advancement for sparse directories in\n'mark_ce_used()' breaks down in two cases:\n\n1. When the 'unpack_trees()' operation is *not* a \"cache diff\" (because the\n   directory contents-based incrementing of 'cache_bottom' does not happen).\n2. When a cache diff is performed with a pathspec (because\n   'unpack_index_entry()' will unpack a sparse directory not matched by the\n   pathspec without performing the directory contents-based increment).\n\nThe former luckily does not appear to affect 'git' behavior, likely because\n'cache_bottom' is largely unused (non-\"cache diff\" 'unpack_trees()' uses\n'find_index_entry()' - rather than 'next_cache_entry()' - to find the index\nentries to unpack).\n\nThe latter, however, causes 'cache_bottom' to \"lag behind\" its intended\nposition by an amount equal to the number of sparse directories unpacked so\nfar with 'unpack_index_entry()'. If a repository is structured such that any\nsparse directories are ordered lexicographically *after* any\npathspec-matching directories, though, this issue won't present any adverse\nbehavior.\n\nThis was the case with the 't1092-sparse-checkout-compatibility.sh' tests\nbefore the addition of the 'before/' sparse directory (ordered *before* the\nin-cone 'deep/' directory), therefore sidestepping the issue. Once the\n'before/' directory was added, though, 'cache_bottom' began to lag behind\nits intended position, causing 'next_cache_entry()' to return index entries\nit had already processed and, ultimately, an incorrect diff.\n\nCORRECTING CACHE_BOTTOM\n-----------------------\nThe problems observed in 't1092' come from 'cache_bottom' lagging behind in\ncases where the cache tree-based advancement doesn't occur. To solve this,\nthen, the fix in 17a1bb570b is \"reversed\"; rather than skipping\n'cache_bottom' advancement in 'mark_ce_used()', we skip the directory\ncontents-based advancement for sparse directories. Now, every index entry\ncan be accounted for in 'cache_bottom':\n\n* if you're working with a single index entry, 'cache_bottom' is incremented\n  in 'mark_ce_used()'\n* if you're working with a directory that contains index entries (but is not\n  one itself), 'cache_bottom' is incremented by the number of entries in\n  that directory.\n\nFinally, change the 'test_expect_failure' tests in 't1092' failing due to\nthis bug back to 'test_expect_success'.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n t/t1092-sparse-checkout-compatibility.sh |  6 +++---\n unpack-trees.c                           | 16 ++++++++--------\n 2 files changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex dcd7061fb3b..236ab530284 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -340,7 +340,7 @@ test_expect_success 'deep changes during checkout' '\n \ttest_all_match git checkout base\n '\n \n-test_expect_failure 'add outside sparse cone' '\n+test_expect_success 'add outside sparse cone' '\n \tinit_repos &&\n \n \trun_on_sparse mkdir folder1 &&\n@@ -382,7 +382,7 @@ test_expect_success 'commit including unstaged changes' '\n \ttest_all_match git status --porcelain=v2\n '\n \n-test_expect_failure 'status/add: outside sparse cone' '\n+test_expect_success 'status/add: outside sparse cone' '\n \tinit_repos &&\n \n \t# folder1 is at HEAD, but outside the sparse cone\n@@ -593,7 +593,7 @@ test_expect_success 'checkout and reset (keep)' '\n \ttest_all_match test_must_fail git reset --keep deepest\n '\n \n-test_expect_failure 'reset with pathspecs inside sparse definition' '\n+test_expect_success 'reset with pathspecs inside sparse definition' '\n \tinit_repos &&\n \n \twrite_script edit-contents <<-\\EOF &&\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 2763a029a17..b82c1a9705e 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -595,13 +595,6 @@ static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)\n {\n \tce->ce_flags |= CE_UNPACKED;\n \n-\t/*\n-\t * If this is a sparse directory, don't advance cache_bottom.\n-\t * That will be advanced later using the cache-tree data.\n-\t */\n-\tif (S_ISSPARSEDIR(ce->ce_mode))\n-\t\treturn;\n-\n \tif (o->cache_bottom < o->src_index->cache_nr &&\n \t    o->src_index->cache[o->cache_bottom] == ce) {\n \t\tint bottom = o->cache_bottom;\n@@ -1478,7 +1471,14 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \t\t\t * it does not do any look-ahead, so this is safe.\n \t\t\t */\n \t\t\tif (matches) {\n-\t\t\t\to->cache_bottom += matches;\n+\t\t\t\t/*\n+\t\t\t\t * Only increment the cache_bottom if the\n+\t\t\t\t * directory isn't a sparse directory index\n+\t\t\t\t * entry (if it is, it was already incremented)\n+\t\t\t\t * in 'mark_ce_used()'\n+\t\t\t\t */\n+\t\t\t\tif (!src[0] || !S_ISSPARSEDIR(src[0]->ce_mode))\n+\t\t\t\t\to->cache_bottom += matches;\n \t\t\t\treturn mask;\n \t\t\t}\n \t\t}\n-- \ngitgitgadget\n\n"},{"id":"451568","messageId":"d74b304f560a789594cfa6eb57e677464a0b34cb.1647532537.git.gitgitgadget@gmail.com","threadId":"57574","inReplyTo":"pull.1179.v2.git.1647532536.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] Revert \"unpack-trees: improve performance of next_cache_entry\"","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-03-17T15:55:36Z","receivedAt":"2022-03-17T15:55:53Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nThis reverts commit f2a454e0a5 (unpack-trees: improve performance of\nnext_cache_entry, 2021-11-29).\n\nThe \"hint\" value was originally needed to improve performance in 'git reset\n-- <pathspec>' caused by 'cache_bottom' lagging behind its correct value\nwhen using a sparse index. The 'cache_bottom' tracking has since been\ncorrected, removing the need for an additional \"pseudo-cache_bottom\"\ntracking variable.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n unpack-trees.c | 23 ++++++-----------------\n 1 file changed, 6 insertions(+), 17 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex b82c1a9705e..7f528d35cc2 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -644,24 +644,17 @@ static void mark_ce_used_same_name(struct cache_entry *ce,\n \t}\n }\n \n-static struct cache_entry *next_cache_entry(struct unpack_trees_options *o, int *hint)\n+static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n {\n \tconst struct index_state *index = o->src_index;\n \tint pos = o->cache_bottom;\n \n-\tif (*hint > pos)\n-\t\tpos = *hint;\n-\n \twhile (pos < index->cache_nr) {\n \t\tstruct cache_entry *ce = index->cache[pos];\n-\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n-\t\t\t*hint = pos + 1;\n+\t\tif (!(ce->ce_flags & CE_UNPACKED))\n \t\t\treturn ce;\n-\t\t}\n \t\tpos++;\n \t}\n-\n-\t*hint = pos;\n \treturn NULL;\n }\n \n@@ -1409,13 +1402,12 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str\n \n \t/* Are we supposed to look at the index too? */\n \tif (o->merge) {\n-\t\tint hint = -1;\n \t\twhile (1) {\n \t\t\tint cmp;\n \t\t\tstruct cache_entry *ce;\n \n \t\t\tif (o->diff_index_cached)\n-\t\t\t\tce = next_cache_entry(o, &hint);\n+\t\t\t\tce = next_cache_entry(o);\n \t\t\telse\n \t\t\t\tce = find_cache_entry(info, p);\n \n@@ -1777,7 +1769,7 @@ static int verify_absent(const struct cache_entry *,\n int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)\n {\n \tstruct repository *repo = the_repository;\n-\tint i, hint, ret;\n+\tint i, ret;\n \tstatic struct cache_entry *dfc;\n \tstruct pattern_list pl;\n \tint free_pattern_list = 0;\n@@ -1869,15 +1861,13 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tinfo.pathspec = o->pathspec;\n \n \t\tif (o->prefix) {\n-\t\t\thint = -1;\n-\n \t\t\t/*\n \t\t\t * Unpack existing index entries that sort before the\n \t\t\t * prefix the tree is spliced into.  Note that o->merge\n \t\t\t * is always true in this case.\n \t\t\t */\n \t\t\twhile (1) {\n-\t\t\t\tstruct cache_entry *ce = next_cache_entry(o, &hint);\n+\t\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n \t\t\t\tif (!ce)\n \t\t\t\t\tbreak;\n \t\t\t\tif (ce_in_traverse_path(ce, &info))\n@@ -1898,9 +1888,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \n \t/* Any left-over entries in the index? */\n \tif (o->merge) {\n-\t\thint = -1;\n \t\twhile (1) {\n-\t\t\tstruct cache_entry *ce = next_cache_entry(o, &hint);\n+\t\t\tstruct cache_entry *ce = next_cache_entry(o);\n \t\t\tif (!ce)\n \t\t\t\tbreak;\n \t\t\tif (unpack_index_entry(ce, o) < 0)\n-- \ngitgitgadget\n"},{"id":"451747","messageId":"df403c7b-5152-492a-96b5-575ccc1520de@github.com","threadId":"57574","inReplyTo":"cf8dc50c300a08f54d0cf69c82d4d979922a8143.1647532536.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/3] unpack-trees: increment cache_bottom for sparse directories","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-03-21T19:03:01Z","receivedAt":"2022-03-21T19:03:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/17/2022 11:55 AM, Victoria Dye via GitGitGadget wrote:\n> From: Victoria Dye <vdye@github.com>\n> \n> Correct tracking of the 'cache_bottom' for cases where sparse directories\n> are present in the index.\n\nThank you for the detailed background (that I cut from my reply).\n\n> CORRECTING CACHE_BOTTOM\n> -----------------------\n> The problems observed in 't1092' come from 'cache_bottom' lagging behind in\n> cases where the cache tree-based advancement doesn't occur. To solve this,\n> then, the fix in 17a1bb570b is \"reversed\"; rather than skipping\n> 'cache_bottom' advancement in 'mark_ce_used()', we skip the directory\n> contents-based advancement for sparse directories. Now, every index entry\n> can be accounted for in 'cache_bottom':\n\nI have sufficient background to be confident that you are doing the\nright thing here!\n\n> -test_expect_failure 'add outside sparse cone' '\n> +test_expect_success 'add outside sparse cone' '\n\n> -test_expect_failure 'status/add: outside sparse cone' '\n> +test_expect_success 'status/add: outside sparse cone' '\n\n> -test_expect_failure 'reset with pathspecs inside sparse definition' '\n> +test_expect_success 'reset with pathspecs inside sparse definition' '\n\nLove to see it.\n\n>  \t\t\tif (matches) {\n> -\t\t\t\to->cache_bottom += matches;\n> +\t\t\t\t/*\n> +\t\t\t\t * Only increment the cache_bottom if the\n> +\t\t\t\t * directory isn't a sparse directory index\n> +\t\t\t\t * entry (if it is, it was already incremented)\n> +\t\t\t\t * in 'mark_ce_used()'\n> +\t\t\t\t */\n> +\t\t\t\tif (!src[0] || !S_ISSPARSEDIR(src[0]->ce_mode))\n> +\t\t\t\t\to->cache_bottom += matches;\n>  \t\t\t\treturn mask;\n\nLooks great.\n\nThanks,\n-Stolee\n"},{"id":"451751","messageId":"b4803b58-018b-fb02-717f-95e48d6f844a@github.com","threadId":"57574","inReplyTo":"pull.1179.v2.git.1647532536.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/3] Fix use of 'cache_bottom' in sparse index","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-03-21T19:12:07Z","receivedAt":"2022-03-21T19:12:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/17/2022 11:55 AM, Victoria Dye via GitGitGadget wrote:\n> To fix this, the 'cache_bottom' advancement is reinstated in\n> 'mark_ce_used(...)', and instead it is disabled in 'unpack_callback(...)' if\n> the tree in question is a sparse directory. This corrects both the\n> non-\"cache diff\" cases and the 'unpack_index_entry(...)' cases while\n> preventing the double-advancement 17a1bb570b originally intended to avoid\n> (patch [2/3]).\n\nThank you for digging deep and finding the root cause here _and_ the\ncorrect fix.\n \n> Finally, now that the cache bottom is advanced properly, we can revert the\n> \"performance improvement\" introduced in f2a454e0a5 (unpack-trees: improve\n> performance of next_cache_entry, 2021-11-29) that mitigated performance\n> issues arising in 'next_cache_entry(...)' from the non-advancing\n> 'cache_bottom' (patch [3/3]). The performance results in\n> 'p2000-sparse-operations.sh' showed expected variability around 0% change in\n> execution time (+/= 0.04s, depending on the command), with example results\n> for potentially-affected commands below.\n> \n> 'git reset'                      master            this_series                  \n> ------------------------------------------------------------------------\n> full-v3                          0.51(0.21+0.27)   0.50(0.21+0.25) -2.0%\n> full-v4                          0.51(0.22+0.27)   0.50(0.21+0.24) -2.0%\n> sparse-v3                        0.30(0.04+0.55)   0.28(0.04+0.50) -6.7%\n> sparse-v4                        0.31(0.04+0.51)   0.29(0.04+0.51) -6.5%\n> \n> 'git reset -- does-not-exist'    master            this_series                  \n> ------------------------------------------------------------------------\n> full-v3                          0.54(0.23+0.27)   0.55(0.22+0.28) +1.9%\n> full-v4                          0.56(0.25+0.26)   0.54(0.24+0.26) -3.6%\n> sparse-v3                        0.31(0.04+0.54)   0.31(0.04+0.50) +0.0%\n> sparse-v4                        0.31(0.04+0.52)   0.31(0.04+0.50) +0.0%\n> \n> 'git diff --cached'              master            this_series    \n> -------------------------------------------------------------------------\n> full-v3                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\n> full-v4                          0.09(0.04+0.04)   0.09(0.04+0.04) +0.0%\n> sparse-v3                        0.05(0.01+0.02)   0.05(0.01+0.03) +0.0%\n> sparse-v4                        0.04(0.01+0.02)   0.04(0.01+0.02) +0.0%\n\nI'm glad this also makes things simpler here. It's interesting that\nit previously manifested only as a performance issue and not a\ncorrectness issue.\n  \nI carefully read these patches and think they are ready to go.\n\nThanks,\n-Stolee\n"},{"id":"451769","messageId":"xmqqr16vvxhy.fsf@gitster.g","threadId":"57574","inReplyTo":"df403c7b-5152-492a-96b5-575ccc1520de@github.com","subject":"Re: [PATCH v2 2/3] unpack-trees: increment cache_bottom for sparse directories","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-03-21T20:52:57Z","receivedAt":"2022-03-21T20:53:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> On 3/17/2022 11:55 AM, Victoria Dye via GitGitGadget wrote:\n>> From: Victoria Dye <vdye@github.com>\n>> \n>> Correct tracking of the 'cache_bottom' for cases where sparse directories\n>> are present in the index.\n>\n> Thank you for the detailed background (that I cut from my reply).\n>\n>> CORRECTING CACHE_BOTTOM\n>> -----------------------\n>> The problems observed in 't1092' come from 'cache_bottom' lagging behind in\n>> cases where the cache tree-based advancement doesn't occur. To solve this,\n>> then, the fix in 17a1bb570b is \"reversed\"; rather than skipping\n>> 'cache_bottom' advancement in 'mark_ce_used()', we skip the directory\n>> contents-based advancement for sparse directories. Now, every index entry\n>> can be accounted for in 'cache_bottom':\n>\n> I have sufficient background to be confident that you are doing the\n> right thing here!\n\n;-)  \n\nThe \"partly lagging\" walking of the index guided by cache_bottom has\nbeen a tricky thing in the unpack_trees machinery, and I am very\nhappy that we now have two more experts on the topic ;-)\n\nThanks, both.\n\n"}]}