News for hackers. Stuff that matters.
Re:GCC optimized code gives strange floating point results by emmelaich on Sunday February 26, 2017 @04:51PM (#13740139)
Is having a set of floats reasonable?
Re:GCC optimized code gives strange floating point results by int_19h on Sunday February 26, 2017 @05:17PM (#13740320)
That question should be immaterial from the perspective of the implementation. The question that they need to answer is, "does the standard for the language allow a set of floats, and require a certain behavior for it?". The answer is "yes" to both, and for the second answer, that behavior certainly doesn't include crashes.
Re:GCC optimized code gives strange floating point results by Negitivefrags on Sunday February 26, 2017 @05:01PM (#13740213)
Yes. There is nothing about floats that should make them unusable in a set.

In particular though, it's fairly common to use std::sets (or std::maps which use the same underlying data structure) to maintain something in a sorted order.

I ran into this myself when implementing A*. I was using an std::map with the float as key for the priority queue. Under GCC with default compile arguments it would randomly hang or crash due to GCC breaking the set invariant.

Re:GCC optimized code gives strange floating point results by Sharlin on Sunday February 26, 2017 @05:29PM (#13740390)
> Yes. There is nothing about floats that should make them unusable in a set.

Strictly speaking, there is. The < operator for floating-point types does not impose a strict weak order because NaNs are a thing.

In any case, comparing floating-point values for strict equality (instead of using an appropriate epsilon) is more often a bad idea than not.

Re:GCC optimized code gives strange floating point results by Someone on Sunday February 26, 2017 @06:52PM (#13740767)
But std::set doesn't use operator< for comparing values, but !(a<b) && !(b<a).

http://www.cplusplus.com/reference/set/set:

"Compare

A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines. The set object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a set container can be equivalent. This can be a function pointer or a function object (see constructor for an example). This defaults to less<T>, which returns the same as applying the less-than operator (a<b)."

I think that guarantees that std::set works for IEEE floating point values, and that NaNs are at the end of the set.

Re:GCC optimized code gives strange floating point results by DannyBee on Monday February 27, 2017 @12:37AM (#13742125)
"I think that guarantees that std::set works for IEEE floating point values, and that NaNs are at the end of the set. "

No, this is, by definition, not a strict weak order because it's not transitive. It also doesn't have transitivity of equivalence.

It's at best partial ordering. "strict weak" order is, by the way, such an incredibly stupid name it's hard to know where to begin (it's what they call it in math, but it doesn't make it any more sensible)

It's much easier to understand in terms of the invariants.

Partial orders: f(x, x) must be false.

f(x, y) implies !f(y, x)

f(x, y) and f(y, z) imply f(x, z).

Strict weak ordering: All of the above plus Define equivalence as f(x, y) and f(y, x) being both false. Then if x equivalent to y, and y equivalent to z, then x must be equivalent to z.

IE for all x, y, z: if f(x, y) and f(y, x) are both false, and f(y, z) and f(z,y) are both false, then f(x,z) and f(z, x) must both be false.

It's strict because it's not reflexive, and it's weak because b < a && a < b does not imply a == b. It just implies they are "equivalent", and as mentioned, you get a total ordering on the equivalence classes.

Re:GCC optimized code gives strange floating point results by Sharlin on Sunday February 26, 2017 @08:29PM (#13741188)
A strict weak order partitions a set of values into a collection of equivalence classes. Two values belong to different equivalence classes if and only if a<b or b<a. If either a or b is NaN, that condition is always false. Thus, every NaN is equivalent to every other value (regardless of the fact that no NaN is equal to any other value!)

However, any equivalence relation must be transitive, that is, if a≡b and b≡c then a≡c. Let a=1, c=2, and b=(any)NaN. We now have 1≡NaN and 2≡Nan which implies that 1≡2 which is clearly false. Thus, the < operator for floating-point types is not a strict weak order in the presence of NaNs.

Re:GCC optimized code gives strange floating point results by temac on Sunday February 26, 2017 @05:52PM (#13740482)
Well the thing is, it should not fail because of obscure reasons completely unrelated to NaNs...
Re:GCC optimized code gives strange floating point results by kobeya on Monday February 27, 2017 @12:01AM (#13742003)
It's also a credulous bug that a standard ordering isn't defined for NaNs.
Re:GCC optimized code gives strange floating point results by brucedawson on Monday February 27, 2017 @02:02AM (#13742430)
So, you want to redefine IEEE floats? 'cause it says that there is no ordering for NaNs.

And if you do redefine IEEE floats, where do NaNs go, and why is that better?

Re:GCC optimized code gives strange floating point results by kobeya on Monday February 27, 2017 @03:23AM (#13742766)
I'm saying IEEE shouldn't have defined them that way, yes. It was an arbitrary choice. As to where, before negative infinity or after positive infinity; I don't really care which. But the fact that we can't have good things (e.g. a standards compliant std::set<float>) because of a standards committee punted on making that choice makes me sad :(
Re:GCC optimized code gives strange floating point results by Sharlin on Monday February 27, 2017 @04:07AM (#13742912)
I do wonder why they didn't special-case std::less for floats. They already did it for pointers - operator< for pointers isn't even defined, much less a strict weak order, if the operands do not point to the same object (region of storage). This is in order to facilitate non-flat addressing schemes. std::less, however, is explicitly specified to work with any pair of pointers.
Re:GCC optimized code gives strange floating point results by emmelaich on Sunday February 26, 2017 @09:47PM (#13741461)
Thanks for the example. But I'd be wary of anything that involves comparing floats.

I wonder if you could make a template specialization for set of floats that would fix the problem. I suspect not easily.

I'll wander off and look at the source now ...

Re:GCC optimized code gives strange floating point results by Negitivefrags on Sunday February 26, 2017 @11:39PM (#13741908)
I suspect you are only wary of comparing floats due to Bug #323 in the first place though! Programmers have built up a lot of superstition when it comes to floats which they don't really deserve due to it.

There is a bizarre notion of non-determinism that plagues their reputation. People think that adding the same two numbers on two different CPUs can produce different results, or even that adding the same two numbers on the same CPU can have different results.

No wonder when bug #323 causes floats to compare differently when you come back and read them later!

When you use SSE math exclusively the weirdness of doing calculations in a different precision then what you store goes away.

Re:GCC optimized code gives strange floating point results by TwoBit on Sunday February 26, 2017 @11:56PM (#13741981)
If I was going to use a std::set of float, I'd also implement my own comparison operator for the set in order to avoid these problems.