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
next prev 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).