Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line

From: David Kastrup <dak@gnu.org>
Date: Feb 4, 2014, 20:52 UTC
Message-ID: <87ha8ewqfv.fsf@fencepost.gnu.org>
In-Reply-To: <xmqqd2j28w3h.fsf@gitster.dls.corp.google.com>

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';

Ok.

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