Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)

Subject: Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-06-11 15:39:19

Oleg Grunin <ogrunin <at> yahoo.com> writes:

>
> Louis Dionne <ldionne.2 <at> gmail.com> writes:
>
> > > [...]
> >
> > Indeed, you are using a Map when what you really want is a Tuple, since
> > your keys are integers. Here's the version I would have written:
> >
> >     #include <boost/hana/integral_constant.hpp>
> >     #include <boost/hana/range.hpp>
> >     #include <boost/hana/tuple.hpp>
> >     using namespace boost::hana;
> >
> >     static constexpr int map_size = 100;
> >
> >     void run() {
> >       constexpr auto hana_range = range(int_<0>, int_<map_size>);
> >       auto hana_tuple = unpack(hana_range, [](auto ...n) {
> >         return tuple_t<std::array<char, decltype(n)::value>...>;
> >       });
> >
> >       auto Array = hana_tuple[int_<69>];
> >
> >       // instantiate the array
> >       constexpr decltype(Array)::type arr = {{0}};
> >       static_assert(sizeof(arr) == 69, "");
> >     }
> >
> > However, I can easily imagine another example where you actually need
> > the functionality of a Map. See below for performance comments.
> >
> Indeed, I used a range just to compress the code. It could have been:
>  typedef mpl::joint_view<mpl::range_c<int, 0, 50>, mpl::range_c<int, 51,
> 100> > mpl_range, which would likely not work with a tuple.
> Btw, I couldn't find a way to combine several ranges with hana.

I understand your reason for using a Map. You can't directly concatenate
Ranges with Hana, but you can concatenate them if you put them into Tuples
first, and what you get is a Tuple of IntegralConstants:

    constexpr auto xs = concat(
        to<Tuple>(range(int_<-10>, int_<0>)),
        to<Tuple>(range(int_<0>, int_<10>))
    );

> > 1. Clang generates horrible code for your example. I think the fault is
> >    principally on the compiler, since it generates perfect code for up
> >    to ~20 elements, and then starts emitting complete crap. I'll follow
> >    up with the Clang team about this.
> >
>
>  I hope they'll take it up, since it's the only compiler capable of
> compiling this code.

I hope so too. I have reduced the problem to what I think is an inlining
problem. This might be solved by a mixture of

1. Marking functions `inline` more aggressively by Hana and ensuring they
   have internal linkage so that they don't have to be emitted for nothing.

2. Compressing the storage of empty objects in Hana's containers. I have
   implemented this locally, and I can confirm it solves the runtime
   performance issue completely. The assembly generated by your original
   code and the MPL are now 100% identical. I'll push this to Hana's
   develop branch soon, but the patch still needs some work.

3. Having a better optimization of empty structures in Clang.

For reference, the bug report I filed is at [1].

> > 2. The fault is also partially on the library, which does not compress
> >    the storage of empty types right now. Hence, your compile-time map,
> >    which contains (int_<...>, type<...>) pairs, actually has a huge
> >    sizeof, whereas it should have sizeof(char) since all those pairs
> >    are empty.
> >
> >    Indeed, I was able to make the runtime performance issue go away by
> >    compressing the storage of empty types in Hana pairs. I opened an
> >    issue [2] to track the progress of this feature. By the way, I
> >    consider this a high priority feature.
> >
> >  [...]
> > As you can see, only your original Map example is bad, and it starts
> > sudenly at about 30 elements, which reinforces my thinking that it's
> > a compiler bug or quality of implementation issue. As you can see, my
> > version using Hana Tuple is indeed 0 overhead, just like the MPL. I am
> > confident that compressing empty types and making the Map implementation
> > more clever should resolve the issue you presented.
>
>  I wish there was a deterministic, language enforced way, to make sure
> that stuff intended to be compile-time stayed as such. Relying on an
> optimizer isn't all that comforting in this case. Although, it maybe
> that the lack of constexpr lambda's makes it impossible.

