git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "Victoria Dye via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: stolee@gmail.com, gitster@pobox.com, newren@gmail.com,
	"Taylor Blau" <me@ttaylorr.com>,
	"Bagas Sanjaya" <bagasdotme@gmail.com>,
	"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
	"Phillip Wood" <phillip.wood123@gmail.com>,
	"Emily Shaffer" <emilyshaffer@google.com>,
	"Victoria Dye" <vdye@github.com>
Subject: [PATCH v6 0/8] Sparse Index: integrate with reset
Date: Mon, 29 Nov 2021 15:52:35 +0000	[thread overview]
Message-ID: <pull.1048.v6.git.1638201164.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1048.v5.git.1635345563.gitgitgadget@gmail.com>

This series integrates the sparse index with git reset and provides
miscellaneous fixes and improvements to the command in sparse checkouts.
This includes:

 1. tests added to t1092 and p2000 to establish the baseline functionality
    of the command
 2. repository settings to enable the sparse index with ensure_full_index
    guarding any code paths that break tests without other compatibility
    updates.
 3. modifications to remove or reduce the scope in which ensure_full_index
    must be called.

The sparse index updates are predicated on a fix originating from the
microsoft/git fork [1], correcting how git reset --mixed handles resetting
entries outside the sparse checkout definition. Additionally, a performance
"bug" in next_cache_entry with sparse index is corrected, preventing
repeatedly looping over already-searched entries.

The p2000 tests demonstrate a ~70% execution time reduction in git reset
using a sparse index, and no change (within expected variability [2]) using
a full index. Results summarized below [3, 4]:

Test                           base              [5/8]                 
-----------------------------------------------------------------------
git reset --hard (full-v3)     1.00(0.50+0.39)   0.97(0.50+0.37) -3.0% 
git reset --hard (full-v4)     1.00(0.51+0.38)   0.96(0.50+0.36) -4.0% 
git reset --hard (sparse-v3)   1.68(1.17+0.39)   1.37(0.91+0.35) -18.5%
git reset --hard (sparse-v4)   1.70(1.18+0.40)   1.41(0.94+0.35) -17.1%

Test                           base              [6/8]   
-----------------------------------------------------------------------
git reset --hard (full-v3)     1.00(0.50+0.39)   0.94(0.48+0.34) -6.0% 
git reset --hard (full-v4)     1.00(0.51+0.38)   0.95(0.51+0.34) -5.0% 
git reset --hard (sparse-v3)   1.68(1.17+0.39)   0.46(0.05+0.29) -72.6%
git reset --hard (sparse-v4)   1.70(1.18+0.40)   0.46(0.06+0.29) -72.9%

Test                               base              [7/8]
---------------------------------------------------------------------------
git reset (full-v3)                0.77(0.27+0.37)   0.72(0.26+0.32) -6.5%
git reset (full-v4)                0.75(0.27+0.34)   0.73(0.26+0.32) -2.7%
git reset (sparse-v3)              1.44(0.96+0.36)   0.43(0.04+0.96) -70.1%
git reset (sparse-v4)              1.46(0.97+0.36)   0.43(0.05+0.79) -70.5%
git reset -- missing (full-v3)     0.72(0.26+0.32)   0.69(0.26+0.30) -4.2%
git reset -- missing (full-v4)     0.74(0.28+0.33)   0.71(0.27+0.32) -4.1% 
git reset -- missing (sparse-v3)   1.45(0.97+0.35)   0.81(0.42+0.90) -44.1%
git reset -- missing (sparse-v4)   1.41(0.94+0.34)   0.79(0.42+0.76) -44.0%

Test                               base              [8/8]            
---------------------------------------------------------------------------
git reset -- missing (full-v3)     0.72(0.26+0.32)   0.73(0.26+0.33) +1.4% 
git reset -- missing (full-v4)     0.74(0.28+0.33)   0.74(0.27+0.32) +0.0% 
git reset -- missing (sparse-v3)   1.45(0.97+0.35)   0.43(0.05+0.80) -70.3%
git reset -- missing (sparse-v4)   1.41(0.94+0.34)   0.44(0.05+0.76) -68.8%



