Re: [boost] [range/iterators/algorithms/phoenix/bind...] Coordinated Approach

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-10 09:52:28

On Thu, Jul 10, 2008 at 12:25 PM, Dean Michael Berris
<mikhailberis_at_[hidden]> wrote:
>
> On Mon, Jul 7, 2008 at 10:48 PM, Giovanni Piero Deretta
> <gpderetta_at_[hidden]> wrote:
>> On Mon, Jul 7, 2008 at 12:19 PM, Dean Michael Berris
>> <mikhailberis_at_[hidden]> wrote:
> <snip>
>>>
>>> Removing the need to actually create temporary objects.
>>
>> You would be substituting one light weight temporary (a lazy range)
>> for another one, the expression template node.
>>
>
> Right, but the expression template "node" will just contain references
> -- and actual iterators will only be built once with the exact type,
> instead of encapsulating and creating multiple range objects passed
> from function to function.

You can do the same thing with ranges (thus my claim that we are
actually talking about the same thing:) ). If you look at the file I
have attached a couple of posts ago, you'll find, for example, that
the definition of transform_range (I call it map range) is:

    template<class R, class M>
    struct map_range {
        map_range(R const&r_, M m_) : r(r_), m(m_) {}

        typedef typename detail::make_transform_iterator<R, M>::type iterator;
        typedef iterator const_iterator;

        iterator begin() const {
            return iterator(detail::begin(r), m);
        }

        iterator end() const {
            return iterator(detail::end(r), m);
        }

        R r;
        M m;
    };

I.e. the iterators are built on demand. You can do a bit better by
inheriting from compressed_pair<R, M>, just in case any of R or M is
an empty class (uncommon for the former, but likely for the latter),
but I didn't bother for this example. Note that both R and M are by
value (otherwise some code might break horribly). If you want
references, specify the template parameters as needed.

(BTW, the above code is broken as a const_iterator is not necessary
the same as iterator, also the const variant of begin and end should
return a const_iterator: I converted the code from actually holding an
iterator pair to holding the original range, and forgot to fix this
mistake)

Building iterators on demand has the advantage that complex range
objects might be smaller, but means that you have to explicitly wrap
the initial range object in a boost::sub_range to prevent it from
being copied around, so it is not necessarily a win.
Holding the original range by reference means that you risk dangling references.

<snip>
>> May be I'm misunderstanding you; could you provide an example and show
>> exactly where is the difference between expression templates and lazy
>> ranges (IMHO they are exactly the same thing)?
>>
>
> I tried above, but generally I think there's a difference between
> creating the type first at compile time then reducing the number of
> steps actually done at runtime (constructing and destroying objects or
> even a bunch of bytes).

Have you ever measured this overhead? Did it matter? I user lazy
ranges extensively and never measured any significant overhead the
expression  construction itself.
<snip>
> So in essence, you'd want expression templates because if:
>
>  reduce(map(filter(source, f), m), r)
>
> Is less efficient than:
>
>  source | filter(f) | map(m) | reduce(r)

I claim that if a range library makes the former less efficient than
the latter, the library is broken. In fact It would be take very hard
work to make the first syntax inefficient :)

>
> Then that's a good reason to either: make the range generation
> functions as efficient as the expression template approach, or remove
> the range generation functions in favor of the more concise (and
> efficient) pipe syntax.

The former syntax is more natural and can work with binders (if you
make map, filter and friends function objects), so I'm against
dropping it.

Also neither of these two syntaxes:

  auto r = map(filter(range, f), m);
  auto r = range|map(_,m)|filter(_,f)

should produce dangling references (use result_of for a c++03 variant).
Which means that ranges should close by value over their arguments or
use iterators internally, unless you want to add another step to do a
deep copy.

-- 
gpd