[unordered_map]: Unexpected exception on value insertion

Johannes Brunen

21 Aug 2012 21 Aug '12

8:47 a.m.

Hello, My program is crashing (not handling an unexpected exception) on inserting a value into a unorderd map of type: unordered_map with struct Pnt3fHashT : public std::unary_function { std::size_t operator()(const osg::Pnt3f& pnt) const { std::size_t seed = 0; boost::hash_combine(seed, pnt[0]); boost::hash_combine(seed, pnt[1]); boost::hash_combine(seed, pnt[2]); return seed; } }; Pnt3f is a common 3D float point. The program is compiled with Microsoft Visual C++ 2008 9.0.30729.1SP 64Bit and Boost 1.48.0. The crash does only occur on 64Bit compilations. After inspection, I found the crash to be happening in the function inline std::size_t float_hash_impl2(T v) found in source hash_float_generic.hpp. Since the code looks fine for me I investigated the generated assembler code and found std::size_t seed = static_caststd::size_t(v); 000007FEE8A4D3C0 xor ecx,ecx 000007FEE8A4D3C2 movss xmm0,dword ptr [v] 000007FEE8A4D3CB comiss xmm0,dword ptr [__real@5f000000 (7FEE8FB7A34h)] 000007FEE8A4D3D2 jbe boost::hash_detail::float_hash_impl2<float>+0D2h (7FEE8A4D3F2h) 000007FEE8A4D3D4 subss xmm0,dword ptr [__real@5f000000 (7FEE8FB7A34h)] 000007FEE8A4D3DC comiss xmm0,dword ptr [__real@5f000000 (7FEE8FB7A34h)] 000007FEE8A4D3E3 jae boost::hash_detail::float_hash_impl2<float>+0D2h (7FEE8A4D3F2h) 000007FEE8A4D3E5 mov rax,8000000000000000h 000007FEE8A4D3EF add rcx,rax 000007FEE8A4D3F2 cvttss2si rax,xmm0 000007FEE8A4D3F7 add rax,rcx 000007FEE8A4D3FA mov qword ptr [seed],rax The crash happens at the 000007FEE8A4D3F2 cvttss2si rax,xmm0 instruction since the value in xmm0 is larger than the maximum signed 32bit integer. In this case depending on the settings an floating-point invalid exception is raised. It crashes since my code is not prepared for this exception. Now I have some questions: 1. Is it known that this mapping into the realm of 32Bit is happening for the above cast operation? 2. Is this a compiler bug? The generated assembler code does not allow 'safe' casting into 64bit integer? 3. Any advice how I should handle this situation? Best, Johannes ____________ Virus checked by G DATA AntiVirusKit Version: AVF 22.889 from 20.08.2012 Virus news: www.antiviruslab.com

Show replies by date

Daniel James

21 Aug 21 Aug

11:19 a.m.

On 21 August 2012 09:47, Johannes Brunen wrote:

...

Now I have some questions: 1. Is it known that this mapping into the realm of 32Bit is happening for the above cast operation? 2. Is this a compiler bug? The generated assembler code does not allow 'safe' casting into 64bit integer? 3. Any advice how I should handle this situation?

This is certainly surprising. I'll need to look into it some more, but the best course is probably to use a different technique for hashing floats with Visual C++. I'm already directly hashing the binary representation of floating point numbers on cygwin, so could probably do the same for Visual C++, it'll also be a bit quicker. I'm a bit surprised this wasn't caught by the unit tests. Can you try running the hash unit tests? They're at 'libs/functional/hash/test' - especially 'hash_float_test.cpp' and 'hash_long_double_test.cpp'.

Johannes Brunen

12:21 p.m.

New subject: [unordered_map]: Unexpected exception on valueinsertion

