mini-refactor in rerere.c

mini-refactor in rerere.c

[Pierre Habouzit]

  Here is a smallish series in builtin-rerere.c. Nothing very exciting
though.

Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.

[Johannes Schindelin]

Hi,

both patches appear to be obviously correct to me.  (However, I was lazy 
enough not to compile and test, but I'd not expect any breakage there, 
given your previous patch serieses.  ;-)

Ciao,
Dscho

Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.

[Junio C Hamano]

Signoffs?

Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.

[Pierre Habouzit]

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

On mer, sep 26, 2007 at 12:31:47 +0000, Junio C Hamano wrote:
> Signoffs?

  This is obviously a lapse on my end.  You can add:

Signed-off-by: Pierre Habouzit <madcoder@debian.org>

  To any patch I send to this list.

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

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

[PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

It is definitely less code (also object code). It is not always
measurably faster (but mostly is).

Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
---
 strbuf.c |   12 ------------
 strbuf.h |    9 ++++++++-
 2 files changed, 8 insertions(+), 13 deletions(-)

diff --git a/strbuf.c b/strbuf.c
index f4201e1..215837b 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -58,18 +58,6 @@ void strbuf_rtrim(struct strbuf *sb)
 	sb->buf[sb->len] = '\0';
 }
 
-int strbuf_cmp(struct strbuf *a, struct strbuf *b)
-{
-	int cmp;
-	if (a->len < b->len) {
-		cmp = memcmp(a->buf, b->buf, a->len);
-		return cmp ? cmp : -1;
-	} else {
-		cmp = memcmp(a->buf, b->buf, b->len);
-		return cmp ? cmp : a->len != b->len;
-	}
-}
-
 void strbuf_splice(struct strbuf *sb, size_t pos, size_t len,
 				   const void *data, size_t dlen)
 {
diff --git a/strbuf.h b/strbuf.h
index 9b9e861..3116387 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -78,7 +78,14 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len) {
 
 /*----- content related -----*/
 extern void strbuf_rtrim(struct strbuf *);
-extern int strbuf_cmp(struct strbuf *, struct strbuf *);
+static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
+{
+	int len = a->len < b->len ? a->len: b->len;
+	int cmp = memcmp(a->buf, b->buf, len);
+	if (cmp)
+		return cmp;
+	return a->len < b->len ? -1: a->len != b->len;
+}
 
 /*----- add data in your buffer -----*/
 static inline void strbuf_addch(struct strbuf *sb, int c) {
-- 
1.5.3.4.223.g78587

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Timo Hirvonen]

Alex Riesen <raa.lkml@gmail.com> wrote:

> +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> +{
> +	int len = a->len < b->len ? a->len: b->len;
> +	int cmp = memcmp(a->buf, b->buf, len);
> +	if (cmp)
> +		return cmp;
> +	return a->len < b->len ? -1: a->len != b->len;
> +}

strbuf->buf is always non-NULL and NUL-terminated so you could just do

static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
{
	int len = a->len < b->len ? a->len : b->len;
	return memcmp(a->buf, b->buf, len + 1);
}

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[David Kastrup]

Alex Riesen <raa.lkml@gmail.com> writes:

> It is definitely less code (also object code). It is not always
> measurably faster (but mostly is).

> -int strbuf_cmp(struct strbuf *a, struct strbuf *b)
> -{
> -	int cmp;
> -	if (a->len < b->len) {
> -		cmp = memcmp(a->buf, b->buf, a->len);
> -		return cmp ? cmp : -1;
> -	} else {
> -		cmp = memcmp(a->buf, b->buf, b->len);
> -		return cmp ? cmp : a->len != b->len;
> -	}
> -}
> -

> +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> +{
> +	int len = a->len < b->len ? a->len: b->len;
> +	int cmp = memcmp(a->buf, b->buf, len);
> +	if (cmp)
> +		return cmp;
> +	return a->len < b->len ? -1: a->len != b->len;
> +}

My guess is that you are conflating two issues about speed here: the
inlining will like speed the stuff up.  But having to evaluate the
(a->len < b->len) comparison twice will likely slow it down.

So if you do any profiling, you should do it on both separate angles
of this patch.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Pierre Habouzit]

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

