git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Phillip Wood <phillip.wood@talktalk.net>
To: Git Mailing List <git@vger.kernel.org>,
	Stefan Beller <sbeller@google.com>,
	Junio C Hamano <gitster@pobox.com>
Cc: Phillip Wood <phillip.wood@dunelm.org.uk>
Subject: [PATCH v2 7/9] diff --color-moved-ws: optimize allow-indentation-change
Date: Fri, 23 Nov 2018 11:16:56 +0000	[thread overview]
Message-ID: <20181123111658.30342-8-phillip.wood@talktalk.net> (raw)
In-Reply-To: <20181123111658.30342-1-phillip.wood@talktalk.net>

From: Phillip Wood <phillip.wood@dunelm.org.uk>

When running

  git diff --color-moved-ws=allow-indentation-change v2.18.0 v2.19.0

cmp_in_block_with_wsd() is called 694908327 times. Of those 42.7%
return after comparing a and b. By comparing the lengths first we can
return early in all but 0.03% of those cases without dereferencing the
string pointers. The comparison between a and c fails in 6.8% of
calls, by comparing the lengths first we reject all the failing calls
without dereferencing the string pointers.

This reduces the time to run the command above by by 42% from 14.6s to
8.5s. This is still much slower than the normal --color-moved which
takes ~0.6-0.7s to run but is a significant improvement.

The next commits will replace the current implementation with one that
works with mixed tabs and spaces in the indentation. I think it is
worth optimizing the current implementation first to enable a fair
comparison between the two implementations.

Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 diff.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/diff.c b/diff.c
index 8c08dd68df..c378ce3daf 100644
--- a/diff.c
+++ b/diff.c
@@ -829,20 +829,23 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,
 				 int n)
 {
 	struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n];
-	int al = cur->es->len, cl = l->len;
+	int al = cur->es->len, bl = match->es->len, cl = l->len;
 	const char *a = cur->es->line,
 		   *b = match->es->line,
 		   *c = l->line;
-
+	const char *orig_a = a;
 	int wslen;
 
 	/*
-	 * We need to check if 'cur' is equal to 'match'.
-	 * As those are from the same (+/-) side, we do not need to adjust for
-	 * indent changes. However these were found using fuzzy matching
-	 * so we do have to check if they are equal.
+	 * We need to check if 'cur' is equal to 'match'.  As those
+	 * are from the same (+/-) side, we do not need to adjust for
+	 * indent changes. However these were found using fuzzy
+	 * matching so we do have to check if they are equal. Here we
+	 * just check the lengths. We delay calling memcmp() to check
+	 * the contents until later as if the length comparison for a
+	 * and c fails we can avoid the call all together.
 	 */
-	if (strcmp(a, b))
+	if (al != bl)
 		return 1;
 
 	if (!pmb->wsd.string)
@@ -870,7 +873,7 @@ static int cmp_in_block_with_wsd(const struct diff_options *o,
 		al -= wslen;
 	}
 
-	if (al != cl || memcmp(a, c, al))
+	if (al != cl || memcmp(orig_a, b, bl) || memcmp(a, c, al))
 		return 1;
 
 	return 0;
-- 
2.19.1.1690.g258b440b18


  parent reply	other threads:[~2018-11-23 11:17 UTC|newest]

Thread overview: 44+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-09-24 10:06 [RFC PATCH 0/3] diff --color-moved-ws: allow mixed spaces and tabs in indentation change Phillip Wood
2018-09-24 10:06 ` [RFC PATCH 1/3] xdiff-interface: make xdl_blankline() available Phillip Wood
2018-09-24 23:19   ` Stefan Beller
2018-09-24 10:06 ` [RFC PATCH 2/3] diff.c: remove unused variables Phillip Wood
2018-09-24 10:06 ` [RFC PATCH 3/3] diff: add --color-moved-ws=allow-mixed-indentation-change Phillip Wood
2018-09-25  1:07   ` Stefan Beller
2018-10-09  9:50     ` Phillip Wood
2018-10-09 21:10       ` Stefan Beller
2018-10-10 15:26         ` Phillip Wood
2018-10-10 18:05           ` Stefan Beller
2018-09-24 11:03 ` [RFC PATCH 0/3] diff --color-moved-ws: allow mixed spaces and tabs in indentation change Phillip Wood
2018-11-16 11:03 ` [PATCH v1 0/9] diff --color-moved-ws fixes and enhancment Phillip Wood
2018-11-16 11:03   ` [PATCH v1 1/9] diff: document --no-color-moved Phillip Wood
2018-11-16 11:03   ` [PATCH v1 2/9] diff: use whitespace consistently Phillip Wood
2018-11-16 18:29     ` Stefan Beller
2018-11-16 11:03   ` [PATCH v1 3/9] diff: allow --no-color-moved-ws Phillip Wood
2018-11-16 11:03   ` [PATCH v1 4/9] diff --color-moved-ws: demonstrate false positives Phillip Wood
2018-11-16 11:03   ` [PATCH v1 5/9] diff --color-moved-ws: fix " Phillip Wood
2018-11-16 11:03   ` [PATCH v1 6/9] diff --color-moved=zebra: be stricter with color alternation Phillip Wood
2018-11-16 11:03   ` [PATCH v1 7/9] diff --color-moved-ws: optimize allow-indentation-change Phillip Wood
2018-11-16 20:40     ` Stefan Beller
2018-11-17 14:52       ` Phillip Wood
2018-11-16 11:03   ` [PATCH v1 8/9] diff --color-moved-ws: modify allow-indentation-change Phillip Wood
2018-11-16 21:47     ` Stefan Beller
2018-11-17 14:59       ` Phillip Wood
2018-11-16 11:03   ` [PATCH v1 9/9] diff --color-moved-ws: handle blank lines Phillip Wood
2018-11-20 18:05     ` Stefan Beller
2018-11-21 15:49       ` Phillip Wood
2018-11-23 11:16 ` [PATCH v2 0/9] diff --color-moved-ws fixes and enhancment Phillip Wood
2018-11-23 11:16   ` [PATCH v2 1/9] diff: document --no-color-moved Phillip Wood
2018-11-23 11:16   ` [PATCH v2 2/9] Use "whitespace" consistently Phillip Wood
2018-11-23 11:16   ` [PATCH v2 3/9] diff: allow --no-color-moved-ws Phillip Wood
2018-11-23 11:16   ` [PATCH v2 4/9] diff --color-moved-ws: demonstrate false positives Phillip Wood
2018-11-23 11:16   ` [PATCH v2 5/9] diff --color-moved-ws: fix " Phillip Wood
2018-11-23 11:16   ` [PATCH v2 6/9] diff --color-moved=zebra: be stricter with color alternation Phillip Wood
2018-11-23 11:16   ` Phillip Wood [this message]
2018-11-23 11:16   ` [PATCH v2 8/9] diff --color-moved-ws: modify allow-indentation-change Phillip Wood
2018-11-23 11:16   ` [PATCH v2 9/9] diff --color-moved-ws: handle blank lines Phillip Wood
2018-11-26 21:20   ` [PATCH v2 0/9] diff --color-moved-ws fixes and enhancment Stefan Beller
2018-11-27 20:52     ` Phillip Wood
2019-01-08 16:22   ` Phillip Wood
2019-01-08 18:31     ` Junio C Hamano
2019-01-10  0:37       ` Stefan Beller
2019-01-10 18:39         ` 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=20181123111658.30342-8-phillip.wood@talktalk.net \
    --to=phillip.wood@talktalk.net \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=phillip.wood@dunelm.org.uk \
    --cc=sbeller@google.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).