{"thread":{"id":"35797","subject":"[PATCH] blame.c: prepare_lines should not call xrealloc for every line","startedAt":"2014-02-04T20:06:07Z","lastAt":"2014-02-06T10:29:16Z","messageCount":23,"participants":["David Kastrup","Junio C Hamano","Philip Oakley"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"234220","messageId":"1391544367-14599-1-git-send-email-dak@gnu.org","threadId":"35797","inReplyTo":null,"subject":"[PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T20:06:07Z","receivedAt":"2014-02-04T20:06:07Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Making a single preparation run for counting the lines will avoid memory\nfragmentation. Also, fix the allocated memory size which was wrong\nwhen sizeof(int *) != sizeof(int), and would have been too small\nfor sizeof(int *) < sizeof(int), admittedly unlikely.\n\nSigned-off-by: David Kastrup \n---\n builtin/blame.c | 40 ++++++++++++++++++++++++----------------\n 1 file changed, 24 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex e44a6bb..522986d 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1772,25 +1772,33 @@ static int prepare_lines(struct scoreboard *sb)\n {\n \tconst char *buf = sb->final_buf;\n \tunsigned long len = sb->final_buf_size;\n-\tint num = 0, incomplete = 0, bol = 1;\n+\tconst char *end = buf + len;\n+\tconst char *p;\n+\tint *lineno;\n+\t\n+\tint num = 0, incomplete = 0;\n+\n+\tfor (p = buf;;) {\n+\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n+\t\t\tbreak;\n+\t\t++num, ++p;\n+\t}\n \n-\tif (len && buf[len-1] != '\\n')\n+\tif (len && end[-1] != '\\n')\n \t\tincomplete++; /* incomplete line at the end */\n-\twhile (len--) {\n-\t\tif (bol) {\n-\t\t\tsb->lineno = xrealloc(sb->lineno,\n-\t\t\t\t\t sizeof(int *) * (num + 1));\n-\t\t\tsb->lineno[num] = buf - sb->final_buf;\n-\t\t\tbol = 0;\n-\t\t}\n-\t\tif (*buf++ == '\\n') {\n-\t\t\tnum++;\n-\t\t\tbol = 1;\n-\t\t}\n+\n+\tsb->lineno = lineno = xmalloc(sizeof(int) * (num + incomplete + 1));\n+\n+\tfor (p = buf;;) {\n+\t\t*lineno++ = p-buf;\n+\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n+\t\t\tbreak;\n+\t\t++p;\n \t}\n-\tsb->lineno = xrealloc(sb->lineno,\n-\t\t\t sizeof(int *) * (num + incomplete + 1));\n-\tsb->lineno[num + incomplete] = buf - sb->final_buf;\n+\n+\tif (incomplete)\n+\t\t*lineno++ = len;\n+\n \tsb->num_lines = num + incomplete;\n \treturn sb->num_lines;\n }\n-- \n1.8.3.2\n"},{"id":"234221","messageId":"87lhxqwse8.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"1391544367-14599-1-git-send-email-dak@gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T20:10:39Z","receivedAt":"2014-02-04T20:10:39Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nWhitespace error in line 1778. Should I be reposting?\n\n-- \nDavid Kastrup\n"},{"id":"234224","messageId":"xmqqd2j28w3h.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"1391544367-14599-1-git-send-email-dak@gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T20:24:34Z","receivedAt":"2014-02-04T20:24:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Making a single preparation run for counting the lines will avoid memory\n> fragmentation. Also, fix the allocated memory size which was wrong\n> when sizeof(int *) != sizeof(int), and would have been too small\n> for sizeof(int *) < sizeof(int), admittedly unlikely.\n>\n> Signed-off-by: David Kastrup \n> ---\n> builtin/blame.c | 40 ++++++++++++++++++++++++----------------\n> 1 file changed, 24 insertions(+), 16 deletions(-)\n>\n> diff --git a/builtin/blame.c b/builtin/blame.c\n> index e44a6bb..522986d 100644\n> --- a/builtin/blame.c\n> +++ b/builtin/blame.c\n> @@ -1772,25 +1772,33 @@ static int prepare_lines(struct scoreboard *sb)\n> {\n> \tconst char *buf = sb->final_buf;\n> \tunsigned long len = sb->final_buf_size;\n> -\tint num = 0, incomplete = 0, bol = 1;\n> +\tconst char *end = buf + len;\n> +\tconst char *p;\n> +\tint *lineno;\n> +\t\n> +\tint num = 0, incomplete = 0;\n\nIs there any significance to the blank line between these two\nvariable definitions?\n\n> +\n> +\tfor (p = buf;;) {\n> +\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n> +\t\t\tbreak;\n> +\t\t++num, ++p;\n\nYou have a peculiar style that is somewhat distracting. Why isn't\nthis more like so?\n\n\tfor (p = buf; p++, num++; ) {\n\t\tp = memchr(p, '\\n', end - p);\n\t\tif (!p)\n\t\t\tbreak;\n\t}\n\nwhich I think is the prevalent style in our codebase. The same for\nthe other loop we see in the new code below.\n\n - favor post-increment unless you use it as rvalue and need\n pre-increment;\n\n - SP around each binary ops e.g. 'end - p';\n\n - avoid assignments in conditionals when you do not have to.\n\n> +\t}\n> \n> -\tif (len && buf[len-1] != '\\n')\n> +\tif (len && end[-1] != '\\n')\n> \t\tincomplete++; /* incomplete line at the end */\n\nOK, so far we counted \"num\" complete lines and \"incomplete\" may be\none if there is an incomplete line after them.\n\n> -\twhile (len--) {\n> -\t\tif (bol) {\n> -\t\t\tsb->lineno = xrealloc(sb->lineno,\n> -\t\t\t\t\t sizeof(int *) * (num + 1));\n> -\t\t\tsb->lineno[num] = buf - sb->final_buf;\n> -\t\t\tbol = 0;\n> -\t\t}\n> -\t\tif (*buf++ == '\\n') {\n> -\t\t\tnum++;\n> -\t\t\tbol = 1;\n> -\t\t}\n> +\n> +\tsb->lineno = lineno = xmalloc(sizeof(int) * (num + incomplete + 1));\n\nOK, this function is called only once, so we know sb->lineno is NULL\noriginally and there is no reason to start from xrealloc().\n\n> +\tfor (p = buf;;) {\n> +\t\t*lineno++ = p-buf;\n> +\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n> +\t\t\tbreak;\n> +\t\t++p;\n> \t}\n> -\tsb->lineno = xrealloc(sb->lineno,\n> -\t\t\t sizeof(int *) * (num + incomplete + 1));\n\nThese really *were* unnecessary reallocations.\n\nThanks for catching them, but this patch needs heavy style fixes.\n\n> -\tsb->lineno[num + incomplete] = buf - sb->final_buf;\n> +\n> +\tif (incomplete)\n> +\t\t*lineno++ = len;\n> +\n> \tsb->num_lines = num + incomplete;\n> \treturn sb->num_lines;\n> }\n"},{"id":"234225","messageId":"xmqq8utq8uxn.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"87lhxqwse8.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T20:49:40Z","receivedAt":"2014-02-04T20:49:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Whitespace error in line 1778. Should I be reposting?\n\nHeh, let me try to clean it up first and then repost for your\nreview.\n\nThanks.\n"},{"id":"234226","messageId":"87ha8ewqfv.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqd2j28w3h.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T20:52:52Z","receivedAt":"2014-02-04T20:52:52Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Making a single preparation run for counting the lines will avoid memory\n>> fragmentation. Also, fix the allocated memory size which was wrong\n>> when sizeof(int *) != sizeof(int), and would have been too small\n>> for sizeof(int *) < sizeof(int), admittedly unlikely.\n>>\n>> Signed-off-by: David Kastrup \n>> ---\n>> builtin/blame.c | 40 ++++++++++++++++++++++++----------------\n>> 1 file changed, 24 insertions(+), 16 deletions(-)\n>>\n>> diff --git a/builtin/blame.c b/builtin/blame.c\n>> index e44a6bb..522986d 100644\n>> --- a/builtin/blame.c\n>> +++ b/builtin/blame.c\n>> @@ -1772,25 +1772,33 @@ static int prepare_lines(struct scoreboard *sb)\n>> {\n>> \tconst char *buf = sb->final_buf;\n>> \tunsigned long len = sb->final_buf_size;\n>> -\tint num = 0, incomplete = 0, bol = 1;\n>> +\tconst char *end = buf + len;\n>> +\tconst char *p;\n>> +\tint *lineno;\n>> +\t\n>> +\tint num = 0, incomplete = 0;\n>\n> Is there any significance to the blank line between these two\n> variable definitions?\n\nWell, I needed more than the whitespace error to be motivated for\nredoing. Cough, cough.\n\n>> +\n>> +\tfor (p = buf;;) {\n>> +\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n>> +\t\t\tbreak;\n>> +\t\t++num, ++p;\n>\n> You have a peculiar style that is somewhat distracting. Why isn't\n> this more like so?\n>\n> \tfor (p = buf; p++, num++; ) {\n\nMore likely\n\tfor (p = buf;; p++, num++)\n \n> \t\tp = memchr(p, '\\n', end - p);\n> \t\tif (!p)\n> \t\t\tbreak;\n> \t}\n>\n> which I think is the prevalent style in our codebase. The same for\n> the other loop we see in the new code below.\n\nI rearranged a few times in order to have both loops be closely\nanalogous. The second loop would then have to be\n\n for (p = buf;; p++) {\n *lineno++ = p-buf;\n p = memchr(p, '\\n', end-p)\n if (!p)\n break;\n }\n\nAdmittedly, that works. I am not too happy about the termination\ncondition being at the end of the loop but not in the for statement, but\nyes, this seems somewhat nicer than what I proposed.\n\n> - favor post-increment unless you use it as rvalue and need\n> pre-increment;\n\nIn my youth, the very non-optimizing C compiler I used under CP/M\nproduced less efficient code for x++ than for ++x even when not using\nthe resulting expression. Surprisingly habit-forming.\n\n>\n> - SP around each binary ops e.g. 'end - p';\n\nOk.\n\n>> +\t}\n>> \n>> -\tif (len && buf[len-1] != '\\n')\n>> +\tif (len && end[-1] != '\\n')\n>> \t\tincomplete++; /* incomplete line at the end */\n>\n> OK, so far we counted \"num\" complete lines and \"incomplete\" may be\n> one if there is an incomplete line after them.\n\nThat's pretty much the gist of the original code.\n\n>> -\twhile (len--) {\n>> -\t\tif (bol) {\n>> -\t\t\tsb->lineno = xrealloc(sb->lineno,\n>> -\t\t\t\t\t sizeof(int *) * (num + 1));\n>> -\t\t\tsb->lineno[num] = buf - sb->final_buf;\n>> -\t\t\tbol = 0;\n>> -\t\t}\n>> -\t\tif (*buf++ == '\\n') {\n>> -\t\t\tnum++;\n>> -\t\t\tbol = 1;\n>> -\t\t}\n>> +\n>> +\tsb->lineno = lineno = xmalloc(sizeof(int) * (num + incomplete + 1));\n>\n> OK, this function is called only once, so we know sb->lineno is NULL\n> originally and there is no reason to start from xrealloc().\n\n[...]\n\n> These really *were* unnecessary reallocations.\n\nWell, if a realloc will increase the allocation size by a constant\nfactor each time, the amortization cost is O(n) for n entries. So with\na suitable realloc, the effect will not really be noticeable. It still\noffends my sense of aesthetics.\n\n> Thanks for catching them, but this patch needs heavy style fixes.\n\nWell, does not look all that heavy, but I'll repost.\n\nThere is another oversight: I am using memchr here, but there is no\nobvious header file definiting it (the respective header will likely be\npulled in indirectly via something unrelated).\n\nAnybody know offhand what I should be including here? It looks like Git\nhas some fallback definitions of its own, so it's probably not just\n I should include?\n\n-- \nDavid Kastrup\n"},{"id":"234227","messageId":"xmqq4n4e8uf1.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"xmqq8utq8uxn.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T21:00:50Z","receivedAt":"2014-02-04T21:00:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Whitespace error in line 1778. Should I be reposting?\n>\n> Heh, let me try to clean it up first and then repost for your\n> review.\n>\n> Thanks.\n\n-- >8 --\nFrom: David Kastrup \n\nMaking a single preparation run for counting the lines will avoid memory\nfragmentation. Also, fix the allocated memory size which was wrong\nwhen sizeof(int *) != sizeof(int), and would have been too small\nfor sizeof(int *) < sizeof(int), admittedly unlikely.\n\nSigned-off-by: David Kastrup \n---\n\n One logic difference from what was posted is that sb->lineno[num]\n is filled with the length of the entire buffer when the file ends\n with a complete line. I do not remember if the rest of the logic\n actually depends on it (I think I use lineno[n+1] - lineno[n] to\n find the end of line, so this may matter for the last line),\n though.\n\n The original code dates back to 2006 when the author of the code\n was not paid for doing anything for Git but was doing it as a\n weekend and evening hobby, so it may not be so surprising to find\n this kind of \"what was I thinking when I wrote it\" inefficiency in\n such a code with $0 monetary value ;-)\n\n builtin/blame.c | 37 +++++++++++++++++++++----------------\n 1 file changed, 21 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex e44a6bb..2364661 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1772,25 +1772,30 @@ static int prepare_lines(struct scoreboard *sb)\n {\n \tconst char *buf = sb->final_buf;\n \tunsigned long len = sb->final_buf_size;\n-\tint num = 0, incomplete = 0, bol = 1;\n+\tconst char *end = buf + len;\n+\tconst char *p;\n+\tint *lineno;\n+\tint num = 0, incomplete = 0;\n+\n+\tfor (p = buf; p < end; p++) {\n+\t\tp = memchr(p, '\\n', end - p);\n+\t\tif (!p)\n+\t\t\tbreak;\n+\t\tnum++;\n+\t}\n \n-\tif (len && buf[len-1] != '\\n')\n+\tif (len && end[-1] != '\\n')\n \t\tincomplete++; /* incomplete line at the end */\n-\twhile (len--) {\n-\t\tif (bol) {\n-\t\t\tsb->lineno = xrealloc(sb->lineno,\n-\t\t\t\t\t sizeof(int *) * (num + 1));\n-\t\t\tsb->lineno[num] = buf - sb->final_buf;\n-\t\t\tbol = 0;\n-\t\t}\n-\t\tif (*buf++ == '\\n') {\n-\t\t\tnum++;\n-\t\t\tbol = 1;\n-\t\t}\n+\n+\tsb->lineno = lineno = xmalloc(sizeof(int) * (num + incomplete + 1));\n+\n+\tfor (p = buf; p < end; p++) {\n+\t\t*lineno++ = p - buf;\n+\t\tp = memchr(p, '\\n', end - p);\n+\t\tif (!p)\n+\t\t\tbreak;\n \t}\n-\tsb->lineno = xrealloc(sb->lineno,\n-\t\t\t sizeof(int *) * (num + incomplete + 1));\n-\tsb->lineno[num + incomplete] = buf - sb->final_buf;\n+\tsb->lineno[num + incomplete] = len;\n \tsb->num_lines = num + incomplete;\n \treturn sb->num_lines;\n }\n"},{"id":"234228","messageId":"xmqqzjm67fpu.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"87ha8ewqfv.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T21:03:41Z","receivedAt":"2014-02-04T21:03:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Anybody know offhand what I should be including here? It looks like Git\n> has some fallback definitions of its own, so it's probably not just\n> I should include?\n\nIn general, no *.c files outside the compatibility layer should\ninclude anything \"#include \", as there seem to be\nfinicky systems that care about order of inclusion and feature macro\ndefinitions, all of which are meant to be handled by including\ngit-compat-util.h as the very first thing.\n"},{"id":"234231","messageId":"87d2j2wpnr.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqq4n4e8uf1.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T21:09:44Z","receivedAt":"2014-02-04T21:09:44Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> Junio C Hamano writes:\n>\n>> David Kastrup writes:\n>>\n>>> Whitespace error in line 1778. Should I be reposting?\n>>\n>> Heh, let me try to clean it up first and then repost for your\n>> review.\n>>\n>> Thanks.\n>\n> -- >8 --\n> From: David Kastrup \n>\n> Making a single preparation run for counting the lines will avoid memory\n> fragmentation. Also, fix the allocated memory size which was wrong\n> when sizeof(int *) != sizeof(int), and would have been too small\n> for sizeof(int *) < sizeof(int), admittedly unlikely.\n>\n> Signed-off-by: David Kastrup \n> ---\n>\n> One logic difference from what was posted is that sb->lineno[num]\n> is filled with the length of the entire buffer when the file ends\n> with a complete line.\n\nWhere's the difference? This is exactly what will happen with my code\nas well. I _do_ rely on memchr(whatever, '\\n', 0) to return NULL\nwithout looking at any memory for that. If there is a fear of memchr\nnot being able to deal with a count of 0, this code needs to be somewhat\nmore complex.\n\n> I do not remember if the rest of the logic\n> actually depends on it (I think I use lineno[n+1] - lineno[n] to\n> find the end of line,\n\nWell, you do it about _half_ the time. The other half, you scan for the\n'\\n' explicitly.\n\n> The original code dates back to 2006 when the author of the code\n> was not paid for doing anything for Git but was doing it as a\n> weekend and evening hobby, so it may not be so surprising to find\n> this kind of \"what was I thinking when I wrote it\" inefficiency in\n> such a code with $0 monetary value ;-)\n\nOh, _this_ patch is not in the \"I want to make money from it\" range. If\nthat were the case, I should not have bothered at all. This is just the\n\"this code offends my sense of aesthetics\" class. It's purely optional\nto apply. It's conceivable that it will make a performance difference\non non-glibc (or what it's called) platforms.\n\n-- \nDavid Kastrup\n"},{"id":"234230","messageId":"878utqwpkx.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqzjm67fpu.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T21:11:26Z","receivedAt":"2014-02-04T21:11:26Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Anybody know offhand what I should be including here? It looks like Git\n>> has some fallback definitions of its own, so it's probably not just\n>> I should include?\n>\n> In general, no *.c files outside the compatibility layer should\n> include anything \"#include \", as there seem to be\n> finicky systems that care about order of inclusion and feature macro\n> definitions, all of which are meant to be handled by including\n> git-compat-util.h as the very first thing.\n\nOk, and that one's not yet in blame.c. Will include, thanks.\n\n-- \nDavid Kastrup\n"},{"id":"234232","messageId":"874n4ewouz.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqd2j28w3h.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T21:27:00Z","receivedAt":"2014-02-04T21:27:00Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Making a single preparation run for counting the lines will avoid memory\n>> fragmentation. Also, fix the allocated memory size which was wrong\n>> when sizeof(int *) != sizeof(int), and would have been too small\n>> for sizeof(int *) < sizeof(int), admittedly unlikely.\n>>\n>> Signed-off-by: David Kastrup \n>> ---\n>> builtin/blame.c | 40 ++++++++++++++++++++++++----------------\n>> 1 file changed, 24 insertions(+), 16 deletions(-)\n>>\n>> diff --git a/builtin/blame.c b/builtin/blame.c\n>> index e44a6bb..522986d 100644\n>> --- a/builtin/blame.c\n>> +++ b/builtin/blame.c\n>> @@ -1772,25 +1772,33 @@ static int prepare_lines(struct scoreboard *sb)\n>> {\n>> \tconst char *buf = sb->final_buf;\n>> \tunsigned long len = sb->final_buf_size;\n>> -\tint num = 0, incomplete = 0, bol = 1;\n>> +\tconst char *end = buf + len;\n>> +\tconst char *p;\n>> +\tint *lineno;\n>> +\t\n>> +\tint num = 0, incomplete = 0;\n>\n> Is there any significance to the blank line between these two\n> variable definitions?\n>\n>> +\n>> +\tfor (p = buf;;) {\n>> +\t\tif ((p = memchr(p, '\\n', end-p)) == NULL)\n>> +\t\t\tbreak;\n>> +\t\t++num, ++p;\n>\n> You have a peculiar style that is somewhat distracting. Why isn't\n> this more like so?\n>\n> \tfor (p = buf; p++, num++; ) {\n> \t\tp = memchr(p, '\\n', end - p);\n> \t\tif (!p)\n> \t\t\tbreak;\n> \t}\n\nOk, I now wrote\n\n\tfor (p = buf;; num++, p++) {\n\t\tp = memchr(p, '\\n', end - p);\n\t\tif (!p)\n\t\t\tbreak;\n\t}\n\nand you know what? Its logic seems wrong. The reason is that the p++\ndoes not really have anything to do with the iteration, but rather steps\npast the '\\n' from the memchr. So it's more like\n\n\tfor (p = buf;; num++) {\n\t\tp = memchr(p, '\\n', end - p);\n\t\tif (p) {\n\t\t\tp++;\n continue;\n }\n\t\tbreak;\n\t}\n\nSo barring protests, that's what I'm going to use instead.\n\n-- \nDavid Kastrup\n"},{"id":"234234","messageId":"xmqqvbwu7dya.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"878utqwpkx.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T21:41:49Z","receivedAt":"2014-02-04T21:41:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Junio C Hamano writes:\n>\n>> David Kastrup writes:\n>>\n>>> Anybody know offhand what I should be including here? It looks like Git\n>>> has some fallback definitions of its own, so it's probably not just\n>>> I should include?\n>>\n>> In general, no *.c files outside the compatibility layer should\n>> include anything \"#include \", as there seem to be\n>> finicky systems that care about order of inclusion and feature macro\n>> definitions, all of which are meant to be handled by including\n>> git-compat-util.h as the very first thing.\n>\n> Ok, and that one's not yet in blame.c. Will include, thanks.\n\nNo, don't. Some well-known *.h files of ourse, most notably\ncache.h, are known to include compat-util as the first thing, and\nthat is what *.c files typically include.\n"},{"id":"234235","messageId":"xmqqr47i7dt4.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"874n4ewouz.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T21:44:55Z","receivedAt":"2014-02-04T21:44:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Ok, I now wrote\n>\n> \tfor (p = buf;; num++, p++) {\n> \t\tp = memchr(p, '\\n', end - p);\n> \t\tif (!p)\n> \t\t\tbreak;\n> \t}\n\nLooks still wrong (perhaps this is a taste issue).\n\n\tnum++ is not \"loop control\", but the real action of this\n\tloop to count lines. It is better left inside.\n\n\tp++ is \"loop control\", and belongs to the third part of\n\tfor(;;).\n\n\tIsn't the normal continuation condition \"p < end\"?\n\nso something like\n\n\tfor (p = buf; p < end; p++) {\n \tp = find the end of this line\n if (!p)\n \tbreak;\n\t\tnum++;\n\t}\n\nperhaps?\n"},{"id":"234237","messageId":"87zjm6v99y.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqr47i7dt4.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-04T21:48:57Z","receivedAt":"2014-02-04T21:48:57Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Ok, I now wrote\n>>\n>> \tfor (p = buf;; num++, p++) {\n>> \t\tp = memchr(p, '\\n', end - p);\n>> \t\tif (!p)\n>> \t\t\tbreak;\n>> \t}\n>\n> Looks still wrong (perhaps this is a taste issue).\n>\n> \tnum++ is not \"loop control\", but the real action of this\n> \tloop to count lines. It is better left inside.\n\nOk.\n\n> \tp++ is \"loop control\", and belongs to the third part of\n> \tfor(;;).\n\nNo, it isn't. The \"real\" loop control is the p = memchr line. p++ only\nskips over the newline.\n\n> \tIsn't the normal continuation condition \"p < end\"?\n\nmemchr returns NULL when not finding anything any more.\n\n> so something like\n>\n> \tfor (p = buf; p < end; p++) {\n> \tp = find the end of this line\n> if (!p)\n> \tbreak;\n> \t\tnum++;\n> \t}\n>\n> perhaps?\n\nWould crash on incomplete last line.\n\n-- \nDavid Kastrup\n"},{"id":"234238","messageId":"xmqqmwi67cty.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"87zjm6v99y.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T22:06:01Z","receivedAt":"2014-02-04T22:06:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n>> so something like\n>>\n>> \tfor (p = buf; p < end; p++) {\n>> \tp = find the end of this line\n>> if (!p)\n>> \tbreak;\n>> \t\tnum++;\n>> \t}\n>>\n>> perhaps?\n>\n> Would crash on incomplete last line.\n\nHmph, even with \"if !p\"? From your other message:\n\n+\tfor (p = buf;; num++) {\n+\t\tp = memchr(p, '\\n', end - p);\n+\t\tif (p) {\n+\t\t\tp++;\n+\t\t\tcontinue;\n \t\t}\n+\t\tbreak;\n+\t}\n\nIf you flip the if statement around that would be the same as:\n\n+\tfor (p = buf;; num++) {\n+\t\tp = memchr(p, '\\n', end - p);\n+\t\tif (!p)\n\t\t\tbreak;\n\t\tp++;\n+\t}\n\nAnd with \"loop action not in the control part\", that would be the\nsame as:\n\n\tfor (p = buf; ; p++) {\n\t\tp = memchr...\n if (!p)\n \tbreak;\n\t\tnum++;\n\t}\n\nno? Would this crash on incomplete last line?\n\nAhh, \"p < end\" in \"for (p = buf; p < end; p++) {\" is not correct;\nyou depend on overrunning the end of the buffer to feed length 0 to\nmemchr and returning NULL inside the loop. So to be equivalent to\nyour version, the contination condition needs to be\n\n\tfor (p = buf; p <= end; p++) {\n\nBut that last round of the loop will be no-op, so \"p < end\" vs \"p <=\nend\" does not make any difference. It is not even strictly\nnecessary because memchr() limits the scan to end, but it would\nstill be a good belt-and-suspenders defensive coding practice, I\nwould think.\n\n+\tfor (p = buf;;) {\n+\t\t*lineno++ = p - buf;\n+\t\tp = memchr(p, '\\n', end - p);\n+\t\tif (p) {\n+\t\t\tp++;\n+\t\t\tcontinue;\n \t\t}\n+\t\tbreak;\n \t}\n\nCan we do the same transformation here?\n\n\tfor (p = buf;;) {\n \t*lineno++ = p - buf;\n p = memchr...\n if (!p)\n \tbreak;\n\t\tp++;\n\t}\n\nwhich is the same as\n\n\tfor (p = buf; ; p++) {\n \t*lineno++ = p - buf;\n p = memchr...\n if (!p)\n \tbreak;\n\t}\n\nand the latter has the loop control p++ at where it belongs to. The\npost-condition of one iteration of the body of the loop being \"p\npoints at the terminating LF of this line\", incrementing the pointer\nis how the loop control advances the pointer to the beginning of the\nnext line.\n\nIf we wanted to have a belt-and-suspenders safety, we need \"p <=\nend\" here, not \"p < end\", because of how p is used when it is past\nthe last LF. As we want to make these two loops look similar, that\nmeans we should use \"p <= end\" in the previous loop as well.\n\nThis was fun ;-)\n"},{"id":"234253","messageId":"79CA69ED4EBA4271A40DE714AEEA5424@PhilipOakley","threadId":"35797","inReplyTo":"87d2j2wpnr.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2014-02-04T22:25:25Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"David Kastrup\" \nTo: \"Junio C Hamano\" \nCc: \nSent: Tuesday, February 04, 2014 9:09 PM\nSubject: Re: [PATCH] blame.c: prepare_lines should not call xrealloc for \nevery line\n\n\n> Junio C Hamano writes:\n>\n>> Junio C Hamano writes:\n>>\n>>> David Kastrup writes:\n>>>\n>>>> Whitespace error in line 1778. Should I be reposting?\n>>>\n>>> Heh, let me try to clean it up first and then repost for your\n>>> review.\n>>>\n>>> Thanks.\n>>\n>> -- >8 --\n>> From: David Kastrup \n>>\n>> Making a single preparation run for counting the lines will avoid \n>> memory\n>> fragmentation. Also, fix the allocated memory size which was wrong\n>> when sizeof(int *) != sizeof(int), and would have been too small\n>> for sizeof(int *) < sizeof(int), admittedly unlikely.\n>>\n>> Signed-off-by: David Kastrup \n>> ---\n>>\n>> One logic difference from what was posted is that sb->lineno[num]\n>> is filled with the length of the entire buffer when the file ends\n>> with a complete line.\n>\n> Where's the difference? This is exactly what will happen with my code\n> as well. I _do_ rely on memchr(whatever, '\\n', 0) to return NULL\n> without looking at any memory for that. If there is a fear of memchr\n> not being able to deal with a count of 0, this code needs to be \n> somewhat\n> more complex.\n\nA bit of googling found http://marc.info/?l=gnulib-bug&m=130108029329021 \nwhich suggests that behaviour can't be relied upon, and that perhaps \nsome code is 'buggy' relative to expectations (hence the patch it \nproposed).\n\nIt suggests that one can't properly reference a zero length object.\n\n>\n>> I do not remember if the rest of the logic\n>> actually depends on it (I think I use lineno[n+1] - lineno[n] to\n>> find the end of line,\n>\n> Well, you do it about _half_ the time. The other half, you scan for \n> the\n> '\\n' explicitly.\n>\n>> The original code dates back to 2006 when the author of the code\n>> was not paid for doing anything for Git but was doing it as a\n>> weekend and evening hobby, so it may not be so surprising to find\n>> this kind of \"what was I thinking when I wrote it\" inefficiency in\n>> such a code with $0 monetary value ;-)\n>\n> Oh, _this_ patch is not in the \"I want to make money from it\" range. \n> If\n> that were the case, I should not have bothered at all. This is just \n> the\n> \"this code offends my sense of aesthetics\" class. It's purely \n> optional\n> to apply. It's conceivable that it will make a performance difference\n> on non-glibc (or what it's called) platforms.\n>\n> -- \n> David Kastrup\n> --\n\nPhilip \n"},{"id":"234255","messageId":"303363DDF4184D37A3D5A52147EE728B@PhilipOakley","threadId":"35797","inReplyTo":"79CA69ED4EBA4271A40DE714AEEA5424@PhilipOakley","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2014-02-04T22:45:11Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Philip Oakley\" \n> From: \"David Kastrup\" \n> To: \"Junio C Hamano\" \n> Cc: \n> Sent: Tuesday, February 04, 2014 9:09 PM\n> Subject: Re: [PATCH] blame.c: prepare_lines should not call xrealloc \n> for every line\n>\n[...]\n>>\n>> Where's the difference? This is exactly what will happen with my \n>> code\n>> as well. I _do_ rely on memchr(whatever, '\\n', 0) to return NULL\n>> without looking at any memory for that. If there is a fear of memchr\n>> not being able to deal with a count of 0, this code needs to be \n>> somewhat\n>> more complex.\n>\n> A bit of googling found \n> http://marc.info/?l=gnulib-bug&m=130108029329021 which suggests that \n> behaviour can't be relied upon, and that perhaps some code is 'buggy' \n> relative to expectations (hence the patch it proposed).\n>\n> It suggests that one can't properly reference a zero length object.\n>\n\nI think I've confused myself between the patch \nhttps://lkml.org/lkml/2010/11/24/429 which fixed a bug in memchr() and \nthe discussion in \nhttp://lists.gnu.org/archive/html/bug-gnulib/2011-03/msg00273.html \n(alternate link to marc.info) that discusses realloc() which has\n\"\nwe changed gnulib's test-memchr to\ninstead test memchr(zerosize_ptr(),a,0) rather than memchr(NULL,a,0).\nHowever, once you can handle memchr(,0) on any other zero-size object,\nmost implementations also happen to do what you want for\nmemchr(NULL,a,0), even though it is technically undefined behavior.\"\nending with 'technically undefined behavior' which I misconstrued.\n\nApologies for the noise.\n\n>>\n>>> I do not remember if the rest of the logic\n>>> actually depends on it (I think I use lineno[n+1] - lineno[n] to\n>>> find the end of line,\n>>\n...\n>> -- \n>> David Kastrup\n>> --\n>\n> Philip\n> --\n"},{"id":"234274","messageId":"87vbwuuf5g.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqmwi67cty.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-05T08:39:39Z","receivedAt":"2014-02-05T08:39:39Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>>> so something like\n>>>\n>>> \tfor (p = buf; p < end; p++) {\n>>> \tp = find the end of this line\n>>> if (!p)\n>>> \tbreak;\n>>> \t\tnum++;\n>>> \t}\n>>>\n>>> perhaps?\n>>\n>> Would crash on incomplete last line.\n>\n> Hmph, even with \"if !p\"?\n\nAdmitted. So we have one _proper_ loop termination condition in the\nmiddle of the loop, and we have a snake oil condition at the start of\nthe loop that can, according to the standard, _only_ yield true reliably\nwhen p == end (any end > p can only result from undefined behavior when\np points to an object of size end - p).\n\nThe effect of this condition basically is to state \"we don't trust\nmemchr to do the right thing when called with 0 as its last argument\nwhich can happen at most once\". This condition will come about by the\n_combined_ effect of p = ... _in_ the loop (which is the real iteration\nadvancing p) and p++ hidden in the for statement (which never makes any\nsense separated from the p = ...).\n\nIt turns out that\na) memchr is provided by a compatibility layer in case it is missing or\n defective\nb) other code in Git demands that memchr works correctly with a zero\n last argument. See, for example, attr.c:\n if (dirlen <= len)\n break;\n cp = memchr(path + len + 1, '/', dirlen - len - 1);\n\nThis clearly needs to be able to work with dirlen == len + 1.\n\nSo the loop gets rewritten in a manner where the for statement\n_pretends_ to loop linearly through buf, but where the loop _body_ has\nits own _regular_ termination condition it shields from the original\nfor, and p is advanced _independently_. The advancement of p to beyond\nthe next '\\n' is distributed to two different places in the loop, and\none place is made to look as if it does something else.\n\n> But that last round of the loop will be no-op, so \"p < end\" vs \"p <=\n> end\" does not make any difference. It is not even strictly\n> necessary because memchr() limits the scan to end, but it would\n> still be a good belt-and-suspenders defensive coding practice, I\n> would think.\n\nIt's snake oil making debugging harder. It masks the real action, and\nit will route around suspected faulty behavior that is wrong according\nto the standards and not permitted elsewhere in the codebase. Other\nthan that, it just takes additional performance from every iteration.\n\nPutting belts and suspenders on a bike looks comforting until the\nsuspenders get caught in the wheelspokes.\n\n> which is the same as\n>\n> \tfor (p = buf; ; p++) {\n> \t*lineno++ = p - buf;\n> p = memchr...\n> if (!p)\n> \tbreak;\n> \t}\n>\n> and the latter has the loop control p++ at where it belongs to.\n\nBut it's only half the control.\n\nAs it is clear that we won't get to a state where I'd be willing to have\n\"git blame\" pointing to me as the author, I suggest that you either put\nyour belts and suspenders on with a separate commit under your own\nauthorship, or that we drop this altogether.\n\nAs I stated already: this patch was just provided because the original\ncode offends my sense of aesthetics, so there is no point to it if it\noffends yours.\n\nI'd still recommend fixing the sizeof(int *) with sizeof(int) confusion.\n\n> If we wanted to have a belt-and-suspenders safety, we need \"p <=\n> end\" here, not \"p < end\",\n\nThat would be totally ridiculous since end > p cannot ever happen except\nby undefined behavior. Pointer inequalities require both pointers to be\nassociated with the same object.\n\n> This was fun ;-)\n\nAt the expense of seriously impacting my motivation to do any further\ncode cleanup on Git.\n\nWhich is a reasonable tradeoff since your fun is more important to Git's\nwell-being than my one.\n\n-- \nDavid Kastrup\n"},{"id":"234275","messageId":"87r47hvrqt.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqd2j28w3h.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-05T09:22:18Z","receivedAt":"2014-02-05T09:22:18Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> which I think is the prevalent style in our codebase. The same for\n> the other loop we see in the new code below.\n>\n> - avoid assignments in conditionals when you do not have to.\n\ncommit a77a48c259d9adbe7779ca69a3432e493116b3fd\nAuthor: Junio C Hamano \nDate: Tue Jan 28 13:55:59 2014 -0800\n\n combine-diff: simplify intersect_paths() further\n[...]\n\n+ while ((p = *tail) != NULL) {\n\nBecause we can.\n\nAt any rate, I am not going to put any more work into this patch as it\nis decidedly not worth the bad taste this discussion leaves in my mouth.\nAnd I don't want any code marked as written by me that does not\ncorrespond to what I'd be willing to write. So please make sure to put\nany rewrites in a separate commit with different authorship.\n\nThanks\n\n-- \nDavid Kastrup\n"},{"id":"234328","messageId":"xmqqob2l2ta7.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"87r47hvrqt.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-05T20:34:08Z","receivedAt":"2014-02-05T20:34:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Junio C Hamano writes:\n>\n>> which I think is the prevalent style in our codebase. The same for\n>> the other loop we see in the new code below.\n>>\n>> - avoid assignments in conditionals when you do not have to.\n>\n> commit a77a48c259d9adbe7779ca69a3432e493116b3fd\n> Author: Junio C Hamano \n> Date: Tue Jan 28 13:55:59 2014 -0800\n>\n> combine-diff: simplify intersect_paths() further\n> [...]\n>\n> + while ((p = *tail) != NULL) {\n>\n> Because we can.\n\nBe reasonable. You cannot sensibly rewrite it to\n\n\tp = *tail;\n while (p) {\n \t...\n\t\tp = *tail;\n\t}\n\nwhen you do not know how ... part would evolve in the future.\n\n\tif ((p = *tail) != NULL) {\n \t...\n\nis a totally different issue.\n"},{"id":"234331","messageId":"xmqqk3d92t0z.fsf@gitster.dls.corp.google.com","threadId":"35797","inReplyTo":"87vbwuuf5g.fsf@fencepost.gnu.org","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-05T20:39:40Z","receivedAt":"2014-02-05T20:39:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> It's snake oil making debugging harder.\n\nOK, that is a sensible argument.\n\n>> This was fun ;-)\n>\n> At the expense of seriously impacting my motivation to do any further\n> code cleanup on Git.\n\nWell, I said it was \"fun\" because I was learning from a new person\nwho haven't made much technical or code aethesitics discussion here\nso far. If teaching others frustrates you and stops contributing to\nthe project, that is a loss.\n\nBut the styles matter, as the known pattern in the existing code is\nwhat lets our eyes coast over unimportant details of the code while\nreviewing and understanding. I tend to be pickier when reviewing\ncode from new people who are going to make large contributions for\nexactly that reason---new blood bringing in new ideas is fine, but\nI'd want to see those new ideas backed by solid thiniking, and that\nmeans they may have to explain themselves to those who are new to\ntheir ideas.\n"},{"id":"234349","messageId":"87vbwtjf81.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqob2l2ta7.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-05T23:45:50Z","receivedAt":"2014-02-05T23:45:50Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Junio C Hamano writes:\n>>\n>>> which I think is the prevalent style in our codebase. The same for\n>>> the other loop we see in the new code below.\n>>>\n>>> - avoid assignments in conditionals when you do not have to.\n>>\n>> commit a77a48c259d9adbe7779ca69a3432e493116b3fd\n>> Author: Junio C Hamano \n>> Date: Tue Jan 28 13:55:59 2014 -0800\n>>\n>> combine-diff: simplify intersect_paths() further\n>> [...]\n>>\n>> + while ((p = *tail) != NULL) {\n>>\n>> Because we can.\n>\n> Be reasonable. You cannot sensibly rewrite it to\n>\n> \tp = *tail;\n> while (p) {\n> \t...\n> \t\tp = *tail;\n> \t}\n>\n> when you do not know how ... part would evolve in the future.\n\nThe only unknown here is the potential presence of \"continue;\" in\n... and that can be addressed by writing\n\n for (p = *tail; p; p = *tail) {\n ...\n }\n\nHowever, that only makes sense where ... is rather large and diverse and\nthe assignment in question provides a unifying point. In this case, the\nloop is rather small and perfectly fits on one screen. It turns out\nthat the assignment only serves for _obfuscating_ the various code\npaths. We have:\n\n while ((p = *tail) != NULL) {\n cmp = ((i >= q->nr)\n ? -1 : strcmp(p->path, q->queue[i]->two->path));\n\n if (cmp < 0) {\n /* p->path not in q->queue[]; drop it */\n *tail = p->next;\n free(p);\n continue;\n }\n\n if (cmp > 0) {\n /* q->queue[i] not in p->path; skip it */\n i++;\n continue;\n }\n\n hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n p->parent[n].mode = q->queue[i]->one->mode;\n p->parent[n].status = q->queue[i]->status;\n\n tail = &p->next;\n i++;\n }\n\nWhile we could instead have:\n p = curr;\n while (p) {\n cmp = ((i >= q->nr)\n ? -1 : strcmp(p->path, q->queue[i]->two->path));\n\n if (cmp < 0) {\n struct combine_diff_path *n = p->next;\n /* p->path not in q->queue[]; drop it */\n free(p);\n p = *tail = n;\n continue;\n }\n\n if (cmp > 0) {\n /* q->queue[i] not in p->path; skip it */\n i++;\n continue;\n }\n\n hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n p->parent[n].mode = q->queue[i]->one->mode;\n p->parent[n].status = q->queue[i]->status;\n\n p = *(tail = &p->next);\n i++;\n }\n\nOf course, it only makes limited sense to recheck p after the second if, so\nit would be clearer to write\n\n p = curr;\n while (p) {\n cmp = ((i >= q->nr)\n ? -1 : strcmp(p->path, q->queue[i]->two->path));\n\n if (cmp < 0) {\n struct combine_diff_path *n = p->next;\n /* p->path not in q->queue[]; drop it */\n free(p);\n p = *tail = n;\n continue;\n }\n\n if (cmp > 0) {\n /* q->queue[i] not in p->path; skip it */\n i++;\n continue;\n }\n\n hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n p->parent[n].mode = q->queue[i]->one->mode;\n p->parent[n].status = q->queue[i]->status;\n\n p = *(tail = &p->next);\n i++;\n }\n\nBut that's sort of a red herring since the actual loop structure is\nhidden in conditions where it does not belong. (i >= q->nr) is a\n_terminal_ condition.\n\nSo it's more like\n\n p = curr;\n while (p) {\n if (i >= q->nr) {\n *tail = NULL;\n do {\n struct combine_diff_path *n = p->next;\n free(p);\n p = n;\n } while (p);\n break;\n }\n cmp = strcmp(p->path, q->queue[i]->two->path));\n if (cmp < 0) {\n struct combine_diff_path *n = p->next;\n /* p->path not in q->queue[]; drop it */\n free(p);\n p = *tail = n;\n continue;\n }\n if (cmp == 0) {\n hashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n p->parent[n].mode = q->queue[i]->one->mode;\n p->parent[n].status = q->queue[i]->status;\n\n p = *(tail = &p->next);\n }\n i++;\n }\n\n> \tif ((p = *tail) != NULL) {\n> \t...\n>\n> is a totally different issue.\n\nYes: it was just a matter of style instead of preventing _other_ code to\nbe rewritten in a clearer manner.\n\nFor a \"don't look elsewhere\" solution,\n\n while ((p = *tail) != NULL)\n\ncan _always_ be equivalently replaced with\n\n for (p = *tail; p; p = *tail)\n\nand in this case already trivially improved with\n\n for (p = curr; p; p = *tail)\n\nwhich meets your style prescription \"avoid assignments in conditionals\nwhen you do not have to.\" but in this particular case, the \"don't look\nelsewhere\" solution was not called for. It unifies code paths that\ndeserve to stay separate: we don't _want_ the assignment to take place\nfor every path leading to the loop control. It makes it less clear to\nsee what happens.\n\n-- \nDavid Kastrup\n"},{"id":"234353","messageId":"87r47hjcyc.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqk3d92t0z.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-06T00:34:51Z","receivedAt":"2014-02-06T00:34:51Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> It's snake oil making debugging harder.\n>\n> OK, that is a sensible argument.\n>\n>>> This was fun ;-)\n>>\n>> At the expense of seriously impacting my motivation to do any further\n>> code cleanup on Git.\n>\n> Well, I said it was \"fun\" because I was learning from a new person\n> who haven't made much technical or code aethesitics discussion here\n> so far. If teaching others frustrates you and stops contributing to\n> the project, that is a loss.\n\nThe implication of \"Thanks for catching them, but this patch needs heavy\nstyle fixes.\" is not one of learning.\n\n> But the styles matter, as the known pattern in the existing code is\n> what lets our eyes coast over unimportant details of the code while\n> reviewing and understanding. I tend to be pickier when reviewing code\n> from new people who are going to make large contributions for exactly\n> that reason---new blood bringing in new ideas is fine, but I'd want to\n> see those new ideas backed by solid thiniking, and that means they may\n> have to explain themselves to those who are new to their ideas.\n\nWell, the point of stylistic decisions is exactly that they are not\nindividually \"backed by solid thinking\": if they were, one would not\nrequire a style.\n\nA pattern of\nsome loop {\n ...\n if (condition) {\n code intimately related to condition;\n continue;\n }\n break;\n}\n\nis somewhat awkward. The superficially simpler\n\nsome loop {\n ...\n if (!condition)\n break;\n code intimately related to condition;\n}\n\nseparates related parts with a central loop exit. Which maybe a tossup.\nThe former pattern of break; at the end of a loop, however, becomes\nindispensible in the form\n\nsome loop {\n ...\n switch (...) {\n various cases ending in either break; or continue;\n }\n break;\n}\n\nIn this case, the break; before the end of the loop establishes the\nstatement \"any commencement of the loop will be explicitly done using\ncontinue;\", particularly important since a break; inside of the switch\nstatement does not, without this help, break out of the loop.\n\nIt's a pattern that is transparent enough to be still preferable over\n\"crank out the goto already, chicken\".\n\nIs \"if I have to use x in some situations anyway I may as well pick it\nwhen there would be equivalent solutions\" solid thinking? Not really.\nIt's about choosing one's familiars. Which ultimately boils down to\npersonal style. And where the differences are not really significant\nfor understanding and _are_ a conscious expression rather than just an\naccident, the thin line between \"write in a way that does not go against\nour style and/or good sense\" and \"write in the way I would have written\nit\" may be the line between fun and work.\n\n-- \nDavid Kastrup\n"},{"id":"234359","messageId":"87mwi4k003.fsf@fencepost.gnu.org","threadId":"35797","inReplyTo":"xmqqk3d92t0z.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-02-06T10:29:16Z","receivedAt":"2014-02-06T10:29:16Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> It's snake oil making debugging harder.\n>\n> OK, that is a sensible argument.\n>\n>>> This was fun ;-)\n>>\n>> At the expense of seriously impacting my motivation to do any further\n>> code cleanup on Git.\n>\n> Well, I said it was \"fun\" because I was learning from a new person\n> who haven't made much technical or code aethesitics discussion here\n> so far. If teaching others frustrates you and stops contributing to\n> the project, that is a loss.\n\nSo let's post something noteworthy technical: the current code iteration\nsported the following routine:\n\nstatic struct blame_entry *blame_merge(struct blame_entry *list1,\n\t\t\t\t struct blame_entry *list2)\n{\n\tstruct blame_entry *p1 = list1, *p2 = list2,\n\t\t**tail = &list1;\n\n\tif (!p1)\n\t\treturn p2;\n\tif (!p2)\n\t\treturn p1;\n\n\tif (p1->s_lno <= p2->s_lno) {\n\t\tdo {\n\t\t\ttail = &p1->next;\n\t\t\tif ((p1 = *tail) == NULL) {\n\t\t\t\t*tail = p2;\n\t\t\t\treturn list1;\n\t\t\t}\n\t\t} while (p1->s_lno <= p2->s_lno);\n\t}\n\tfor (;;) {\n\t\t*tail = p2;\n\t\tdo {\n\t\t\ttail = &p2->next;\n\t\t\tif ((p2 = *tail) == NULL) {\n\t\t\t\t*tail = p1;\n\t\t\t\treturn list1;\n\t\t\t}\n\t\t} while (p1->s_lno > p2->s_lno);\n\t\t*tail = p1;\n\t\tdo {\n\t\t\ttail = &p1->next;\n\t\t\tif ((p1 = *tail) == NULL) {\n\t\t\t\t*tail = p2;\n\t\t\t\treturn list1;\n\t\t\t}\n\t\t} while (p1->s_lno <= p2->s_lno);\n\t}\n}\n\n\nThis is decidedly more complex than the equivalent\n\nstatic struct blame_entry *blame_merge(struct blame_entry *list1,\n\t\t\t\t struct blame_entry *list2)\n{\n\tstruct blame_entry *p1 = list1, *p2 = list2,\n\t\t**tail = &list1;\n\n\twhile (p1 && p2) {\n\t\tif (p1->s_lno <= p2->s_lno) {\n\t\t\t*tail = p1;\n\t\t\tp1 = *(tail = &p1->next);\n\t\t} else {\n\t\t\t*tail = p2;\n\t\t\tp2 = *(tail = &p2->next);\n\t\t}\n\t}\n\t*tail = p1 ? p1 : p2;\n\treturn list1;\n}\n\nWhy not use the latter one? Apart from the somewhat\nobsessive-compulsive avoidance of checking the same condition twice in a\nrow (which nowadays compilers are pretty capable of taking into account\nby themselves) the actually decisive difference is to avoid rewriting\nlinks that are already pointing to the right place.\n\nThose are the only write accesses that take place, and since we are\ntalking about _sorting_, it is to be expected that in the long run,\nevery record ends up in a cacheline different from its ultimate\nneighbors. Also, assuming a more or less random distribution and\nequally sized chains, about half of the links will already be correct.\nIn practice, the situation tends to be more degenerate, leading to a\n_higher_ ratio of already correct links. Cutting down the expensive\nwriteout of cachelines by a factor of more than 2 makes quite a\ndifference in performance.\n\nDoes it matter here? Unlikely. Profiling tools tend to be useless for\nseeing the impact of dirty cachelines since their operation\nsignificantly interferes with the read/write patterns so this kind of\ndetail often escapes notice. But the total contribution of this stage\nto the runtime of git blame will be insignificant either way.\n\n> new blood bringing in new ideas is fine, but I'd want to see those new\n> ideas backed by solid thiniking, and that means they may have to\n> explain themselves to those who are new to their ideas.\n\nWell, there _is_ solid thinking behind the above code, but there _also_\nis solid thinking behind the notion that it won't matter in this case.\nI still prefer not pushing out code in the wild that I would hesitate to\nemploy in _all_ comparable circumstances. Consider it as a pattern or a\nstyle: a lot of thinking went into it once, and what this should buy you\nis to never have to think about this issue again.\n\nC++ is better at actual code reuse, but with C you basically get pattern\nreuse. Your head is instantiating the templates. And it's a good idea\nnot to crowd one's head with unnecessary and/or suboptimal patterns.\n\n-- \nDavid Kastrup\n"}]}