On 20/03/2015 17:13, costis glynos wrote:

On 20/03/2015 16:59, costis glynos wrote:

...

...

Hello,Is there any interest in a library which automatically sorts types from smallest to largest at compile time?The benefit would be the automatic Data Structure Alignment and potential improvement in performance.Foo<int,bool,Custom16ByteType,char,double,short> foo_1; //normal Foo<int,bool,Custom16ByteType,char,double,short> foo_2; //using the TypeSort output: size of foo_1 = 48 size of foo_2 = 32 Kind Regards,

...

There is already a sort meta-function in Boost.MPL. <http://www.boost.org/doc/libs/1_57_0/libs/mpl/doc/refmanual/sort.html>

Sweet! Thanks for bringing this to my attention.

You also need to use Boost.Fusion to make it into a tuple at the end, since this is what you want. Here is an example: #include <boost/mpl/sort.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/sizeof.hpp> #include <boost/fusion/include/as_vector.hpp> #include <boost/fusion/adapted/mpl.hpp> #include <iostream> int main() { namespace mpl = boost::mpl; namespace fusion = boost::fusion; typedef mpl::vector<short, int, short> types; typedef mpl::sort<types, mpl::less< mpl::sizeof_<mpl::_1> , mpl::sizeof_<mpl::_2> > >::type sorted_types; typedef fusion::result_of::as_vector<sorted_types>::type tuple; tuple t; std::cout << sizeof(t) << std::endl; // 8 instead of 12 } This appears to work.

On 20/03/2015 17:49, costis glynos wrote:

...

You also need to use Boost.Fusion to make it into a tuple at the end, since this is what you want.

Here is an example:

#include <boost/mpl/sort.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/sizeof.hpp> #include <boost/fusion/include/as_vector.hpp> #include <boost/fusion/adapted/mpl.hpp> #include <iostream>

int main() { namespace mpl = boost::mpl; namespace fusion = boost::fusion;

typedef mpl::vector<short, int, short> types; typedef mpl::sort<types, mpl::less< mpl::sizeof_<mpl::_1> , mpl::sizeof_<mpl::_2> > >::type sorted_types; typedef fusion::result_of::as_vector<sorted_types>::type tuple;

tuple t; std::cout << sizeof(t) << std::endl; // 8 instead of 12 }

This appears to work.

That's fantastic! Thank you for your recommendation.

You probably need to be able to access the final tuple with the original indices though, which is a bit more involved. #include <boost/mpl/sort.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/range_c.hpp> #include <boost/mpl/transform.hpp> #include <boost/mpl/front.hpp> #include <boost/mpl/back.hpp> #include <boost/mpl/zip_view.hpp> #include <boost/mpl/copy.hpp> #include <boost/mpl/sizeof.hpp> #include <boost/mpl/at.hpp> #include <boost/fusion/include/as_vector.hpp> #include <boost/fusion/include/at.hpp> #include <boost/fusion/adapted/mpl.hpp> #include <iostream> int main() { namespace mpl = boost::mpl; namespace fusion = boost::fusion; typedef mpl::vector<short, int, short> types; typedef mpl::copy< mpl::zip_view< mpl::vector< types , mpl::range_c<long, 0L, mpl::size<types>::value> > > , mpl::back_inserter< mpl::vector0<> >

::type indexes_types; typedef mpl::sort< indexes_types , mpl::less< mpl::sizeof_< mpl::front<mpl::_1> > , mpl::sizeof_< mpl::front<mpl::_2> > > ::type indexes_types_sorted; typedef mpl::transform< indexes_types_sorted , mpl::front<mpl::_1> ::type sorted_types; typedef mpl::transform< indexes_types_sorted , mpl::back<mpl::_1> ::type sorted_indexes; typedef fusion::result_of::as_vector<sorted_types>::type tuple;

tuple t; std::cout << sizeof( fusion::at_c<mpl::at_c<sorted_indexes, 0>::type::value>(t) ) << std::endl; std::cout << sizeof( fusion::at_c<mpl::at_c<sorted_indexes, 1>::type::value>(t) ) << std::endl; std::cout << sizeof( fusion::at_c<mpl::at_c<sorted_indexes, 2>::type::value>(t) ) << std::endl; } This could make an interesting addition to Boost.Fusion.

Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:

