5
\$\begingroup\$

This is the 2nd iteration of a code review. The 1st iteration (completed) is at
Iter 1: 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.

2. Current Approach

Since C++17, the standard library provides the specialization hash<string_view> which is used to produce the initial hash value.
First, the magnitude data of the big integer is wrapped into a string_view and then its hash value is calculated using hash<string_view>. This produces an initial hash value which only depends on the magnitude, but not on the sign, of the big integer.
To keep the hashes of positive and negative big integers different, the initial hash value is scrambled once for negative big integers only.

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 <cstddef>
#include <string_view>

constexpr size_t pi_size_t() {
    if (sizeof(size_t) == 4) {
        return 0xc90fdaa2; // floor(pi/4 * 2^32)
    } else if (sizeof(size_t) == 8) {
        return 0xc90fdaa22168c234; // floor(pi/4 * 2^64)
    } else {
        throw std::logic_error(
                "sizeof(size_t) not supported. only 32 or 64 bits are supported. you can easily add the required code for other sizes.");
    }
}

inline size_t scramble(size_t v) {
    return v ^ (pi_size_t() + (v << 6) + (v >> 2));
}

namespace std {

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

    // produce different hashes for negative x
    if (x->_mp_size < 0) {
        result = scramble(result);
    }

    return result;
}

size_t hash<mpz_t>::operator()(const mpz_t x) const {
    return hash<mpz_srcptr> { }(static_cast<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;
    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;
}

4. Question

Is there anything which can benefit from further improvement?

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

Make functions that should not be exported static

Functions that should only be available locally should be marked static. This applies to pi_size_t() and scramble() in hash_mpz.cpp.

Avoid using std::endl

Use "\n" instead of std::endl, the latter is equivalent to "\n", but also forces a flush of the output. This is rarely necessary, and might hurt performance, especially when writing to a file, or when standard output is redirected to a file.

Consider not using namespace std

It's very good that you are not using namespace std in the header files. But consider not using it at all, since even if only used in .cpp files it can result in namespace conflicts that are hard to debug. If you do find yourself typing std:: a lot and want to avoid it, consider only importing the names that you do use from std::, like so:

using std::cout;
using std::unordered_map;

Final nitpicks

  • There's still one unnecessary std:: inside the namespace std block in hash_mpz.cpp.
  • You don't need return 0 at the end of main().
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Regarding your sentence "Functions that should only be available locally should be marked static.", does "locally" mean "inside of the same file"? \$\endgroup\$ – Daniel S. Jul 6 at 9:14
  • \$\begingroup\$ Yes. Inside the same translation unit to be precise. \$\endgroup\$ – G. Sliepen Jul 6 at 9:26
0
\$\begingroup\$

You're not my library!

I think it unwise to add additional symbols to std. It's great to use a namespace for the purpose of defining a library, but it's both surprising and confusing for a third-party user to need to use std to get your code which is not STL code. Just make your own name.

| improve this answer | |
\$\endgroup\$

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.