5
\$\begingroup\$

This Q&A was iteration 1. Now there is
Iter 2: Reusable, robust c++ std::hash<mpz_class> for GMP's big integer type

1. Goal

My intention is to provide a fast hashing algorithm to hash GMP's big integer type mpz_class and mpz_t so I can use these types as keys for an unordered_map. The code shall be reusable for others.

cf. my stackoverflow question about this topic

2. My Approach

I've written the C++ glue code to use MurmurHash3 to hash a GMP big integer. The questions about the code are at the bottom of this post.

3. Code

File hash_mpz.h:

#ifndef HASH_MPZ_H_
#define HASH_MPZ_H_

#include <gmpxx.h>

namespace std {

template<> struct hash<mpz_srcptr> {
    size_t operator()(const mpz_srcptr x) const;
};

template<> struct hash<mpz_t> {
    size_t operator()(const mpz_t &x) const;
};

template<> struct hash<mpz_class> {
    size_t operator()(const mpz_class &x) const;
};

}

#endif /* HASH_MPZ_H_ */

File hash_mpz.cpp:

#include "hash_mpz.h"
#include "MurmurHash3.h"

size_t MurmurHash3_size_t(const void *key, int len, uint32_t seed) {

#if SIZE_MAX==0xffffffff
    size_t result;
    MurmurHash3_x86_32(key, len, seed, &result);
    return result;

#elif SIZE_MAX==0xffffffffffffffff
    size_t result[2];
    MurmurHash3_x64_128(key, len, seed, &result);
    return result[0] ^ result[1];

#else
#error cannot determine correct version of MurmurHash3, because SIZE_MAX is neither 0xffffffff nor 0xffffffffffffffff
#endif

}

namespace std {

size_t hash<mpz_srcptr>::operator()(const mpz_srcptr x) const {
    // found 1846872219 by randomly typing digits on my keyboard
    return MurmurHash3_size_t(x->_mp_d, x->_mp_size * sizeof(mp_limb_t),
            1846872219);
}

size_t hash<mpz_t>::operator()(const mpz_t &x) const {
    return hash<mpz_srcptr> { }((mpz_srcptr) x);
}

size_t hash<mpz_class>::operator()(const mpz_class &x) const {
    return hash<mpz_srcptr> { }(x.get_mpz_t());
}

}

File main.cpp:

#include <iostream>
#include <gmpxx.h>
#include <unordered_map>

#include "hash_mpz.h"

using namespace std;

int main() {
    mpz_class a;

    mpz_ui_pow_ui(a.get_mpz_t(), 168, 16);

    cout << "a      : " << a << endl;
    cout << "hash(a): " << (hash<mpz_class> { }(a)) << endl;

    unordered_map<mpz_class, int> map;
    map[a] = 2;
    cout << "map[a] : " << map[a] << endl;

    return 0;
}

(click to view MurmurHash3.h)

4. Questions

4.1. In MurmurHash3_size_t(), I check SIZE_MAX to tell whether I'm on a 32 bit system or a 64 bit system. Does this check make sense, are there alternatives which are better?

4.2. Near the end of the file hash_mpz.cpp, I have the statement return hash<mpz_srcptr> { }(x.get_mpz_t());. Does this create an object of type hash<mpz_srcptr> for every calculated hash value?

4.3. I'm not sure whether I'm using the references const mpz_class &x and const mpz_t &x in the most efficient way. This is partly due to GMP being a C library, mpz_t is a 1 element array with element type __mpz_struct and mpz_class being something rather obscure to me.

Excerpt from gmp.h:

typedef struct
{
  int _mp_alloc;        /* Number of *limbs* allocated and pointed
                   to by the _mp_d field.  */
  int _mp_size;         /* abs(_mp_size) is the number of limbs the
                   last field points to.  If _mp_size is
                   negative this is a negative number.  */
  mp_limb_t *_mp_d;     /* Pointer to the limbs.  */
} __mpz_struct;

//...

typedef __mpz_struct mpz_t[1];

Excerpt from gmpxx.h:

typedef __gmp_expr<mpz_t, mpz_t> mpz_class;

4.4. Last but not least, do you see anything else which can be improved?

\$\endgroup\$
0
3
\$\begingroup\$

Answers to your questions

In MurmurHash3_size_t(), I check SIZE_MAX to tell whether I'm on a 32 bit system or a 64 bit system. Does this check make sense, are there alternatives which are better?

I think it's not worth it to write a generic version of this that avoids checking SIZE_MAX, even though that is possible. Machines with a different size_t size than 32 or 64 bits are uncommon, unless you're talking about 8 and 16 bit machines, but I'm assuming you are not interested in using bigints on those.

But don't forget to #include <cstdint>, otherwise SIZE_MAX might not be defined! Alternatively, use sizeof(size_t) == 4 and == 8, in combination with if constexpr (...) instead of #if ....

Near the end of the file hash_mpz.cpp, I have the statement return hash<mpz_srcptr> { }(x.get_mpz_t());. Does this create an object of type hash<mpz_srcptr> for every calculated hash value?

Technically, yet. But those objects don't have any member variables, just a member function operator(), which is resolved at compile-time, so there is no need to worry about inefficiencies here.

I'm not sure whether I'm using the references const mpz_class &x and const mpz_t &x in the most efficient way. This is partly due to GMP being a C library, mpz_t is a 1 element array with element type __mpz_struct and mpz_class being something rather obscure to me.

Using const references to the objects is perfectly fine.

Last but not least, do you see anything else which can be improved?

Yes, see below.

Your functions don't handle negative bigints correctly

As it mentions in the excerpt from gmp.h you posted, _mp_size will be negative for negative bigints. You need to handle this. One way would just be to write:

return MurmurHash3_size_t(..., abs(x->_mp_size) * sizeof(mp_limb_t), ...);

However, this means that for a given positive number, that number and its negative will get the same hash value. It may or may not be an issue for your application. One possible solution is to use a different seed value for negative numbers.

Consider using std::hash to calculate the hash

Yes, you can use std::hash instead of implementing your own. Of course, you need to pick an appropriate existing specialization std::hash. You could iterate over the limbs in the bignum, which are either 32 or 64 bit integers, so you could std::hash those individually, but then the questions is how to combine them. Just adding or XORing them might not result in a good final hash value if there are any patterns in the input. But in C++17, there is a specialization of std::hash for std::string_view. So you can create a view for the limb array, and hash that:

size_t hash<mpz_srcptr>::operator()(const mpz_srcptr x) const {
    std::string_view view{reinterpret_cast<char *>(x->_mp_d), abs(x->_mp_size) * sizeof(mp_limb_t)};
    return std::hash<std::string_view>{}(view);
}

There is a good chance that the standard library's hash function for strings is a variant of MurmurHash, see for example this question.

Use the appropriate cast operator instead of C-style casts

You should use static_cast<>() if possible to cast similar types, so the compiler will be able to generate an error if you are doing incorrect casts. For example:

size_t hash<mpz_t>::operator()(const mpz_t x) const {
    return hash<mpz_srcptr>{}(static_cast<mpz_srcptr>(x));
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ It's always a pleasure when an experienced wizard takes the effort to explain his magic spells and you have the opportunity to listen. 🎩 Thank you! \$\endgroup\$ – Daniel S. Jun 24 '20 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.