From: Brandon Williams <bmwill@google.com>
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org
Subject: Re: [PATCH 4/4 v4] ls-files: add pathspec matching for submodules
Date: Tue, 27 Sep 2016 13:40:20 -0700 [thread overview]
Message-ID: <20160927204020.GC32565@google.com> (raw)
In-Reply-To: <xmqq1t05nmcs.fsf@gitster.mtv.corp.google.com>
On 09/27, Junio C Hamano wrote:
> Brandon Williams <bmwill@google.com> writes:
>
> > - /* Find common prefix for all pathspec's */
> > - max_prefix = common_prefix(&pathspec);
> > + /*
> > + * Find common prefix for all pathspec's
> > + * This is used as a performance optimization which unfortunately cannot
> > + * be done when recursing into submodules
> > + */
> > + if (recurse_submodules)
> > + max_prefix = NULL;
> > + else
> > + max_prefix = common_prefix(&pathspec);
> > max_prefix_len = max_prefix ? strlen(max_prefix) : 0;
>
> I still wonder if we can do better than this, as this would be a big
> cycle-saver especially in recurse-submodules case.
>
> When you get max_prefix that is "a/b/c", there are three cases:
>
> * a/b/c is a path prefix for an entry in the index, e.g. a/b/c/d;
> you then can safely use it and you do not have to do any
> recursive invocation of ls-files outside "a/b/c". You may match
> a/b/c/d in the toplevel, or you may recurse a/b/c/e that is a
> submodule, but you won't have to pay attention to submodules
> outside.
>
> * a leading path of a/b/c, e.g. a/b, is a gitlink or a blob in the
> index; you can use a/b and you only have to recurse into a/b if
> that is a submodule; if a/b is a blob, you'd show nothing.
>
> * a/b/c itself and no leading path of it appears in the index; you
> know that nothing will match once you know that you are in this
> situation.
>
> Because a gitlink "a/b" sorts at the same location in the index as a
> regular blob "a/b" would, by feeding the max_prefix common_prefix()
> gives you (i.e. "a/b/c") to index_name_pos() to see which one of the
> three situations you are in can be done fairly cheaply, I would
> think. The index_name_pos() call may find "a/b/c" exactly (case 1),
> or return a location where "a/b/c" would be inserted in the list of
> existing entries. If there were "a/b" (or "a") in the index, there
> wouldn't be any "a/b/x" (or "a/x") at the same time, so a query for
> "a/b/c" would land you next to (just after) an existing entry that
> is a leading path of it, if such an entry exists, no? That would
> allow you to tell case 2 above fairly cheaply, I would expect.
>
> It is a separate issue if adding that support to 4/4 is a good idea;
> I personally think doing it as a separate follow-up patch would make
> more sense, so all of the above is tangent.
I agree that this could be a big cycle saver. At the present I was
working towards getting a working implementation but this should
definitely be addressed in a follow-up patch to introduce the
optimization to the recurse-submodule mode. It hopefully wouldn't be
too hard to implement seeing as its using string literals.
--
Brandon Williams
next prev parent reply other threads:[~2016-09-27 20:40 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-09-24 0:13 [PATCH 0/3] recursive support for ls-files Brandon Williams
2016-09-24 0:13 ` [PATCH 1/3 v3] submodules: make submodule-prefix option an envvar Brandon Williams
2016-09-25 23:34 ` Junio C Hamano
2016-09-24 0:13 ` [PATCH 2/3 v3] ls-files: optionally recurse into submodules Brandon Williams
2016-09-24 0:13 ` [PATCH 3/3 v3] ls-files: add pathspec matching for submodules Brandon Williams
2016-09-25 7:17 ` [PATCH 0/3] recursive support for ls-files Jeff King
2016-09-25 16:32 ` Brandon Williams
2016-09-25 18:38 ` Junio C Hamano
2016-09-26 17:04 ` Brandon Williams
2016-09-26 18:17 ` Junio C Hamano
2016-09-26 18:38 ` Brandon Williams
2016-09-26 18:48 ` Junio C Hamano
2016-09-26 22:46 ` [PATCH 0/4 v4] " Brandon Williams
2016-09-26 22:46 ` [PATCH 1/4 v4] submodules: make submodule-prefix option Brandon Williams
2016-09-27 18:17 ` Junio C Hamano
2016-09-27 20:29 ` Brandon Williams
2016-09-27 20:35 ` Junio C Hamano
2016-09-27 20:43 ` Brandon Williams
2016-09-26 22:46 ` [PATCH 2/4 v4] ls-files: optionally recurse into submodules Brandon Williams
2016-09-27 18:29 ` Junio C Hamano
2016-09-27 20:33 ` Brandon Williams
2016-09-26 22:46 ` [PATCH 3/4 v4] ls-files: pass through safe options for --recurse-submodules Brandon Williams
2016-09-27 18:40 ` Junio C Hamano
2016-09-27 20:11 ` Junio C Hamano
2016-09-27 20:52 ` Brandon Williams
2016-09-27 20:58 ` Junio C Hamano
2016-09-27 20:59 ` Stefan Beller
2016-09-28 17:24 ` Brandon Williams
2016-09-28 18:59 ` Junio C Hamano
2016-09-27 20:49 ` Brandon Williams
2016-09-27 18:43 ` Junio C Hamano
2016-09-27 20:44 ` Brandon Williams
2016-09-27 20:59 ` Junio C Hamano
2016-09-26 22:46 ` [PATCH 4/4 v4] ls-files: add pathspec matching for submodules Brandon Williams
2016-09-27 20:01 ` Junio C Hamano
2016-09-27 20:40 ` Brandon Williams [this message]
2016-09-28 21:50 ` [PATCH v5 0/4] recursive support for ls-files Brandon Williams
2016-09-28 21:50 ` [PATCH v5 1/4] git: make super-prefix option Brandon Williams
2016-09-28 22:01 ` Stefan Beller
2016-09-28 22:19 ` Junio C Hamano
2016-09-29 18:39 ` Jeff King
2016-09-29 18:44 ` Brandon Williams
2016-09-28 21:50 ` [PATCH v5 2/4] ls-files: optionally recurse into submodules Brandon Williams
2016-09-28 22:11 ` Stefan Beller
2016-09-28 22:22 ` Junio C Hamano
2016-09-28 21:50 ` [PATCH v5 3/4] ls-files: pass through safe options for --recurse-submodules Brandon Williams
2016-09-28 21:50 ` [PATCH v5 4/4] ls-files: add pathspec matching for submodules Brandon Williams
2016-09-29 21:48 ` [PATCH v6 0/4] recursive support for ls-files Brandon Williams
2016-09-29 21:48 ` [PATCH v6 1/4] git: make super-prefix option Brandon Williams
2016-10-04 17:31 ` Stefan Beller
2016-10-04 17:35 ` Junio C Hamano
2016-10-04 17:39 ` Jeff King
2016-09-29 21:48 ` [PATCH v6 2/4] ls-files: optionally recurse into submodules Brandon Williams
2016-09-29 21:48 ` [PATCH v6 3/4] ls-files: pass through safe options for --recurse-submodules Brandon Williams
2016-09-30 0:14 ` Junio C Hamano
2016-09-30 16:33 ` Brandon Williams
2016-09-30 17:01 ` Brandon Williams
2016-09-29 21:48 ` [PATCH v6 4/4] ls-files: add pathspec matching for submodules Brandon Williams
2016-10-04 17:56 ` Stefan Beller
2016-10-07 18:18 ` [PATCH v7 0/4] recursive support for ls-files Brandon Williams
2016-10-07 18:18 ` [PATCH v7 1/4] git: make super-prefix option Brandon Williams
2016-10-07 18:18 ` [PATCH v7 2/4] ls-files: optionally recurse into submodules Brandon Williams
2016-10-07 18:18 ` [PATCH v7 3/4] ls-files: pass through safe options for --recurse-submodules Brandon Williams
2016-10-07 18:18 ` [PATCH v7 4/4] ls-files: add pathspec matching for submodules Brandon Williams
2016-10-07 18:34 ` [PATCH v7 0/4] recursive support for ls-files Stefan Beller
2016-10-07 18:35 ` Stefan Beller
2016-10-07 18:45 ` Brandon Williams
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
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160927204020.GC32565@google.com \
--to=bmwill@google.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).