Changes since V1
================

 * Add --force-full-index option to update-index. The option is used
   circumvent changing command_requires_full_index from its default value -
   right now this is effectively a no-op, but will change once update-index
   is integrated with sparse index. By using this option in the t1092
   expand/collapse test, the command used to test will not need to be
   updated with subsequent sparse index integrations.
 * Update implementation of mixed reset for entries outside sparse checkout
   definition. The condition in which a file should be checked out before
   index reset is simplified to "if it has skip-worktree enabled and a reset
   would change the file, check it out".
   * After checking the behavior of update_index_from_diff with renames,
     found that the diff used by reset does not produce diff queue entries
     with different pathnames for one and two. Because of this, and that
     nothing in the implementation seems to rely on identical path names, no
     BUG check is added.
 * Correct a bug in the sparse index is not expanded tests in t1092 where
   failure of a git reset --mixed test was not being reported. Test now
   verifies an appropriate scenario with corrected failure-checking.


Changes since V2
================

 * Replace patch adding checkouts for git reset --mixed with sparse checkout
   with preserving the skip-worktree flag (including a new test for git
   reset --mixed and update to t1092 - checkout and reset (mixed))
 * Move rename of is_missing into its own patch
 * Further extend t1092 tests and remove unnecessary commands/tests where
   possible
 * Refine logic determining which pathspecs require ensure_full_index in git
   reset --mixed, add related ensure_not_expanded tests
 * Add index_search_mode enum to index_name_stage_pos
 * Clean up variable usage & remove unnecessary subtree_path in
   prime_cache_tree_rec
 * Update cover letter performance data
 * More thoroughly explain changes in each commit message


