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 не вставляет пару. После консультации с boost documentation за insert и find Я пришел к выводу, что пока find не находит пару, insert находит и отклоняет ввод.

Скомпилировано с кодом -O1 код работает должным образом.

У кого-нибудь есть понимание, почему find может давать разные результаты с -O1 и -O2? Или почему результаты поиска find и insert могут отличаться?

Хеши используют MurmurHash3_x86_32 от MurmurHash3. Система представляет собой 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-битовому блоку (uint32_t). Это нормально, так как it's allowed to alias signed and unsigned variants of the same integral type (и любой тривиально скопируемый тип bytewise), а uint32_t должен быть unsigned int, так как нет никаких других фундаментальных неподписанных 32-битных интегральных типов на x86_64 Linux.

Однако в этом коде есть две ошибки. Во-первых, параметр 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 сохраняет свои элементы смежно и ближе к тому, как предполагается использовать хеш-функцию; он не предназначен для многократного вызова.

Answer 2

Ваше состояние fabs(x.get<1>() - y.get<1>()) > 0.00001 может сделать разные объекты одинаковыми с контейнером. Вы должны просто сказать x.get<1>() != y.get<1>().