{"thread":{"id":"9993","subject":"mini-refactor in rerere.c","startedAt":"2007-09-24T09:25:02Z","lastAt":"2007-10-08T18:51:11Z","messageCount":25,"participants":["Pierre Habouzit","Johannes Schindelin","Junio C Hamano","Alex Riesen","Timo Hirvonen","David Kastrup","Miles Bader","Wincent Colaiuta","Jeff King","Florian Weimer"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"53902","messageId":"1190625904-22808-1-git-send-email-madcoder@debian.org","threadId":"9993","inReplyTo":null,"subject":"mini-refactor in rerere.c","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-09-24T09:25:02Z","receivedAt":"2007-09-24T09:25:02Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":" Here is a smallish series in builtin-rerere.c. Nothing very exciting\nthough.\n"},{"id":"53905","messageId":"Pine.LNX.4.64.0709241136320.28395@racer.site","threadId":"9993","inReplyTo":"1190625904-22808-3-git-send-email-madcoder@debian.org","subject":"Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-24T10:38:15Z","receivedAt":"2007-09-24T10:38:15Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nboth patches appear to be obviously correct to me. (However, I was lazy \nenough not to compile and test, but I'd not expect any breakage there, \ngiven your previous patch serieses. ;-)\n\nCiao,\nDscho\n"},{"id":"54070","messageId":"7v3ax22rnw.fsf@gitster.siamese.dyndns.org","threadId":"9993","inReplyTo":"1190625904-22808-3-git-send-email-madcoder@debian.org","subject":"Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-26T00:31:47Z","receivedAt":"2007-09-26T00:31:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signoffs?\n"},{"id":"54088","messageId":"20070926084116.GA11479@artemis.corp","threadId":"9993","inReplyTo":"7v3ax22rnw.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 2/2] Make builtin-rerere use of strbuf nicer and more efficient.","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-09-26T08:41:16Z","receivedAt":"2007-09-26T08:41:16Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On mer, sep 26, 2007 at 12:31:47 +0000, Junio C Hamano wrote:\n> Signoffs?\n\n This is obviously a lapse on my end. You can add:\n\nSigned-off-by: Pierre Habouzit \n\n To any patch I send to this list.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"55046","messageId":"20071007140052.GA3260@steel.home","threadId":"9993","inReplyTo":"1190625904-22808-2-git-send-email-madcoder@debian.org","subject":"[PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-07T14:00:52Z","receivedAt":"2007-10-07T14:00:52Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"It is definitely less code (also object code). It is not always\nmeasurably faster (but mostly is).\n\nSigned-off-by: Alex Riesen \n---\n strbuf.c | 12 ------------\n strbuf.h | 9 ++++++++-\n 2 files changed, 8 insertions(+), 13 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex f4201e1..215837b 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -58,18 +58,6 @@ void strbuf_rtrim(struct strbuf *sb)\n \tsb->buf[sb->len] = '\\0';\n }\n \n-int strbuf_cmp(struct strbuf *a, struct strbuf *b)\n-{\n-\tint cmp;\n-\tif (a->len < b->len) {\n-\t\tcmp = memcmp(a->buf, b->buf, a->len);\n-\t\treturn cmp ? cmp : -1;\n-\t} else {\n-\t\tcmp = memcmp(a->buf, b->buf, b->len);\n-\t\treturn cmp ? cmp : a->len != b->len;\n-\t}\n-}\n-\n void strbuf_splice(struct strbuf *sb, size_t pos, size_t len,\n \t\t\t\t const void *data, size_t dlen)\n {\ndiff --git a/strbuf.h b/strbuf.h\nindex 9b9e861..3116387 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -78,7 +78,14 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len) {\n \n /*----- content related -----*/\n extern void strbuf_rtrim(struct strbuf *);\n-extern int strbuf_cmp(struct strbuf *, struct strbuf *);\n+static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n+{\n+\tint len = a->len < b->len ? a->len: b->len;\n+\tint cmp = memcmp(a->buf, b->buf, len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn a->len < b->len ? -1: a->len != b->len;\n+}\n \n /*----- add data in your buffer -----*/\n static inline void strbuf_addch(struct strbuf *sb, int c) {\n-- \n1.5.3.4.223.g78587\n"},{"id":"55048","messageId":"20071007172425.bb691da9.tihirvon@gmail.com","threadId":"9993","inReplyTo":"20071007140052.GA3260@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Timo Hirvonen","fromEmail":"tihirvon@gmail.com","sentAt":"2007-10-07T14:24:25Z","receivedAt":"2007-10-07T14:24:25Z","isPatch":true,"sender":{"key":"tihirvon@gmail.com","avatar":null},"body":"Alex Riesen wrote:\n\n> +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> +{\n> +\tint len = a->len < b->len ? a->len: b->len;\n> +\tint cmp = memcmp(a->buf, b->buf, len);\n> +\tif (cmp)\n> +\t\treturn cmp;\n> +\treturn a->len < b->len ? -1: a->len != b->len;\n> +}\n\nstrbuf->buf is always non-NULL and NUL-terminated so you could just do\n\nstatic inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n{\n\tint len = a->len < b->len ? a->len : b->len;\n\treturn memcmp(a->buf, b->buf, len + 1);\n}\n"},{"id":"55049","messageId":"85fy0nknnq.fsf@lola.goethe.zz","threadId":"9993","inReplyTo":"20071007140052.GA3260@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-10-07T14:24:57Z","receivedAt":"2007-10-07T14:24:57Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Alex Riesen writes:\n\n> It is definitely less code (also object code). It is not always\n> measurably faster (but mostly is).\n\n> -int strbuf_cmp(struct strbuf *a, struct strbuf *b)\n> -{\n> -\tint cmp;\n> -\tif (a->len < b->len) {\n> -\t\tcmp = memcmp(a->buf, b->buf, a->len);\n> -\t\treturn cmp ? cmp : -1;\n> -\t} else {\n> -\t\tcmp = memcmp(a->buf, b->buf, b->len);\n> -\t\treturn cmp ? cmp : a->len != b->len;\n> -\t}\n> -}\n> -\n\n> +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> +{\n> +\tint len = a->len < b->len ? a->len: b->len;\n> +\tint cmp = memcmp(a->buf, b->buf, len);\n> +\tif (cmp)\n> +\t\treturn cmp;\n> +\treturn a->len < b->len ? -1: a->len != b->len;\n> +}\n\nMy guess is that you are conflating two issues about speed here: the\ninlining will like speed the stuff up. But having to evaluate the\n(a->len < b->len) comparison twice will likely slow it down.\n\nSo if you do any profiling, you should do it on both separate angles\nof this patch.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"55050","messageId":"20071007143912.GB10024@artemis.corp","threadId":"9993","inReplyTo":"20071007172425.bb691da9.tihirvon@gmail.com","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-07T14:39:12Z","receivedAt":"2007-10-07T14:39:12Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:\n> Alex Riesen wrote:\n> \n> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > +{\n> > +\tint len = a->len < b->len ? a->len: b->len;\n> > +\tint cmp = memcmp(a->buf, b->buf, len);\n> > +\tif (cmp)\n> > +\t\treturn cmp;\n> > +\treturn a->len < b->len ? -1: a->len != b->len;\n> > +}\n> \n> strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> \n> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> {\n> \tint len = a->len < b->len ? a->len : b->len;\n> \treturn memcmp(a->buf, b->buf, len + 1);\n> }\n\n doesn't work, because a buffer can have (in some very specific cases)\nan embeded NUL.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"55055","messageId":"87sl4nlyg0.fsf@catnip.gol.com","threadId":"9993","inReplyTo":"20071007143912.GB10024@artemis.corp","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Miles Bader","fromEmail":"miles@gnu.org","sentAt":"2007-10-07T15:46:39Z","receivedAt":"2007-10-07T15:46:39Z","isPatch":true,"sender":{"key":"miles@gnu.org","avatar":"https://gravatar.com/avatar/01069b69593af7bff28e2f97afeb3644ae6fe2f5f56cb3a8cf34c5fb8c36efe5?d=mp&s=160"},"body":"Pierre Habouzit writes:\n>> strbuf->buf is always non-NULL and NUL-terminated so you could just do\n>> \n>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n>> {\n>> \tint len = a->len < b->len ? a->len : b->len;\n>> \treturn memcmp(a->buf, b->buf, len + 1);\n>> }\n>\n> doesn't work, because a buffer can have (in some very specific cases)\n> an embeded NUL.\n\nCouldn't you then just do:\n\n int len = a->len < b->len ? a->len : b->len;\n int cmp = memcmp(a->buf, b->buf, len);\n if (cmp == 0)\n cmp = b->len - a->len;\n return cmp;\n\n[In the case where one string is a prefix of the other, then the longer\none is \"greater\".]\n\n?\n\n-Miles\n\n-- \n\"Suppose He doesn't give a shit? Suppose there is a God but He\njust doesn't give a shit?\" [George Carlin]\n"},{"id":"55058","messageId":"857ilylxhm.fsf@lola.goethe.zz","threadId":"9993","inReplyTo":"87sl4nlyg0.fsf@catnip.gol.com","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-10-07T16:07:17Z","receivedAt":"2007-10-07T16:07:17Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Miles Bader writes:\n\n> Pierre Habouzit writes:\n>>> strbuf->buf is always non-NULL and NUL-terminated so you could just do\n>>> \n>>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n>>> {\n>>> \tint len = a->len < b->len ? a->len : b->len;\n>>> \treturn memcmp(a->buf, b->buf, len + 1);\n>>> }\n>>\n>> doesn't work, because a buffer can have (in some very specific cases)\n>> an embeded NUL.\n>\n> Couldn't you then just do:\n>\n> int len = a->len < b->len ? a->len : b->len;\n> int cmp = memcmp(a->buf, b->buf, len);\n> if (cmp == 0)\n> cmp = b->len - a->len;\n> return cmp;\n>\n> [In the case where one string is a prefix of the other, then the longer\n> one is \"greater\".]\n>\n> ?\n\nI fail to see where this variant is simpler than what we started the\njourney of simplification from.\n\nThe only change I consider worth checking from the whole series in\nthis thread is making the function inline. All the rest pretty much\nwas worse than what we started from in that it needed to reevaluate\nmore conditions and turned out more complicated and obfuscate even to\nthe human reader.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"55059","messageId":"20071007161012.GB3270@steel.home","threadId":"9993","inReplyTo":"85fy0nknnq.fsf@lola.goethe.zz","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-07T16:10:12Z","receivedAt":"2007-10-07T16:10:12Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200:\n> Alex Riesen writes:\n> \n> > It is definitely less code (also object code). It is not always\n> > measurably faster (but mostly is).\n> \n> > -int strbuf_cmp(struct strbuf *a, struct strbuf *b)\n> > -{\n> > -\tint cmp;\n> > -\tif (a->len < b->len) {\n> > -\t\tcmp = memcmp(a->buf, b->buf, a->len);\n> > -\t\treturn cmp ? cmp : -1;\n> > -\t} else {\n> > -\t\tcmp = memcmp(a->buf, b->buf, b->len);\n> > -\t\treturn cmp ? cmp : a->len != b->len;\n> > -\t}\n> > -}\n> > -\n> \n> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > +{\n> > +\tint len = a->len < b->len ? a->len: b->len;\n> > +\tint cmp = memcmp(a->buf, b->buf, len);\n> > +\tif (cmp)\n> > +\t\treturn cmp;\n> > +\treturn a->len < b->len ? -1: a->len != b->len;\n> > +}\n> \n> My guess is that you are conflating two issues about speed here: the\n> inlining will like speed the stuff up. But having to evaluate the\n> (a->len < b->len) comparison twice will likely slow it down.\n\n\nCan't the result of the expression be reused in compiled?\nIsn't it a common expression?\n\n> So if you do any profiling, you should do it on both separate angles\n> of this patch.\n> \n\nI compared the inlined versions of both.\n"},{"id":"55060","messageId":"Pine.LNX.4.64.0710071710190.4174@racer.site","threadId":"9993","inReplyTo":"20071007143912.GB10024@artemis.corp","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-10-07T16:11:29Z","receivedAt":"2007-10-07T16:11:29Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 7 Oct 2007, Pierre Habouzit wrote:\n\n> On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:\n>\n> > strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> > \n> > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > {\n> > \tint len = a->len < b->len ? a->len : b->len;\n> > \treturn memcmp(a->buf, b->buf, len + 1);\n> > }\n> \n> doesn't work, because a buffer can have (in some very specific cases)\n> an embeded NUL.\n\nBut it should work. The function memcmp() could not care less if there is \na NUL or not, it just compares until it finds a difference.\n\nCiao,\nDscho\n"},{"id":"55061","messageId":"20071007191821.c872cc51.tihirvon@gmail.com","threadId":"9993","inReplyTo":"Pine.LNX.4.64.0710071710190.4174@racer.site","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Timo Hirvonen","fromEmail":"tihirvon@gmail.com","sentAt":"2007-10-07T16:18:21Z","receivedAt":"2007-10-07T16:18:21Z","isPatch":true,"sender":{"key":"tihirvon@gmail.com","avatar":null},"body":"Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Sun, 7 Oct 2007, Pierre Habouzit wrote:\n> \n> > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:\n> >\n> > > strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> > > \n> > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > > {\n> > > \tint len = a->len < b->len ? a->len : b->len;\n> > > \treturn memcmp(a->buf, b->buf, len + 1);\n> > > }\n> > \n> > doesn't work, because a buffer can have (in some very specific cases)\n> > an embeded NUL.\n> \n> But it should work. The function memcmp() could not care less if there is \n> a NUL or not, it just compares until it finds a difference.\n\nAlmost. If a is \"hello\\0world\" and b is \"hello\" then it would compare 6\ncharacters from both and think the strings are equal.\n"},{"id":"55062","messageId":"851wc6lwkc.fsf@lola.goethe.zz","threadId":"9993","inReplyTo":"20071007161012.GB3270@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-10-07T16:27:15Z","receivedAt":"2007-10-07T16:27:15Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Alex Riesen writes:\n\n> David Kastrup, Sun, Oct 07, 2007 16:24:57 +0200:\n>> Alex Riesen writes:\n>> \n>> > It is definitely less code (also object code). It is not always\n>> > measurably faster (but mostly is).\n>> \n>> > -int strbuf_cmp(struct strbuf *a, struct strbuf *b)\n>> > -{\n>> > -\tint cmp;\n>> > -\tif (a->len < b->len) {\n>> > -\t\tcmp = memcmp(a->buf, b->buf, a->len);\n>> > -\t\treturn cmp ? cmp : -1;\n>> > -\t} else {\n>> > -\t\tcmp = memcmp(a->buf, b->buf, b->len);\n>> > -\t\treturn cmp ? cmp : a->len != b->len;\n>> > -\t}\n>> > -}\n>> > -\n>> \n>> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n>> > +{\n>> > +\tint len = a->len < b->len ? a->len: b->len;\n>> > +\tint cmp = memcmp(a->buf, b->buf, len);\n>> > +\tif (cmp)\n>> > +\t\treturn cmp;\n>> > +\treturn a->len < b->len ? -1: a->len != b->len;\n>> > +}\n>> \n>> My guess is that you are conflating two issues about speed here: the\n>> inlining will like speed the stuff up. But having to evaluate the\n>> (a->len < b->len) comparison twice will likely slow it down.\n>\n> Can't the result of the expression be reused in compiled?\n> Isn't it a common expression?\n\nNo, since the call to memcmp might change a->len or b->len. A\nstandard-compliant C compiler can't make assumptions about what memcmp\nmight or might not touch unless both a and b can be shown to refer to\nvariables with an address never passed out of the scope of the\ncompilation unit.\n\n>> So if you do any profiling, you should do it on both separate\n>> angles of this patch.\n>\n> I compared the inlined versions of both.\n\nInteresting.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"55070","messageId":"20071007165424.GF10024@artemis.corp","threadId":"9993","inReplyTo":"Pine.LNX.4.64.0710071710190.4174@racer.site","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-07T16:54:24Z","receivedAt":"2007-10-07T16:54:24Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Sun, Oct 07, 2007 at 04:11:29PM +0000, Johannes Schindelin wrote:\n> Hi,\n> \n> On Sun, 7 Oct 2007, Pierre Habouzit wrote:\n> \n> > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:\n> >\n> > > strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> > > \n> > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > > {\n> > > \tint len = a->len < b->len ? a->len : b->len;\n> > > \treturn memcmp(a->buf, b->buf, len + 1);\n> > > }\n> > \n> > doesn't work, because a buffer can have (in some very specific cases)\n> > an embeded NUL.\n> \n> But it should work. The function memcmp() could not care less if there is \n> a NUL or not, it just compares until it finds a difference.\n\n not if your one of your strbuf has as prefix, the other followed by\n'\\0', then anything else (including nothing ;p).\n\n Your test would yield equality.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"55077","messageId":"Pine.LNX.4.64.0710071925120.4174@racer.site","threadId":"9993","inReplyTo":"20071007191821.c872cc51.tihirvon@gmail.com","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-10-07T18:25:24Z","receivedAt":"2007-10-07T18:25:24Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 7 Oct 2007, Timo Hirvonen wrote:\n\n> Johannes Schindelin wrote:\n> \n> > On Sun, 7 Oct 2007, Pierre Habouzit wrote:\n> > \n> > > On Sun, Oct 07, 2007 at 02:24:25PM +0000, Timo Hirvonen wrote:\n> > >\n> > > > strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> > > > \n> > > > static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> > > > {\n> > > > \tint len = a->len < b->len ? a->len : b->len;\n> > > > \treturn memcmp(a->buf, b->buf, len + 1);\n> > > > }\n> > > \n> > > doesn't work, because a buffer can have (in some very specific cases)\n> > > an embeded NUL.\n> > \n> > But it should work. The function memcmp() could not care less if there is \n> > a NUL or not, it just compares until it finds a difference.\n> \n> Almost. If a is \"hello\\0world\" and b is \"hello\" then it would compare 6\n> characters from both and think the strings are equal.\n\nGood point.\n\nCiao,\nDscho\n"},{"id":"55095","messageId":"20071007215432.GC2765@steel.home","threadId":"9993","inReplyTo":"857ilylxhm.fsf@lola.goethe.zz","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-07T21:54:32Z","receivedAt":"2007-10-07T21:54:32Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"David Kastrup, Sun, Oct 07, 2007 18:07:17 +0200:\n> Miles Bader writes:\n> \n> > Pierre Habouzit writes:\n> >>> strbuf->buf is always non-NULL and NUL-terminated so you could just do\n> >>> \n> >>> static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> >>> {\n> >>> \tint len = a->len < b->len ? a->len : b->len;\n> >>> \treturn memcmp(a->buf, b->buf, len + 1);\n> >>> }\n> >>\n> >> doesn't work, because a buffer can have (in some very specific cases)\n> >> an embeded NUL.\n> >\n> > Couldn't you then just do:\n> >\n> > int len = a->len < b->len ? a->len : b->len;\n> > int cmp = memcmp(a->buf, b->buf, len);\n> > if (cmp == 0)\n> > cmp = b->len - a->len;\n> > return cmp;\n> >\n> > [In the case where one string is a prefix of the other, then the longer\n> > one is \"greater\".]\n> >\n> > ?\n> \n> I fail to see where this variant is simpler than what we started the\n> journey of simplification from.\n> \n> The only change I consider worth checking from the whole series in\n> this thread is making the function inline. \n\nIt also makes arguments const (which admittedly wont make it faster).\n\n> ... All the rest pretty much\n> was worse than what we started from in that it needed to reevaluate\n> more conditions and turned out more complicated and obfuscate even to\n> the human reader.\n\nit _is_ smaller. And it is _measurably_ faster on that thing I have at\nhome (and old p4).\n"},{"id":"55096","messageId":"20071007215749.GD2765@steel.home","threadId":"9993","inReplyTo":"851wc6lwkc.fsf@lola.goethe.zz","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-07T21:57:49Z","receivedAt":"2007-10-07T21:57:49Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"David Kastrup, Sun, Oct 07, 2007 18:27:15 +0200:\n> Alex Riesen writes:\n> >> > +static inline int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)\n> >> > +{\n> >> > +\tint len = a->len < b->len ? a->len: b->len;\n> >> > +\tint cmp = memcmp(a->buf, b->buf, len);\n> >> > +\tif (cmp)\n> >> > +\t\treturn cmp;\n> >> > +\treturn a->len < b->len ? -1: a->len != b->len;\n> >> > +}\n> >> \n> >> My guess is that you are conflating two issues about speed here: the\n> >> inlining will like speed the stuff up. But having to evaluate the\n> >> (a->len < b->len) comparison twice will likely slow it down.\n> >\n> > Can't the result of the expression be reused in compiled?\n> > Isn't it a common expression?\n> \n> No, since the call to memcmp might change a->len or b->len. A\n\nHuh?! How's that? It is not even given them!\n"},{"id":"55099","messageId":"EF81F7DD-73C7-4B6F-92D2-4A143CA05365@wincent.com","threadId":"9993","inReplyTo":"20071007215432.GC2765@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Wincent Colaiuta","fromEmail":"win@wincent.com","sentAt":"2007-10-07T22:12:17Z","receivedAt":"2007-10-07T22:12:17Z","isPatch":true,"sender":{"key":"greg@hurrell.net","avatar":"https://avatars.githubusercontent.com/u/7074?v=4"},"body":"El 7/10/2007, a las 23:54, Alex Riesen escribió:\n\n>> ... All the rest pretty much\n>> was worse than what we started from in that it needed to reevaluate\n>> more conditions and turned out more complicated and obfuscate even to\n>> the human reader.\n>\n> it _is_ smaller. And it is _measurably_ faster on that thing I have at\n> home (and old p4).\n\nCan we see the numbers and the steps used to obtain them? I'm also a \nlittle bit confused about how an inlined function can lead to a \nsmaller executable... or did you just mean lines-of-code?\n\nCheers,\nWincent\n"},{"id":"55103","messageId":"20071007223140.GG2765@steel.home","threadId":"9993","inReplyTo":"EF81F7DD-73C7-4B6F-92D2-4A143CA05365@wincent.com","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-07T22:31:40Z","receivedAt":"2007-10-07T22:31:40Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Wincent Colaiuta, Mon, Oct 08, 2007 00:12:17 +0200:\n> El 7/10/2007, a las 23:54, Alex Riesen escribió:\n> \n> >>... All the rest pretty much\n> >>was worse than what we started from in that it needed to reevaluate\n> >>more conditions and turned out more complicated and obfuscate even to\n> >>the human reader.\n> >\n> >it _is_ smaller. And it is _measurably_ faster on that thing I have at\n> >home (and old p4).\n> \n> Can we see the numbers and the steps used to obtain them? I'm also a \n> little bit confused about how an inlined function can lead to a \n> smaller executable... or did you just mean lines-of-code?\n\nI did mean the bytes of object code. I never said it produces a\nsmaller executable.\n\nI compiled with gcc -O2 and -O4, gcc 4.1.2 (Ubuntu 4.1.2-0ubuntu4).\nCut the functions out into their own files and compile them to get the\nobject code. Compile with -S (assembly) to examine the generated code.\nCompare.\n\n#include \n#include \n#include \n#include \n#include \n#include \n\nstruct strbuf {\n\tsize_t alloc;\n\tsize_t len;\n\tchar *buf;\n};\n\nint strbuf_cmp2(struct strbuf *a, struct strbuf *b)\n{\n\tint len = a->len < b->len ? a->len: b->len;\n\tint cmp = memcmp(a->buf, b->buf, len);\n\tif (cmp)\n\t\treturn cmp;\n\treturn a->len < b->len ? -1: a->len != b->len;\n}\n\nint strbuf_cmp1(struct strbuf *a, struct strbuf *b)\n{\n\tint cmp;\n\tif (a->len < b->len) {\n\t\tcmp = memcmp(a->buf, b->buf, a->len);\n\t\treturn cmp ? cmp : -1;\n\t} else {\n\t\tcmp = memcmp(a->buf, b->buf, b->len);\n\t\treturn cmp ? cmp : a->len != b->len;\n\t}\n}\n\nint main(int argc, char *argv[], char *envp[])\n{\n\tstruct strbuf s1 = {\n\t\t.alloc = 0,\n\t\t.len = 50,\n\t\t.buf = \"01234567890123456789012345678901234567890123456789\",\n\t};\n\tstruct strbuf s2 = {\n\t\t.alloc = 0,\n\t\t.len = 50,\n\t\t.buf = \"0123456789012345678901234567890123456789\",\n\t};\n\tstruct strbuf s3 = {\n\t\t.alloc = 0,\n\t\t.len = 50,\n\t\t.buf = \"0123456789012345678901234567890123456789012345678x\",\n\t};\n\tstruct timeval tv1, tv2, diff;\n\tunsigned n;\n\tint result;\n#define CYCLES 0xffffffffu\n\n\tstrbuf_cmp1(&s1, &s2);\n\tstrbuf_cmp1(&s2, &s3);\n\tresult = 0;\n\tgettimeofday(&tv1, NULL);\n\tfor (n = CYCLES; n--; ) {\n\t\tresult += strbuf_cmp1(&s1, &s2);\n\t\tresult += strbuf_cmp1(&s2, &s3);\n\t\tresult += strbuf_cmp1(&s1, &s3);\n\t\tresult += strbuf_cmp1(&s1, &s1);\n\t\tresult += n;\n\t}\n\tgettimeofday(&tv2, NULL);\n\ttimersub(&tv2, &tv1, &diff);\n\tprintf(\"ph=%ld.%ld (%d)\\n\", diff.tv_sec, diff.tv_usec, result);\n\n\tstrbuf_cmp2(&s1, &s2);\n\tstrbuf_cmp2(&s2, &s3);\n\tresult = 0;\n\tgettimeofday(&tv1, NULL);\n\tfor (n = CYCLES; n--; ) {\n\t\tresult += strbuf_cmp2(&s1, &s2);\n\t\tresult += strbuf_cmp2(&s2, &s3);\n\t\tresult += strbuf_cmp2(&s1, &s3);\n\t\tresult += strbuf_cmp2(&s1, &s1);\n\t\tresult += n;\n\t}\n\tgettimeofday(&tv2, NULL);\n\ttimersub(&tv2, &tv1, &diff);\n\tprintf(\"ar=%ld.%ld (%d)\\n\", diff.tv_sec, diff.tv_usec, result);\n\treturn 0;\n}\n"},{"id":"55143","messageId":"87odfapefc.fsf@catnip.gol.com","threadId":"9993","inReplyTo":"20071007223140.GG2765@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Miles Bader","fromEmail":"miles@gnu.org","sentAt":"2007-10-08T01:45:27Z","receivedAt":"2007-10-08T01:45:27Z","isPatch":true,"sender":{"key":"miles@gnu.org","avatar":"https://gravatar.com/avatar/01069b69593af7bff28e2f97afeb3644ae6fe2f5f56cb3a8cf34c5fb8c36efe5?d=mp&s=160"},"body":"Alex Riesen writes:\n> int strbuf_cmp2(struct strbuf *a, struct strbuf *b)\n> {\n> \tint len = a->len < b->len ? a->len: b->len;\n> \tint cmp = memcmp(a->buf, b->buf, len);\n> \tif (cmp)\n> \t\treturn cmp;\n> \treturn a->len < b->len ? -1: a->len != b->len;\n> }\n\nBTW, why are you making such effort to return only -1, 0, or 1 in the\nlast line? memcmp/strcmp make no such guarantee; e.g. glibc says:\n\n The `strcmp' function compares the string S1 against S2, returning\n a value that has the same sign as the difference between the first\n differing pair of characters (interpreted as `unsigned char'\n objects, then promoted to `int').\n\n If the two strings are equal, `strcmp' returns `0'.\n\n A consequence of the ordering used by `strcmp' is that if S1 is an\n initial substring of S2, then S1 is considered to be \"less than\"\n S2.\n\nSo I think the last line can just be:\n\n return a->len - b->len;\n\n-miles\n\n-- \nSuburbia: where they tear out the trees and then name streets after them.\n"},{"id":"55147","messageId":"20071008021945.GC20050@coredump.intra.peff.net","threadId":"9993","inReplyTo":"20071007215749.GD2765@steel.home","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-08T02:19:45Z","receivedAt":"2007-10-08T02:19:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 07, 2007 at 11:57:49PM +0200, Alex Riesen wrote:\n\n> > > Can't the result of the expression be reused in compiled?\n> > > Isn't it a common expression?\n> > \n> > No, since the call to memcmp might change a->len or b->len. A\n> \n> Huh?! How's that? It is not even given them!\n\nBut they are non-local variables (they are part of structs passed in as\npointers), so that translation unit has no idea how they are allocated.\nThey could be globals that memcmp mucks with as a side effect.\n\nThat being said, standards-conforming compilers _can_ realize that\nmemcmp is a special, standards-defined function with no side effects and\nact accordingly. gcc provides the 'pure' function attribute for this\npurpose, which is used by glibc.\n\n-Peff\n"},{"id":"55166","messageId":"20071008072312.GA22552@artemis.corp","threadId":"9993","inReplyTo":"87odfapefc.fsf@catnip.gol.com","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-10-08T07:23:12Z","receivedAt":"2007-10-08T07:23:12Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Mon, Oct 08, 2007 at 01:45:27AM +0000, Miles Bader wrote:\n> Alex Riesen writes:\n> > int strbuf_cmp2(struct strbuf *a, struct strbuf *b)\n> > {\n> > \tint len = a->len < b->len ? a->len: b->len;\n> > \tint cmp = memcmp(a->buf, b->buf, len);\n> > \tif (cmp)\n> > \t\treturn cmp;\n> > \treturn a->len < b->len ? -1: a->len != b->len;\n> > }\n> \n> BTW, why are you making such effort to return only -1, 0, or 1 in the\n> last line? memcmp/strcmp make no such guarantee; e.g. glibc says:\n> \n> The `strcmp' function compares the string S1 against S2, returning\n> a value that has the same sign as the difference between the first\n> differing pair of characters (interpreted as `unsigned char'\n> objects, then promoted to `int').\n> \n> If the two strings are equal, `strcmp' returns `0'.\n> \n> A consequence of the ordering used by `strcmp' is that if S1 is an\n> initial substring of S2, then S1 is considered to be \"less than\"\n> S2.\n> \n> So I think the last line can just be:\n> \n> return a->len - b->len;\n\n Won't work because ->len are size_t and return value is int, so on 64\nbits platform, this has chances to overflow.\n\n FWIW I believe we are doing micro-benchs in a function that is used in\n2 places in git right now.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"55168","messageId":"82k5py6l6f.fsf@mid.bfk.de","threadId":"9993","inReplyTo":"20071008072312.GA22552@artemis.corp","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Florian Weimer","fromEmail":"fweimer@bfk.de","sentAt":"2007-10-08T08:54:32Z","receivedAt":"2007-10-08T08:54:32Z","isPatch":true,"sender":{"key":"fweimer@bfk.de","avatar":null},"body":"* Pierre Habouzit:\n\n>> So I think the last line can just be:\n>> \n>> return a->len - b->len;\n>\n> Won't work because ->len are size_t and return value is int, so on 64\n> bits platform, this has chances to overflow.\n\nNit: It can overflow on 32-bit, too.\n\nAnd \"int len\" in the first line of the function body should be\n\"size_t len\".\n\nMoving that to a compare_int/compare_size_t function should help;\nAFAIK there's no short idiom which does the job.\n\n-- \nFlorian Weimer \nBFK edv-consulting GmbH http://www.bfk.de/\nKriegsstraße 100 tel: +49-721-96201-1\nD-76133 Karlsruhe fax: +49-721-96201-99\n"},{"id":"55201","messageId":"20071008185111.GC3123@steel.home","threadId":"9993","inReplyTo":"82k5py6l6f.fsf@mid.bfk.de","subject":"Re: [PATCH] Make strbuf_cmp inline, constify its arguments and optimize it a bit","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-08T18:51:11Z","receivedAt":"2007-10-08T18:51:11Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Florian Weimer, Mon, Oct 08, 2007 10:54:32 +0200:\n> And \"int len\" in the first line of the function body should be\n> \"size_t len\".\n\nright. Missed that.\n"}]}