[PATCH] Speedup prefixcmp() common case

[PATCH] Speedup prefixcmp() common case

[Marco Costalba]

In case the prefix string is a single char avoid a
costly call to strlen() + strncmp()

With this patch git log with --pretty=format option
is 10% faster

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---

Some profiling of git-log shows that strbuf_expand() is
called for each commit, and every time checks the
placeholders vector against the current one.

This check is done calling prefixcmp() in a tight loop.
Speeding up prefixcmp() speeds up the whole git-log thing.

NOTE I: I have tried to perform the single char check
directly in the loop, so to avoid to modify prefixcmp()
but the results, although better then the vanilla case,
are not so good. This means that there are other fast
paths that benefit from this optimization of prefixcmp().

NOTE II: currently for _each_ commit is done the whole
check of the --pretty=format against the placeholders vector.
This is clearly suboptimal because the custom format
_never changes_ for the whole git-log run, so some
caching  of the parsed format would be surely effective.

Anyhow, as I said before, this change seems to positively
impact other paths apart from the loop in strbuf_expand()
so it seems worth to have anyway.


 git-compat-util.h |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/git-compat-util.h b/git-compat-util.h
index 79eb10e..e26b684 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -398,6 +398,10 @@ static inline int sane_case

 static inline int prefixcmp(const char *str, const char *prefix)
 {
+	// shortcut common case of a single char prefix
+	if (prefix && *(prefix + 1) == '\0' && str)
+		return *str - *prefix;
+
 	return strncmp(str, prefix, strlen(prefix));
 }

-- 
1.5.4.rc2-dirty

[PATCH] Optimize prefixcmp()

[Johannes Schindelin]

Certain codepaths (notably "git log --pretty=format...") use
prefixcmp() extensively, with very short prefixes.  In those cases,
calling strlen() is a wasteful operation, so avoid it.

Initial patch by Marco Costalba.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	On Sat, 29 Dec 2007, Marco Costalba wrote:

	> In case the prefix string is a single char avoid a costly call 
	> to strlen() + strncmp()

	Could you test this patch, please?

	Not only does it avoid the strlen() call also for longer prefixes; 
	it also avoids a C++ comment.

 git-compat-util.h |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/git-compat-util.h b/git-compat-util.h
index 79eb10e..7059cbd 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -398,7 +398,11 @@ static inline int sane_case(int x, int high)
 
 static inline int prefixcmp(const char *str, const char *prefix)
 {
-	return strncmp(str, prefix, strlen(prefix));
+	for (; ; str++, prefix++)
+		if (!*prefix)
+			return 0;
+		else if (*str != *prefix)
+			return (unsigned char)*prefix - (unsigned char)*str;
 }
 
 static inline int strtoul_ui(char const *s, int base, unsigned int *result)
-- 
1.5.2.rc0.4321.gd618

Re: [PATCH] Optimize prefixcmp()

[Marco Costalba]

On Dec 29, 2007 8:22 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
>
>         Not only does it avoid the strlen() call also for longer prefixes;
>         it also avoids a C++ comment.
>

Avoiding a C++ comment is good ;-) sorry, it slipped to me.

What your patch does not seem to avoid is a segfault if prefix or str
are NULL pointers.


Marco

Re: [PATCH] Optimize prefixcmp()

[Johannes Schindelin]

Hi,

On Sat, 29 Dec 2007, Marco Costalba wrote:

> What your patch does not seem to avoid is a segfault if prefix or str 
> are NULL pointers.

I am quite certain that it is not allowed to pass NULL pointers to strcmp, 
and even if it was, I maintain that it is bad style.

FWIW the test suite seems to agree with me, as it passes with my patch.

However, since you already seem to have a profiling setup ready, I would 
be interested in some numbers, i.e. if this patch is faster for you or 
slower, or shows no effect at all.

Ciao,
Dscho

Re: [PATCH] Optimize prefixcmp()

[Marco Costalba]

On Dec 29, 2007 11:15 PM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
>
> However, since you already seem to have a profiling setup ready, I would
> be interested in some numbers, i.e. if this patch is faster for you or
> slower, or shows no effect at all.
>

