git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
David Kastrup <dak@gnu.org>
Date
Feb 5, 2014, 08:39 UTC
Message-ID
<87vbwuuf5g.fsf@fencepost.gnu.org>
In-Reply-To
<xmqqmwi67cty.fsf@gitster.dls.corp.google.com>
Junio C Hamano <gitster@pobox.com> writes:
Show 16 quoted lines
> David Kastrup <dak@gnu.org> writes:
>
>>> so something like
>>>
>>> 	for (p = buf; p < end; p++) {
>>>         	p = find the end of this line
>>>                 if (!p)
>>>                 	break;
>>> 		num++;
>>> 	}
>>>
>>> perhaps?
>>
>> Would crash on incomplete last line.
>
> Hmph, even with "if !p"?

Admitted. So we have one _proper_ loop termination condition in the middle of the loop, and we have a snake oil condition at the start of the loop that can, according to the standard, _only_ yield true reliably when p == end (any end > p can only result from undefined behavior when p points to an object of size end - p).

The effect of this condition basically is to state "we don't trust memchr to do the right thing when called with 0 as its last argument which can happen at most once". This condition will come about by the _combined_ effect of p = ... _in_ the loop (which is the real iteration advancing p) and p++ hidden in the for statement (which never makes any sense separated from the p = ...).

It turns out that
a) memchr is provided by a compatibility layer in case it is missing or
   defective
b) other code in Git demands that memchr works correctly with a zero
   last argument.  See, for example, attr.c:
                        if (dirlen <= len)
                                break;
                        cp = memchr(path + len + 1, '/', dirlen - len - 1);
This clearly needs to be able to work with dirlen == len + 1.

So the loop gets rewritten in a manner where the for statement _pretends_ to loop linearly through buf, but where the loop _body_ has its own _regular_ termination condition it shields from the original for, and p is advanced _independently_. The advancement of p to beyond the next '\n' is distributed to two different places in the loop, and one place is made to look as if it does something else.

Show 5 quoted lines
> But that last round of the loop will be no-op, so "p < end" vs "p <=
> end" does not make any difference.  It is not even strictly
> necessary because memchr() limits the scan to end, but it would
> still be a good belt-and-suspenders defensive coding practice, I
> would think.

It's snake oil making debugging harder. It masks the real action, and it will route around suspected faulty behavior that is wrong according to the standards and not permitted elsewhere in the codebase. Other than that, it just takes additional performance from every iteration.

Putting belts and suspenders on a bike looks comforting until the suspenders get caught in the wheelspokes.

Show 10 quoted lines
> which is the same as
>
> 	for (p = buf; ; p++) {
>         	*lineno++ = p - buf;
>                 p = memchr...
>                 if (!p)
>                 	break;
> 	}
>
> and the latter has the loop control p++ at where it belongs to.
But it's only half the control.

As it is clear that we won't get to a state where I'd be willing to have "git blame" pointing to me as the author, I suggest that you either put your belts and suspenders on with a separate commit under your own authorship, or that we drop this altogether.

As I stated already: this patch was just provided because the original code offends my sense of aesthetics, so there is no point to it if it offends yours.

I'd still recommend fixing the sizeof(int *) with sizeof(int) confusion.
> If we wanted to have a belt-and-suspenders safety, we need "p <=
> end" here, not "p < end",

That would be totally ridiculous since end > p cannot ever happen except by undefined behavior. Pointer inequalities require both pointers to be associated with the same object.

> This was fun ;-)

At the expense of seriously impacting my motivation to do any further code cleanup on Git.

Which is a reasonable tradeoff since your fun is more important to Git's well-being than my one.

-- 
David Kastrup
Previous: Junio C HamanoNext: Junio C Hamano
Message 17 of 23 in “blame.c: prepare_lines should not call xrealloc for every line”
  1. blame.c: prepare_lines should not call xrealloc for every lineDavid Kastrup, Feb 4, 2014
  2. David KastrupFeb 4, 2014
  3. Junio C HamanoFeb 4, 2014
  4. Junio C HamanoFeb 4, 2014
  5. David KastrupFeb 4, 2014
  6. Philip OakleyFeb 4, 2014
  7. Philip OakleyFeb 4, 2014
  8. Junio C HamanoFeb 4, 2014
  9. David KastrupFeb 4, 2014
  10. Junio C HamanoFeb 4, 2014
  11. David KastrupFeb 4, 2014
  12. Junio C HamanoFeb 4, 2014
  13. David KastrupFeb 4, 2014
  14. Junio C HamanoFeb 4, 2014
  15. David KastrupFeb 4, 2014
  16. Junio C HamanoFeb 4, 2014
  17. David KastrupFeb 5, 2014
  18. Junio C HamanoFeb 5, 2014
  19. David KastrupFeb 6, 2014
  20. David KastrupFeb 6, 2014
  21. David KastrupFeb 5, 2014
  22. Junio C HamanoFeb 5, 2014
  23. David KastrupFeb 5, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.