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

From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2008-07-07 06:19:46

On Mon, Jul 7, 2008 at 5:43 PM, Giovanni Piero Deretta
<gpderetta_at_[hidden]> wrote:
> On Mon, Jul 7, 2008 at 6:29 AM, Dean Michael Berris
> <mikhailberis_at_[hidden]> wrote:
>>
>> The advantage would be that if operator| constructed the type by
>> itself compared to having 'f' construct the type at runtime, then the
>> compiler can (and usually would) perform optimizations on the code it
>> generates for the type created by operator|.
>
> Which optimizations cannot be performed by an 'f' that returns a lazy range?
>

Removing the need to actually create temporary objects.

>>This is the same reason
>> why expression templates work very well for Blitz++ and the ublas
>> library IIRC.
>
> <snip blitz example>
>
>>
>> If you use expression templates in this situation, you would do away
>> with the temporary object(s) created in the intermediate
>> multiplication -- and have the compiler optimize the code it creates
>> for you because at compile time you're dealing first with types rather
>> than values deferred at runtime. The final assignment in the above
>> line would perform the necessary traversal(s) and assignments with the
>> benefit of the compiler having optimized already everything it would
>> have had optimized.
>>
>> In the case of implementing operator| in this way, we are then able to
>> compose/combine the chained lazy range implementation by building the
>> type at compile time
>
> This is not a property of operator|(). Any lazy range library I have
> seen does it.
>

True, but these lazy ranges aren't lazy enough -- precisely because
they rely on temporaries returned from the previously chained
expressions.

>> -- where at runtime, the code would have
>> benefitted from compiler opimizations.
>>
>> More concretely, if 'f' created the lazy range, then you'd be passing
>> the instance of the temporary range to the next 'f' in the chain, then
>> the next, then the next... Then the temporaries you'd be creating are
>> wasteful which you would avoid when using expression templates.
>
> The lazy range temporaries returned by the various 'f' are the
> equivalent expression templates. Lazy ranges are meant to be very
> lightweight (little more that two iterators). I see 0 advantages to
> adding another level of complication.
>

When you have a chain of at least three operations, you then need to
have at least two returned temporary objects -- I don't know about you
but inside a tight loop that's not good especially if the compiler
doesn't remove the temporaries for you (which I don't think there's a
standard optimization for anyway, without move semantics or something
similar that will eliminate the temporaries).

The complication introduced should be offset by the efficiency of not
having to instantiate and potentially destroy temporary objects when
chaining using the compile-time built types. The temporary object
construction, copy, and destruction is the killer that when you do it
in a tight enough loop (or even enough times in the case of
asynchronous massively parallel high performance applications) -- the
only recourse is to create *by hand* the exact range type you want so
that you don't rely on the temporary objects returned by chaining
operations; which actually defeats the purpose of introducing the
chaining using operator| in the first place (for ease of use).

So, if operator| built the *type* at compile time without having to
create temporaries, you get both the expressive power of operator| and
the efficiency brought about by the expression templates.

>> Having
>> a 'lazy_range' allows you to apply your own re-write rules (like what
>> you mention below) when the nested 'type' class is accessed to yield a
>> real instance of the range.
>
> You can do rewrite rules any way.
>

True, but only if you knew the type beforehand and invoke the rewrite
explicitly.

> <snip>
>>
>>> Also, how is the above different from
>>> mapped_range<filtered_range<taken_range<range_type>, Filter>,Mapper>
>>> which is still lazy?
>>>
>>
>> Not much except the actual type yielded by 'lazy_range<T>::type' can
>> be what mapped_range<filtered_range<taken_range<range_type>,
>> Filter>,Mapper>.
>
> The advantage is?
>

The advantage is that you built the type using zero temporaries, and
get the exact type you want at the cost of an extra nested type
instantiation.

>>
>> Without expression templates, you'll need extra temporaries (which is
>> wasteful) to achieve things with merely lamda's.
>
> Why the extra temporaries will be wasteful? They will be the
> equivalent of iterator pairs. In fact they will be exactly the same
> thing as a node in an expression template.

The node in an expression template will be encapsulated in the type
you're building, rather than an actual temporary object that gets
constructed and destroyed at run-time.

> <snip>
>>>> [...] zip_with can return a range: map<map<zip<transform<R1, F1>,
>>>> transform<R2, F2> > >, A>, B> which can still be re-written.
>>>>
>>>
>>> eh? What is transform there? What are F1 and F2?
>>>
>>
>> Given that zipped_with can result a zipped transform iterator, and F1
>> and F2 are the types of the functions used/provided with zip_with.
>
> I do not understand. Why you have both map and transform in the same
> expression? Map and transform are the same thing, why do you use two
> different names?
>
> IMHO zipWith(r1, r2, f) should return
>
>   mapped_range< zipped_range<R1, R2>, F >
>
> Which is the same as map(zip(r1, r2), f).
>

Actually, I was thinking more:

  zip_with(r1, r2, f1, f2)

Where you get:

  zipped_range< mapped_range<R1, F1>, mapped_range<R2, F2> >.

Without variadic templates though it would have to look like:

  zip_with( make_tuple(r1, r2), make_tuple(f1, f2) );

In turn, you get a zipped range, where each element is an iterator to
a tuple that is the result of the operation f1(*r1_it) and f2(*r2_it),
and so on.

>>
>> Which is precisely what can be implemented with lazy_range<...>. :D
>
> See attached for rewrite rules implemented *without* lazy_range.
>

I understand that this can be implemented without lazy_range, but the
point of using expression templates to build the lazy_range is to be
able to implement the rewrite rules as part of the lazy_range
implementation.

-- 
Dean Michael C. Berris
Software Engineer, Friendster, Inc.