c++ - boost::unordered_map::find 根据编译器优化级别产生不同的结果，而 boost::unordered_map::insert 产生相同的结果

Question

使用 gcc 4.8.1 和 libboost 1.53，根据我用于编译代码的优化级别，我得到了不同的结果。作为更大程序的一部分，函数 insertValues 对相同的 a、key 和 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));
    }
}

用-O2编译，keyIter总是等于iter->second.end()，说明key , value 对不在 map 中。但是，第二次运行时，insert 不会插入对。经咨询boost documentation对于 insert 和 find 我得出的结论是，虽然 find 没有找到这对，但是 insert 找到了并拒绝插入。

使用 -O1 编译，代码按预期工作。

有没有人知道为什么 find 可能与 -O1 和 -O2 产生不同的结果？或者为什么 find 和 insert 的查找结果会不同？

哈希使用来自 MurmurHash3 的 MurmurHash3_x86_32 .该系统是 OpenSuse x86_64 GNU/Linux。

Answer 1

错误最可能的来源是您对哈希函数的调用:

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

您使用的是 OpenSuse x86_64 GNU/Linux，它是一个 LP64 平台，所以 int 是 32 位，而 size_t(和 long ) 为 64 位宽。在 the implementation of MurmurHash3_x86_32 key 可按字节访问，也可按 32 位 block (uint32_t) 访问。这没关系，因为 it's allowed to alias signed and unsigned variants of the same integral type (以及任何按字节方式简单复制的类型)，并且 uint32_t 必须是 unsigned int，因为在 x86_64 Linux 上没有其他基本的无符号 32 位整数类型。

但是，这段代码中有两个错误。首先，len 参数应该是 key 的大小，但是 sizeof(size_t) 在您的平台上是 8，而 int num 的大小为 4 个字节。这意味着哈希函数将读取未定义的内存位置 (&num + 1)，并且优化编译器可以自由地为此读取提供任何值或导致其他未定义的行为。

其次，您提供 &hash 作为 out 参数。但是 MurmurHash3_x86_32 写入 *out 为 uint32_t，而 size_t 不能将 uint32_t 别名为这两种类型是不同的算术类型，而不是有符号/无符号变体。这意味着对 hash 的写入具有未定义的行为，并且优化编译器可以自由地忽略此写入或导致其他未定义的行为。

像这样会更正确:

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

请注意，与您的代码相反，这会在对哈希函数的一次调用中提供所有 xNumbers。这保证可以作为 vector 连续存储其元素，并且更接近散列函数的预期使用方式；它不是为重复调用而设计的。