On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:
> Alex Riesen <raa.lkml@gmail.com> wrote:
> 
> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > +{
> > +	int len = a->len < b->len ? a->len: b->len;
> > +	int cmp = memcmp(a->buf, b->buf, len);
> > +	if (cmp)
> > +		return cmp;
> > +	return a->len < b->len ? -1: a->len != b->len;
> > +}
> 
> strbuf->buf is always non-NULL and NUL-terminated so you could just do
> 
> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> {
> 	int len = a->len < b->len ? a->len : b->len;
> 	return memcmp(a->buf, b->buf, len + 1);
> }

  doesn't work, because a buffer can have (in some very specific cases)
an embeded NUL.

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

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

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Miles Bader]

Pierre Habouzit <madcoder@debian.org> writes:
>> strbuf->buf is always non-NULL and NUL-terminated so you could just do
>> 
>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
>> {
>> 	int len = a->len < b->len ? a->len : b->len;
>> 	return memcmp(a->buf, b->buf, len + 1);
>> }
>
>   doesn't work, because a buffer can have (in some very specific cases)
> an embeded NUL.

Couldn't you then just do:

   int len = a->len < b->len ? a->len : b->len;
   int cmp = memcmp(a->buf, b->buf, len);
   if (cmp == 0)
      cmp = b->len - a->len;
   return cmp;

[In the case where one string is a prefix of the other, then the longer
one is "greater".]

?

-Miles

-- 
"Suppose He doesn't give a shit?  Suppose there is a God but He
just doesn't give a shit?"  [George Carlin]

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[David Kastrup]

Miles Bader <miles@gnu.org> writes:

> Pierre Habouzit <madcoder@debian.org> writes:
>>> strbuf->buf is always non-NULL and NUL-terminated so you could just do
>>> 
>>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
>>> {
>>> 	int len = a->len < b->len ? a->len : b->len;
>>> 	return memcmp(a->buf, b->buf, len + 1);
>>> }
>>
>>   doesn't work, because a buffer can have (in some very specific cases)
>> an embeded NUL.
>
> Couldn't you then just do:
>
>    int len = a->len < b->len ? a->len : b->len;
>    int cmp = memcmp(a->buf, b->buf, len);
>    if (cmp == 0)
>       cmp = b->len - a->len;
>    return cmp;
>
> [In the case where one string is a prefix of the other, then the longer
> one is "greater".]
>
> ?

I fail to see where this variant is simpler than what we started the
journey of simplification from.

The only change I consider worth checking from the whole series in
this thread is making the function inline.  All the rest pretty much
was worse than what we started from in that it needed to reevaluate
more conditions and turned out more complicated and obfuscate even to
the human reader.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200:
> Alex Riesen <raa.lkml@gmail.com> writes:
> 
> > It is definitely less code (also object code). It is not always
> > measurably faster (but mostly is).
> 
> > -int strbuf_cmp(struct strbuf *a, struct strbuf *b)
> > -{
> > -	int cmp;
> > -	if (a->len < b->len) {
> > -		cmp = memcmp(a->buf, b->buf, a->len);
> > -		return cmp ? cmp : -1;
> > -	} else {
> > -		cmp = memcmp(a->buf, b->buf, b->len);
> > -		return cmp ? cmp : a->len != b->len;
> > -	}
> > -}
> > -
> 
> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > +{
> > +	int len = a->len < b->len ? a->len: b->len;
> > +	int cmp = memcmp(a->buf, b->buf, len);
> > +	if (cmp)
> > +		return cmp;
> > +	return a->len < b->len ? -1: a->len != b->len;
> > +}
> 
> My guess is that you are conflating two issues about speed here: the
> inlining will like speed the stuff up.  But having to evaluate the
> (a->len < b->len) comparison twice will likely slow it down.


