clockworklabs / SpacetimeDB

Multiplayer at the speed of light
https://spacetimedb.com
Other
4.41k stars 110 forks source link

Decide on a consistent semantics for float eq/ord #1579

Open Centril opened 3 months ago

Centril commented 3 months ago

Currently, AlgebraicValue::F32/F64 uses decorum::Total<f32> and Total<f64> as a way to get Ord and PartialEq implementations for floats. The Ord impl eventually uses decorum::FloatOrd and decorum::FloatEq. For FloatEq, this eventually results in calling to_canonical_bits, which is implemented here. As explained in the FloatOrd and FloatEq docs, one of their properties is that they treat all NaNs as equal. These semantics for floats are used for AlgebraicValue, eq_bsatn, and in eq_to_pv.

Meanwhile, the spacetimedb_table::eq implementation compares bytes directly, which is ostensibly compatible with the {f32, f64}::total_cmp methods, which behave according to the totalOrd predicate defined by IEEE 754 FP standard, and unlike the behavior of FloatOrd.

We thus have an inconsistency in our implementation and should pick one. For performance, it seems like total_cmp would be the winner, as it allows us to keep comparing bytes directly for VLOs.

gefjon commented 3 months ago

Note that {f32,f64}::total_cmp, aka IEEE 754-2008 totalOrder:

  1. Is implemented relatively efficiently in the Rust standard library as branchless integer arithmetic, whereas decorum::FloatOrd and FloatEq are implemented relatively slowly with branches in an external dependency.
  2. Misbehaves on denormalized floats, i.e. those of the format 0.xxx * 2^n, where a normalized float is always in the format 1.xxx * 2^n. Denormalized floats may occur naturally as a result of arithmetic on values very close to 0, but they are generally sketchy and unsupported anyways, which is reasonable because they can only appear at the limit of the float type's precision. Because of this misbehavior, totalOrder is technically a distinct ordering from {f32,f64}::partial_cmp, but this is unlikely to matter in practice.
  3. Is a bitwise ordering (though not 2's complement). (a.total_cmp(b) == Ordering::Equal) <=> (a.to_bits() == b.to_bits()).