threads / patch / 24288

patchxdiff: optimise for no whitespace difference when ignoring whitespace.

Subject: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.

## tl;dr

7 messages between Jul 5, 2010 and Jul 6, 2010. Diffs are folded; open one to read it.

replies: 6people: 3as markdown or json

Dylan Reid· Jul 5, 2010, 06:06 UTC · lore

Invert the order of the memcmp and flag check are done in xdl_recmatch, as it makes the common case (there is no whitespace difference) faster. It costs the case where lines are the same length and contain whitespace differences, but the common case is more than 20% faster.

Signed-off-by: Dylan Reid <dgreid@gmail.com>
---
 xdiff/xutils.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)
Show changes to xdiff/xutils.c +4 −2
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index bc12f29..dc97a21 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
 {
 	int i1, i2;
 
-	if (!(flags & XDF_WHITESPACE_FLAGS))
-		return s1 == s2 && !memcmp(l1, l2, s1);
+	if (s1 == s2 && !memcmp(l1, l2, s1))
+		return 1;
+	else if (!(flags & XDF_WHITESPACE_FLAGS))
+		return 0;
 
 	i1 = 0;
 	i2 = 0;

-- 
1.7.1
Michael J Gruber· Jul 5, 2010, 08:34 UTC · re: Dylan Reid · lore

Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.

Dylan Reid venit, vidit, dixit 05.07.2010 08:06:
> Invert the order of the memcmp and flag check are done in xdl_recmatch,

I was wondering whether you describe old (before patch) or new (after patch) here. Maybe one of the following is clearer:

"Invert the order of the memcmp and flag check which are done in xdl_recmatch,"

"Invert the order of the memcmp and flag check in xdl_recmatch,"
Show 22 quoted lines
> as it makes the common case (there is no whitespace difference) faster.
> It costs the case where lines are the same length and contain
> whitespace differences, but the common case is more than 20% faster.
> 
> Signed-off-by: Dylan Reid <dgreid@gmail.com>
> ---
>  xdiff/xutils.c |    6 ++++--
>  1 files changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/xdiff/xutils.c b/xdiff/xutils.c
> index bc12f29..dc97a21 100644
> --- a/xdiff/xutils.c
> +++ b/xdiff/xutils.c
> @@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
>  {
>  	int i1, i2;
>  
> -	if (!(flags & XDF_WHITESPACE_FLAGS))
> -		return s1 == s2 && !memcmp(l1, l2, s1);
> +	if (s1 == s2 && !memcmp(l1, l2, s1))
> +		return 1;
> +	else if (!(flags & XDF_WHITESPACE_FLAGS))
You can do without the "else" here.
> +		return 0;
>  
>  	i1 = 0;
>  	i2 = 0;
BTW: How did you find this? Are you profiling parts of git?
Michael
Dylan Reid· Jul 5, 2010, 12:34 UTC · re: Michael J Gruber · lore

Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.

On Mon, Jul 5, 2010 at 4:34 AM, Michael J Gruber <git@drmicha.warpmail.net> wrote:

Show 11 quoted lines
> Dylan Reid venit, vidit, dixit 05.07.2010 08:06:
>> Invert the order of the memcmp and flag check are done in xdl_recmatch,
>
> I was wondering whether you describe old (before patch) or new (after
> patch) here. Maybe one of the following is clearer:
>
> "Invert the order of the memcmp and flag check which are done in
> xdl_recmatch,"
>
> "Invert the order of the memcmp and flag check in xdl_recmatch,"
>
I'll make that more clear.
Show 5 quoted lines
>> +     if (s1 == s2 && !memcmp(l1, l2, s1))
>> +             return 1;
>> +     else if (!(flags & XDF_WHITESPACE_FLAGS))
>
> You can do without the "else" here.
sure can, will do.
Show 9 quoted lines
>> +             return 0;
>>
>>       i1 = 0;
>>       i2 = 0;
>
> BTW: How did you find this? Are you profiling parts of git?
>
> Michael
>

I was looking to add an unrelated feature and just happened to notice this. It was a really cheap change for a good speedup.

Thanks,
Dylan
Dylan Reid· Jul 5, 2010, 13:00 UTC · re: Dylan Reid · lore

In xdl_recmatch, do the memcmp to check if the two lines are equal before checking if whitespace flags are set. If the lines are identicle, then there is no need to check if they differ only in whitespace. This makes the common case (there is no whitespace difference) faster. It costs the case where lines are the same length and contain whitespace differences, but the common case is more than 20% faster.

Signed-off-by: Dylan Reid <dgreid@gmail.com>
---
 xdiff/xutils.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)
Show changes to xdiff/xutils.c +3 −1
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index bc12f29..22f9bd6 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
 {
 	int i1, i2;
 
+	if (s1 == s2 && !memcmp(l1, l2, s1))
+		return 1;
 	if (!(flags & XDF_WHITESPACE_FLAGS))
-		return s1 == s2 && !memcmp(l1, l2, s1);
+		return 0;
 
 	i1 = 0;
 	i2 = 0;

-- 
1.7.1
Junio C Hamano· Jul 6, 2010, 02:36 UTC · re: Dylan Reid · lore

Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.

Dylan Reid <dgreid@gmail.com> writes:
> In xdl_recmatch, do the memcmp to check if the two lines are equal before
> checking if whitespace flags are set.  If the lines are identicle, then
"identical"?
> there is no need to check if they differ only in whitespace.
> This makes the common case (there is no whitespace difference) faster.
> It costs the case where lines are the same length and contain
> whitespace differences, but the common case is more than 20% faster.
"more than 20% faster" based on what dataset and benchmark?
Show 29 quoted lines
>
> Signed-off-by: Dylan Reid <dgreid@gmail.com>
> ---
>  xdiff/xutils.c |    4 +++-
>  1 files changed, 3 insertions(+), 1 deletions(-)
>
> diff --git a/xdiff/xutils.c b/xdiff/xutils.c
> index bc12f29..22f9bd6 100644
> --- a/xdiff/xutils.c
> +++ b/xdiff/xutils.c
> @@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
>  {
>  	int i1, i2;
>  
> +	if (s1 == s2 && !memcmp(l1, l2, s1))
> +		return 1;
>  	if (!(flags & XDF_WHITESPACE_FLAGS))
> -		return s1 == s2 && !memcmp(l1, l2, s1);
> +		return 0;
>  
>  	i1 = 0;
>  	i2 = 0;
> -- 
> 1.7.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
Dylan Reid· Jul 6, 2010, 03:04 UTC · re: Junio C Hamano · lore

Re: [PATCH] xdiff: optimise for no whitespace difference when ignoring whitespace.

On Mon, Jul 5, 2010 at 10:36 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 6 quoted lines
> Dylan Reid <dgreid@gmail.com> writes:
>
>> In xdl_recmatch, do the memcmp to check if the two lines are equal before
>> checking if whitespace flags are set.  If the lines are identicle, then
>
> "identical"?
That's exaclty what I meant.  Correct patch sent.
Show 8 quoted lines
>
>> there is no need to check if they differ only in whitespace.
>> This makes the common case (there is no whitespace difference) faster.
>> It costs the case where lines are the same length and contain
>> whitespace differences, but the common case is more than 20% faster.
>
> "more than 20% faster" based on what dataset and benchmark?
>

I benchmarked it with some of the bigger files from Linux. The results were consistenly > 20% faster across different file sizes. I tested it by simply running the command a few times then running it with my local build a few times to see if I had achieved any speedup.

~/linux-2.6(119)$ time git blame --incremental -w ./sound/pci/hda/patch_realtek.c > /dev/null

real 0m8.166s user 0m8.063s sys 0m0.090s ~/linux-2.6(120)$ time git blame --incremental -w ./sound/pci/hda/patch_realtek.c > /dev/null

real 0m8.010s user 0m7.866s sys 0m0.137s ~/linux-2.6(121)$ time ~/work/git/git blame --incremental -w ./sound/pci/hda/patch_realtek.c > /dev/null

real 0m6.115s user 0m5.986s sys 0m0.123s ~/linux-2.6(122)$ time ~/work/git/git blame --incremental -w ./sound/pci/hda/patch_realtek.c > /dev/null

real 0m6.119s user 0m5.986s sys 0m0.127s

Thanks for taking the time to read the patch.
Dylan
Dylan Reid· Jul 6, 2010, 03:11 UTC · re: Dylan Reid · lore

In xdl_recmatch, do the memcmp to check if the two lines are equal before checking if whitespace flags are set. If the lines are identical, then there is no need to check if they differ only in whitespace. This makes the common case (there is no whitespace difference) faster. It costs the case where lines are the same length and contain whitespace differences, but the common case is more than 20% faster.

Signed-off-by: Dylan Reid <dgreid@gmail.com>
---
 xdiff/xutils.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)
Show changes to xdiff/xutils.c +3 −1
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index bc12f29..22f9bd6 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -190,8 +190,10 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
 {
 	int i1, i2;
 
+	if (s1 == s2 && !memcmp(l1, l2, s1))
+		return 1;
 	if (!(flags & XDF_WHITESPACE_FLAGS))
-		return s1 == s2 && !memcmp(l1, l2, s1);
+		return 0;
 
 	i1 = 0;
 	i2 = 0;

-- 
1.7.1

← back to recent threads