[PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[George Papanikolaou]

Hi fellows,
I'm planning on applying on GSOC 2014...

I tried my luck with that kinda weird microproject about inefficiencies,
and I think I've discovered some.

(also on a totally different mood, there are some warning about empty format
strings during compilation that could easily be silenced with some #pragma
calls on "-Wformat-zero-length". Is there a way you're not adding this?)

The empty buffers check could happen at the beggining.
Leading whitespace check was unnecessary.
Some style changes

Thanks.
---
 builtin/apply.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/builtin/apply.c b/builtin/apply.c
index b0d0986..df2435f 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -294,20 +294,16 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
 	const char *last2 = s2 + n2 - 1;
 	int result = 0;
 
+	/* early return if both lines are empty */
+	if ((s1 > last1) && (s2 > last2))
+		return 1;
+
 	/* ignore line endings */
 	while ((*last1 == '\r') || (*last1 == '\n'))
 		last1--;
 	while ((*last2 == '\r') || (*last2 == '\n'))
 		last2--;
 
-	/* skip leading whitespace */
-	while (isspace(*s1) && (s1 <= last1))
-		s1++;
-	while (isspace(*s2) && (s2 <= last2))
-		s2++;
-	/* early return if both lines are empty */
-	if ((s1 > last1) && (s2 > last2))
-		return 1;
 	while (!result) {
 		result = *s1++ - *s2++;
 		/*
@@ -315,18 +311,15 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
 		 * both buffers because we don't want "a b" to match
 		 * "ab"
 		 */
-		if (isspace(*s1) && isspace(*s2)) {
-			while (isspace(*s1) && s1 <= last1)
-				s1++;
-			while (isspace(*s2) && s2 <= last2)
-				s2++;
-		}
+		while (isspace(*s1) && s1 <= last1)
+			s1++;
+		while (isspace(*s2) && s2 <= last2)
+			s2++;
 		/*
 		 * If we reached the end on one side only,
 		 * lines don't match
 		 */
-		if (
-		    ((s2 > last2) && (s1 <= last1)) ||
+		if (((s2 > last2) && (s1 <= last1)) ||
 		    ((s1 > last1) && (s2 <= last2)))
 			return 0;
 		if ((s1 > last1) && (s2 > last2))
-- 
1.9.0

Re: [PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[Michael Haggerty]

Hello and welcome.  See the comments inline.

On 03/20/2014 02:32 AM, George Papanikolaou wrote:
> Hi fellows,
> I'm planning on applying on GSOC 2014...
> 
> I tried my luck with that kinda weird microproject about inefficiencies,
> and I think I've discovered some.
> 
> (also on a totally different mood, there are some warning about empty format
> strings during compilation that could easily be silenced with some #pragma
> calls on "-Wformat-zero-length". Is there a way you're not adding this?)

The main reason is probably that #pragmas are compiler-specific.  It is
undesirable to clutter up the source code with ugly #pragmas that only
benefit people using gcc.

I think that most people who use gcc compile with
-Wno-format-zero-length.  FWIW, the options that I use are

    O = 2
    CFLAGS = -g -O$(O) -Wall -Werror -Wdeclaration-after-statement
-Wno-format-zero-length -Wno-format-security $(EXTRA_CFLAGS)

, which you can put in your config.mak.

> The empty buffers check could happen at the beggining.

s/beggining/beginning/

> Leading whitespace check was unnecessary.
> Some style changes
> 
> Thanks.
> ---

Please pay attention to how patches have to be formatted:

The subject of the email and everything above the "---" line is used as
the commit's log message.  This should only include information that
belongs in the Git project's permanent history, not incidental
information like the fact that you are applying for GSoC.

The commit message *should* include an explanation of *why* you are
making a change, any tradeoffs that might be involved, etc.

The commit message also *must* include a Signed-off-by line.

Other discussion, not intended for the commit message, should be placed
directly *under* the "---" line.

>  builtin/apply.c | 25 +++++++++----------------
>  1 file changed, 9 insertions(+), 16 deletions(-)
> 
> diff --git a/builtin/apply.c b/builtin/apply.c
> index b0d0986..df2435f 100644
> --- a/builtin/apply.c
> +++ b/builtin/apply.c
> @@ -294,20 +294,16 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
>  	const char *last2 = s2 + n2 - 1;
>  	int result = 0;
>  
> +	/* early return if both lines are empty */
> +	if ((s1 > last1) && (s2 > last2))
> +		return 1;
> +

Why is this an improvement?  Do you expect this function to be called
often for empty lines (as opposed, for example, to lines consisting
solely of whitespace characters)?

>  	/* ignore line endings */
>  	while ((*last1 == '\r') || (*last1 == '\n'))
>  		last1--;
>  	while ((*last2 == '\r') || (*last2 == '\n'))
>  		last2--;
>  
> -	/* skip leading whitespace */
> -	while (isspace(*s1) && (s1 <= last1))
> -		s1++;
> -	while (isspace(*s2) && (s2 <= last2))
> -		s2++;
> -	/* early return if both lines are empty */
> -	if ((s1 > last1) && (s2 > last2))
> -		return 1;
>  	while (!result) {
>  		result = *s1++ - *s2++;
>  		/*
> @@ -315,18 +311,15 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
>  		 * both buffers because we don't want "a b" to match
>  		 * "ab"
>  		 */
> -		if (isspace(*s1) && isspace(*s2)) {
> -			while (isspace(*s1) && s1 <= last1)
> -				s1++;
> -			while (isspace(*s2) && s2 <= last2)
> -				s2++;
> -		}
> +		while (isspace(*s1) && s1 <= last1)
> +			s1++;
> +		while (isspace(*s2) && s2 <= last2)
> +			s2++;

The comment just above this change gives a justification for putting an
"if" statement surrounding the "while" statements.  Do you think the
comment's argument is incorrect?  If so, please explain why, and remove
or change the comment.

>  		/*
>  		 * If we reached the end on one side only,
>  		 * lines don't match
>  		 */
> -		if (
> -		    ((s2 > last2) && (s1 <= last1)) ||
> +		if (((s2 > last2) && (s1 <= last1)) ||

This reformatting doesn't have anything to do with the rest of your
patch.  If it were important enough to make this change, then it should
be submitted as a separate patch.  But it is probably not important
enough, and is only code churn, so it should probably be omitted entirely.

>  		    ((s1 > last1) && (s2 <= last2)))
>  			return 0;
>  		if ((s1 > last1) && (s2 > last2))
> 


-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[George Papanikolaou]

Hi,
Thanks for the feedback,

On Thu, Mar 20, 2014 at 11:58 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>
> Why is this an improvement?  Do you expect this function to be called
> often for empty lines (as opposed, for example, to lines consisting
> solely of whitespace characters)?
>

Yes, you are probably right, we are not gonna get much (if any)
completely empty lines

>
> The comment just above this change gives a justification for putting an
> "if" statement surrounding the "while" statements.  Do you think the
> comment's argument is incorrect?  If so, please explain why, and remove
> or change the comment.
>

I see what I did wrong. I thought since that the if-condition is double checked
(from the while clause) so I removed it.

Also this lead me to see that since the while clause is now unconditioned, there
is no point of it being replicated exactly the same above, so I
removed that too. =(

I'm trying to find other inefficiencies/irregularities on that
function. I'm currently
thinking on merging the first checks with a call to iswspace() or
something similar.

Also thanks for clarifying the way patches/mails work.

Cheers.

---
papanikge's surrogate email.
I may reply back.
http://www.5slingshots.com/

[PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[George Papanikolaou]

Hi again guys,
I forgot to add the signed-of line to the tiny patch I sent earlier for GSOC.
Any ideas about the changes?
Thanks...

Signed-off-by: George Papanikolaou <g3orge.app@gmail.com>
---
 builtin/apply.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/builtin/apply.c b/builtin/apply.c
index b0d0986..df2435f 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -294,20 +294,16 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
 	const char *last2 = s2 + n2 - 1;
 	int result = 0;
 
+	/* early return if both lines are empty */
+	if ((s1 > last1) && (s2 > last2))
+		return 1;
+
 	/* ignore line endings */
 	while ((*last1 == '\r') || (*last1 == '\n'))
 		last1--;
 	while ((*last2 == '\r') || (*last2 == '\n'))
 		last2--;
 
-	/* skip leading whitespace */
-	while (isspace(*s1) && (s1 <= last1))
-		s1++;
-	while (isspace(*s2) && (s2 <= last2))
-		s2++;
-	/* early return if both lines are empty */
-	if ((s1 > last1) && (s2 > last2))
-		return 1;
 	while (!result) {
 		result = *s1++ - *s2++;
 		/*
@@ -315,18 +311,15 @@ static int fuzzy_matchlines(const char *s1, size_t n1,
 		 * both buffers because we don't want "a b" to match
 		 * "ab"
 		 */
-		if (isspace(*s1) && isspace(*s2)) {
-			while (isspace(*s1) && s1 <= last1)
-				s1++;
-			while (isspace(*s2) && s2 <= last2)
-				s2++;
-		}
+		while (isspace(*s1) && s1 <= last1)
+			s1++;
+		while (isspace(*s2) && s2 <= last2)
+			s2++;
 		/*
 		 * If we reached the end on one side only,
 		 * lines don't match
 		 */
-		if (
-		    ((s2 > last2) && (s1 <= last1)) ||
+		if (((s2 > last2) && (s1 <= last1)) ||
 		    ((s1 > last1) && (s2 <= last2)))
 			return 0;
 		if ((s1 > last1) && (s2 > last2))
-- 
1.9.0

Re: [PATCH] builtin/apply.c: fuzzy_matchlines:trying to fix some inefficiencies

[Jeff King]

On Thu, Mar 20, 2014 at 11:35:03AM +0200, George Papanikolaou wrote:

> Hi again guys,
> I forgot to add the signed-of line to the tiny patch I sent earlier for GSOC.
> Any ideas about the changes?
> Thanks...

You don't give any detail on the inefficiencies, or what specific
benchmark is made faster. Have you done any timings to show that there
is a measurable improvement? If so, can you share them in the commit
message?

-Peff