Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: David Abrahams (dave_at_[hidden])
Date: 2008-09-03 09:05:48

on Tue Sep 02 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

>> I'm trying to find out what the specific example applications are.  I
>> have a suspicion that range adapters or single-level iterator adaptors
>> may not be the best way to address these applications and may even
>> sacrifice significant performance, but I can't tell until I know what
>> the applications are.  Just so, single-level iterators (or ordinary
>> range adapters, which don't add anything conceptually to iterators) are
>> not the best way to address iteration over hierarchical data structures,
>> which is why we have segmented iterators.
>
> This is a typical one, copied straight from our code:
>
> 		grdlns->InsertGridlines( 
> 			vecgvepsSource,
> 			make_first_range(vecpairanchorsrcgrdln), 
> 			GridlineInsertionPositions( 
> 				make_transform_range(
> 					make_transform_range( 
> 						make_first_range(
> vecpairanchorsrcgrdln ),
> 						boost::mem_fn(&_vector<
> Ref<CGridlineAnchor> >::begin)
> 					),
> 					boost::mem_fn( &CGridlineAnchor::Binding
> )
> 				), 
> 				vecgrdlnSnapped),
> 			vecgrdlnSnapped 
> 		);

The first problem is that I can't tell what that does.  So it doesn't
really begin to answer the question.

> This is a case in point: I did not write this code, and in the absence of
> specific guidelines against, the programmer decided to stack transform_range. In
> this case, performance-wise, this is no better or worse than using a single
> transform_range with boost::bind. Likewise, people may innocently write
>
> rng | filtered( funcA ) 
>     | filtered( funcB ) 
>     | filtered( funcC ) 
>     | filtered( funcD ) 
>     | filtered( funcE )
>
> blissfully unaware of any performance penalty.

Yes, but:

 1. _Do_ they write that?  

 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.

 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.

 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.

>> However, it seems to me that you already have a general answer in mind, 
>> and it might be better to back up and look at the real problems you want 
>> to solve before moving on to the answer.
>
> Would it be my turn now to ask for some credit ;-) ? 

Take as much as you like, but -- sorry -- I'm not yet convinced we're
solving a real problem here, and if it _is_ real, I am not quite
convinced the general approach of squeezing out redundant storage would
address all of the problem.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com