These are chat archives for boostorg/hana

26th
Jan 2016
Louis Dionne
@ldionne
Jan 26 2016 00:24

When you compare hana::integral_constant<signed char, 42> and hana::integral_constant<signed int, 42>, it falls into this equal_impl specialization:

template <typename T, typename U>
struct equal_impl<T, U, when<
    detail::has_nontrivial_common_embedding<Comparable, T, U>::value &&
    !detail::EqualityComparable<T, U>::value
>> {
    using C = typename hana::common<T, U>::type;
    template <typename X, typename Y>
    static constexpr auto apply(X&& x, Y&& y) {
        return hana::equal(hana::to<C>(static_cast<X&&>(x)),
                           hana::to<C>(static_cast<Y&&>(y)));
    }
};

Note that T and U are hana::tag_of_t<hana::integral_constant<signed char, 42>> and hana::tag_of_t<hana::integral_constant<signed int, 42>>, respectively. In turn, those are hana::integral_constant_tag<signed char> and hana::integral_constant_tag<signed int>, respectively. They have a non-trivial common embedding to hana::integral_constant_tag<signed int>, so both keys are converted to it and then compared in this representation.

Jason Rice
@ricejasonf
Jan 26 2016 00:28
aha
Jason Rice
@ricejasonf
Jan 26 2016 00:48
char does not play well with others, not even unsigned char
I have no opinion on that btw.
..and unsigned char does not play with unsigned short
So, I'm thinking maybe char and unsigned char just get hashed to their identity.
Louis Dionne
@ldionne
Jan 26 2016 00:54
Why do they not play well?
What do you mean by that?
Jason Rice
@ricejasonf
Jan 26 2016 00:55
#include <boost/hana.hpp>

namespace hana = boost::hana;

using A = hana::integral_constant<unsigned char, 42>;
using B = hana::integral_constant<unsigned short, 42>;

int main() {
    //explodes
    hana::equal(A{}, B{});
}
but unsigned char and unsigned int work
and char with anything else does not work
Louis Dionne
@ldionne
Jan 26 2016 01:23
Why is std::common_type<unsigned char, unsigned short>::type equal to int?
Jason Rice
@ricejasonf
Jan 26 2016 01:30
maybe because their range could never exceed that of int?
Louis Dionne
@ldionne
Jan 26 2016 01:31
It seems to me that it should be unsigned int, no?
I understand what you mean.
I still dislike it.
Hmmmm.
Jason Rice
@ricejasonf
Jan 26 2016 01:32
ditto
Louis Dionne
@ldionne
Jan 26 2016 01:34
In all cases, the problem you’re running into above is caused by the fact that while unsigned char is embedded into unsigned short, their commont type is found to be int, to which they do not have an embedding.
#include <boost/hana.hpp>
namespace hana = boost::hana;

using A = hana::integral_constant<unsigned char, 42>;
using B = hana::integral_constant<unsigned short, 42>;

using T = hana::tag_of_t<A>;
using U = hana::tag_of_t<B>;

