Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Sep 20, 2017, 02:30 UTC
Message-ID: <20170920023008.GB126984@aiede.mtv.corp.google.com>
In-Reply-To: <b03c7b09-853f-a2ed-f73e-7d946c90cedb@gmail.com>

Hi,

Kaartic Sivaraam wrote:

> On Saturday 16 September 2017 09:36 AM, Michael Haggerty wrote:
>> Jonathan Nieder wrote:

Show 19 quoted lines

>>> Does the following alternate fix work?  I think I prefer it because
>>> it doesn't require introducing a new global. [...]
>>>   #define for_each_string_list_item(item,list) \
>>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>>> +	for (item = (list)->items; \
>>> +	     (list)->items && item < (list)->items + (list)->nr; \
>>> +	     ++item)
>>
>> This is the possibility that I was referring to as "add[ing] overhead to
>> each iteration of the loop". I'd rather not add an extra test-and-branch
>> to every iteration of a loop in which `list->items` is *not* NULL, which
>> your solution appears to do. Or are compilers routinely able to optimize
>> the check out?
>
> I t seems at least 'gcc' is able to optimize this out even with a -O1
> and 'clang' optimizes this out with a -O2. Taking a sneak peek at
> the 'Makefile' shows that our default is -O2.
>
> For a proof, see https://godbolt.org/g/CPt73L

From that link:

    for ( ;valid_int && *valid_int < 10; (*valid_int)++) {
        printf("Valid instance");
    }

Both gcc and clang are able to optimize out the 'valid_int &&' because it is dereferenced on the RHS of the &&.

For comparison, 'item < (list)->items + (list)->nr' does not dereference (list)->items. So that optimization doesn't apply here.

A smart compiler could be able to take advantage of there being no object pointed to by a null pointer, which means

	item < (list)->items + (list)->nr

is always false when (list)->items is NULL, which in turn makes a '(list)->items &&' test redundant. But a quick test with gcc 4.8.4 -O2 finds that at least this compiler does not contain such an optimization. The overhead Michael Haggerty mentioned is real.

Thanks and hope that helps, Jonathan