Can't the result of the expression be reused in compiled?
Isn't it a common expression?

> So if you do any profiling, you should do it on both separate angles
> of this patch.
> 

I compared the inlined versions of both.

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Johannes Schindelin]

Hi,

On Sun, 7 Oct 2007, Pierre Habouzit wrote:

> On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:
>
> > strbuf->buf is always non-NULL and NUL-terminated so you could just do
> > 
> > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > {
> > 	int len = a->len < b->len ? a->len : b->len;
> > 	return memcmp(a->buf, b->buf, len + 1);
> > }
> 
>   doesn't work, because a buffer can have (in some very specific cases)
> an embeded NUL.

But it should work.  The function memcmp() could not care less if there is 
a NUL or not, it just compares until it finds a difference.

Ciao,
Dscho

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Timo Hirvonen]

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

> Hi,
> 
> On Sun, 7 Oct 2007, Pierre Habouzit wrote:
> 
> > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:
> >
> > > strbuf->buf is always non-NULL and NUL-terminated so you could just do
> > > 
> > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > > {
> > > 	int len = a->len < b->len ? a->len : b->len;
> > > 	return memcmp(a->buf, b->buf, len + 1);
> > > }
> > 
> >   doesn't work, because a buffer can have (in some very specific cases)
> > an embeded NUL.
> 
> But it should work.  The function memcmp() could not care less if there is 
> a NUL or not, it just compares until it finds a difference.

Almost.  If a is "hello\0world" and b is "hello" then it would compare 6
characters from both and think the strings are equal.

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[David Kastrup]

Alex Riesen <raa.lkml@gmail.com> writes:

> David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200:
>> Alex Riesen <raa.lkml@gmail.com> writes:
>> 
>> > It is definitely less code (also object code). It is not always
>> > measurably faster (but mostly is).
>> 
>> > -int strbuf_cmp(struct strbuf *a, struct strbuf *b)
>> > -{
>> > -	int cmp;
>> > -	if (a->len < b->len) {
>> > -		cmp = memcmp(a->buf, b->buf, a->len);
>> > -		return cmp ? cmp : -1;
>> > -	} else {
>> > -		cmp = memcmp(a->buf, b->buf, b->len);
>> > -		return cmp ? cmp : a->len != b->len;
>> > -	}
>> > -}
>> > -
>> 
>> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
>> > +{
>> > +	int len = a->len < b->len ? a->len: b->len;
>> > +	int cmp = memcmp(a->buf, b->buf, len);
>> > +	if (cmp)
>> > +		return cmp;
>> > +	return a->len < b->len ? -1: a->len != b->len;
>> > +}
>> 
>> My guess is that you are conflating two issues about speed here: the
>> inlining will like speed the stuff up.  But having to evaluate the
>> (a->len < b->len) comparison twice will likely slow it down.
>
> Can't the result of the expression be reused in compiled?
> Isn't it a common expression?

No, since the call to memcmp might change a->len or b->len.  A
standard-compliant C compiler can't make assumptions about what memcmp
might or might not touch unless both a and b can be shown to refer to
variables with an address never passed out of the scope of the
compilation unit.

>> So if you do any profiling, you should do it on both separate
>> angles of this patch.
>
> I compared the inlined versions of both.

Interesting.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Pierre Habouzit]

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

On Sun, Oct 07, 2007 at 04:11:29PM +0000, Johannes Schindelin wrote:
> Hi,
> 
> On Sun, 7 Oct 2007, Pierre Habouzit wrote:
> 
> > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:
> >
> > > strbuf->buf is always non-NULL and NUL-terminated so you could just do
> > > 
> > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > > {
> > > 	int len = a->len < b->len ? a->len : b->len;
> > > 	return memcmp(a->buf, b->buf, len + 1);
> > > }
> > 
> >   doesn't work, because a buffer can have (in some very specific cases)
> > an embeded NUL.
> 
> But it should work.  The function memcmp() could not care less if there is 
> a NUL or not, it just compares until it finds a difference.

  not if your one of your strbuf has as prefix, the other followed by
