Re: [PATCH] Optimize prefixcmp()

From

MCMarco Costalba <mcostalba@gmail.com>

Date

Dec 30, 2007, 13:02 UTC

Message-ID

<e5bfff550712300502p543680b9jbeb9469a5a970f0@mail.gmail.com>

In-Reply-To

<Pine.LNX.4.64.0712292307210.14355@wbgn129.biozentrum.uni-wuerzburg.de>

>
> 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's path

Johannes's patch

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

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