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

On Thu, Jun 18, 2015 at 4:27 PM, Louis Dionne wrote:

Zach Laine writes:

...

On Wed, Jun 17, 2015 at 9:58 AM, Louis Dionne

wrote:

...

...

Zach Laine 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 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 xs{...}; hana::tuple 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