// fails
static_assert(hana::detail::has_nontrivial_common_embedding<
    hana::Comparable, T, U
>::value,"”);
Jason Rice
@ricejasonf
Jan 26 2016 01:36
Are you fine with 1_c != hana::char_c<1>?
Louis Dionne
@ldionne
Jan 26 2016 01:38
IDK what I’m fine with anymore! It seems like rules that would follow C++ more closely would be better.
They might be broken in several ways (as is C++), but at least they would stick closely to the language.
Jason Rice
@ricejasonf
Jan 26 2016 01:38
I'm going to make the hash function use taht has_nontrivial_common_embedding instead of is_signed
Louis Dionne
@ldionne
Jan 26 2016 01:39
Sure, you can do this for the time being. I’m currently considering getting rid of some of this complexity (and mathematical correctness, but whatever).
Jason Rice
@ricejasonf
Jan 26 2016 01:39
lol.. I'm not trying to stir anything up
:P
Louis Dionne
@ldionne
Jan 26 2016 01:40
You know, someone is inevitably going to bring this up when Hana is released with the rest of Boost and used by more people.
I might as well avoid 100 duplicate bug reports and change it now.
But my mind is not set on whether it must be change.d
Mathematically, comparing 1_c == char_c<1> does not make sense, because a char is a character, whereas 1 is a number.
Jason Rice
@ricejasonf
Jan 26 2016 01:41
right.. and I don't know why someone would want to do that in metaprogramming anyways
Louis Dionne
@ldionne
Jan 26 2016 01:42
Why would one want to do that in programming at all?
Appart, perhaps, from very low-level stuff where you manipulate bytes as unsigned chars..?
Jason Rice
@ricejasonf
Jan 26 2016 01:42
networking stuff
Louis Dionne
@ldionne
Jan 26 2016 01:42
Right.
Jason Rice
@ricejasonf
Jan 26 2016 04:18
gtg.. I'll be on tomorrow
Louis Dionne
@ldionne
Jan 26 2016 13:40
I would think the problem is that it can’t infer the whole of bucket<TypeHash, i…>. You can’t infer after expanding a parameter pack.
(here BucketsBefore…)
Louis Dionne
@ldionne
Jan 26 2016 13:45
@ricejasonf Regarding map benchmarks; I have written two benchmarks that are good, I think. Could you put your new map implementation(s) in experimental, so that we can easily benchmark different map implementations against each other?
Jason Rice
@ricejasonf
Jan 26 2016 17:36
I will.
BucketsBefore... and BucketsAfter... is just right out.
Jason Rice
@ricejasonf
Jan 26 2016 19:35
@ldionne I have not moved anything to experimental yet. I tried pushing the fixed version of ricejasonf/map, but it failed, citing conflicts. Is that just the benchmark stuff?
Louis Dionne
@ldionne
Jan 26 2016 19:37
Yes, it should be. Basically, you can discard the changes we did to the benchmarks in your PRs and just keep the other changes, which should rebase cleanly on top of develop.
Jason Rice
@ricejasonf
Jan 26 2016 19:50
@ldionne Of the "new map implementations", which ones should I put in experimental? (find_index_eager, actual hash map, and/or normalized type lookup)
Louis Dionne
@ldionne
Jan 26 2016 19:51
What is “normalized type lookup”? I thought there were two alternative implementations: the eager approach and the type-level hash one.
Jason Rice
@ricejasonf
Jan 26 2016 19:53
the one that did not permit hash collisions ie ignored Comparable and did type comparisons on the "hash"
Louis Dionne
@ldionne
Jan 26 2016 19:56
Do you have a link to this one? It does not ring a bell.
I have #226 and #242
I'll just clean it up and throw it in as experimental::map3 or something
Louis Dionne
@ldionne
Jan 26 2016 20:00
Yeah, ok. I’m fairly mixed up between all the branches and the PRs, now.
Just put each thing you think is worth taking a look at in a different experimental file, and then we’ll compare them all.
This detail::hash_table you linked above is not being used in the map implementation, right? Looking at <boost/hana/map.hpp> at the commit you linked above, hana::map seems to be implemented from scratch using buckets.
Jason Rice
@ricejasonf
Jan 26 2016 20:06
Oh yeah. In map.hpp it's using detail::map_hash_table because it is calling first. It will be cleaned up.
Louis Dionne
@ldionne
Jan 26 2016 20:09

Ok. Ideally, what I would like is to have two pull requests:

  1. #226 with the eager map lookup cleaned up, without changes to benchmarks and rebased on top of develop
  2. #242 with the hash table cleaned up, without changes to benchmarks and rebased on top of develop (not on top of #226, as it currently is)

Plus, each of these PRs would introduce whatever they introduce in the experimental namespace. This way, it will be easy to review and evaluate the compile-time tradeoffs of all approaches.

Jason Rice
@ricejasonf
Jan 26 2016 20:11
Ok. You don't want them all in the same branch?
Louis Dionne
@ldionne
Jan 26 2016 20:12
No, I’d rather have them as two separate PRs (as currently), because that will preserve a cleaner GitHub issues history.
Jason Rice
@ricejasonf
Jan 26 2016 20:12
ok
Louis Dionne
@ldionne
Jan 26 2016 20:13
What I’ll do then is simply merge both PRs (if they pass the tests), and throw away the least efficient implementation.
Or if they both are efficient but in different scenarios, we’ll have to talk about what we do
Jason Rice
@ricejasonf
Jan 26 2016 20:18
Do all of the test.map tests need to be duplicated for each experimental::map?
Louis Dionne
@ldionne
Jan 26 2016 20:18
Ah crap, I had not thought of this. It wouldn’t make much sense to duplicate them, but we do need a way of testing.
Hmm 1 minute
Jason Rice
@ricejasonf
Jan 26 2016 20:19
That's why I pushed ricejasonf/map to prove that it works.
in#242
ah crap...
Louis Dionne
@ldionne
Jan 26 2016 20:22
Well, the only other way I see would be to just have two PRs that replace the current map (as you did), but that’s not very convenient for testing both map implementations.
Ok; I’m fine if you just overwrite the current map implementation in each pull request, and not put everything in experimental.
I’ll generate the benchmarks on each branch and compare them this way.
So just make sure that each PR is cleaned up, rebased on top of develop and self-standing (i.e. I’d like #242 not to be on top of #226). Then, if everything passes, I’ll see which one I merge and how.
Jason Rice
@ricejasonf
Jan 26 2016 20:37
BTW I could put a static_assert inside the bucket insert to prevent duplicates. It would only do the check on hash collision which I think is rare. Should I do that in #242?
..and delete the has_duplicate check inside make_map
Louis Dionne
@ldionne
Jan 26 2016 20:38
This is a great idea.
Jason Rice
@ricejasonf
Jan 26 2016 20:38
ok
Louis Dionne
@ldionne
Jan 26 2016 20:38
It would greatly improve compile-times in debug mode.
Jason Rice
@ricejasonf
Jan 26 2016 20:39
Is there a way to make test pass if it fails to compile? :P
Louis Dionne
@ldionne
Jan 26 2016 20:39
I don’t understand?
Do you mean with CMake?
Jason Rice
@ricejasonf
Jan 26 2016 20:39
yes
Louis Dionne
@ldionne
Jan 26 2016 20:39
No, and that’s a real bummer.
Sometimes you can get away by SFINAE-ing on the thing you want to check, but if you want to check for a hard compilation error, then you’re out of luck.
Jason Rice
@ricejasonf
Jan 26 2016 23:41
/usr/local/src/hana/include/boost/hana/detail/hash_table.hpp:121:9: error: static_assert failed
      "Associative containers may not have duplicate keys."
maybe it should say "hash based containers"