These are chat archives for boostorg/hana

25th
Jan 2016
Louis Dionne
@ldionne
Jan 25 2016 20:34
@ricejasonf The bummer right now is that I’m unable to come up with meaningful benchmarks for map lookup. It always seem to either (1) benchmark the creation of the map or (2) have so much noise the results are useless
If we could have a good way to benchmark map lookup, all the PRs related to maps could be closed or at least unblocked.
Jason Rice
@ricejasonf
Jan 25 2016 20:38
maybe we could hack clang to make our own profiler :P
doesn't your version of benchmark.at_key.lookup do the trick?
Louis Dionne
@ldionne
Jan 25 2016 20:40

maybe we could hack clang to make our own profiler

That would be great, but a lot of work. And perhaps it couldn’t be made to work properly, because we want to benchmark parsing + semantic analysis + optimization for a part of the code, but these are performed in different passes.

doesn't your version of benchmark.at_key.lookup do the trick?

No, not yet. I’m working on it now, but IDK if that will work. The problem is that without a proper benchmark, we could just as well be pessimizing the map implementation, which would be quite bad.

Jason Rice
@ricejasonf
Jan 25 2016 20:40
my original intent with that was to show that map was random access whereas tuple was a linear search
Louis Dionne
@ldionne
Jan 25 2016 20:42
The problem with your original benchmark.at_key.lookup is that it creates a map/tuple whose size grows as well as searching for the last element in it. However, the cost of creating the data structure itself is not negligible compared to the cost of looking up stuff in it. Basically, we end up measuring the compile-time of make<…> instead of find_if.
We’re really measuring both, but find_if is not isolated this way.
Jason Rice
@ricejasonf
Jan 25 2016 20:43
at_key.lookup was originally created to construct a map with a fixed size of 200 elements
maybe its more common to access n-elements in an n-size map
what if the expensive to create hash map was used only when n>50?
Jason Rice
@ricejasonf
Jan 25 2016 20:51
just spitballing
Louis Dionne
@ldionne
Jan 25 2016 20:53

at_key.lookup was originally created to construct a map with a fixed size of 200 elements

You are right, but it looked up the n-th element in the map, instead of looking up n distinct elements.

I think looking up n distinct elements in a fixed-size map is the most telling benchmark, but I could be wrong.
I’m running one like that right now.
Louis Dionne
@ldionne
Jan 25 2016 21:07
No wonder why I had weird results; debug mode was on and hana::make_map was checking for duplicates. I’m re-running now.
Jason Rice
@ricejasonf
Jan 25 2016 21:13
lol
I'm lost on the whole common embedding thing. I would expect this to not fail:
        static_assert(hana::is_embedded<
            hana::integral_constant<signed char, 42>
            , hana::integral_constant<signed short, 42>
        >::value, "");
Louis Dionne
@ldionne
Jan 25 2016 21:15
This should probably work.
Let me check why it doesn't
Jason Rice
@ricejasonf
Jan 25 2016 21:17
I wrote a test for hash to make sure types with common hash are able to be compared
what's weird is that hash is using is_embedded too
but always to signed long
hana::is_embedded<decltype(X::value), signed long>
Louis Dionne
@ldionne
Jan 25 2016 21:20
Why?
The reason why the above does not work is, I think, just an oversight.
Jason Rice
@ricejasonf
Jan 25 2016 21:22
if hana::is_embedded<decltype(X::value), signed long> then it hashes to an integral_constant of signed long
all I know is that any two items in a bucket need to not explode when called with hana::equal
Louis Dionne
@ldionne
Jan 25 2016 21:27

all I know is that any two items in a bucket need to not explode when called with hana::equal

That’s correct. I think this is annoying, but I don’t see any way to work around it.

@ricejasonf For hashing purposes, you should probably just use hana::is_convertible.
Jason Rice
@ricejasonf
Jan 25 2016 21:28
ok
Louis Dionne
@ldionne
Jan 25 2016 21:28
hana::is_embedded is just a way to convey the fact that “mathematical structure” is preserved by the conversion, but you don’t care about that when you are hashing.
Jason Rice
@ricejasonf
Jan 25 2016 21:32
In the ricejasonf/map PR, you'll see the test.map.hash_collision explodes in debug mode because the two values are actually equal (dups). What is a case where the hashes are the same but the values are not equal.
(assuming hashes of integral constants normalize to signed long or unsigned long respectively)
Louis Dionne
@ldionne
Jan 25 2016 21:40
Well.. I would indeed expect an error to be triggered, because integral_c<signed int, 42> == integral_c<signed char, 42>, aren’t they?
IOW, creating a map with key1 and key2 as you do in the test is not allowed, because these are duplicate keys.
Well, creating such a map with hana::make_map is not allowed.
Jason Rice
@ricejasonf
Jan 25 2016 21:47
Yes, what is a case that is allowed that will cause a bucket to contain two values because they have the same hash?
Louis Dionne
@ldionne
Jan 25 2016 21:53
Unless I’m mistaken, this should do the trick:
struct A { };
struct B { };


