git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
* [PATCH v1 0/2] grep: integrate with sparse index
@ 2022-08-17  7:56 Shaoxuan Yuan
  2022-08-17  7:56 ` [PATCH v1 1/2] builtin/grep.c: add --sparse option Shaoxuan Yuan
                   ` (7 more replies)
  0 siblings, 8 replies; 71+ messages in thread
From: Shaoxuan Yuan @ 2022-08-17  7:56 UTC (permalink / raw)
  To: git; +Cc: derrickstolee, vdye, Shaoxuan Yuan

Integrate `git-grep` with sparse-index and test the performance
improvement.

Note: This series is based on 'next' because the 'rm' series
ede241c715 (rm: integrate with sparse-index, Aug 7th 2022) is in the
'next', and the test cases overlap. Base on top of 'next' makes sure
there are no conflicts to reduce work for Junio.

Shaoxuan Yuan (2):
  builtin/grep.c: add --sparse option
  builtin/grep.c: integrate with sparse index

 builtin/grep.c                           | 18 +++++++++++++++---
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 17 +++++++++++++++++
 t/t7817-grep-sparse-checkout.sh          | 12 ++++++------
 4 files changed, 39 insertions(+), 9 deletions(-)


base-commit: c19287026c9b940f7f43d34e6dacbd5c34e4a2e0
-- 
2.37.0


