On Mon, Jul 7, 2008 at 5:43 PM, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
On Mon, Jul 7, 2008 at 6:29 AM, Dean Michael Berris <mikhailberis@gmail.com> 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.