struct the_hash;

template <>
struct hash_impl<A> {
    static constexpr auto apply(A const&) {
        return hana::type_c<the_hash>;
    }
};

template <>
struct hash_impl<B> {
    static constexpr auto apply(B const&) {
        return hana::type_c<the_hash>;
    }
};


struct undefined { };

int main() {
    auto map = hana::make_map(
        hana::make_pair(A{}, undefined{}),
        hana::make_pair(B{}, undefined{})
    );

    // A{} and B{} have the same hash, but they are not equal.
    // Note that in order for this to work, A would have to be comparable
    // with itself, and B too.
}
Not tested, though.
Jason Rice
@ricejasonf
Jan 25 2016 21:54
yeah, hana::equal(A{}, B{}) would have to not explode.
Louis Dionne
@ldionne
Jan 25 2016 22:07
Well, you can probably define trivial comparisons for A == A and B == B that always return true.
By the way, if you have a better idea about how heterogeneous comparisons should be handled, say so. The current approach works well in most cases, and it is most of the time unsurprising, but sometimes it bites.
Jason Rice
@ricejasonf
Jan 25 2016 22:26
when it searches the bucket it is going to try A == B
Louis Dionne
@ldionne
Jan 25 2016 22:34
Yes, and that’s going to be false_c if I’m not mistaken.
#include <boost/hana.hpp>

struct A { };
struct B { };

static_assert(!hana::equal(A{}, B{}), "");
Jason Rice
@ricejasonf
Jan 25 2016 22:49
oh... maybe I'm having a complete brain fart.
:sweat_smile:
Louis Dionne
@ldionne
Jan 25 2016 22:50
Well.. What’s your question or issue?
Jason Rice
@ricejasonf
Jan 25 2016 23:05
keep in mind that I am a straight up noob :P
#include <boost/hana.hpp>

namespace hana = boost::hana;

using A = hana::integral_constant<signed char, 42>;
using B = hana::integral_constant<short, 42>;
using C = hana::integral_constant<int, 42>;
using D = hana::integral_constant<long, 42>;

static_assert(hana::is_convertible<A, hana::integral_constant<signed long, 42>>::value, "");
static_assert(hana::is_convertible<B, hana::integral_constant<signed long, 42>>::value, "");
static_assert(hana::is_convertible<C, hana::integral_constant<signed long, 42>>::value, "");
static_assert(hana::is_convertible<D, hana::integral_constant<signed long, 42>>::value, "");

int main() { }
So, I figured hashing any of those to a signed long would be appropriate...
equal works just find on those and it uses is_convertible but when I use it, it explodes.
Louis Dionne
@ldionne
Jan 25 2016 23:09
hana::is_convertible checks for the tags of objects:
#include <boost/hana.hpp>

namespace hana = boost::hana;

using A = hana::integral_constant<signed char, 42>;
using B = hana::integral_constant<short, 42>;
using C = hana::integral_constant<int, 42>;
using D = hana::integral_constant<long, 42>;

using E = hana::integral_constant<signed long, 42>;

static_assert(hana::is_convertible<hana::tag_of_t<A>, hana::tag_of_t<E>>::value, "");
static_assert(hana::is_convertible<hana::tag_of_t<B>, hana::tag_of_t<E>>::value, "");
static_assert(hana::is_convertible<hana::tag_of_t<C>, hana::tag_of_t<E>>::value, "");
static_assert(hana::is_convertible<hana::tag_of_t<D>, hana::tag_of_t<E>>::value, "");

int main() { }
Jason Rice
@ricejasonf
Jan 25 2016 23:09
ahh
Louis Dionne
@ldionne
Jan 25 2016 23:14
Does that fix the issue?
Jason Rice
@ricejasonf
Jan 25 2016 23:16
If I change E to unsigned long it still works.
I think I will just use std::is_signed.
Louis Dionne
@ldionne
Jan 25 2016 23:23
I think std::is_signed should be fine.
Jason Rice
@ricejasonf
Jan 25 2016 23:36
lol... It just hit me that the default equal_impl asserts that they are not convertible.
Louis Dionne
@ldionne
Jan 25 2016 23:37
Because if they are convertible, then you are comparing stuff that has no user-defined equality comparison, but that can still be converted one to another. This usually hides a programming error.
Jason Rice
@ricejasonf
Jan 25 2016 23:40
So how is test.map.hash_collision working at all. It should be exploding when it tries to compare key1 and key2.
sorry if I am being a pain :sweat_smile:
Louis Dionne
@ldionne
Jan 25 2016 23:41
No, no, it’s fine. I’ll try to figure out how this test works. I’ll brb later, dinner’s ready.
Jason Rice
@ricejasonf
Jan 25 2016 23:42
cool