Ranges, Performance, and opApply

[Andrei Alexandrescu]

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.

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