[...]

You probably need to be able to access the final tuple with the original indices though, which is a bit more involved.

[...code...]

This could make an interesting addition to Boost.Fusion.

As a simple curiosity, here's how this could be implemented with Hana: ------------------------------------------------------------------------------ #include <boost/hana/functional.hpp> #include <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> #include <boost/hana/type.hpp> #include <iostream> namespace hana = boost::hana; using namespace hana::literals; int main() { auto types = hana::tuple_t<short, int, short>; auto indexed_types = hana::zip( types, hana::to<hana::Tuple>(hana::range(0_c, hana::size(types))) ); auto sorted_indexed_types = hana::sort_by([](auto t, auto u) { return hana::sizeof_(t[0_c]) < hana::sizeof_(u[0_c]); }, indexed_types); auto sorted_types = hana::transform(sorted_indexed_types, hana::head); auto sorted_indices = hana::transform(sorted_indexed_types, hana::last); using tuple = decltype( hana::unpack(sorted_types, hana::template_<hana::_tuple>) )::type; tuple t; std::cout << sizeof(t[sorted_indices[0_c]]) << std::endl; std::cout << sizeof(t[sorted_indices[1_c]]) << std::endl; std::cout << sizeof(t[sorted_indices[2_c]]) << std::endl; } ------------------------------------------------------------------------------ It's essentially the same thing than with MPL/Fusion, except there's a bit more syntactic sugar because of C++14 features. Also, this example showcases how low the syntactic cost of the MPL/Fusion unification is. The only place where we need to bridge between types and values is using tuple = decltype( hana::unpack(sorted_types, hana::template_<hana::_tuple>) )::type; which is (IMO) not too cumbersome. Regards, Louis P.S.: I know the order of the arguments to sort_by is backwards. I'm working on a consistent scheme for these algorithms.

Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:

On 20/03/2015 19:44, Louis Dionne wrote:

...

It's essentially the same thing than with MPL/Fusion, except there's a bit more syntactic sugar because of C++14 features. Also, this example showcases how low the syntactic cost of the MPL/Fusion unification is. The only place where we need to bridge between types and values is

using tuple = decltype( hana::unpack(sorted_types, hana::template_<hana::_tuple>) )::type;

which is (IMO) not too cumbersome.

I find it very clear and nice to read (much nicer than the MPL code), except for that final tuple_t to _tuple conversion.

I had to read through the documentation to understand this bit, though I suppose something like a transform with [](auto t) { return make<typename decltype(t)::type>(); } would have worked too?

First, I am glad you find it pleasing to read. Regarding the final tuple_t to _tuple conversion, here is what happens. This is not directed towards you in particular, but to anyone else reading this who haven't read the docs: First, `unpack` is basically the equivalent to `apply` from the Fundamentals TS. It applies a tuple of arguments to a function. For example, given a sequence [x1, ..., xn]: unpack([x1, ..., xn], function) == function(x1, ..., xn) Second, `template_<F>` is a function object whose arguments are Types and which returns a Type. This works well with the intuition that C++ templates are nothing more than functions on types. Hence, template_<_tuple>(type<T1>, ..., type<Tn>) == type<_tuple<T1, ..., Tn>> The final twist is that a type<T> is a nullary metafunction in the MPL sense of the word. Hence, decltype(type<T>)::type is the same as T. In our example, this gives us: decltype(type<_tuple<T1, ..., Tn>>)::type which is the same as _tuple<T1, ..., Tn> Finally, as you suggest, creating the tuple would have been possible with transform(sorted_types, [](auto t) { using T = typename decltype(t)::type; return make<T>(); }); Regards, Louis

Eric Niebler <eniebler <at> boost.org> writes:

On 3/20/2015 11:44 AM, Louis Dionne wrote:

...

As a simple curiosity, here's how this could be implemented with Hana: <snip>

And using Meta:

[...]