'\0', then anything else (including nothing ;p).

  Your test would yield equality.

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

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

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Johannes Schindelin]

Hi,

On Sun, 7 Oct 2007, Timo Hirvonen wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> 
> > On Sun, 7 Oct 2007, Pierre Habouzit wrote:
> > 
> > > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:
> > >
> > > > strbuf->buf is always non-NULL and NUL-terminated so you could just do
> > > > 
> > > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> > > > {
> > > > 	int len = a->len < b->len ? a->len : b->len;
> > > > 	return memcmp(a->buf, b->buf, len + 1);
> > > > }
> > > 
> > >   doesn't work, because a buffer can have (in some very specific cases)
> > > an embeded NUL.
> > 
> > But it should work.  The function memcmp() could not care less if there is 
> > a NUL or not, it just compares until it finds a difference.
> 
> Almost.  If a is "hello\0world" and b is "hello" then it would compare 6
> characters from both and think the strings are equal.

Good point.

Ciao,
Dscho

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

David Kastrup, Sun, Oct 07, 2007 18:07:17 +0200:
> Miles Bader <miles@gnu.org> writes:
> 
> > Pierre Habouzit <madcoder@debian.org> writes:
> >>> strbuf->buf is always non-NULL and NUL-terminated so you could just do
> >>> 
> >>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> >>> {
> >>> 	int len = a->len < b->len ? a->len : b->len;
> >>> 	return memcmp(a->buf, b->buf, len + 1);
> >>> }
> >>
> >>   doesn't work, because a buffer can have (in some very specific cases)
> >> an embeded NUL.
> >
> > Couldn't you then just do:
> >
> >    int len = a->len < b->len ? a->len : b->len;
> >    int cmp = memcmp(a->buf, b->buf, len);
> >    if (cmp == 0)
> >       cmp = b->len - a->len;
> >    return cmp;
> >
> > [In the case where one string is a prefix of the other, then the longer
> > one is "greater".]
> >
> > ?
> 
> I fail to see where this variant is simpler than what we started the
> journey of simplification from.
> 
> The only change I consider worth checking from the whole series in
> this thread is making the function inline. 

It also makes arguments const (which admittedly wont make it faster).

> ... All the rest pretty much
> was worse than what we started from in that it needed to reevaluate
> more conditions and turned out more complicated and obfuscate even to
> the human reader.

it _is_ smaller. And it is _measurably_ faster on that thing I have at
home (and old p4).

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

David Kastrup, Sun, Oct 07, 2007 18:27:15 +0200:
> Alex Riesen <raa.lkml@gmail.com> writes:
> >> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
> >> > +{
> >> > +	int len = a->len < b->len ? a->len: b->len;
> >> > +	int cmp = memcmp(a->buf, b->buf, len);
> >> > +	if (cmp)
> >> > +		return cmp;
> >> > +	return a->len < b->len ? -1: a->len != b->len;
> >> > +}
> >> 
> >> My guess is that you are conflating two issues about speed here: the
> >> inlining will like speed the stuff up.  But having to evaluate the
> >> (a->len < b->len) comparison twice will likely slow it down.
> >
> > Can't the result of the expression be reused in compiled?
> > Isn't it a common expression?
> 
> No, since the call to memcmp might change a->len or b->len.  A

Huh?! How's that? It is not even given them!

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Wincent Colaiuta]

El 7/10/2007, a las 23:54, Alex Riesen escribió:

>> ... All the rest pretty much
>> was worse than what we started from in that it needed to reevaluate
>> more conditions and turned out more complicated and obfuscate even to
>> the human reader.
>
> it _is_ smaller. And it is _measurably_ faster on that thing I have at
> home (and old p4).

