Re: [boost] [Hana] Formal review for Hana

Subject: Re: [boost] [Hana] Formal review for Hana
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-06-18 17:27:28

Zach Laine <whatwasthataddress <at> gmail.com> writes:

> 
> On Wed, Jun 17, 2015 at 9:58 AM, Louis Dionne <ldionne.2 <at> gmail.com> wrote:
> 
> > Zach Laine <whatwasthataddress <at> gmail.com> writes:
> >
> > >
> > > > [...]
> > > >
> > > > The current implementation of filter for Tuple will be as good as I
> > > > described.
> > > > The generic implementation for other sequence types (say an adapted
> > > > std::tuple)
> > > > will be slower. So there's room for improvement, of course.
> > > >
> > >
> > > When you say "slower" do you mean 2*N or N^2?
> >
> > Definitely more like 2*N. But I'll let you count . For generic
> > sequences,
> > the implementation is roughly equivalent to (once simplified):
> >
> . [...]
> >
> > So it's O(k*N) for some constant k (say k <= 10 to be safe), but not
> > O(N^2).
> 
> That will be unacceptably slow for many-to-most C++ users.

Can't you use Hana's Tuple, then? It's very hard to give good compile-time
performance and runtime performance without knowing the internal representation
of the data structures. One way to get good runtime performance is to use 
iterators and views like Fusion, but then you get lifetime issues. Hana takes
for granted that types should be cheap to move. If that's not the case, can't
you use a reference_wrapper or something like that?

> [...]
>
> > Also, it just occurred to me that some algorithms simply can't write their
> > result into an existing sequence, because the type of that resulting
> > sequence
> > isn't even known yet. Consider:
> >
> >     hana::tuple<A, B, C> xs;
> >     hana::tuple<?, ?, ?> result;
> >
> >     // should write the resulting sequence into 'result'.
> >     filter_mutate(xs, result, predicate);
> >
> > You don't know what's the type of the tuple before you have performed the
> > algorithm.
> 
> Right.  I can certainly live with only copy(), convert(), move(), and
> transform_mutate().

I don't easily see how these mutating algorithms would fit in Hana given
its functional design, but I'm not giving up. However, I suspect there 
might be better (read more functional :-) ways to achieve this optimal
performance.

To get there, I'd like to make sure I understand exactly what operation 
you're trying to avoid. Let's assume you wrote the following instead of 
a transform_mutate equivalent:

    hana::tuple<T...> xs{...};
    hana::tuple<U...> ys;
    ys = hana::transform(xs, f);

This will first apply f() to each element of xs(), and then store the 
temporary values in a (temporary) tuple by moving them into place. This 
will then move-assign each element from the temporary tuple into ys. 

__Is the first move what you are trying to avoid?__

Because in all cases, even with transform_mutate, at least one move is 
required, in order to assign the temporary return value of f() to the 
corresponding element of ys.

Regards,
Louis