10 ms·

This is the bug that makes std::set< float > crash randomly under GCC with default compile options. The fact that they consider this reasonable is insane.

emmelaich 10y ago
Is having a set of floats reasonable?
- Negitivefrags 10y ago
  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.
  - Sharlin 10y ago
    > 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.
    - temac 10y ago
      Well the thing is, it should not fail because of obscure reasons completely unrelated to NaNs...
    - Someone 10y ago
      But std::set doesn't use operator< for comparing values, but !(a<b) && !(b<a). http://www.cplusplus.com/reference/set/set 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.
      - Sharlin 10y ago
        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.
      - DannyBee 10y ago
        "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.
    - kobeya 10y ago
      It's also a credulous bug that a standard ordering isn't defined for NaNs.
      - brucedawson 10y ago
        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?
        kobeya 10y ago
        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 :(
        Sharlin 10y ago
        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.
  - emmelaich 10y ago
    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 ...
    - Negitivefrags 10y ago
      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.
    - TwoBit 10y ago
      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.
- int_19h 10y ago
  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.
  - deleted 10y ago
    [deleted]

emmelaich 10y ago

Is having a set of floats reasonable?

Negitivefrags 10y ago
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.
- Sharlin 10y ago
  > 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.
  - temac 10y ago
    Well the thing is, it should not fail because of obscure reasons completely unrelated to NaNs...
  - Someone 10y ago
    But std::set doesn't use operator< for comparing values, but !(a<b) && !(b<a). http://www.cplusplus.com/reference/set/set 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.
    - Sharlin 10y ago
      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.
    - DannyBee 10y ago
      "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.
  - kobeya 10y ago
    It's also a credulous bug that a standard ordering isn't defined for NaNs.
    - brucedawson 10y ago
      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?
      - kobeya 10y ago
        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 :(
        Sharlin 10y ago
        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.
- emmelaich 10y ago
  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 ...
  - Negitivefrags 10y ago
    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.
  - TwoBit 10y ago
    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.
int_19h 10y ago
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.
- deleted 10y ago
  [deleted]