Eric, abstracting the sort into an `indexed_sort` (meta)function is a great idea. Here's an updated version: ------------------------------------------------------------------------------ #include <boost/hana/integral_constant.hpp> #include <boost/hana/pair.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> #include <boost/hana/type.hpp> using namespace boost::hana; using namespace boost::hana::literals; auto indexed_sort = [](auto list, auto predicate) { auto indexed_list = zip(list, to<Tuple>(range(0_c, size(list)))); auto sorted = sort_by(predicate, indexed_list); return make_pair(transform(sorted, head), transform(sorted, last)); }; int main() { auto types = tuple_t<char[4], char[2], char[1], char[5], char[3]>; auto sorted = indexed_sort(types, [](auto t, auto u) { return sizeof_(t[0_c]) < sizeof_(u[0_c]); }); using Tup = decltype(unpack(first(sorted), template_<_tuple>))::type; auto indices = second(sorted); Tup tup; char(&a)[3] = tup[indices[0_c]]; char(&b)[2] = tup[indices[1_c]]; char(&c)[5] = tup[indices[2_c]]; } ------------------------------------------------------------------------------

FWIW, these indices don't seem all that useful to me. What exactly was the desired behavior?

No idea :-) Louis

Peter Dimov <lists <at> pdimov.com> writes:

Louis Dionne wrote:

...

Eric Niebler <eniebler <at> boost.org> writes: ...

...

FWIW, these indices don't seem all that useful to me. What exactly was the desired behavior?

No idea

The desired behavior was for indexing the sorted tuple to work like indexing the original tuple. That is, given tuple<char[4], char[2], char[1], char[5], char[3]>, you were supposed to produce another tuple for which get<0> still returns char[4], even though the first element is physically char[1].

Oh, yes of course. Then I think the original code did not do the right thing, or I made a mistake while translating it to Hana. Anyway, here's a version that does what was probably needed by the OP (notice the additional indexed_sort of the indices): ------------------------------------------------------------------------------ #include <boost/hana/integral_constant.hpp> #include <boost/hana/pair.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> #include <boost/hana/type.hpp> #include <type_traits> using namespace boost::hana; using namespace boost::hana::literals; auto indexed_sort = [](auto list, auto predicate) { auto indexed_list = zip(list, to<Tuple>(range(0_c, size(list)))); auto sorted = sort_by(predicate ^on^ head, indexed_list); return make_pair(transform(sorted, head), transform(sorted, last)); }; int main() { auto types = tuple_t<char[4], char[2], char[1], char[5], char[3]>; auto sorted = indexed_sort(types, [](auto t, auto u) { return sizeof_(t) < sizeof_(u); }); using Tup = decltype(unpack(first(sorted), template_<_tuple>))::type; auto indices = second(indexed_sort(second(sorted), less)); // When accessed through the indices sequence, the tuple appears to be // ordered as the `types` above. However, as can be seen in the // static_assert below, the tuple is actually ordered differently. Tup tup; char(&a)[4] = tup[indices[0_c]]; char(&b)[2] = tup[indices[1_c]]; char(&c)[1] = tup[indices[2_c]]; char(&d)[5] = tup[indices[3_c]]; char(&e)[3] = tup[indices[4_c]]; static_assert(std::is_same< Tup, _tuple<char[1], char[2], char[3], char[4], char[5]> >{}, ""); } ------------------------------------------------------------------------------ It should also be noted that Hana does not guarantee any particular layout for tuples. Hence, having _tuple<char[1], char[2], char[3], char[4], char[5]> does not mean that it's akin to a struct defined as struct { char member1[1]; char member2[2]; char member3[3]; char member4[4]; char member5[5]; }; Instead, if one requires a special layout, a new structure which ensures the right physical layout should be created. At the same time, this structure could take care of the indexing business to abstract it from the user. This can be done easily by using Hana's extension mechanism. Regards, Louis

(Trying again. EnigMail for Thunderbird seems deeply confused on my machine, sorry.) On 3/21/2015 11:52 PM, Louis Dionne wrote:

Anyway, here's a version that does what was probably needed by the OP (notice the additional indexed_sort of the indices):

