Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
From: Elijah Newren <newren@gmail.com>
To: Matheus Tavares Bernardino <matheus.bernardino@usp.br>
Cc: Git Mailing List <git@vger.kernel.org>,
	Derrick Stolee <dstolee@microsoft.com>,
	"brian m. carlson" <sandals@crustytoothpaste.net>,
	Stefan Beller <stefanbeller@gmail.com>,
	Jonathan Nieder <jrnieder@gmail.com>
Subject: Re: [RFC PATCH 2/3] grep: honor sparse checkout patterns
Date: Mon, 20 Apr 2020 20:08:46 -0700
Message-ID: <CABPp-BGUf-4exGW23xka1twf2D=nFOz1CkD_f-rDX_AGdVEeDA@mail.gmail.com> (raw)
In-Reply-To: <CAHd-oW6PQNC-ZFj6ydbHFzfL4KpSwXVSd8s3H429tOiRgSra8A@mail.gmail.com>

On Mon, Apr 20, 2020 at 7:11 PM Matheus Tavares Bernardino
<matheus.bernardino@usp.br> wrote:
>
> Hi, Elijah, Stolee and others
>
> On Tue, Mar 24, 2020 at 7:55 PM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > On Tue, Mar 24, 2020 at 4:15 AM Elijah Newren <newren@gmail.com> wrote:
> > >
> > > On Mon, Mar 23, 2020 at 11:12 PM Matheus Tavares
> > > <matheus.bernardino@usp.br> wrote:
> > > >
> > > > Something I'm not entirely sure in this patch is how we implement the
> > > > mechanism to honor sparsity for the `git grep <commit-ish>` case (which
> > > > is treated in the grep_tree() function). Currently, the patch looks for
> > > > an index entry that matches the path, and then checks its skip_worktree
> > >
> > > As you discuss below, checking the index is both wrong _and_ costly.
> > > You should use the sparsity patterns; Stolee did a lot of work to make
> > > those correspond to simple hashes you could check to determine whether
> > > to even walk into a subdirectory.
> [...]
> > OK, makes sense.
>
> I've been working on the file skipping mechanism using the sparsity
> patterns directly. But I'm uncertain about some implementation
> details. So I wanted to share my current plan with you, to get some
> feedback before going deeper.
>
> The first idea was to load the sparsity patterns a priori and pass
> them to grep_tree(), which recursively greps the entries of a given
> tree object. If --recurse-submodules is given, however, we would also
> need to load each surepo's sparse-checkout file on the fly (as the
> subrepos are lazily initialized in grep_tree()'s call chain). That's
> not a problem on its own. But in the most naive implementation, this
> means unnecessarily re-loading the sparse-checkout files of the
> submodules for each tree given to git-grep (as grep_tree() is called
> separately for each one of them).

Wouldn't loading the sparse-checkout files be fast compared to
grepping a submodule for matching strings?  And not just fast, but
essentially in the noise and hard to even measure?  I have a hard time
fathoming parsing the sparse-checkout file for a submodule somehow
appreciably affecting the cost of grepping through that submodule.  If
the submodule has a huge number of sparse-checkout patterns, that'll
be because it has a ginormous number of files and grepping through
them all would be way, way longer.  If the submodule only has a few
files, then the sparse-checkout file is only going to be a few lines
at most.

Also, from another angle: I think the original intent of submodules
was an alternate form of sparse-checkout/partial-clone, letting people
deal with just their piece of the repo.  As such, do we really even
expect people to use sparse-checkouts and submodules together, let
alone use them very heavily together?  Sure, someone will use them,
but I have a hard time imagining the scale of use of both features
heavily enough for this to matter, especially since it also requires
specifying multiple trees to grep (which is slightly unusual) in
addition to the combination of these other features before your
optimization here could kick in and be worthwhile.

I'd be very tempted to just implement the most naive implementation
and maybe leave a TODO note in the code for some future person to come
along and optimize if it really matters, but I'd like to see numbers
before we spend the development and maintenance effort on it because
I'm having a hard time imagining any scale where it could matter.

> So my next idea was to implement a cache, mapping 'struct repository's
> to 'struct pattern_list'. Well, not 'struct repository' itself, but
> repo->gitdir. This way we could load each file once, store the pattern
> list, and quickly retrieve the one that affect the repository
> currently being grepped, whether it is a submodule or not. But, is
> gitidir unique per repository? If not, could we use
> repo_git_path(repo, "info/sparse-checkout") as the key?
>
> I already have a prototype implementation of the last idea (using
> repo_git_path()). But I wanted to make sure, does this seem like a
> good path? Or should we avoid the work of having this hashmap here and
> do something else, as adding a 'struct pattern_list' to 'struct
> repository', directly?

Honestly, it sounds a bit like premature optimization to me.  Sorry if
that's disappointing since you've apparently already put some effort
into this, and it sounds like you're on a good track for optimizing
this if it were necessary, but I'm just having a hard time figuring
out whether it'd really help and be worth the code complexity.

  reply index

