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

Subject: Re: [boost] [Hana] Formal review for Hana
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2015-06-19 08:42:05

On Thu, Jun 18, 2015 at 4:27 PM, Louis Dionne <ldionne.2_at_[hidden]> wrote:

> 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?
>

I was using Hana tuples everywhere.  The issue is that even for those,
there is a k>1 when copying.  If that k is >2 for other types, it's an even
larger problem there.

>
> > [...]
> >
> > > 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?__
>

No, I'm trying to get rid of the temporary altogether.  We all know that
copies of temporaries get RVO'd out of code like the above a lot of the
time, *but not always*.  I want a guarantee that I don't need to rely on
RVO in a particular case, if efficiency is critical.

> 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.

 This is only true if there are only functional versions of Hana
algorithms.  Mutating ones can write straight into the result object, a la
the STL algorithms.

Zach