Ok. I will do some tests with your patch and I'll let you know.

Marco

Re: [PATCH] Optimize prefixcmp()

[Marco Costalba]

On Dec 29, 2007 11:15 PM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
>
> However, since you already seem to have a profiling setup ready, I would
> be interested in some numbers, i.e. if this patch is faster for you or
> slower, or shows no effect at all.
>

Yes Johannes, your patch is faster then mine ;-)


These are the results tested on Linux tree:

Vanilla

[marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
3.61user 0.09system 0:03.70elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27155minor)pagefaults 0swaps


Marco's path

[marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
3.21user 0.08system 0:03.30elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27154minor)pagefaults 0swaps


Johannes's patch

[marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
2.92user 0.08system 0:03.01elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27155minor)pagefaults 0swaps



But that's not the end of the story....

After profiling I have found a better yet patch :-)

-------------------- CUT ABOVE --------------------

Subject: [PATCH] Certain codepaths (notably "git log --pretty=format...") use

prefixcmp() extensively, with very short prefixes.  In those cases,
calling strlen() is a wasteful operation, so avoid it.

Initial patch by Johannes Schindelin.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---
 git-compat-util.h |   11 ++++++++++-
 1 files changed, 10 insertions(+), 1 deletions(-)

diff --git a/git-compat-util.h b/git-compat-util.h
index 79eb10e..843a8f5 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)

 static inline int prefixcmp(const char *str, const char *prefix)
 {
-	return strncmp(str, prefix, strlen(prefix));
+	do {
+		if (*str != *prefix)
+			return *(unsigned const char *)prefix - *(unsigned const char *)str;
+
+		if (!*(++prefix))
+			return 0;
+
+		str++;
+
+	} while (1);
 }

 static inline int strtoul_ui(char const *s, int base, unsigned int *result)
-- 
1.5.4.rc2-dirty

BTW the results with this profiled patch are the followings:

Marco's patch TAKE 2 (profiled one)

[marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
2.89user 0.07system 0:02.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27154minor)pagefaults 0swaps


Not a big improvement, but an improvement in any case because the
check for (*prefix==0) and for (*str != *prefix) are swapped regarding
your patch, this means that in the common case of a failing match (as
happens where you are looking for a specific prefix in a string
vector) with this patch you avoid the (*prefix==0) comparison because
prefixcmp() exsits just after the (*str != *prefix).


Of course we need that the *prefix is not "", but we have already
ruled out prefix == NULL, so It does not seem a biggie...

Thanks...it was very fun!
Marco

Re: [PATCH] Optimize prefixcmp()

[Pierre Habouzit]

[-- Attachment #1: Type: text/plain, Size: 1453 bytes --]

On Sun, Dec 30, 2007 at 01:02:28PM +0000, Marco Costalba wrote:
> Subject: [PATCH] Certain codepaths (notably "git log --pretty=format...") use
> 
> prefixcmp() extensively, with very short prefixes.  In those cases,
> calling strlen() is a wasteful operation, so avoid it.
> 
> Initial patch by Johannes Schindelin.
> 
> Signed-off-by: Marco Costalba <mcostalba@gmail.com>
> ---
>  git-compat-util.h |   11 ++++++++++-
>  1 files changed, 10 insertions(+), 1 deletions(-)
> 
> diff --git a/git-compat-util.h b/git-compat-util.h
> index 79eb10e..843a8f5 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)
> 
>  static inline int prefixcmp(const char *str, const char *prefix)
>  {
> -	return strncmp(str, prefix, strlen(prefix));
> +	do {
> +		if (*str != *prefix)
> +			return *(unsigned const char *)prefix - *(unsigned const char *)str;
> +
> +		if (!*(++prefix))
> +			return 0;
> +
> +		str++;
> +
> +	} while (1);

  This code doesn't work if prefix is "". You want something like:

    for (; *prefix; prefix++, str++) {
        if (*str != *prefix)
            return *(unsigned const char *)prefix - *(unsigned const char *)str;
    }
    return 0;

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] Optimize prefixcmp()

