# mini-refactor in rerere.c 25 messages from 2007-09-24 to 2007-10-08. Participants: Pierre Habouzit, Johannes Schindelin, Junio C Hamano, Alex Riesen, Timo Hirvonen, David Kastrup, Miles Bader, Wincent Colaiuta, Jeff King, Florian Weimer. Thread: https://gitlist.dev/t/9993 ## Pierre Habouzit, 2007-09-24 09:25 Subject: mini-refactor in rerere.c Message-ID: <1190625904-22808-1-git-send-email-madcoder@debian.org> URL: https://gitlist.dev/e/1190625904-22808-1-git-send-email-madcoder%40debian.org ``` Here is a smallish series in builtin-rerere.c. Nothing very exciting though. ``` ## Johannes Schindelin, 2007-09-24 10:38 Subject: Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient. Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0709241136320.28395%40racer.site In-Reply-To: <1190625904-22808-3-git-send-email-madcoder@debian.org> ``` 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 ``` ## Junio C Hamano, 2007-09-26 00:31 Subject: Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient. Message-ID: <7v3ax22rnw.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7v3ax22rnw.fsf%40gitster.siamese.dyndns.org In-Reply-To: <1190625904-22808-3-git-send-email-madcoder@debian.org> ``` Signoffs? ``` ## Pierre Habouzit, 2007-09-26 08:41 Subject: Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient. Message-ID: <20070926084116.GA11479@artemis.corp> URL: https://gitlist.dev/e/20070926084116.GA11479%40artemis.corp In-Reply-To: <7v3ax22rnw.fsf@gitster.siamese.dyndns.org> ``` 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 To any patch I send to this list. -- ·O· Pierre Habouzit ··O madcoder@debian.org OOO http://www.madism.org ``` ## Alex Riesen, 2007-10-07 14:00 Subject: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007140052.GA3260@steel.home> URL: https://gitlist.dev/e/20071007140052.GA3260%40steel.home In-Reply-To: <1190625904-22808-2-git-send-email-madcoder@debian.org> ``` It is definitely less code (also object code). It is not always measurably faster (but mostly is). Signed-off-by: Alex Riesen --- 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 ``` ## Timo Hirvonen, 2007-10-07 14:24 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007172425.bb691da9.tihirvon@gmail.com> URL: https://gitlist.dev/e/20071007172425.bb691da9.tihirvon%40gmail.com In-Reply-To: <20071007140052.GA3260@steel.home> ``` Alex Riesen 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); } ``` ## David Kastrup, 2007-10-07 14:24 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <85fy0nknnq.fsf@lola.goethe.zz> URL: https://gitlist.dev/e/85fy0nknnq.fsf%40lola.goethe.zz In-Reply-To: <20071007140052.GA3260@steel.home> ``` Alex Riesen 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 ``` ## Pierre Habouzit, 2007-10-07 14:39 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007143912.GB10024@artemis.corp> URL: https://gitlist.dev/e/20071007143912.GB10024%40artemis.corp In-Reply-To: <20071007172425.bb691da9.tihirvon@gmail.com> ``` On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote: > Alex Riesen 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 ``` ## Miles Bader, 2007-10-07 15:46 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <87sl4nlyg0.fsf@catnip.gol.com> URL: https://gitlist.dev/e/87sl4nlyg0.fsf%40catnip.gol.com In-Reply-To: <20071007143912.GB10024@artemis.corp> ``` Pierre Habouzit 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] ``` ## David Kastrup, 2007-10-07 16:07 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <857ilylxhm.fsf@lola.goethe.zz> URL: https://gitlist.dev/e/857ilylxhm.fsf%40lola.goethe.zz In-Reply-To: <87sl4nlyg0.fsf@catnip.gol.com> ``` Miles Bader writes: > Pierre Habouzit 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 ``` ## Alex Riesen, 2007-10-07 16:10 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007161012.GB3270@steel.home> URL: https://gitlist.dev/e/20071007161012.GB3270%40steel.home In-Reply-To: <85fy0nknnq.fsf@lola.goethe.zz> ``` David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200: > Alex Riesen 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. ``` ## Johannes Schindelin, 2007-10-07 16:11 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0710071710190.4174%40racer.site In-Reply-To: <20071007143912.GB10024@artemis.corp> ``` 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 ``` ## Timo Hirvonen, 2007-10-07 16:18 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007191821.c872cc51.tihirvon@gmail.com> URL: https://gitlist.dev/e/20071007191821.c872cc51.tihirvon%40gmail.com In-Reply-To: ``` 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. Almost. If a is "hello\0world" and b is "hello" then it would compare 6 characters from both and think the strings are equal. ``` ## David Kastrup, 2007-10-07 16:27 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <851wc6lwkc.fsf@lola.goethe.zz> URL: https://gitlist.dev/e/851wc6lwkc.fsf%40lola.goethe.zz In-Reply-To: <20071007161012.GB3270@steel.home> ``` Alex Riesen writes: > David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200: >> Alex Riesen 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 ``` ## Pierre Habouzit, 2007-10-07 16:54 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007165424.GF10024@artemis.corp> URL: https://gitlist.dev/e/20071007165424.GF10024%40artemis.corp In-Reply-To: ``` 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 ``` ## Johannes Schindelin, 2007-10-07 18:25 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0710071925120.4174%40racer.site In-Reply-To: <20071007191821.c872cc51.tihirvon@gmail.com> ``` Hi, On Sun, 7 Oct 2007, Timo Hirvonen wrote: > Johannes Schindelin 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 ``` ## Alex Riesen, 2007-10-07 21:54 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007215432.GC2765@steel.home> URL: https://gitlist.dev/e/20071007215432.GC2765%40steel.home In-Reply-To: <857ilylxhm.fsf@lola.goethe.zz> ``` David Kastrup, Sun, Oct 07, 2007 18:07:17 +0200: > Miles Bader writes: > > > Pierre Habouzit 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). ``` ## Alex Riesen, 2007-10-07 21:57 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007215749.GD2765@steel.home> URL: https://gitlist.dev/e/20071007215749.GD2765%40steel.home In-Reply-To: <851wc6lwkc.fsf@lola.goethe.zz> ``` David Kastrup, Sun, Oct 07, 2007 18:27:15 +0200: > Alex Riesen 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! ``` ## Wincent Colaiuta, 2007-10-07 22:12 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: URL: https://gitlist.dev/e/EF81F7DD-73C7-4B6F-92D2-4A143CA05365%40wincent.com In-Reply-To: <20071007215432.GC2765@steel.home> ``` 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 ``` ## Alex Riesen, 2007-10-07 22:31 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071007223140.GG2765@steel.home> URL: https://gitlist.dev/e/20071007223140.GG2765%40steel.home In-Reply-To: ``` 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 #include #include #include #include #include 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; } ``` ## Miles Bader, 2007-10-08 01:45 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <87odfapefc.fsf@catnip.gol.com> URL: https://gitlist.dev/e/87odfapefc.fsf%40catnip.gol.com In-Reply-To: <20071007223140.GG2765@steel.home> ``` Alex Riesen 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. ``` ## Jeff King, 2007-10-08 02:19 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071008021945.GC20050@coredump.intra.peff.net> URL: https://gitlist.dev/e/20071008021945.GC20050%40coredump.intra.peff.net In-Reply-To: <20071007215749.GD2765@steel.home> ``` 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 ``` ## Pierre Habouzit, 2007-10-08 07:23 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071008072312.GA22552@artemis.corp> URL: https://gitlist.dev/e/20071008072312.GA22552%40artemis.corp In-Reply-To: <87odfapefc.fsf@catnip.gol.com> ``` On Mon, Oct 08, 2007 at 01:45:27AM +0000, Miles Bader wrote: > Alex Riesen 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 ``` ## Florian Weimer, 2007-10-08 08:54 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <82k5py6l6f.fsf@mid.bfk.de> URL: https://gitlist.dev/e/82k5py6l6f.fsf%40mid.bfk.de In-Reply-To: <20071008072312.GA22552@artemis.corp> ``` * 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 BFK edv-consulting GmbH http://www.bfk.de/ Kriegsstraße 100 tel: +49-721-96201-1 D-76133 Karlsruhe fax: +49-721-96201-99 ``` ## Alex Riesen, 2007-10-08 18:51 Subject: Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit Message-ID: <20071008185111.GC3123@steel.home> URL: https://gitlist.dev/e/20071008185111.GC3123%40steel.home In-Reply-To: <82k5py6l6f.fsf@mid.bfk.de> ``` 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. ```