Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue

Subject: Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-06-26 20:22:38

On Tue, Jun 26, 2012 at 5:12 PM, Michel Morin <mimomorin_at_[hidden]> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
> > My rebuttal is that:
> [...]
> > (b) Range adaptors can be free to cache begin and end iterators (in
> > addition to the adapted range), if that would yield noticeably better
> > performance for more than one begin/end calls (e.g., filtered_range and
> > dropped_range), but I suspect for most range adaptors, it doesn't make a
> > difference. Take, for example, a transformed_range. If it's implemented
> as
> > a pair of transform_iterators, calling begin/end requires copying the
> > underlying iterators in addition to the transform function. If
> > transformed_range is implemented as the underlying range paired with a
> > function, calling begin/end requires generating the underlying begin/end
> > iterators and still copying the transformation function. If copying the
> > underlying iterators is no faster than generating the begin/end iterators
> > from the underlying range, there should be no difference in performance
> > between the two implementations of transformed_range. Of course, there's
> a
> > big assumption on the relative speed of begin/end versus iterator copying
> > of the underlying range, but I think it's, again, the common case; it's
> > something we can aim to guarantee for all provided range adaptors; and if
> > it's a client range that fails this assumption, we can provide a facility
> > (oh yeah, that's what iterator_range is for) to explicitly address this.
> [...]
>
> I don't know what the consequence of the following fact is,
> but it's worth noting:
>
> Repeatedly adapted ranges might have **very** large size.
> For example, on Mac OS X 10.7 with gcc-4.7,
>
>    std::vector<int> v;
>
>    sizeof(v | uniqued)                               --> 32
>    sizeof(v | uniqued | uniqued)                     --> 80
>    sizeof(v | uniqued | uniqued | uniqued)           --> 176
>    sizeof(v | uniqued | uniqued | uniqued | uniqued) --> 368
>
>    // OvenToBoost's taken adaptor
>    sizeof(v | taken(1))                                  --> 48
>    sizeof(v | taken(1) | taken(1))                       --> 112
>    sizeof(v | taken(1) | taken(1) | taken(1))            --> 240
>    sizeof(v | taken(1) | taken(1) | taken(1) | taken(1)) --> 496
>
>    sizeof(v | strided(1))                                        --> 80
>    sizeof(v | strided(1) | strided(1))                           --> 272
>    sizeof(v | strided(1) | strided(1) | strided(1))              --> 848
>    sizeof(v | strided(1) | strided(1) | strided(1) | strided(1)) --> 2576
>

Wow. I might investigate what this looks like with this alternative range
adaptor implementation I've been suggesting (i.e., a lazy implementation
rather than the iterator-based implementation presently in Boost.Range).

This might be a consequence of failing or not having the necessary
infrastructure to take advantage of EBO within the adapted iterators...?

- Jeff