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
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 http://www.think-cell.com Â· 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk