From: David Kastrup <dak@gnu•org>
To: git@vger•kernel.org
Subject: Re: [PATCH] blame.c: prepare_lines should not call xrealloc for every line
Date: Tue, 04 Feb 2014 21:52:52 +0100 [thread overview]
Message-ID: <87ha8ewqfv.fsf@fencepost.gnu.org> (raw)
In-Reply-To: xmqqd2j28w3h.fsf@gitster.dls.corp.google.com
Junio C Hamano <gitster@pobox•com> writes:
> 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.
>> +
>> + 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++)
> 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.
>> + }
>>
>> - 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.
>> - 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
next prev parent reply other threads:[~2014-02-04 20:53 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-02-04 20:06 [PATCH] blame.c: prepare_lines should not call xrealloc for every line David Kastrup
2014-02-04 20:10 ` David Kastrup
2014-02-04 20:49 ` Junio C Hamano
2014-02-04 21:00 ` Junio C Hamano
2014-02-04 21:09 ` David Kastrup
2014-02-04 22:28 ` Philip Oakley
2014-02-04 22:48 ` Philip Oakley
2014-02-04 20:24 ` Junio C Hamano
2014-02-04 20:52 ` David Kastrup [this message]
2014-02-04 21:03 ` Junio C Hamano
2014-02-04 21:11 ` David Kastrup
2014-02-04 21:41 ` Junio C Hamano
2014-02-04 21:27 ` David Kastrup
2014-02-04 21:44 ` Junio C Hamano
2014-02-04 21:48 ` David Kastrup
2014-02-04 22:06 ` Junio C Hamano
2014-02-05 8:39 ` David Kastrup
2014-02-05 20:39 ` Junio C Hamano
2014-02-06 0:34 ` David Kastrup
2014-02-06 10:29 ` David Kastrup
2014-02-05 9:22 ` David Kastrup
2014-02-05 20:34 ` Junio C Hamano
2014-02-05 23:45 ` David Kastrup
-- strict thread matches above, loose matches on Subject: below --
2014-02-04 21:40 David Kastrup
2014-02-04 21:46 David Kastrup
2014-02-12 14:27 David Kastrup
2014-02-12 19:36 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87ha8ewqfv.fsf@fencepost.gnu.org \
--to=dak@gnu$(echo .)org \
--cc=git@vger$(echo .)kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox