Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line
Junio C Hamano <gitster@pobox.com> writes:
Show 29 quoted lines
> David Kastrup <dak@gnu.org> writes:
>
>> Making a single preparation run for counting the lines will avoid memory
>> fragmentation. Also, fix the allocated memory size which was wrong
>> when sizeof(int *) != sizeof(int), and would have been too small
>> for sizeof(int *) < sizeof(int), admittedly unlikely.
>>
>> Signed-off-by: David Kastrup <dak@gnu.org>
>> ---
>> builtin/blame.c | 40 ++++++++++++++++++++++++----------------
>> 1 file changed, 24 insertions(+), 16 deletions(-)
>>
>> diff --git a/builtin/blame.c b/builtin/blame.c
>> index e44a6bb..522986d 100644
>> --- a/builtin/blame.c
>> +++ b/builtin/blame.c
>> @@ -1772,25 +1772,33 @@ static int prepare_lines(struct scoreboard *sb)
>> {
>> const char *buf = sb->final_buf;
>> unsigned long len = sb->final_buf_size;
>> - int num = 0, incomplete = 0, bol = 1;
>> + const char *end = buf + len;
>> + const char *p;
>> + int *lineno;
>> +
>> + int num = 0, incomplete = 0;
>
> Is there any significance to the blank line between these two
> variable definitions?Well, I needed more than the whitespace error to be motivated for redoing. Cough, cough.
Show 10 quoted lines
>> +
>> + for (p = buf;;) {
>> + if ((p = memchr(p, '\n', end-p)) == NULL)
>> + break;
>> + ++num, ++p;
>
> You have a peculiar style that is somewhat distracting. Why isn't
> this more like so?
>
> for (p = buf; p++, num++; ) {More likely
for (p = buf;; p++, num++)
Show 7 quoted lines
> p = memchr(p, '\n', end - p);
> if (!p)
> break;
> }
>
> which I think is the prevalent style in our codebase. The same for
> the other loop we see in the new code below.
I rearranged a few times in order to have both loops be closely analogous. The second loop would then have to be
for (p = buf;; p++) {
*lineno++ = p-buf;
p = memchr(p, '\n', end-p)
if (!p)
break;
}Admittedly, that works. I am not too happy about the termination condition being at the end of the loop but not in the for statement, but yes, this seems somewhat nicer than what I proposed.
> - favor post-increment unless you use it as rvalue and need
> pre-increment;
In my youth, the very non-optimizing C compiler I used under CP/M produced less efficient code for x++ than for ++x even when not using the resulting expression. Surprisingly habit-forming.
>
> - SP around each binary ops e.g. 'end - p';
Show 8 quoted lines
>> + }
>>
>> - if (len && buf[len-1] != '\n')
>> + if (len && end[-1] != '\n')
>> incomplete++; /* incomplete line at the end */
>
> OK, so far we counted "num" complete lines and "incomplete" may be
> one if there is an incomplete line after them.
That's pretty much the gist of the original code.
Show 16 quoted lines
>> - while (len--) {
>> - if (bol) {
>> - sb->lineno = xrealloc(sb->lineno,
>> - sizeof(int *) * (num + 1));
>> - sb->lineno[num] = buf - sb->final_buf;
>> - bol = 0;
>> - }
>> - if (*buf++ == '\n') {
>> - num++;
>> - bol = 1;
>> - }
>> +
>> + sb->lineno = lineno = xmalloc(sizeof(int) * (num + incomplete + 1));
>
> OK, this function is called only once, so we know sb->lineno is NULL
> originally and there is no reason to start from xrealloc().> These really *were* unnecessary reallocations.
Well, if a realloc will increase the allocation size by a constant factor each time, the amortization cost is O(n) for n entries. So with a suitable realloc, the effect will not really be noticeable. It still offends my sense of aesthetics.
> Thanks for catching them, but this patch needs heavy style fixes.
Well, does not look all that heavy, but I'll repost.
There is another oversight: I am using memchr here, but there is no obvious header file definiting it (the respective header will likely be pulled in indirectly via something unrelated).
Anybody know offhand what I should be including here? It looks like Git has some fallback definitions of its own, so it's probably not just <string.h> I should include?
--
David Kastrup
David Kastrup