If constexpr lambdas were allowed, you could simply stick constexpr in front
of it and you would indeed be guaranteed that it is evaluated at compile-time.
Another way to go is to enclose the whole compile-time computation into
decltype, like I did in the Gist I posted [2]:

    static constexpr int INPUT_SIZE = ...;
    static constexpr int INDEX = (INPUT_SIZE * 2) / 3;

    void run() {
        auto get_array = [](auto index) {
            auto inserter = [](auto map, auto n) {
                using Array = std::array<char, decltype(n)::value>;
                return insert(map, make_pair(n, type<Array>));
            };

            auto arrays = fold.left(range(int_<0>, int_<INPUT_SIZE>),
                                    make_map(),
                                    inserter);
            return arrays[index];
        };

        constexpr decltype(get_array(int_<INDEX>))::type array{};
        //                 ^^^^^^^^^ whole computation inside decltype
        static_assert(array.size() == INDEX, "");
    }

This ensures that the computation is done at compile-time, and the
`get_array` function is never actually used. It is only used to force
the compiler to perform a compile-time computation of the lambda's
return type, which is what we're interested in.

I find if slightly inconvenient to write everything like that, however.

> > > Also it appears that Hana lets the compiler swallow all kinds of code
> > > that doesn't appear to have any practical meaning:
> > >
> > > I understand (maybe erroneously) that a hana::map can have a useful
> > > application only if its keys are compile-time constructs, and yet I
> > > was able to compile:
> > > make_map(make_pair(1, "one"), make_pair(2, "two"));
> >
> > You are correct when you state that Hana Maps require the keys to be
> > comparable at compile-time, i.e. the comparison of two keys must return
> > an IntegralConstant.
> >
> > The above usage, which is generally meaningless, is impossible to catch
> > at compile-time in general, because the type of the object returned by
> > the comparison of 1 with something else may depend on that something
> > else. In other words, we can only flag the above usage if there exists
> > no 'x' (of any type) such that '1 == x' returns an IntegralConstant.
> > However there is no way to assess that in general.
> >
>
> I am probably missing something, but can't you check that the first
> element of every pair going into the map is a compile-time constant.

No, because not only compile-time constants can be used as the keys of a Map.
For example, you can use a Type to index a Map:

    auto map = make_map(
        make_pair(int_<1>, "1"s),
        make_pair(type<int>, "int"s)
    );

    assert(map[int_<1>] == "1"s);
    assert(map[type<int>] == "int"s);

More generally, anything that can be compared at compile-time can be used
as a key in a Map. Hence, the following code is perfectly valid, even though
the keys are not compile-time constants (in the usual sense):

    auto map = make_map(
        make_pair(tuple_t<int, char, float>, "[int, char, float]"s),
        make_pair(make_tuple(type<int>, int_<2>), "[int, 2]"s)
    );

    assert((map[tuple_t<int, char, float>] == "[int, char, float]"s));
    assert(map[make_tuple(type<int>, int_<2>)] == "[int, 2]"s);

> Isn't (1 == anything) either a bool or a compile-time error, whereas
> int_<1> == anything is always a bool_<> or error?

For 1 == anything, you are right. Let's instead focus on the result
of Hana's `equal` function, which performs a comparison on possibly
heterogeneous values. `equal(1, anything)` is either a bool or an
IntegralConstant. Roughly speaking, it is

- a bool equivalent to `1 == anything` when 1 and `anything` are
  EqualityComparable, as the standard defines it.

- the IntegralConstant false_ when 1 and `anything` are completely
  unrelated. Roughly speaking, they are unrelated when they don't
  have a common type.

Heterogeneity makes things slightly more complex than they are in the
usual world. If we did not return false_ for comparisons of unrelated
objects, the following would trigger a compilation error because of the
comparison between int and std::string:

    auto xs = make_tuple(1, 2, 3);
    auto c = contains(xs, std::string{"abcdef"});

Instead, in a heterogeneous setting, you probably want it to return false_.
With Fusion/MPL, this is not a problem because they use `std::is_same` to
perform comparisons. However, `std::is_same` performs a very shallow
comparison and only allows comparing types. Instead, Hana uses a more
general system which also allows comparing values, but we have to return
false_ for unrelated objects, a bit like `std::is_same` returns
`std::false_type` on unrelated types.

> Thanks for your more than exhaustive reply.

Thanks for your challenging questions and observations.

Regards,
Louis

[1]: https://llvm.org/bugs/show_bug.cgi?id=23818
[2]: https://goo.gl/TpxR7v