Changes since V3
================

 * Replace git update-index --force-full-index with git reset update-folder1
   -- folder1/a, remove introduction of new --force-full-index option
   entirely, and add comment clarifying the intent of sparse-index is
   expanded and converted back test
 * Fix authorship on reset: preserve skip-worktree bit in mixed reset
   (current patch fully replaces original patch, but metadata of the
   original wasn't properly replaced)


Changes since V4
================

 * Update t1092 test 'checkout and reset (mixed)' to explicitly verify
   differences between sparse and full checkouts


Changes since V5
================

 * Update t1092 test 'reset with wildcard pathspec' with more cases and
   better checks
 * Add "special case" wildcard pathspec check when determining whether to
   expand the index (avoids double-loop over pathspecs & index entries)

Thanks! -Victoria

[1] microsoft@6b8a074 [2]
https://lore.kernel.org/git/8b9fe3f8-f0e3-4567-b20b-17c92bd1a5c5@github.com/
[3] If a test and/or commit is not mentioned, there is no significant change
to performance [4] Pathspec "does-not-exist" is changed to "missing" to save
space in performance report

Victoria Dye (8):
  reset: rename is_missing to !is_in_reset_tree
  reset: preserve skip-worktree bit in mixed reset
  sparse-index: update command for expand/collapse test
  reset: expand test coverage for sparse checkouts
  reset: integrate with sparse index
  reset: make sparse-aware (except --mixed)
  reset: make --mixed sparse-aware
  unpack-trees: improve performance of next_cache_entry

 builtin/reset.c                          | 113 ++++++++++++++++-
 cache-tree.c                             |  46 ++++++-
 cache.h                                  |  10 ++
 read-cache.c                             |  27 ++--
 t/perf/p2000-sparse-operations.sh        |   3 +
 t/t1092-sparse-checkout-compatibility.sh | 154 ++++++++++++++++++++---
 t/t7102-reset.sh                         |  17 +++
 unpack-trees.c                           |  23 +++-
 8 files changed, 356 insertions(+), 37 deletions(-)


base-commit: cefe983a320c03d7843ac78e73bd513a27806845
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1048%2Fvdye%2Fvdye%2Fsparse-index-part1-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1048/vdye/vdye/sparse-index-part1-v6
Pull-Request: https://github.com/gitgitgadget/git/pull/1048

Range-diff vs v5:

 1:  ad7013a31aa = 1:  ad7013a31aa reset: rename is_missing to !is_in_reset_tree
 2:  b221b00b7e0 = 2:  b221b00b7e0 reset: preserve skip-worktree bit in mixed reset
 3:  1bb2ca92c60 = 3:  1bb2ca92c60 sparse-index: update command for expand/collapse test
 4:  cc76c694647 ! 4:  741a2c9ffaa reset: expand test coverage for sparse checkouts
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'checkout and rese
      +test_expect_success 'reset with wildcard pathspec' '
      +	init_repos &&
      +
     -+	test_all_match git checkout -b reset-test update-deep &&
     -+	test_all_match git reset base -- \*/a &&
     -+	test_all_match git status --porcelain=v2 &&
     -+	test_all_match git rev-parse HEAD:folder1/a &&
     ++	test_all_match git reset update-deep -- deep\* &&
     ++	test_all_match git ls-files -s -- deep &&
      +
     -+	test_all_match git reset base -- folder\* &&
     -+	test_all_match git status --porcelain=v2 &&
     -+	test_all_match git rev-parse HEAD:folder2
     ++	test_all_match git reset deepest -- deep\*\*\* &&
     ++	test_all_match git ls-files -s -- deep &&
     ++
     ++	# The following `git reset`s result in updating the index on files with
     ++	# `skip-worktree` enabled. To avoid failing due to discrepencies in reported
     ++	# "modified" files, `test_sparse_match` reset is performed separately from
     ++	# "full-checkout" reset, then the index contents of all repos are verified.
     ++
     ++	test_sparse_match git reset update-folder1 -- \*/a &&
     ++	git -C full-checkout reset update-folder1 -- \*/a &&
     ++	test_all_match git ls-files -s -- deep/a folder1/a &&
     ++
     ++	test_sparse_match git reset update-folder2 -- folder\* &&
     ++	git -C full-checkout reset update-folder2 -- folder\* &&
     ++	test_all_match git ls-files -s -- folder10 folder1 folder2 &&
     ++
     ++	test_sparse_match git reset base -- folder1/\* &&
     ++	git -C full-checkout reset base -- folder1/\* &&
     ++	test_all_match git ls-files -s -- folder1
      +'
      +
       test_expect_success 'merge, cherry-pick, and rebase' '
 5:  217ae445418 = 5:  65b0eafd27c reset: integrate with sparse index
 6:  a3e2fd59867 = 6:  908c84005b9 reset: make sparse-aware (except --mixed)
 7:  a9135a5ed64 ! 7:  822d7344587 reset: make --mixed sparse-aware
     @@ Commit message
      
          Remove the `ensure_full_index` guard on `read_from_tree` and update `git
          reset --mixed` to ensure it can use sparse directory index entries wherever
     -    possible. Sparse directory entries are reset use `diff_tree_oid`, which
     +    possible. Sparse directory entries are reset using `diff_tree_oid`, which
          requires `change` and `add_remove` functions to process the internal
          contents of the sparse directory. The `recursive` diff option handles cases
          in which `reset --mixed` must diff/merge files that are nested multiple
     @@ builtin/reset.c: static void update_index_from_diff(struct diff_queue_struct *q,
      +		 * (since we can reset whole sparse directories without expanding them).
      +		 */
      +		if (item.nowildcard_len < item.len) {
     ++			/*
     ++			 * Special case: if the pattern is a path inside the cone
     ++			 * followed by only wildcards, the pattern cannot match
     ++			 * partial sparse directories, so we don't expand the index.
     ++			 */
     ++			if (path_in_cone_mode_sparse_checkout(item.original, &the_index) &&
     ++			    strspn(item.original + item.nowildcard_len, "*") == item.len - item.nowildcard_len)
     ++				continue;
     ++
      +			for (pos = 0; pos < active_nr; pos++) {
      +				struct cache_entry *ce = active_cache[pos];
      +
 8:  f91d1dcf024 = 8:  ddd97fb2837 unpack-trees: improve performance of next_cache_entry

-- 
gitgitgadget

  parent reply	other threads:[~2021-11-29 19:35 UTC|newest]

Thread overview: 114+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-09-30 14:50 [PATCH 0/7] " Victoria Dye via GitGitGadget
2021-09-30 14:50 ` [PATCH 1/7] reset: behave correctly with sparse-checkout Kevin Willford via GitGitGadget
2021-09-30 18:34   ` Junio C Hamano
2021-10-01 14:55     ` Victoria Dye
2021-09-30 14:50 ` [PATCH 2/7] sparse-index: update command for expand/collapse test Victoria Dye via GitGitGadget
2021-09-30 19:17   ` Taylor Blau
2021-09-30 20:11     ` Victoria Dye
2021-09-30 21:32       ` Junio C Hamano
2021-09-30 22:59         ` Victoria Dye
2021-10-01  0:04           ` Junio C Hamano
2021-10-04 13:47             ` Victoria Dye
2021-10-01  9:14   ` Bagas Sanjaya
2021-09-30 14:50 ` [PATCH 3/7] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-09-30 14:50 ` [PATCH 4/7] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-09-30 14:50 ` [PATCH 5/7] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-09-30 14:51 ` [PATCH 6/7] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-10-01 15:03   ` Victoria Dye
2021-09-30 14:51 ` [PATCH 7/7] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-10-05 13:20 ` [PATCH v2 0/7] Sparse Index: integrate with reset Victoria Dye via GitGitGadget
2021-10-05 13:20   ` [PATCH v2 1/7] reset: behave correctly with sparse-checkout Kevin Willford via GitGitGadget
2021-10-05 19:30     ` Junio C Hamano
2021-10-05 21:59       ` Victoria Dye
2021-10-06 12:44         ` Junio C Hamano
2021-10-06  1:46     ` Elijah Newren
2021-10-06 20:09       ` Victoria Dye
2021-10-06 10:31     ` Bagas Sanjaya
2021-10-05 13:20   ` [PATCH v2 2/7] update-index: add --force-full-index option for expand/collapse test Victoria Dye via GitGitGadget
2021-10-06  2:00     ` Elijah Newren
2021-10-06 20:40       ` Victoria Dye
2021-10-08  3:42         ` Elijah Newren
2021-10-08 17:11           ` Junio C Hamano
2021-10-06 10:33     ` Bagas Sanjaya
2021-10-05 13:20   ` [PATCH v2 3/7] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-10-06  2:04     ` Elijah Newren
2021-10-05 13:20   ` [PATCH v2 4/7] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-10-06  2:15     ` Elijah Newren
2021-10-06 17:48       ` Junio C Hamano
2021-10-05 13:20   ` [PATCH v2 5/7] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-10-06  3:43     ` Elijah Newren
2021-10-06 20:56       ` Victoria Dye
2021-10-06 10:34     ` Bagas Sanjaya
2021-10-05 13:20   ` [PATCH v2 6/7] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-10-06  4:43     ` Elijah Newren
2021-10-07 14:34       ` Victoria Dye
2021-10-05 13:20   ` [PATCH v2 7/7] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-10-06 10:37     ` Bagas Sanjaya
2021-10-05 15:34   ` [PATCH v2 0/7] Sparse Index: integrate with reset Ævar Arnfjörð Bjarmason
2021-10-05 20:44     ` Victoria Dye
2021-10-06  5:46   ` Elijah Newren
2021-10-07 21:15   ` [PATCH v3 0/8] " Victoria Dye via GitGitGadget
2021-10-07 21:15     ` [PATCH v3 1/8] reset: rename is_missing to !is_in_reset_tree Victoria Dye via GitGitGadget
2021-10-07 21:15     ` [PATCH v3 2/8] reset: preserve skip-worktree bit in mixed reset Kevin Willford via GitGitGadget
2021-10-08  9:04       ` Junio C Hamano
2021-10-07 21:15     ` [PATCH v3 3/8] update-index: add --force-full-index option for expand/collapse test Victoria Dye via GitGitGadget
2021-10-08  2:50       ` Bagas Sanjaya
2021-10-08  5:24       ` Junio C Hamano
2021-10-08 15:47         ` Victoria Dye
2021-10-08 17:19           ` Junio C Hamano
2021-10-11 14:12             ` Derrick Stolee
2021-10-11 15:05               ` Victoria Dye
2021-10-11 15:24               ` Junio C Hamano
2021-10-07 21:15     ` [PATCH v3 4/8] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-10-07 21:15     ` [PATCH v3 5/8] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-10-07 21:15     ` [PATCH v3 6/8] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-10-08 11:09       ` Phillip Wood
2021-10-08 17:14         ` Victoria Dye
2021-10-08 18:31           ` Junio C Hamano
2021-10-09 11:18             ` Phillip Wood
2021-10-10 22:03               ` Junio C Hamano
2021-10-11 15:55                 ` Victoria Dye
2021-10-11 16:16                   ` Junio C Hamano
2021-10-12 10:16                 ` Phillip Wood
2021-10-12 19:15                   ` Junio C Hamano
2021-10-12 10:17           ` Phillip Wood
2021-10-07 21:15     ` [PATCH v3 7/8] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-11-20 22:02       ` Elijah Newren
2021-11-22 16:46         ` Victoria Dye
2021-10-07 21:15     ` [PATCH v3 8/8] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-10-11 20:30     ` [PATCH v4 0/8] Sparse Index: integrate with reset Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 1/8] reset: rename is_missing to !is_in_reset_tree Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 2/8] reset: preserve skip-worktree bit in mixed reset Victoria Dye via GitGitGadget
2021-10-22  4:19         ` Emily Shaffer
2021-10-25 15:59           ` Victoria Dye
2021-10-11 20:30       ` [PATCH v4 3/8] sparse-index: update command for expand/collapse test Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 4/8] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 5/8] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 6/8] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 7/8] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-10-11 20:30       ` [PATCH v4 8/8] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-10-27 14:39       ` [PATCH v5 0/8] Sparse Index: integrate with reset Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 1/8] reset: rename is_missing to !is_in_reset_tree Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 2/8] reset: preserve skip-worktree bit in mixed reset Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 3/8] sparse-index: update command for expand/collapse test Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 4/8] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 5/8] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 6/8] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-10-27 14:39         ` [PATCH v5 7/8] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-11-20 22:05           ` Elijah Newren
2021-11-22 16:54             ` Victoria Dye
2021-10-27 14:39         ` [PATCH v5 8/8] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-11-20 22:13         ` [PATCH v5 0/8] Sparse Index: integrate with reset Elijah Newren
2021-11-29 15:52         ` Victoria Dye via GitGitGadget [this message]
2021-11-29 15:52           ` [PATCH v6 1/8] reset: rename is_missing to !is_in_reset_tree Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 2/8] reset: preserve skip-worktree bit in mixed reset Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 3/8] sparse-index: update command for expand/collapse test Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 4/8] reset: expand test coverage for sparse checkouts Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 5/8] reset: integrate with sparse index Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 6/8] reset: make sparse-aware (except --mixed) Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 7/8] reset: make --mixed sparse-aware Victoria Dye via GitGitGadget
2021-11-29 15:52           ` [PATCH v6 8/8] unpack-trees: improve performance of next_cache_entry Victoria Dye via GitGitGadget
2021-11-29 18:37           ` [PATCH v6 0/8] Sparse Index: integrate with reset Elijah Newren
2021-11-29 19:44             ` Victoria Dye
2021-11-30  3:59               ` Elijah Newren
2021-12-01 20:26               ` Ævar Arnfjörð Bjarmason

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=pull.1048.v6.git.1638201164.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=avarab@gmail.com \
    --cc=bagasdotme@gmail.com \
    --cc=emilyshaffer@google.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=me@ttaylorr.com \
    --cc=newren@gmail.com \
    --cc=phillip.wood123@gmail.com \
    --cc=stolee@gmail.com \
    --cc=vdye@github.com \
    --subject='Re: [PATCH v6 0/8] Sparse Index: integrate with reset' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).