------------------------------------------------------------------------------ #include <boost/hana/integral_constant.hpp> #include <boost/hana/pair.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> #include <boost/hana/type.hpp>

#include <type_traits> using namespace boost::hana; using namespace boost::hana::literals;

auto indexed_sort = [](auto list, auto predicate) { auto indexed_list = zip(list, to<Tuple>(range(0_c, size(list)))); auto sorted = sort_by(predicate ^on^ head, indexed_list); return make_pair(transform(sorted, head), transform(sorted, last)); };

int main() { auto types = tuple_t<char[4], char[2], char[1], char[5], char[3]>; auto sorted = indexed_sort(types, [](auto t, auto u) { return sizeof_(t) < sizeof_(u); }); using Tup = decltype(unpack(first(sorted), template_<_tuple>))::type; auto indices = second(indexed_sort(second(sorted), less));

// When accessed through the indices sequence, the tuple appears to be // ordered as the `types` above. However, as can be seen in the // static_assert below, the tuple is actually ordered differently. Tup tup; char(&a)[4] = tup[indices[0_c]]; char(&b)[2] = tup[indices[1_c]]; char(&c)[1] = tup[indices[2_c]]; char(&d)[5] = tup[indices[3_c]]; char(&e)[3] = tup[indices[4_c]];

static_assert(std::is_same< Tup, _tuple<char[1], char[2], char[3], char[4], char[5]> >{}, ""); } <snip>

Nice! Funny, I wrote pretty much the same code last night, right down to the use of the "on" combinator (which I discovered with the help of Hoogle, assuming rightly the Haskell guys had a name for such a useful utility). #include <tuple> #include <meta/meta.hpp> using namespace meta; namespace l = lazy; template<typename List, typename Pred = quote<less>> using indexed_sort1_ = let< var<struct _sorted_zip, sort<zip< list<List, as_list<make_index_sequence<List::size()>>>>, on<Pred, quote<first>>>>, pair<l::transform<_sorted_zip, quote<first>>, l::transform<_sorted_zip, quote<second>>>>; template<typename PairOfLists> using indexed_sort2_ = pair<first<PairOfLists>, second<indexed_sort1_<second<PairOfLists>>>>; template<typename List, typename Pred = quote<less>> using indexed_sort = indexed_sort2_<indexed_sort1_<List, Pred>>; int main() { using L = list<char[4],char[2],char[1],char[5],char[3]>; using P = indexed_sort<L, on<quote<less>, quote<sizeof_>>>; using Tup = apply_list<quote<std::tuple>, first<P>>; using Idx = second<P>; // list<int_<3>,int_<1>,int_<0>,int_<4>,int_<2>> Tup tup; // std::tuple<char[1],char[2],char[3],char[4],char[5]> char(&a)[4] = std::get<at_c<Idx, 0>::value>(tup); char(&b)[2] = std::get<at_c<Idx, 1>::value>(tup); char(&c)[1] = std::get<at_c<Idx, 2>::value>(tup); } The strange-looking let<var<_x,expr>,body> is a let expression that lets you create the equivalent of named local variables. It's good for storing intermediate results when you don't feel like farming work out to a separate helper alias. The whole thing could be written as one big let expression, actually. I tried it, but IMO this was more grokable. The Hana solution is elegant, too. (Strangely, clang-3.4 pukes on my code. Not sure about 3.5 or 3.6, but trunk likes it just fine, as does gcc 4.9.) -- Eric Niebler Boost.org http://www.boost.org

On 22/03/2015 07:52, Louis Dionne wrote:

Peter Dimov <lists <at> pdimov.com> writes:

...

Louis Dionne wrote:

...

Eric Niebler <eniebler <at> boost.org> writes: ...

...

FWIW, these indices don't seem all that useful to me. What exactly was the desired behavior?

No idea

The desired behavior was for indexing the sorted tuple to work like indexing the original tuple. That is, given tuple<char[4], char[2], char[1], char[5], char[3]>, you were supposed to produce another tuple for which get<0> still returns char[4], even though the first element is physically char[1].

Oh, yes of course. Then I think the original code did not do the right thing, or I made a mistake while translating it to Hana.

What's wrong with the original code?