Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-03 11:08:23

> > rng | filtered( funcA ) 
> >     | filtered( funcB ) 
> >     | filtered( funcC ) 
> >     | filtered( funcD ) 
> >     | filtered( funcE )

> 1. _Do_ they write that?  

Why not? They did for transform_range, and the notation is getting easier...

> 2. If they do that, I believe they are still paying an enormous
>    unnecessary runtime penalty even with your optimization because of
>    the endpoint checks in each layer of the composite iterator or
>    range.  The only way IIUC to avoid such a penalty is to compress the
>    filter adapters into one, essentially by using expression
>    templates.

See answer to 4.

> 3. I am not yet convinced that you are suffering a significant
>    performance penalty due to the wasted space in real applications.
>    Have you measured it?  Unless you're actually *storing* lots of
>    these stacked iterators or passing them around by value in your
>    inner loops, it seems unlikely to make much of a difference.

Giovanni has seen the quadratic stack expansions. If you are worried about performance of pointers, why not worry about the performance of wrappers around pointers?

> 4. I can understand wanting to improve these components so that they
>    can be efficient under more conditions, and avoiding the redundant
>    storage would undoubtedly be a real improvement.  However, I think
>    there's a deeper inefficiency in stacking all those filter iterators
>    together, and it's neither a range library's job, nor I think is it
>    possible in this case, to protect users from "blissful unawareness"
>    of performance implications.

The design we came up with addresses the general problem of stacking range_adaptors that must store their end, like difference_range/filter_range/union_range/[other algorithms that I cannot think of now], in any combination. If you have thought up expression templates that cover all of these in a unified fashion with better performance than stacked iterators, I'd be very happy and try to implement that instead.

> I'm not yet convinced we're
> solving a real problem here, 

I have enough of that stuff in my code that I am convinced we do.

> and if it _is_ real, I am not quite
> convinced the general approach of squeezing out redundant storage would
> address all of the problem.

It does not, you already mentioned the superfluous end checks. As I said, if you have the whole solution, let me know.

Arno

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229