Can we see the numbers and the steps used to obtain them? I'm also a  
little bit confused about how an inlined function can lead to a  
smaller executable... or did you just mean lines-of-code?

Cheers,
Wincent

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

Wincent Colaiuta, Mon, Oct 08, 2007 00:12:17 +0200:
> El 7/10/2007, a las 23:54, Alex Riesen escribió:
> 
> >>... All the rest pretty much
> >>was worse than what we started from in that it needed to reevaluate
> >>more conditions and turned out more complicated and obfuscate even to
> >>the human reader.
> >
> >it _is_ smaller. And it is _measurably_ faster on that thing I have at
> >home (and old p4).
> 
> Can we see the numbers and the steps used to obtain them? I'm also a  
> little bit confused about how an inlined function can lead to a  
> smaller executable... or did you just mean lines-of-code?

I did mean the bytes of object code. I never said it produces a
smaller executable.

I compiled with gcc -O2 and -O4, gcc 4.1.2 (Ubuntu 4.1.2-0ubuntu4).
Cut the functions out into their own files and compile them to get the
object code. Compile with -S (assembly) to examine the generated code.
Compare.

#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/time.h>
#include <stdio.h>
#include <string.h>

struct strbuf {
	size_t alloc;
	size_t len;
	char *buf;
};

int strbuf_cmp2(struct strbuf *a, struct strbuf *b)
{
	int len = a->len < b->len ? a->len: b->len;
	int cmp = memcmp(a->buf, b->buf, len);
	if (cmp)
		return cmp;
	return a->len < b->len ? -1: a->len != b->len;
}

int strbuf_cmp1(struct strbuf *a, struct strbuf *b)
{
	int cmp;
	if (a->len < b->len) {
		cmp = memcmp(a->buf, b->buf, a->len);
		return cmp ? cmp : -1;
	} else {
		cmp = memcmp(a->buf, b->buf, b->len);
		return cmp ? cmp : a->len != b->len;
	}
}

int main(int argc, char *argv[], char *envp[])
{
	struct strbuf s1 = {
		.alloc = 0,
		.len = 50,
		.buf = "01234567890123456789012345678901234567890123456789",
	};
	struct strbuf s2 = {
		.alloc = 0,
		.len = 50,
		.buf = "0123456789012345678901234567890123456789",
	};
	struct strbuf s3 = {
		.alloc = 0,
		.len = 50,
		.buf = "0123456789012345678901234567890123456789012345678x",
	};
	struct timeval tv1, tv2, diff;
	unsigned n;
	int result;
#define CYCLES 0xffffffffu

	strbuf_cmp1(&s1, &s2);
	strbuf_cmp1(&s2, &s3);
	result = 0;
	gettimeofday(&tv1, NULL);
	for (n = CYCLES; n--; ) {
		result += strbuf_cmp1(&s1, &s2);
		result += strbuf_cmp1(&s2, &s3);
		result += strbuf_cmp1(&s1, &s3);
		result += strbuf_cmp1(&s1, &s1);
		result += n;
	}
	gettimeofday(&tv2, NULL);
	timersub(&tv2, &tv1, &diff);
	printf("ph=%ld.%ld (%d)\n", diff.tv_sec, diff.tv_usec, result);

	strbuf_cmp2(&s1, &s2);
	strbuf_cmp2(&s2, &s3);
	result = 0;
	gettimeofday(&tv1, NULL);
	for (n = CYCLES; n--; ) {
		result += strbuf_cmp2(&s1, &s2);
		result += strbuf_cmp2(&s2, &s3);
		result += strbuf_cmp2(&s1, &s3);
		result += strbuf_cmp2(&s1, &s1);
		result += n;
	}
	gettimeofday(&tv2, NULL);
	timersub(&tv2, &tv1, &diff);
	printf("ar=%ld.%ld (%d)\n", diff.tv_sec, diff.tv_usec, result);
	return 0;
}

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Miles Bader]

