Boost logo

Boost :

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.


Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229

Boost list run by bdawes at, gregod at, cpdaniel at, john at