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 对不在映射中。但是，当运行第二次时， insert 不会插入对。在查阅 insert 和 find 的 boost documentation 之后，我得出结论，虽然 find 没有找到这对，但 insert 找到了它并拒绝插入。

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

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

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

Answer 1

您的条件 fabs(x.get<1>() - y.get<1>()) > 0.00001 可以使不同的对象在容器中看起来相同。你应该只说 x.get<1>() != y.get<1>().

Answer 2

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

        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 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 中（以及任何可按字节方式简单复制的类型），并且 uint32_t 必须是 unsigned int 因为 x86_64 [=52= 上没有其他基本的无符号 32 位整数类型].

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

其次，您提供 &hash 作为 out 参数。但是 MurmurHash3_x86_32 写入 *out 作为 uint32_t，并且 size_t 不能别名 uint32_t 因为这两种类型是不同的算术类型而不是 signed/unsigned 变体。这意味着对 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 连续存储其元素，并且更接近散列函数的预期使用方式；它不是为重复调用而设计的。

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

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

c++

gcc

boost

compiler-optimization