Yet another strike against the current AA implementation

[Steven Schveighoffer]

On Sun, 26 Apr 2009 21:20:32 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> Michel Fortin wrote:
>> On 2009-04-26 11:46:51 -0400, dsimcha <dsimcha at yahoo.com> said:
>>
>>> == Quote from Michel Fortin (michel.fortin at michelf.com)'s article
>>>> Hum, are you saying opApply superior when it comes to iterating in a
>>>> tree? It seems that with opApply you could use the stack by  
>>>> recursively
>>>> calling opApply with the given delegate on each one of the branches.
>>>
>>> Exactly.  On the other hand, you lose a lot of flexibility with  
>>> opApply.  If you
>>> tried to port most of std.range to operate on the opApply interface  
>>> instead fo the
>>> forward range interface, I doubt you'd get very far.
>>>
>>> IMHO, though, opApply should *not* be deprecated.  opApply and ranges  
>>> attempt to
>>> solve similar problems, but not the same problem.  Ranges attempt to  
>>> solve the
>>> problem of iterating over some object with maximum flexibility from  
>>> the point of
>>> view of the user of the object.  opApply attempts to solve the problem  
>>> of
>>> iterating with maximum flexibility from the point of view of the  
>>> implementer of
>>> the object.  In some cases, like the one you just described, the  
>>> latter can be
>>> better.
>>  Indeed. I certainly agree that both ranges and opApply have their  
>> place.
>>  So what the implementer can do with opApply is write an optimized  
>> iteration algorithm for use with foreach. Which may mean that when both  
>> opApply and ranges are available for generating foreach's code, the  
>> compiler should favor opApply. Currently, I believe it's the reverse.
>
> I think, all other things being equal, that opApply tends to be slower  
> than iterators.

It depends.  The range must have either inline-able functions, or must NOT  
call virtual functions.  Otherwise, it could be worse.  there is also the  
factor that you are using an inner function with opApply, so if you  
regularly access variables outside the foreach loop, then those add up.

Observe that in opapply style, you do one delegate call per loop iteration.
With range style, you do three calls on the range per loop iteration  
(empty, front, popFront).

If those range calls call virtual calls or ARE virtual calls, then range  
loses.  Of course, the difference might be washed if you do lots of  
accesses to an outer variable in your foreach loop, which require a  
pointer dereference vs. a stack dereference.

We should quantify this and see what the actual performance is.

-Steve