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-13 10:52:11

Larry Evans <cppljevans <at> suddenlink.net> writes:

> 
> On 06/09/2015 11:00 AM, Louis Dionne wrote:
> [snip]
> > 
> > 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.
> > 
> [snip]
> Why couldn't map be implemented as a tuple, as shown here:
> 
> https://gist.github.com/cppljevans/8e545e8d83946cd74311
> 
> Wouldn't that eliminate the difference in performance between
> map and tuple?

The problem with this approach is that equality of keys can't be more general
than type identity. In other words, in your example, writing

    get<_ulong<1>>(mud)

would fail because there is no _ulong<1> key, but only a _uint<1>, even 
though they compare equal. I want to determine the equality of keys with 
the `equal` function, which is more general. Of course, in the specific 
case of a Map mapping types (and only types) to values, then your approach
could be used, and it is in fact exactly what I had in mind.

I had initially misunderstood your question and I wrote what follows. 
Instead of throwing it away, I'll just leave it here since it explains 
why Map's insert is inefficient in more detail:

------------------------------------------------------------------------------
The Map is currently implemented by using a Tuple for its internal storage. 
The problem is not really that the representation is inefficient, but rather 
that inserting in a Map is implemented like this (pseudo code):

    insert(map, {key, value}) {
        if (map contains key) 
            return map;
        else {
            new_storage = append {key, value} to map.storage, which is a tuple
            return a map with this new storage;
        }
    }

The most expensive part is looking whether the key is found inside the map.
Indeed, `contains(map, key)` is equivalent to `contains(map.storage, key)`,
which in turn is implemented as `any_of(map.storage, equal.to(key))`. This
`any_of` is the culprit; it is required to short circuit, and hence it must
be implemented recursively and rather inefficiently. In the general case of
a Tuple, this is mandatory to provide the semantics we want. However, in the
case of a Map, the storage is not guaranteed to be in any special order, so
we don't have to short circuit and we can then use a more efficient approach.
------------------------------------------------------------------------------

Regards,
Louis