[Pierre Habouzit]

[-- Attachment #1: Type: text/plain, Size: 1748 bytes --]

On Sun, Dec 30, 2007 at 01:55:57PM +0000, Pierre Habouzit wrote:
> On Sun, Dec 30, 2007 at 01:02:28PM +0000, Marco Costalba wrote:
> > Subject: [PATCH] Certain codepaths (notably "git log --pretty=format...") use
> > 
> > prefixcmp() extensively, with very short prefixes.  In those cases,
> > calling strlen() is a wasteful operation, so avoid it.
> > 
> > Initial patch by Johannes Schindelin.
> > 
> > Signed-off-by: Marco Costalba <mcostalba@gmail.com>
> > ---
> >  git-compat-util.h |   11 ++++++++++-
> >  1 files changed, 10 insertions(+), 1 deletions(-)
> > 
> > diff --git a/git-compat-util.h b/git-compat-util.h
> > index 79eb10e..843a8f5 100644
> > --- a/git-compat-util.h
> > +++ b/git-compat-util.h
> > @@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)
> > 
> >  static inline int prefixcmp(const char *str, const char *prefix)
> >  {
> > -	return strncmp(str, prefix, strlen(prefix));
> > +	do {
> > +		if (*str != *prefix)
> > +			return *(unsigned const char *)prefix - *(unsigned const char *)str;
> > +
> > +		if (!*(++prefix))
> > +			return 0;
> > +
> > +		str++;
> > +
> > +	} while (1);
> 
>   This code doesn't work if prefix is "". You want something like:
> 
>     for (; *prefix; prefix++, str++) {
>         if (*str != *prefix)
>             return *(unsigned const char *)prefix - *(unsigned const char *)str;
>     }
>     return 0;

  Which happens to be basically the same than what Dscho wrote, though I
suppose the compiler can compile that more efficiently than his code.


-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] Optimize prefixcmp()

[Marco Costalba]

On Dec 30, 2007 2:58 PM, Pierre Habouzit <madcoder@debian.org> wrote:
> >
> >   This code doesn't work if prefix is "". You want something like:
> >
> >     for (; *prefix; prefix++, str++) {
> >         if (*str != *prefix)
> >             return *(unsigned const char *)prefix - *(unsigned const char *)str;
> >     }
> >     return 0;
>
>   Which happens to be basically the same than what Dscho wrote, though I
> suppose the compiler can compile that more efficiently than his code.
>

Yes, your version covers the *prefix == "" case too. If this case is
important for us we could use something as

static inline int prefixcmp(const char *str, const char *prefix)
{
	do {
		if (*str != *prefix)
			return (!*prefix ? 0 : *(unsigned const char *)prefix - *(unsigned
const char *)str);

		if (!*(++prefix))
			return 0;

		str++;

	} while (1);
}


But your code is *surely* nicer then this one. But, for unknown
reasons, this code happens to be faster, probably as you say the
compiler optimizes away the second check in the return statement so
that this version is slightly faster then the 'for' loop one, but
admitelly we are going to much in the academic now.

If *prefix == "" case is to be considered I vote for your/Johannes
version because it's "better code" (tm).


Marco

Re: [PATCH] Optimize prefixcmp()

[Marco Costalba]

On Dec 30, 2007 3:50 PM, Marco Costalba <mcostalba@gmail.com> wrote:
>
> If *prefix == "" case is to be considered I vote for your/Johannes
> version because it's "better code" (tm).
>
Ok this is fast and correct

static inline int prefixcmp(const char *str, const char *prefix)
{
	while (*str == *prefix && *prefix)
    		str++, prefix++;

	return (*prefix ? *(unsigned const char *)prefix - *(unsigned const
char *)str : 0);
}


This is the last one, I promise ;-)

Marco

Re: [PATCH] Optimize prefixcmp()

[Johannes Schindelin]

Hi,

On Sun, 30 Dec 2007, Marco Costalba wrote:

> Initial patch by Johannes Schindelin.

Not true ;-)

Ciao,
Dscho

