CODEWITHSUNDEEP
c++gccboostcompiler-optimization
alsuna
alsuna

Reputation: 73

boost::unordered_map::find produces different results depending on compiler optimization level while boost::unordered_map::insert produces the same

Using gcc 4.8.1 and libboost 1.53 I get different results depending on the optimization levels I use for compiling my code. As part of a larger program the function insertValues is executed twice for the same a, key and value:

/* Complex classes */
class A { /*....*/ }
class Value { /*.....*/ }
class SortedVector : public std::vector<T> { /*.....*/ }

/* Hash for the key */
struct KeyHash : std::unary_function<Key, size_t> {
    size_t operator()(Key const& x) const {
        size_t hash = x.get<0>();
        SortedVector<int>* xNumbers = x.get<2>();
        if(xNumbers != NULL) {
            BOOST_FOREACH(int num, *xNumbers) {
                MurmurHash3_x86_32(&num, sizeof(size_t), hash, &hash);
            }
        }
        return hash;
    }
};

/* Equals for the key */
struct KeyEqual : std::binary_function<Key, Key, bool> {
    size_t operator()(Key const& x, Key const& y) const {
        if(x.get<0>() != y.get<0>() || fabs(x.get<1>() - y.get<1>()) > 0.00001 || x.get<3>() != y.get<3>()) {
            return false;
        }

        SortedVector<int>* xNumbers = x.get<2>();
        SortedVector<int>* yNumbers = y.get<2>();
        if(xNumbers == yNumbers) {
            return true;
        }

        if(xNumbers == NULL || yNumbers == NULL) {
            return false;
        }

        if(xNumbers->size() != yNumbers->size()) {
            return false;
        }
        return std::equal(xNumbers->begin(), xNumbers->end(), yNumbers->begin());
    }
};

/* typedefs */
typedef boost::tuple<int, double, SortedVector<int>*, int> Key;
typedef boost::unordered_map<A, boost::unordered_map<Key, Value*, KeyHash, KeyEqual>, A::Hash, A::Equal> Map;

/* code that shows the problem */
void insertValues(A a, Key key, Value* value) {
    Map::iterator iter = map->find(a);
    if (iter == map->end()) {
        iter = map.insert(std::make_pair(a, Map::value_type::second_type())).first;
    }

    Map::value_type::second_type::iterator keyIter = iter->second.find(key);

    if (keyIter == iter->second.end()) {
        iter->second.insert(std::make_pair(key, value));
    }
}

Compiled with -O2 the keyIter is always equal to iter->second.end(), indicating that the key, value pair is not in the map. However, when run the second time, the insert does not insert the pair. After consulting the boost documentation for insert and find I come to the conclusion, that while find does not find the pair, insert finds it and rejects insertion.

Compiled with -O1 the code works as expected.

Does anyone have an insight, why find might produce different results with -O1 and -O2? Or why the lookup results of find and insert can differ?

The hashes make use of MurmurHash3_x86_32 from MurmurHash3. The system is an OpenSuse x86_64 GNU/Linux.

Upvotes: 2

Views: 215

Answers (2)

ecatmur
ecatmur

Reputation: 157404

The most likely source of the bug is your call to the hash function:

        BOOST_FOREACH(int num, *xNumbers) {
            MurmurHash3_x86_32(&num, sizeof(size_t), hash, &hash);
        }

You're using OpenSuse x86_64 GNU/Linux, which is an LP64 platform, so int is 32 bits while size_t (and long) is 64 bits wide. In the implementation of MurmurHash3_x86_32 the key is accessed bytewise and also by 32-bit block (uint32_t). This is OK, as it's allowed to alias signed and unsigned variants of the same integral type (and any trivially copyable type bytewise), and uint32_t must be unsigned int as there are no other fundamental unsigned 32-bit integral types on x86_64 Linux.

However, there are two bugs in this code. First, the len parameter should be the size of the key, but sizeof(size_t) is 8 on your platform, whereas int num is 4 bytes in size. This means that the hash function will read an undefined memory location (&num + 1), and an optimizing compiler is free to provide any value for this read or cause other undefined behavior.

Second, you supply &hash as the out parameter. But MurmurHash3_x86_32 writes to *out as uint32_t, and size_t cannot alias uint32_t as the two types are distinct arithmetic types and not signed/unsigned variants. This means that the write to hash has undefined behavior and an optimizing compiler is free to ignore this write or cause other undefined behavior.

Something like this would be more correct:

        std::uint32_t result;
        MurmurHash3_x86_32(xNumbers->data(),
            sizeof(*xNumbers->data()) * xNumbers->size(),
            hash, &result);
        hash ^= (static_cast<std::uint32_t>(hash) ^ result);

Note that contrary to your code this supplies all the xNumbers in a single call to the hash function. This is guaranteed to work as vector stores its elements contiguously, and is closer to how the hash function is intended to be used; it is not designed to be called repeatedly.

Upvotes: 5

Mark B
Mark B

Reputation: 96281

Your condition fabs(x.get<1>() - y.get<1>()) > 0.00001 can make different objects look the same to the container. You should just say x.get<1>() != y.get<1>().

Upvotes: 0

Related Questions