From: Jeff King <peff@peff.net>
To: "René Scharfe" <l.s.r@web.de>
Cc: Taylor Blau <me@ttaylorr.com>,
git@vger.kernel.org, avarab@gmail.com, gitster@pobox.com
Subject: Re: [PATCH 0/7] grep.c: teach --column to 'git-grep(1)'
Date: Tue, 19 Jun 2018 13:48:47 -0400 [thread overview]
Message-ID: <20180619174846.GA27820@sigill.intra.peff.net> (raw)
In-Reply-To: <5282e3bb-bf7a-ab3a-98dc-d29ff1c37468@web.de>
On Tue, Jun 19, 2018 at 07:33:39PM +0200, René Scharfe wrote:
> > The key thing about this iteration is that it doesn't regress
> > performance, because we always short-circuit where we used to. The other
> > obvious route is to stop short-circuiting only when "--column" is in
> > effect, which would have the same property (at the expense of a little
> > extra code in match_expr_eval()).
>
> The performance impact of the exhaustive search for --color scales with
> the number of shown lines, while it would scale with the total number of
> lines for --column. Coloring the results of highly selective patterns
> is relatively cheap, short-circuiting them still helps significantly.
I thought that at first, too, but I think we'd still scale with the
number of shown lines. We're talking about short-circuiting OR, so by
definition we stop the short-circuit because we matched the first half
of the OR.
If you stop short-circuiting AND, then yes, you incur a penalty for
every line. But I don't think --column would need to do that.
Although there are interesting cases around inversion. For example:
git grep --not \( --not -e a --and --not -e b \)
is equivalent to:
git grep -e a --or -e b
Do people care if we actually hunt down the exact column where we
_didn't_ match "b" in the first case? The two are equivalent, but I
have to wonder if somebody writing the first one really cares.
> Disabling that optimization for --column wouldn't be a regression since
> it's a new option.. Picking a random result (based on the order of
> evaluation) seems sloppy and is probably going to surprise users.
I don't see it as a random result; short-circuiting logic is well
understood and we follow the user's ordering.
I think the place where it's _most_ ugly is "--column --color", where we
may color the short-circuited value in the second pass.
> We could add an optimizer pass to reduce the number of regular
> expressions in certain cases if that is really too slow. E.g. this:
Yes, we actually discussed this kind of transformation. I think it's way
out of scope for this patch series, though. If we do anything more, I
think it should be to disable short-circuiting when --column is in use.
-Peff
next prev parent reply other threads:[~2018-06-19 17:48 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-06-18 23:43 [PATCH 0/7] grep.c: teach --column to 'git-grep(1)' Taylor Blau
2018-06-18 23:43 ` [PATCH 1/7] Documentation/config.txt: camel-case lineNumber for consistency Taylor Blau
2018-06-18 23:43 ` [PATCH 2/7] grep.c: expose {,inverted} match column in match_line() Taylor Blau
2018-06-19 16:49 ` Junio C Hamano
2018-06-19 17:02 ` Taylor Blau
2018-06-18 23:43 ` [PATCH 3/7] grep.[ch]: extend grep_opt to allow showing matched column Taylor Blau
2018-06-18 23:43 ` [PATCH 4/7] grep.c: display column number of first match Taylor Blau
2018-06-19 16:28 ` Jeff King
2018-06-19 16:34 ` Taylor Blau
2018-06-18 23:43 ` [PATCH 5/7] builtin/grep.c: add '--column' option to 'git-grep(1)' Taylor Blau
2018-06-18 23:43 ` [PATCH 6/7] grep.c: add configuration variables to show matched option Taylor Blau
2018-06-18 23:43 ` [PATCH 7/7] contrib/git-jump/git-jump: jump to exact location Taylor Blau
2018-06-19 16:35 ` [PATCH 0/7] grep.c: teach --column to 'git-grep(1)' Jeff King
2018-06-19 17:33 ` René Scharfe
2018-06-19 17:44 ` Taylor Blau
2018-06-19 17:50 ` René Scharfe
2018-06-19 20:26 ` René Scharfe
2018-06-19 17:48 ` Jeff King [this message]
2018-06-19 17:54 ` Taylor Blau
2018-06-19 17:58 ` Junio C Hamano
2018-06-19 18:02 ` Taylor Blau
2018-06-19 18:05 ` Jeff King
2018-06-19 18:09 ` Junio C Hamano
2018-06-19 18:50 ` René Scharfe
2018-06-19 19:11 ` Jeff King
2018-06-19 20:34 ` René Scharfe
2018-06-19 20:51 ` Junio C Hamano
2018-06-19 16:46 ` Junio C Hamano
2018-06-19 17:02 ` Taylor Blau
2018-06-19 22:51 ` Taylor Blau
2018-06-20 20:05 ` [PATCH v2 " Taylor Blau
2018-06-20 20:05 ` [PATCH v2 1/7] Documentation/config.txt: camel-case lineNumber for consistency Taylor Blau
2018-06-20 20:05 ` [PATCH v2 2/7] grep.c: expose {,inverted} match column in match_line() Taylor Blau
2018-06-20 20:05 ` [PATCH v2 3/7] grep.[ch]: extend grep_opt to allow showing matched column Taylor Blau
2018-06-20 20:05 ` [PATCH v2 4/7] grep.c: display column number of first match Taylor Blau
2018-06-20 20:05 ` [PATCH v2 5/7] builtin/grep.c: add '--column' option to 'git-grep(1)' Taylor Blau
2018-06-20 20:05 ` [PATCH v2 6/7] grep.c: add configuration variables to show matched option Taylor Blau
2018-06-20 20:05 ` [PATCH v2 7/7] contrib/git-jump/git-jump: jump to exact location Taylor Blau
2018-06-21 11:53 ` [PATCH v2 0/7] grep.c: teach --column to 'git-grep(1)' Jeff King
2018-06-21 12:01 ` Jeff King
2018-06-22 21:45 ` Johannes Schindelin
2018-06-22 22:26 ` Jeff King
2018-06-21 20:52 ` Junio C Hamano
2018-06-21 21:45 ` Taylor Blau
2018-06-22 7:22 ` Jeff King
2018-06-22 15:49 ` [PATCH v3 " Taylor Blau
2018-06-22 15:49 ` [PATCH v3 1/7] Documentation/config.txt: camel-case lineNumber for consistency Taylor Blau
2018-06-22 15:49 ` [PATCH v3 2/7] grep.c: expose {,inverted} match column in match_line() Taylor Blau
2018-06-22 15:49 ` [PATCH v3 3/7] grep.[ch]: extend grep_opt to allow showing matched column Taylor Blau
2018-06-22 15:49 ` [PATCH v3 4/7] grep.c: display column number of first match Taylor Blau
2018-06-22 15:49 ` [PATCH v3 5/7] builtin/grep.c: add '--column' option to 'git-grep(1)' Taylor Blau
2018-06-22 15:49 ` [PATCH v3 6/7] grep.c: add configuration variables to show matched option Taylor Blau
2018-06-22 15:49 ` [PATCH v3 7/7] contrib/git-jump/git-jump: jump to exact location Taylor Blau
2018-06-25 18:43 ` [PATCH v3 0/7] grep.c: teach --column to 'git-grep(1)' Jeff King
2018-06-25 18:47 ` Taylor Blau
2018-06-26 16:45 ` Junio C Hamano
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=20180619174846.GA27820@sigill.intra.peff.net \
--to=peff@peff.net \
--cc=avarab@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=l.s.r@web.de \
--cc=me@ttaylorr.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).