Ranges, Performance, and opApply

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Sun Oct 30 12:09:56 PDT 2011


On 10/30/11 11:45 AM, Martin Nowak wrote:
> On Sun, 30 Oct 2011 15:42:36 +0100, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 10/30/11 3:02 AM, Kapps wrote:
>>> As it stands right now, ranges are quite inefficient. Phobos is
>>> designed with an emphasis on ranges, including in
>>> performance-sensitive code such as std.algorithm. No matter how
>>> optimized the range is, it will always be slower than the equivalent
>>> opApply function (and, as far as I can tell, offers no benefit for
>>> just iteration).
>>>
>>
>> The test is flawed in a subtle way and no conclusion can be drawn from
>> it.
>>
>> The test filters a checkerboard distribution (one element satisfies/the
>> next doesn't satisfy the filter). As such, the loop on lines 26-29 will
>> always test exactly two times to take one step. In contrast, the loop at
>> lines 75-81 is integrated and only makes the minimum amount of tests.
>> Calling the delegate is expensive, but there are only half as many calls
>> and the saved tests compensate for that.
>>
> No it does not.

Indeed you're right. In the quiescent state both implementations call 
the support functions the same number of times. Thanks.

> In fact the opApply version does ONE additional check at loop start, which
> doesn't matter for 2.5M iterations.
>
>> I believe there is nothing inherent in the design of ranges that makes
>> them generally less efficient than various alternatives. Yes, there
>> will be the corner cases where internal iteration will be better, but
>> overall I don't think they form a large fraction of all cases.
>>
>>
>> Andrei
>
> The test still doesn't measure anything but spurious effects of
> different inline decisions.
> I get a ~10% hit for range foreach over opApply.
> When looping without predicate than popFront is inlined and the result
> is a ~10% hit for opApply.
> As the opApply body can never be inlined it is a worse choice in general.

That was my intuition too.


Andrei


More information about the Digitalmars-d mailing list