Alex Riesen <raa.lkml@gmail.com> writes:
> int strbuf_cmp2(struct strbuf *a, struct strbuf *b)
> {
> 	int len = a->len < b->len ? a->len: b->len;
> 	int cmp = memcmp(a->buf, b->buf, len);
> 	if (cmp)
> 		return cmp;
> 	return a->len < b->len ? -1: a->len != b->len;
> }

BTW, why are you making such effort to return only -1, 0, or 1 in the
last line?  memcmp/strcmp make no such guarantee; e.g. glibc says:

     The `strcmp' function compares the string S1 against S2, returning
     a value that has the same sign as the difference between the first
     differing pair of characters (interpreted as `unsigned char'
     objects, then promoted to `int').

     If the two strings are equal, `strcmp' returns `0'.

     A consequence of the ordering used by `strcmp' is that if S1 is an
     initial substring of S2, then S1 is considered to be "less than"
     S2.

So I think the last line can just be:

   return a->len - b->len;

-miles

-- 
Suburbia: where they tear out the trees and then name streets after them.

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Jeff King]

On Sun, Oct 07, 2007 at 11:57:49PM +0200, Alex Riesen wrote:

> > > Can't the result of the expression be reused in compiled?
> > > Isn't it a common expression?
> > 
> > No, since the call to memcmp might change a->len or b->len.  A
> 
> Huh?! How's that? It is not even given them!

But they are non-local variables (they are part of structs passed in as
pointers), so that translation unit has no idea how they are allocated.
They could be globals that memcmp mucks with as a side effect.

That being said, standards-conforming compilers _can_ realize that
memcmp is a special, standards-defined function with no side effects and
act accordingly. gcc provides the 'pure' function attribute for this
purpose, which is used by glibc.

-Peff

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Pierre Habouzit]

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

On Mon, Oct 08, 2007 at 01:45:27AM +0000, Miles Bader wrote:
> Alex Riesen <raa.lkml@gmail.com> writes:
> > int strbuf_cmp2(struct strbuf *a, struct strbuf *b)
> > {
> > 	int len = a->len < b->len ? a->len: b->len;
> > 	int cmp = memcmp(a->buf, b->buf, len);
> > 	if (cmp)
> > 		return cmp;
> > 	return a->len < b->len ? -1: a->len != b->len;
> > }
> 
> BTW, why are you making such effort to return only -1, 0, or 1 in the
> last line?  memcmp/strcmp make no such guarantee; e.g. glibc says:
> 
>      The `strcmp' function compares the string S1 against S2, returning
>      a value that has the same sign as the difference between the first
>      differing pair of characters (interpreted as `unsigned char'
>      objects, then promoted to `int').
> 
>      If the two strings are equal, `strcmp' returns `0'.
> 
>      A consequence of the ordering used by `strcmp' is that if S1 is an
>      initial substring of S2, then S1 is considered to be "less than"
>      S2.
> 
> So I think the last line can just be:
> 
>    return a->len - b->len;

  Won't work because ->len are size_t and return value is int, so on 64
bits platform, this has chances to overflow.

  FWIW I believe we are doing micro-benchs in a function that is used in
2 places in git right now.

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

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

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Florian Weimer]

* Pierre Habouzit:

>> So I think the last line can just be:
>> 
>>    return a->len - b->len;
>
>   Won't work because ->len are size_t and return value is int, so on 64
> bits platform, this has chances to overflow.

Nit: It can overflow on 32-bit, too.

And "int len" in the first line of the function body should be
"size_t len".

Moving that to a compare_int/compare_size_t function should help;
AFAIK there's no short idiom which does the job.

-- 
Florian Weimer                <fweimer@bfk.de>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99

Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit

[Alex Riesen]

Florian Weimer, Mon, Oct 08, 2007 10:54:32 +0200:
> And "int len" in the first line of the function body should be
> "size_t len".

right. Missed that.