Hello Daniel, for some reason, we have set the control flag for raising invalid number exceptions. On default this is disabled*. The SSE2 instruction cvttss2si, which causes the problem, does return indefinite integer value (80000000H) if the exception is masked**. I.e. without taking proper action the unit test shouldn't see the problem? Additionally, the problem is 64 bit specific. On 32 bit it would be necessary to explicitely compile with SSE2 support. On 64 bit SSE2 is always used*. *http://msdn.microsoft.com/en-us/library/windows/hardware/ff545910%28v=vs.85%... **http://www.jaist.ac.jp/iscenter-new/mpc/altix/altixdata/opt/intel/vtune/doc/... I see two problems running the unit test: 1. I would have to setup the runtime for 64 bit including the mentioned exception mask. 2. I'm not proficient in the usage of the unit test framework. How can I change the hash function used for floats and doubles, respectively? Do you have an example for hashing the binary representation? I also use the multi_index container with a hashed_index on floats. I see the very same problems lurking on this side. If this is a real problem it might be worth to change the implementation of the hash function in general? Best Johannes "Daniel James" schrieb im Newsbeitrag news:CAHOE3yesZQhP0cg+FENf1WSmRMpEGfzNNQKC52PyHAHEaEPcjA@mail.gmail.com...

...

On 21 August 2012 09:47, Johannes Brunen wrote:

...
Now I have some questions: 1. Is it known that this mapping into the realm of 32Bit is happening for the above cast operation? 2. Is this a compiler bug? The generated assembler code does not allow 'safe' casting into 64bit integer? 3. Any advice how I should handle this situation?

This is certainly surprising. I'll need to look into it some more, but the best course is probably to use a different technique for hashing floats with Visual C++. I'm already directly hashing the binary representation of floating point numbers on cygwin, so could probably do the same for Visual C++, it'll also be a bit quicker.

I'm a bit surprised this wasn't caught by the unit tests. Can you try running the hash unit tests? They're at 'libs/functional/hash/test' - especially 'hash_float_test.cpp' and 'hash_long_double_test.cpp'.

Daniel James

12:51 p.m.

New subject: [unordered_map]: Unexpected exception on valueinsertion

On 21 August 2012 13:21, Johannes Brunen wrote:

...

I see two problems running the unit test: 1. I would have to setup the runtime for 64 bit including the mentioned exception mask. 2. I'm not proficient in the usage of the unit test framework.

You just need to build the .cpp file and run it. Each one is a self-contained program - no linking is required, just remember to add boost's root to the include path. So you can use whatever build setup you normally use.

...

How can I change the hash function used for floats and doubles, respectively? Do you have an example for hashing the binary representation?

I have to write it first. It's a change to the implementation.

...

I also use the multi_index container with a hashed_index on floats. I see the very same problems lurking on this side. If this is a real problem it might be worth to change the implementation of the hash function in general?

Yes, it's an issue in the hash function not the container.

Johannes Brunen

2:59 p.m.

New subject: [unordered_map]: Unexpected exception onvalueinsertion