^ permalink raw reply	[flat|nested] 71+ messages in thread
* [PATCH v6 0/1] grep: integrate with sparse index
@ 2022-09-23  4:15 Shaoxuan Yuan
  2022-09-23  4:21 ` Shaoxuan Yuan
  0 siblings, 1 reply; 71+ messages in thread
From: Shaoxuan Yuan @ 2022-09-23  4:15 UTC (permalink / raw)
  To: git, newren, avarab; +Cc: derrickstolee, gitster, vdye, Shaoxuan Yuan

Integrate `git-grep` with sparse-index and test the performance
improvement.

Changes since v5
----------------

* Drop the `--sparse` option patch and edit corresponding tests. 
  We can wait until a better name is decided to replace `--sparse`.

* Modify the commit message, especially get rid of the `--sparse`
  occurences.

Changes since v4
----------------
* Reset the length of `struct strbuf name` back to `name_base_len`,
  instead of 0, after `grep_tree()` returns.

* Add test cases in t1092 for `grep` recursing into submodules.

* Add a few NEEDSWORK to explain the current problem with submodules.

Changes since v3
----------------
* Shorten the perf result tables in commit message.

* Update the commit message to reflect the changes in the commit.

* Update the commit message to indicate the performance improvement
  is dependent on the pathspec.

* Stop passing `ce_mode` through `check_attr`. Instead, set the
  `base_len` to 0 to make the code more reasonable and less abuse of
  `check_attr`.

* Remove another invention of `base`. Use the existing `name` as the
  argument for `grep_tree()`, and reset it back to `ce->name` after
  `grep_tree()` returns.

* Update the p2000 test to use a more general pathspec for better
  compatibility (i.e. do not use git repository specific pathspec).

* Add tests to t1092 'grep is not expanded' to verify the change
  brought by "builtin/grep.c: walking tree instead of expanding index
  with --sparse": the index *never* expands.

Changes since v2
----------------

* Modify the commit message for "builtin/grep.c: integrate with sparse
  index" to make it obvious that the perf test results are not from
  p2000 tests, but from manual perf runs.

* Add tree-walking logic as an extra (the third) patch to improve the
  performance when --sparse is used. This resolved the left-over-bit
  in v2 [1].

[1] https://lore.kernel.org/git/20220829232843.183711-1-shaoxuan.yuan02@gmail.com/

Changes since v1
----------------

* Rewrite the commit message for "builtin/grep.c: add --sparse option"
  to be clearer.

* Update the documentation (both in-code and man page) for --sparse.

* Add a few tests to test the new behavior (when _only_ --cached is
  supplied).

* Reformat the perf test results to not look like directly from p2000
  tests.

* Put the "command_requires_full_index" lines right after parse_options().

* Add a pathspec test in t1092, and reword a few test documentations.

Shaoxuan Yuan (1):
  builtin/grep.c: integrate with sparse index

 builtin/grep.c                           | 48 +++++++++++++++-
 t/perf/p2000-sparse-operations.sh        |  1 +
 t/t1092-sparse-checkout-compatibility.sh | 72 ++++++++++++++++++++++++
 3 files changed, 118 insertions(+), 3 deletions(-)

Range-diff against v5:
1:  1d00d23bf9 < -:  ---------- builtin/grep.c: add --sparse option
2:  926b8d2462 < -:  ---------- builtin/grep.c: integrate with sparse index
3:  18b65034fe ! 1:  8604111d74 builtin/grep.c: walking tree instead of expanding index with --sparse
    @@ Metadata
     Author: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com>
     
      ## Commit message ##
    -    builtin/grep.c: walking tree instead of expanding index with --sparse
    +    builtin/grep.c: integrate with sparse index
     
    -    Before this patch, whenever --sparse is used, `git-grep` utilizes the
    -    ensure_full_index() method to expand the index and search all the
    -    entries. Because this method requires walking all the trees and
    -    constructing the index, it is the slow part within the whole command.
    +    Turn on sparse index and remove ensure_full_index().
    +
    +    Before this patch, `git-grep` utilizes the ensure_full_index() method to
    +    expand the index and search all the entries. Because this method
    +    requires walking all the trees and constructing the index, it is the
    +    slow part within the whole command.
     
         To achieve better performance, this patch uses grep_tree() to search the
         sparse directory entries and get rid of the ensure_full_index() method.
    @@ Commit message
            result of expanding the index.
     
         2) grep_tree() utilizes pathspecs to limit the scope of searching.
    -       ensure_full_index() always expands the index when --sparse is used,
    -       that means it will always walk all the trees and blobs in the repo
    -       without caring if the user only wants a subset of the content, i.e.
    -       using a pathspec. On the other hand, grep_tree() will only search
    -       the contents that match the pathspec, and thus possibly walking fewer
    -       trees.
    +       ensure_full_index() always expands the index, which means it will
    +       always walk all the trees and blobs in the repo without caring if
    +       the user only wants a subset of the content, i.e. using a pathspec.
    +       On the other hand, grep_tree() will only search the contents that
    +       match the pathspec, and thus possibly walking fewer trees.
     
         3) grep_tree() does not construct and copy back a new index, while
            ensure_full_index() does. This also saves some time.
    @@ Commit message
         - Summary:
     
         p2000 tests demonstrate a ~71% execution time reduction for
    -    `git grep --cached --sparse bogus -- "f2/f1/f1/*"` using tree-walking
    -    logic. However, notice that this result varies depending on the pathspec
    +    `git grep --cached bogus -- "f2/f1/f1/*"` using tree-walking logic.
    +    However, notice that this result varies depending on the pathspec
         given. See below "Command used for testing" for more details.
     
         Test                              HEAD~   HEAD
    @@ Commit message
     
         - Command used for testing:
     
    -            git grep --cached --sparse bogus -- "f2/f1/f1/*"
    +            git grep --cached bogus -- "f2/f1/f1/*"
     
         The reason for specifying a pathspec is that, if we don't specify a
         pathspec, then grep_tree() will walk all the trees and blobs to find the
    @@ Commit message
     
                 Command used:
     
    -                    git grep --cached --sparse bogus
    +                    git grep --cached bogus
     
                 Test                                HEAD~  HEAD
                 ---------------------------------------------------
    @@ Commit message
         Suggested-by: Derrick Stolee <derrickstolee@github.com>
         Helped-by: Derrick Stolee <derrickstolee@github.com>
         Helped-by: Victoria Dye <vdye@github.com>
    +    Helped-by: Elijah Newren <newren@gmail.com>
         Signed-off-by: Shaoxuan Yuan <shaoxuan.yuan02@gmail.com>
     
      ## builtin/grep.c ##
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
      	if (repo_read_index(repo) < 0)
      		die(_("index file corrupt"));
      
    --	if (grep_sparse)
    --		ensure_full_index(repo->index);
    --
    +-	/* TODO: audit for interaction with sparse-index. */
    +-	ensure_full_index(repo->index);
      	for (nr = 0; nr < repo->index->cache_nr; nr++) {
      		const struct cache_entry *ce = repo->index->cache[nr];
      
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
     +			struct tree_desc tree;
     +			void *data;
     +			unsigned long size;
    -+
    -+			data = read_object_file(&ce->oid, &type, &size);
    -+			init_tree_desc(&tree, data, size);
      
     -		if (S_ISREG(ce->ce_mode) &&
    ++			data = read_object_file(&ce->oid, &type, &size);
    ++			init_tree_desc(&tree, data, size);
    ++
     +			hit |= grep_tree(opt, pathspec, &tree, &name, 0, 0);
     +			strbuf_setlen(&name, name_base_len);
     +			strbuf_addstr(&name, ce->name);
    @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
      		    match_pathspec(repo->index, pathspec, name.buf, name.len, 0, NULL,
      				   S_ISDIR(ce->ce_mode) ||
      				   S_ISGITLINK(ce->ce_mode))) {
    +@@ builtin/grep.c: int cmd_grep(int argc, const char **argv, const char *prefix)
    + 			     PARSE_OPT_KEEP_DASHDASH |
    + 			     PARSE_OPT_STOP_AT_NON_OPTION);
    + 
    ++	if (the_repository->gitdir) {
    ++		prepare_repo_settings(the_repository);
    ++		the_repository->settings.command_requires_full_index = 0;
    ++	}
    ++
    + 	if (use_index && !startup_info->have_repository) {
    + 		int fallback = 0;
    + 		git_config_get_bool("grep.fallbacktonoindex", &fallback);
     
      ## t/perf/p2000-sparse-operations.sh ##
     @@ t/perf/p2000-sparse-operations.sh: test_perf_on_all git read-tree -mu HEAD
    @@ t/t1092-sparse-checkout-compatibility.sh: init_repos () {
      run_on_sparse () {
      	(
      		cd sparse-checkout &&
    -@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expanded' '
    +@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'sparse index is not expanded: rm' '
    + 	ensure_not_expanded rm -r deep
    + '
      
    - 	# All files within the folder1/* pathspec are sparse,
    - 	# so this command does not find any matches
    --	ensure_not_expanded ! grep a -- folder1/*
    ++test_expect_success 'grep with and --cached' '
    ++	init_repos &&
    ++
    ++	test_all_match git grep --cached a &&
    ++	test_all_match git grep --cached a -- "folder1/*"
    ++'
    ++
    ++test_expect_success 'grep is not expanded' '
    ++	init_repos &&
    ++
    ++	ensure_not_expanded grep a &&
    ++	ensure_not_expanded grep a -- deep/* &&
    ++
    ++	# All files within the folder1/* pathspec are sparse,
    ++	# so this command does not find any matches
     +	ensure_not_expanded ! grep a -- folder1/* &&
     +
     +	# test out-of-cone pathspec with or without wildcard
    -+	ensure_not_expanded grep --sparse --cached a -- "folder1/a" &&
    -+	ensure_not_expanded grep --sparse --cached a -- "folder1/*" &&
    ++	ensure_not_expanded grep --cached a -- "folder1/a" &&
    ++	ensure_not_expanded grep --cached a -- "folder1/*" &&
     +
     +	# test in-cone pathspec with or without wildcard
    -+	ensure_not_expanded grep --sparse --cached a -- "deep/a" &&
    -+	ensure_not_expanded grep --sparse --cached a -- "deep/*"
    ++	ensure_not_expanded grep --cached a -- "deep/a" &&
    ++	ensure_not_expanded grep --cached a -- "deep/*"
     +'
     +
     +# NEEDSWORK: when running `grep` in the superproject with --recurse-submodules,
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expan
     +	# do not use ensure_not_expanded() here, becasue `grep` should be
     +	# run in the superproject, not in "./sparse-index"
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
    -+	git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" &&
    ++	git grep --cached --recurse-submodules a -- "*/folder1/*" &&
     +	test_region ! index ensure_full_index trace2.txt
     +'
     +
    @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'grep is not expan
     +	sparse-checkout/folder1/a:a
     +	sparse-index/folder1/a:a
     +	EOF
    -+	git grep --sparse --cached --recurse-submodules a -- "*/folder1/*" >actual &&
    ++	git grep --cached --recurse-submodules a -- "*/folder1/*" >actual &&
     +	test_cmp actual expect
    - '
    - 
    ++'
    ++
      test_done

base-commit: 1b3d6e17fe83eb6f79ffbac2f2c61bbf1eaef5f8
-- 
2.37.0


^ permalink raw reply	[flat|nested] 71+ messages in thread

end of thread, other threads:[~2022-09-26 17:55 UTC | newest]

Thread overview: 71+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-17  7:56 [PATCH v1 0/2] grep: integrate with sparse index Shaoxuan Yuan
2022-08-17  7:56 ` [PATCH v1 1/2] builtin/grep.c: add --sparse option Shaoxuan Yuan
2022-08-17 14:12   ` Derrick Stolee
2022-08-17 17:13     ` Junio C Hamano
2022-08-17 17:34       ` Victoria Dye
2022-08-17 17:43         ` Derrick Stolee
2022-08-17 18:47           ` Junio C Hamano
2022-08-17 17:37     ` Elijah Newren
2022-08-24 18:20     ` Shaoxuan Yuan
2022-08-24 19:08       ` Derrick Stolee
2022-08-17  7:56 ` [PATCH v1 2/2] builtin/grep.c: integrate with sparse index Shaoxuan Yuan
2022-08-17 14:23   ` Derrick Stolee
2022-08-24 21:06     ` Shaoxuan Yuan
2022-08-25  0:39       ` Derrick Stolee
2022-08-17 13:46 ` [PATCH v1 0/2] grep: " Derrick Stolee
2022-08-29 23:28 ` [PATCH v2 " Shaoxuan Yuan
2022-08-29 23:28   ` [PATCH v2 1/2] builtin/grep.c: add --sparse option Shaoxuan Yuan
2022-08-29 23:28   ` [PATCH v2 2/2] builtin/grep.c: integrate with sparse index Shaoxuan Yuan
2022-08-30 13:45     ` Derrick Stolee
2022-09-01  4:57 ` [PATCH v3 0/3] grep: " Shaoxuan Yuan
2022-09-01  4:57   ` [PATCH v3 1/3] builtin/grep.c: add --sparse option Shaoxuan Yuan
2022-09-01  4:57   ` [PATCH v3 2/3] builtin/grep.c: integrate with sparse index Shaoxuan Yuan
2022-09-01  4:57   ` [PATCH v3 3/3] builtin/grep.c: walking tree instead of expanding index with --sparse Shaoxuan Yuan
2022-09-01 17:03     ` Derrick Stolee
2022-09-01 18:31       ` Shaoxuan Yuan
2022-09-01 17:17     ` Junio C Hamano
2022-09-01 17:27       ` Junio C Hamano
2022-09-01 22:49         ` Shaoxuan Yuan
2022-09-01 22:36       ` Shaoxuan Yuan
2022-09-02  3:28     ` Victoria Dye
2022-09-02 18:47       ` Shaoxuan Yuan
2022-09-03  0:36 ` [PATCH v4 0/3] grep: integrate with sparse index Shaoxuan Yuan
2022-09-03  0:36   ` [PATCH v4 1/3] builtin/grep.c: add --sparse option Shaoxuan Yuan
2022-09-03  0:36   ` [PATCH v4 2/3] builtin/grep.c: integrate with sparse index Shaoxuan Yuan
2022-09-03  0:36   ` [PATCH v4 3/3] builtin/grep.c: walking tree instead of expanding index with --sparse Shaoxuan Yuan
2022-09-03  4:39     ` Junio C Hamano
2022-09-08  0:24       ` Shaoxuan Yuan
2022-09-08  0:18 ` [PATCH v5 0/3] grep: integrate with sparse index Shaoxuan Yuan
2022-09-08  0:18   ` [PATCH v5 1/3] builtin/grep.c: add --sparse option Shaoxuan Yuan
2022-09-10  1:07     ` Victoria Dye
2022-09-14  6:08     ` Elijah Newren
2022-09-15  2:57       ` Junio C Hamano
2022-09-18  2:14         ` Elijah Newren
2022-09-18 19:52           ` Victoria Dye
2022-09-19  1:23             ` Junio C Hamano
2022-09-19  4:27             ` Shaoxuan Yuan
2022-09-19 11:03             ` Ævar Arnfjörð Bjarmason
2022-09-20  7:13             ` Elijah Newren
2022-09-17  3:34       ` Shaoxuan Yuan
2022-09-18  4:24         ` Elijah Newren
2022-09-19  4:13           ` Shaoxuan Yuan
2022-09-17  3:45       ` Shaoxuan Yuan
2022-09-08  0:18   ` [PATCH v5 2/3] builtin/grep.c: integrate with sparse index Shaoxuan Yuan
2022-09-08  0:18   ` [PATCH v5 3/3] builtin/grep.c: walking tree instead of expanding index with --sparse Shaoxuan Yuan
2022-09-08 17:59     ` Junio C Hamano
2022-09-08 20:46       ` Derrick Stolee
2022-09-08 20:56         ` Junio C Hamano
2022-09-08 21:06           ` Shaoxuan Yuan
2022-09-09 12:49           ` Derrick Stolee
2022-09-13 17:23         ` Junio C Hamano
2022-09-10  2:04     ` Victoria Dye
2022-09-23  4:18 ` [PATCH v6 0/1] grep: integrate with sparse index Shaoxuan Yuan
2022-09-23  4:18   ` [PATCH v6 1/1] builtin/grep.c: " Shaoxuan Yuan
2022-09-23 16:40     ` Junio C Hamano
2022-09-23 16:58     ` Junio C Hamano
2022-09-26 17:28       ` Junio C Hamano
2022-09-23 14:13   ` [PATCH v6 0/1] grep: " Derrick Stolee
2022-09-23 16:01   ` Victoria Dye
2022-09-23 17:08     ` Junio C Hamano
  -- strict thread matches above, loose matches on Subject: below --
2022-09-23  4:15 Shaoxuan Yuan
2022-09-23  4:21 ` Shaoxuan Yuan

Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

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 read-only IMAP folder(s) and NNTP newsgroup(s).