Thread overview: 63+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-24  6:04 [RFC PATCH 0/3] grep: honor sparse checkout and add option to ignore it Matheus Tavares
2020-03-24  6:11 ` [RFC PATCH 1/3] doc: grep: unify info on configuration variables Matheus Tavares
2020-03-24  7:57   ` Elijah Newren
2020-03-24 21:26     ` Junio C Hamano
2020-03-24 23:38       ` Matheus Tavares
2020-03-24  6:12 ` [RFC PATCH 2/3] grep: honor sparse checkout patterns Matheus Tavares
2020-03-24  7:15   ` Elijah Newren
2020-03-24 15:12     ` Derrick Stolee
2020-03-24 16:16       ` Elijah Newren
2020-03-24 17:02         ` Derrick Stolee
2020-03-24 23:01       ` Matheus Tavares Bernardino
2020-03-24 22:55     ` Matheus Tavares Bernardino
2020-04-21  2:10       ` Matheus Tavares Bernardino
2020-04-21  3:08         ` Elijah Newren [this message]
2020-04-22 12:08           ` Derrick Stolee
2020-04-23  6:09           ` Matheus Tavares Bernardino
2020-03-24  6:13 ` [RFC PATCH 3/3] grep: add option to ignore sparsity patterns Matheus Tavares
2020-03-24  7:54   ` Elijah Newren
2020-03-24 18:30     ` Junio C Hamano
2020-03-24 19:07       ` Elijah Newren
2020-03-25 20:18         ` Junio C Hamano
2020-03-30  3:23       ` Matheus Tavares Bernardino
2020-03-31 19:12         ` Elijah Newren
2020-03-31 20:02           ` Derrick Stolee
2020-04-27 17:15             ` Matheus Tavares Bernardino
2020-04-29 16:46               ` Elijah Newren
2020-04-29 17:21             ` Elijah Newren
2020-03-25 23:15     ` Matheus Tavares Bernardino
2020-03-26  6:02       ` Elijah Newren
2020-03-27 15:51         ` Junio C Hamano
2020-03-27 19:01           ` Elijah Newren
2020-03-30  1:12         ` Matheus Tavares Bernardino
2020-03-31 16:48           ` Elijah Newren
2020-05-10  0:41 ` [RFC PATCH v2 0/4] grep: honor sparse checkout and add option to ignore it Matheus Tavares
2020-05-10  0:41   ` [RFC PATCH v2 1/4] doc: grep: unify info on configuration variables Matheus Tavares
2020-05-10  0:41   ` [RFC PATCH v2 2/4] config: load the correct config.worktree file Matheus Tavares
2020-05-11 19:10     ` Junio C Hamano
2020-05-12 22:55       ` Matheus Tavares Bernardino
2020-05-12 23:22         ` Junio C Hamano
2020-05-10  0:41   ` [RFC PATCH v2 3/4] grep: honor sparse checkout patterns Matheus Tavares
2020-05-11 19:35     ` Junio C Hamano
2020-05-13  0:05       ` Matheus Tavares Bernardino
2020-05-13  0:17         ` Junio C Hamano
2020-05-21  7:26           ` Elijah Newren
2020-05-21 17:35             ` Matheus Tavares Bernardino
2020-05-21 17:52               ` Elijah Newren
2020-05-22  5:49                 ` Matheus Tavares Bernardino
2020-05-22 14:26                   ` Elijah Newren
2020-05-22 15:36                     ` Elijah Newren
2020-05-22 20:54                       ` Matheus Tavares Bernardino
2020-05-22 21:06                         ` Elijah Newren
2020-06-10 11:40                     ` Derrick Stolee
2020-06-10 16:22                       ` Matheus Tavares Bernardino
2020-06-10 17:42                         ` Derrick Stolee
2020-06-10 18:14                           ` Matheus Tavares Bernardino
2020-06-10 20:12                         ` Elijah Newren
2020-06-10 19:58                       ` Elijah Newren
2020-05-21  7:36       ` Elijah Newren
2020-05-10  0:41   ` [RFC PATCH v2 4/4] config: add setting to ignore sparsity patterns in some cmds Matheus Tavares
2020-05-10  4:23     ` Matheus Tavares Bernardino
2020-05-21 17:18       ` Elijah Newren
2020-05-21  7:09     ` Elijah Newren
2020-05-28  1:12 [PATCH v3 0/5] grep: honor sparse checkout and add option to ignore it Matheus Tavares
2020-05-28  1:12 ` [PATCH v3 1/5] doc: grep: unify info on configuration variables Matheus Tavares

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='CABPp-BGUf-4exGW23xka1twf2D=nFOz1CkD_f-rDX_AGdVEeDA@mail.gmail.com' \
    --to=newren@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=jrnieder@gmail.com \
    --cc=matheus.bernardino@usp.br \
    --cc=sandals@crustytoothpaste.net \
    --cc=stefanbeller@gmail.com \
    /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

Git Mailing List Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/git/0 git/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 git git/ https://lore.kernel.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.git


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git