Hello Daniel, I have succefully performed the two unit test. Below you can find the output. I have performed the test for my compiler in 32 and 64 bit with and without exception mask. The test are in accordance with my application. Best Johannes ================================================================================ 1. hash_float_test on msvc 2008 9.0.30729.1SP, 32Bit, no SSE2, no exception mask Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<float> boost::hash_detail::limits<T>::digits = 24 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = float boost::hash_detail::call_frexp<T>::float_type = float boost::hash_detail::select_hash_type<T>::type = float x1(infinity) == x1(-infinity) == 4294967295 x1(quiet_NaN) == x1(infinity) == 4294967295 x1(quiet_NaN) == x1(-infinity) == 4294967295 Testing boost::hash<double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = double boost::hash_detail::call_frexp<T>::float_type = double boost::hash_detail::select_hash_type<T>::type = double x1(infinity) == x1(-infinity) == 4294967295 x1(quiet_NaN) == x1(infinity) == 4294967295 x1(quiet_NaN) == x1(-infinity) == 4294967295 Drücken Sie eine beliebige Taste . . . ================================================================================ 2. hash_float_test on msvc 2008 9.0.30729.1SP, 64Bit, SSE2, no exception mask Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<float> boost::hash_detail::limits<T>::digits = 24 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 64 boost::hash_detail::call_ldexp<T>::float_type = float boost::hash_detail::call_frexp<T>::float_type = float boost::hash_detail::select_hash_type<T>::type = float x1(infinity) == x1(-infinity) == 2882303761517117439 x1(quiet_NaN) == x1(infinity) == 2882303761517117439 x1(quiet_NaN) == x1(-infinity) == 2882303761517117439 Testing boost::hash<double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 64 boost::hash_detail::call_ldexp<T>::float_type = double boost::hash_detail::call_frexp<T>::float_type = double boost::hash_detail::select_hash_type<T>::type = double x1(infinity) == x1(-infinity) == 2882303761517117439 x1(quiet_NaN) == x1(infinity) == 2882303761517117439 x1(quiet_NaN) == x1(-infinity) == 2882303761517117439 Drücken Sie eine beliebige Taste . . . ================================================================================ 3. hash_float_test on msvc 2008 9.0.30729.1SP, 32Bit, no SSE2, with exception mask unsigned int flag = _control87(0,0); _control87(0x0,_EM_ZERODIVIDE | _EM_INVALID | _EM_OVERFLOW); Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<float> boost::hash_detail::limits<T>::digits = 24 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = float boost::hash_detail::call_frexp<T>::float_type = float boost::hash_detail::select_hash_type<T>::type = float raise exception: T infinity = -log(zero); ================================================================================ 4. hash_float_test on msvc 2008 9.0.30729.1SP, 64Bit, SSE2, with exception mask unsigned int flag = _control87(0,0); _control87(0x0,_EM_ZERODIVIDE | _EM_INVALID | _EM_OVERFLOW); Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<float> boost::hash_detail::limits<T>::digits = 24 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 64 boost::hash_detail::call_ldexp<T>::float_type = float boost::hash_detail::call_frexp<T>::float_type = float boost::hash_detail::select_hash_type<T>::type = float raise exception: template <class T> inline std::size_t float_hash_impl2(T v) { boost::hash_detail::call_frexp<T> frexp; boost::hash_detail::call_ldexp<T> ldexp; int exp = 0; v = frexp(v, &exp); // A postive value is easier to hash, so combine the // sign with the exponent and use the absolute value. if(v < 0) { v = -v; exp += limits<T>::max_exponent - limits<T>::min_exponent; } v = ldexp(v, limitsstd::size_t::digits); -----> std::size_t seed = static_caststd::size_t(v); v -= static_cast<T>(seed); // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1; std::size_t const length = (limits<T>::digits * boost::static_log2::value + limitsstd::size_t::digits - 1) / limitsstd::size_t::digits; for(std::size_t i = 0; i != length; ++i) { v = ldexp(v, limitsstd::size_t::digits); std::size_t part = static_caststd::size_t(v); v -= static_cast<T>(part); hash_float_combine(seed, part); } hash_float_combine(seed, exp); return seed; } ================================================================================ 5. hash_long_double_test on msvc 2008 9.0.30729.1SP, 32Bit, SSE2, no exception mask Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<long double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = long double boost::hash_detail::call_frexp<T>::float_type = long double boost::hash_detail::select_hash_type<T>::type = long double x1(infinity) == x1(-infinity) == 4294967295 x1(quiet_NaN) == x1(infinity) == 4294967295 x1(quiet_NaN) == x1(-infinity) == 4294967295 Drücken Sie eine beliebige Taste . . . ================================================================================ 6. hash_long_double_test on msvc 2008 9.0.30729.1SP, 64Bit, SSE2, no exception mask Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<long double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = long double boost::hash_detail::call_frexp<T>::float_type = long double boost::hash_detail::select_hash_type<T>::type = long double x1(infinity) == x1(-infinity) == 4294967295 x1(quiet_NaN) == x1(infinity) == 4294967295 x1(quiet_NaN) == x1(-infinity) == 4294967295 Drücken Sie eine beliebige Taste . . . ================================================================================ 7. hash_long_double_test on msvc 2008 9.0.30729.1SP, 32Bit, SSE2, with exception mask unsigned int flag = _control87(0,0); _control87(0x0,_EM_ZERODIVIDE | _EM_INVALID | _EM_OVERFLOW); Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<long double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 32 boost::hash_detail::call_ldexp<T>::float_type = long double boost::hash_detail::call_frexp<T>::float_type = long double boost::hash_detail::select_hash_type<T>::type = long double raise exception: T infinity = -log(zero); ================================================================================ 8. hash_long_double_test on msvc 2008 9.0.30729.1SP, 64Bit, SSE2, with exception mask unsigned int flag = _control87(0,0); _control87(0x0,_EM_ZERODIVIDE | _EM_INVALID | _EM_OVERFLOW); Compiler: Microsoft Visual C++ version 9.0 Platform: Win32 Library: Dinkumware standard library version 505 Testing boost::hash<long double> boost::hash_detail::limits<T>::digits = 53 boost::hash_detail::limits<int>::digits = 31 boost::hash_detail::limitsstd::size_t::digits = 64 boost::hash_detail::call_ldexp<T>::float_type = long double boost::hash_detail::call_frexp<T>::float_type = long double boost::hash_detail::select_hash_type<T>::type = long double raise exception: template <class T> inline std::size_t float_hash_impl2(T v) { boost::hash_detail::call_frexp<T> frexp; boost::hash_detail::call_ldexp<T> ldexp; int exp = 0; v = frexp(v, &exp); // A postive value is easier to hash, so combine the // sign with the exponent and use the absolute value. if(v < 0) { v = -v; exp += limits<T>::max_exponent - limits<T>::min_exponent; } v = ldexp(v, limitsstd::size_t::digits); -----> std::size_t seed = static_caststd::size_t(v); v -= static_cast<T>(seed); // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1; std::size_t const length = (limits<T>::digits * boost::static_log2::value + limitsstd::size_t::digits - 1) / limitsstd::size_t::digits; for(std::size_t i = 0; i != length; ++i) { v = ldexp(v, limitsstd::size_t::digits); std::size_t part = static_caststd::size_t(v); v -= static_cast<T>(part); hash_float_combine(seed, part); } hash_float_combine(seed, exp); return seed; } v = ldexp(v, limitsstd::size_t::digits); 000000013F4240F1 mov r8d,40h 000000013F4240F7 movsd xmm1,mmword ptr [v] 000000013F424100 lea rcx,[ldexp] 000000013F424105 call boost::hash_detail::call_cpp_ldexpl<1>::operator()<int> (13F42107Dh) 000000013F42410A movsd mmword ptr [v],xmm0 std::size_t seed = static_caststd::size_t(v); 000000013F424113 xor ecx,ecx 000000013F424115 movsd xmm0,mmword ptr [v] 000000013F42411E comisd xmm0,mmword ptr [__real@43e0000000000000 (13F42E568h)] 000000013F424126 jbe boost::hash_detail::float_hash_impl2<long double>+0D7h (13F424147h) 000000013F424128 subsd xmm0,mmword ptr [__real@43e0000000000000 (13F42E568h)] 000000013F424130 comisd xmm0,mmword ptr [__real@43e0000000000000 (13F42E568h)] 000000013F424138 jae boost::hash_detail::float_hash_impl2<long double>+0D7h (13F424147h) 000000013F42413A mov rax,8000000000000000h 000000013F424144 add rcx,rax ---->000000013F424147 cvttsd2si rax,xmm0 000000013F42414C add rax,rcx 000000013F42414F mov qword ptr [seed],rax v -= static_cast<T>(seed); "Daniel James" schrieb im Newsbeitrag news:CAHOE3ycbT6fjMOcDvKcrk95UV4uwOgdkdjXLTN_D5a-OACU7BQ@mail.gmail.com...

...

On 21 August 2012 13:21, Johannes Brunen wrote:

...
I see two problems running the unit test: 1. I would have to setup the runtime for 64 bit including the mentioned exception mask. 2. I'm not proficient in the usage of the unit test framework.

You just need to build the .cpp file and run it. Each one is a self-contained program - no linking is required, just remember to add boost's root to the include path. So you can use whatever build setup you normally use.

...
How can I change the hash function used for floats and doubles, respectively? Do you have an example for hashing the binary representation?

I have to write it first. It's a change to the implementation.

...
I also use the multi_index container with a hashed_index on floats. I see the very same problems lurking on this side. If this is a real problem it might be worth to change the implementation of the hash function in general?

Yes, it's an issue in the hash function not the container.

4482

Age (days ago)

4482

Last active (days ago)

List overview

Download

4 comments

3 participants

participants (3)

Daniel James
Johannes Brunen
Johannes Brunen