threads / patch / 11422

patchSpeedup prefixcmp() common case

Subject: [PATCH] Speedup prefixcmp() common case

## tl;dr

20 messages between Dec 29, 2007 and Jan 3, 2008. Diffs are folded; open one to read it.

replies: 19people: 6as markdown or json

Marco Costalba· Dec 29, 2007, 18:01 UTC · lore

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(-)
Show changes to git-compat-util.h +4 −0
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
Johannes Schindelin· Dec 29, 2007, 19:22 UTC · re: Marco Costalba · lore

[PATCH] Optimize prefixcmp()

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(-)
Show changes to git-compat-util.h +5 −1
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
Marco Costalba· Dec 29, 2007, 20:39 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

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
Johannes Schindelin· Dec 29, 2007, 22:15 UTC · re: Marco Costalba · lore

Re: [PATCH] Optimize prefixcmp()

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

Marco Costalba· Dec 29, 2007, 22:44 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

On Dec 29, 2007 11:15 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Show 5 quoted lines
>
> 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
Marco Costalba· Dec 30, 2007, 13:02 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

On Dec 29, 2007 11:15 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Show 5 quoted lines
>
> 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(-)
Show changes to git-compat-util.h +10 −1
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
Pierre Habouzit· Dec 30, 2007, 13:55 UTC · re: Marco Costalba · lore

Re: [PATCH] Optimize prefixcmp()

On Sun, Dec 30, 2007 at 01:02:28PM +0000, Marco Costalba wrote:
Show 31 quoted lines
> 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
Pierre Habouzit· Dec 30, 2007, 13:58 UTC · re: Pierre Habouzit · lore

Re: [PATCH] Optimize prefixcmp()

On Sun, Dec 30, 2007 at 01:55:57PM +0000, Pierre Habouzit wrote:
Show 40 quoted lines
> 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
Marco Costalba· Dec 30, 2007, 14:50 UTC · re: Pierre Habouzit · lore

Re: [PATCH] Optimize prefixcmp()

On Dec 30, 2007 2:58 PM, Pierre Habouzit <madcoder@debian.org> wrote:
Show 12 quoted lines
> >
> >   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
Marco Costalba· Dec 30, 2007, 15:17 UTC · re: Marco Costalba · lore

Re: [PATCH] Optimize prefixcmp()

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
Andy Parkins· Dec 29, 2007, 21:54 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

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
Junio C Hamano· Dec 30, 2007, 00:44 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
Show 37 quoted lines
> 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.

René Scharfe· Jan 2, 2008, 16:59 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Optimize prefixcmp()

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.
Show 11 quoted lines
>  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é
Junio C Hamano· Jan 2, 2008, 18:52 UTC · re: René Scharfe · lore

Re: [PATCH] Optimize prefixcmp()

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
Show 8 quoted lines
> 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?

René Scharfe· Jan 3, 2008, 00:45 UTC · re: Junio C Hamano · lore

Re: [PATCH] Optimize prefixcmp()

Junio C Hamano schrieb:
Show 18 quoted lines
> 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é
Junio C Hamano· Dec 29, 2007, 19:32 UTC · re: Marco Costalba · lore

Re: [PATCH] Speedup prefixcmp() common case

"Marco Costalba" <mcostalba@gmail.com> writes:
Show 12 quoted lines
> 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;
Show 5 quoted lines
>  	return strncmp(str, prefix, strlen(prefix));
>  }
>
> -- 
> 1.5.4.rc2-dirty
Marco Costalba· Dec 29, 2007, 20:14 UTC · re: Junio C Hamano · lore

Re: [PATCH] Speedup prefixcmp() common case

On Dec 29, 2007 8:32 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 5 quoted lines
>
> 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

Junio C Hamano· Dec 30, 2007, 00:05 UTC · re: Marco Costalba · lore

Re: [PATCH] Speedup prefixcmp() common case

"Marco Costalba" <mcostalba@gmail.com> writes:
Show 8 quoted lines
> 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));
 }
Marco Costalba· Dec 29, 2007, 20:43 UTC · re: Marco Costalba · lore

Re: [PATCH] Speedup prefixcmp() common case

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(-)
Show changes to git-compat-util.h +4 −1
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

← back to recent threads