Re: [PATCH] Optimize prefixcmp()

[Andy Parkins]

On Saturday 2007, December 29, Johannes Schindelin wrote:

> 	Not only does it avoid the strlen() call also for longer prefixes;
> 	it also avoids a C++ comment.

I'm sure it doesn't matter; but they're allowed in C99.  So it's not a C++ 
comment any more :-)


Andy

-- 
Dr Andy Parkins, M Eng (hons), MIET
andyparkins@gmail.com

Re: [PATCH] Optimize prefixcmp()

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Certain codepaths (notably "git log --pretty=format...") use
> prefixcmp() extensively, with very short prefixes.  In those cases,
> calling strlen() is a wasteful operation, so avoid it.
>
> Initial patch by Marco Costalba.
>
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
> ---
>
> 	On Sat, 29 Dec 2007, Marco Costalba wrote:
>
> 	> In case the prefix string is a single char avoid a costly call 
> 	> to strlen() + strncmp()
>
> 	Could you test this patch, please?
>
> 	Not only does it avoid the strlen() call also for longer prefixes; 
> 	it also avoids a C++ comment.
>
>  git-compat-util.h |    6 +++++-
>  1 files changed, 5 insertions(+), 1 deletions(-)
>
> diff --git a/git-compat-util.h b/git-compat-util.h
> index 79eb10e..7059cbd 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -398,7 +398,11 @@ static inline int sane_case(int x, int high)
>  
>  static inline int prefixcmp(const char *str, const char *prefix)
>  {
> -	return strncmp(str, prefix, strlen(prefix));
> +	for (; ; str++, prefix++)
> +		if (!*prefix)
> +			return 0;
> +		else if (*str != *prefix)
> +			return (unsigned char)*prefix - (unsigned char)*str;
>  }

Losing the unnecessary check for !str || !prefix is a good
change.

While I think, for the readability's sake, Marco's original
without the unnecessary check would be the way to go, a profile
from your totally inlined version would also be interesting, as
it may or may not beat the underlying strncmp(), which could be
highly optimized.

Re: [PATCH] Optimize prefixcmp()

[René Scharfe]

Johannes Schindelin schrieb:
> Certain codepaths (notably "git log --pretty=format...") use
> prefixcmp() extensively, with very short prefixes.  In those cases,
> calling strlen() is a wasteful operation, so avoid it.

>  static inline int prefixcmp(const char *str, const char *prefix)
>  {
> -	return strncmp(str, prefix, strlen(prefix));
> +	for (; ; str++, prefix++)
> +		if (!*prefix)
> +			return 0;
> +		else if (*str != *prefix)
> +			return (unsigned char)*prefix - (unsigned char)*str;
>  }
>  
>  static inline int strtoul_ui(char const *s, int base, unsigned int *result)

prefixcmp() was already optimized before -- only for a different use
case.  At a number of callsites the prefix is a string literal, which
allowed the compiler to perform the strlen() call at compile time.

The patch increases the text size considerably: the file "git" is
2,620,938 without and 2,640,450 with the patch in my build (there are
136 callsites in builtin*.c).  The new version of prefixcmp() shouldn't
be inlined any more, as the benefit of doing so is gone.

Is there a portable way to let the preprocessor decide if
prefixcmp_literal() or prefixcmp_generic() is to be used, depending on
the prefix being a string literal or not?

René

Re: [PATCH] Optimize prefixcmp()

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

> prefixcmp() was already optimized before -- only for a different use
> case.  At a number of callsites the prefix is a string literal, which
> allowed the compiler to perform the strlen() call at compile time.
>
> The patch increases the text size considerably: the file "git" is
> 2,620,938 without and 2,640,450 with the patch in my build (there are
> 136 callsites in builtin*.c).  The new version of prefixcmp() shouldn't
> be inlined any more, as the benefit of doing so is gone.

Yuck, you are absolutely right.  The late thread may have been
well intentioned but resulted in this regression.  Sorry about
that.

I presume that all callers with constant prefix are outside
performance critical parts?  Can we simply uninline the function
in that case?

Re: [PATCH] Optimize prefixcmp()

[René Scharfe]

Junio C Hamano schrieb:
> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
> 
>> prefixcmp() was already optimized before -- only for a different use
>> case.  At a number of callsites the prefix is a string literal, which
>> allowed the compiler to perform the strlen() call at compile time.
>>
>> The patch increases the text size considerably: the file "git" is
>> 2,620,938 without and 2,640,450 with the patch in my build (there are
>> 136 callsites in builtin*.c).  The new version of prefixcmp() shouldn't
>> be inlined any more, as the benefit of doing so is gone.
> 
> Yuck, you are absolutely right.  The late thread may have been
> well intentioned but resulted in this regression.  Sorry about
> that.
> 
> I presume that all callers with constant prefix are outside
> performance critical parts?  Can we simply uninline the function
> in that case?

Most of them seem to be non-critical performance-wise.  They are part of
code to parse parameters or config files.  Exceptions are the commit
message parsing code used for --pretty=format (which can't be an issue
given that prefixcmp() was made the way it's now to speed up this code
path) and half of the callsites in fast-import.c.

René

Re: [PATCH] Speedup prefixcmp() common case

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> diff --git a/git-compat-util.h b/git-compat-util.h
> index 79eb10e..e26b684 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -398,6 +398,10 @@ static inline int sane_case
>
>  static inline int prefixcmp(const char *str, const char *prefix)
>  {
> +	// shortcut common case of a single char prefix
> +	if (prefix && *(prefix + 1) == '\0' && str)
> +		return *str - *prefix;
> +

Why isn't it like this?

	if (!prefix[1])
		return *str - *prefix;

>  	return strncmp(str, prefix, strlen(prefix));
>  }
>
> -- 
> 1.5.4.rc2-dirty

Re: [PATCH] Speedup prefixcmp() common case

[Marco Costalba]

On Dec 29, 2007 8:32 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> Why isn't it like this?
>
>         if (!prefix[1])
>

well, what about if prefix == NULL ?

Actually I didn't checked if strncmp() checks for NULL pointers before
to proceed, if this is the case I managed to keep the same semantic.

You could say "Why, lazy you, didn't you checked if strncmp() checks
for NULL pointers? "...but I hope you are foregiving ;-)

Thanks
Marco

Re: [PATCH] Speedup prefixcmp() common case

[Junio C Hamano]

"Marco Costalba" <mcostalba@gmail.com> writes:

> On Dec 29, 2007 8:32 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>
>> Why isn't it like this?
>>
>>         if (!prefix[1])
>>
>
> well, what about if prefix == NULL ?

What about it?  Do not trim what's relevant when your quote,
please.

Your slow path does this:

>  	return strncmp(str, prefix, strlen(prefix));
>  }

So it will barf when prefix == NULL anyway due to strlen().  I
think passing NULL as prefix to prefixcmp() is a caller-error.

I think my version is also buggy.  Passing "" as prefix to
prefixcmp() is nonsense but is supported, and checking prefix[1]
without looking at prefix[0] reads past the end of the string.

So, in summary, I think the following is what we would want.

 static inline int prefixcmp(const char *str, const char *prefix)
 {
+	// shortcut common case of a single char prefix
+	if (prefix[0] && !prefix[1])
+		return *str - *prefix;
+
 	return strncmp(str, prefix, strlen(prefix));
 }

Re: [PATCH] Speedup prefixcmp() common case

[Marco Costalba]

In case the prefix string is a single char avoid a
costly call to strlen() + strncmp()

With this patch git log with --pretty=format option
is 10% faster

With suggestions by Junio C Hamano

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---


 git-compat-util.h |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/git-compat-util.h b/git-compat-util.h
index 79eb10e..e26b684 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -398,6 +398,10 @@ static inline int sane_case

 static inline int prefixcmp(const char *str, const char *prefix)
 {
+       /* shortcut common case of a single char prefix */
+       if (prefix && !prefix[1] && str)
+               return *str - *prefix;
+
       return strncmp(str, prefix, strlen(prefix));
 }

--
1.5.4.rc2-dirty