Tracking Issue for algebraic floating point methods

[calder]

Feature gate: #![feature(float_algebraic)]

This is a tracking issue for exposing core::intrinsics::f*_algebraic in stable Rust, including in const.

Public API

// core::num::f16

impl f16 {
    pub const fn algebraic_add(self, rhs: f16) -> f16;
    pub const fn algebraic_sub(self, rhs: f16) -> f16;
    pub const fn algebraic_mul(self, rhs: f16) -> f16;
    pub const fn algebraic_div(self, rhs: f16) -> f16;
    pub const fn algebraic_rem(self, rhs: f16) -> f16;
}

// core::num::f32

impl f32 {
    pub const fn algebraic_add(self, rhs: f32) -> f32;
    pub const fn algebraic_sub(self, rhs: f32) -> f32;
    pub const fn algebraic_mul(self, rhs: f32) -> f32;
    pub const fn algebraic_div(self, rhs: f32) -> f32;
    pub const fn algebraic_rem(self, rhs: f32) -> f32;
}

// core::num::f64

impl f64 {
    pub const fn algebraic_add(self, rhs: f64) -> f64;
    pub const fn algebraic_sub(self, rhs: f64) -> f64;
    pub const fn algebraic_mul(self, rhs: f64) -> f64;
    pub const fn algebraic_div(self, rhs: f64) -> f64;
    pub const fn algebraic_rem(self, rhs: f64) -> f64;
}

// core::num::f128

impl f128 {
    pub const fn algebraic_add(self, rhs: f128) -> f128;
    pub const fn algebraic_sub(self, rhs: f128) -> f128;
    pub const fn algebraic_mul(self, rhs: f128) -> f128;
    pub const fn algebraic_div(self, rhs: f128) -> f128;
    pub const fn algebraic_rem(self, rhs: f128) -> f128;
}

Steps / History

• ACP: ACP: Expose algebraic floating point intrinsics libs-team#532
• Implementation:
  • Add "algebraic" fast-math intrinsics, based on fast-math ops that cannot return poison #120718
  • Expose algebraic floating point intrinsics #136457
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• How does this interact (if at all) with the optional-fused-multiply-add intrinsics added in intrinsics fmuladdf{32,64}: expose llvm.fmuladd.* semantics #124874? Do we even still need those?
• Naming: "algebraic" is not very descriptive of what this does since the operations themselves are algebraic.

References

• Imprecise floating point operations (fast-math) #21690
• ACP: Expose algebraic floating point intrinsics libs-team#532
• Expose algebraic floating point intrinsics #136457
• https://github.com/calder/dot-bench
• https://www.felixcloutier.com/x86/vfmadd132ps:vfmadd213ps:vfmadd231ps

cc @rust-lang/lang @rust-lang/libs-api

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[tgross35]

Added lang as requested in rust-lang/libs-team#532 (comment). That comment also mentions algebraic_mul_add, which could be added after the initial PR if it makes sense.

[RalfJung]

These operations are non-deterministic. @nikic do you know if LLVM scalar evolution handles that properly? We had codegen issues in the past when SE assumed that an operation was deterministic and then actually it was not.

[RalfJung]

That comment also mentions algebraic_mul_add, which could be added after the initial PR if it makes sense.

We also have the "may or may not fuse" intrinsics added in #124874, which so far have not been exposed in any way that has a path to stabilization. Would algebraic_mul_add use those intrinsics, or would it replace them since we likely want some of the algebraic fast-math flags on that operation as well (i.e., we want to give the compiler more freedom than just "fuse or don't fuse").

[nikic]

These operations are non-deterministic. @nikic do you know if LLVM scalar evolution handles that properly? We had codegen issues in the past when SE assumed that an operation was deterministic and then actually it was not.

Are these "algebraic" in the sense that they have reassoc FMF? If so, then yes, SE should be treating them as non-deterministic already: https://github.com/llvm/llvm-project/blob/6684a5970e74b8b4c0c83361a90e25dae9646db0/llvm/lib/Analysis/ConstantFolding.cpp#L1437-L1444

[RalfJung]

reassoc and a few more, yeah. Seems like that is accounted for, thanks. :)

[tgross35]

On that note I added an unresolved question for naming since algebraic isn't the most clear indicator of what is going on.

[tgross35]

In theory the flags could also be represented via const generics, which would allow more fine tuned control and more flags without a method explosion. Something like:

#[derive(Clone, Copy, Debug, Default, ...)]
#[non_exhaustive]
struct FpArithOps {
    reassociate: bool,
    contract: bool,
    reciprocal: bool,
    no_signed_zeros: bool,
    ftz: bool,
    daz: bool,
    poison_nan: bool,
    poison_inf: bool,
}

impl FpArithOps {
    // Current algebraic_* flags
    const ALGEBRAIC: Self = Self { reassociate: true, contract: true, reciprocal: true, no_signed_zeros: true, ..false };
}

// Panics if `poison_*` is set
fn add_with_ops<const OPS: FpArithOps>(self, y: Self) -> Self;

// Alows `poison_*`
unsafe fn add_with_ops_unchecked<const OPS: FpArithOps>(self, y: Self) -> Self;

// same as `f32::algebraic_div`
let x = 1.0f32.div_with_ops::<FpArithOps::ALGEBRAIC>(y);

(Using a struct needs the next step of const generic support, or some way to bless types in std)

[hanna-kruppe]

As I wrote in the ACP:

While this goes on the direction of having multiple combinations of LLVM “fast math flags” exposed, I don’t think that there’s more than two or three sets that are broadly useful enough and well-behaved enough to be worth exposing. And one of those is just “let the hardware do whatever is fast w.r.t. subnormals” which is something that really wants to be applied to entire regions of code and not to individual operations, so it may need an entirely different design. (It’s also a function attribute rather than an instruction flag in LLVM.)

I don’t think that we should expose the power set of LLVM’s flags, nor so many ad-hoc combinations that “method explosion” becomes a realistic problem. I’m not even sure if it’s a good idea to ever expose any of FMFs that can make an operation return poison (has anyone ever used those soundly while still getting a speedup?). And FTZ/DAZ shouldn’t be modeled as per-operation flags because you don’t want to toggle the CPU control registers for that constantly.

[zroug]

Should @llvm.arithmetic.fence be exposed? Sometimes it would be nice to reason about the effects of algebraic operations locally. Currently, there is no clean way to prevent reassociation, etc. with operations outside your local context, because you can't know if the caller is using algebraic operations as well.

[orlp]

On that note I added an unresolved question for naming since algebraic isn't the most clear indicator of what is going on.

I think it is fairly clear. The operations allow algebraically justified optimizations, as-if the arithmetic was real arithmetic.

I don't think you're going to find a clearer name, but feel free to provide suggestions. One alternative one might consider is real_add, real_sub, etc.

[oli-obk]

Seems fine to me. If you're relying on floats being unoptimized in const eval in a frequently used crate then that's on you

[traviscross]

Seems OK to me. We of course should just document what people should not rely on here.

[scottmcm]

Seems trivially-fine to allow them in const in nightly, at least.

I do think Ralf's concern is at least worth a conversation in stabilization discussions, but I think that'll probably also end up arising equivalently at runtime in various ways, so I don't think there's a need to block nightly experimentation as lang.

(Obviously if the maintenance burden is too high, or something, other may still block for other reasons.)

[nikomatsakis]

No objections.

[traviscross]

@rustbot labels -I-lang-nominated

We discussed this in the lang call today, and we had appetite for these being const.

[tczajka]

I don't think you're going to find a clearer name, but feel free to provide suggestions. One alternative one might consider is real_add, real_sub, etc.

These names suggest that the operations are more accurate than normal, where really they are less accurate. One might misinterpret that these are infinite-precision operations (perhaps with rounding after a whole sequence of operations).

The actual meaning isn't that these are real number operations, it's quite the opposite: they have best-effort precision with no strict guarantees.

I find "algebraic" confusing for the same reason.

How about approximate_add, approximate_sub?

[traviscross]

Saying "approximate" feels imperfect, as while these operations don't promise to produce the exact IEEE result on a per-operation basis, the overall result might well be more accurate algebraically. E.g.:

let mut x = 0.0f32;
for _ in 0..100000000 {
    x = x.algebraic_add(0.00000001);
}
println!("algebraic:    {x}");
let mut x = 0.0f32;
for _ in 0..100000000 {
    x += 0.00000001;
}
println!("exact per op: {x}");

Produces (on release mode):

algebraic:    1.0061039
exact per op: 0.25

(The algebraically correct result is 1.0.)

Playground link

Of course, there's no guarantee that it will be. It's just that we've allowed "algebraically justifiable" optimizations to happen.

[hanna-kruppe]

I’m not necessarily opposed to “approximate” but I have some quibbles with it too. While there are no guarantees about precision, in practice the most important optimizations these methods enable (reassociation, mul-add contraction) are often neutral to beneficial for precision. To me, the “approximate” name sounds more like what LLVM’s afn flag enables (substitute individual operations with faster but less precise implementations) which is not quite the same as the purpose of these methods.

[orlp]

How about approximate_add, approximate_sub?

I strongly disagree with this naming. With the few exceptions of exactly representable input/output pairs, almost all floating point math is already an approximation. And it would imply optimizations that aren't permissible.

These names suggest that the operations are more accurate than normal, where really they are less accurate.

Whether or not they are more or less accurate depends on the exact expression and input domain. For example, .fold(0.0, f64::algebraic_add) is more accurate than .sum::<f64>() for virtually all inputs. In fact, if we so desired Rust/LLVM could in theory incorporate an optimization pass similar to Herbie which chooses the fastest most accurate alternative, something that would be impossible with normal operations which do not allow rewriting at all.

[orlp]

@bjoernager There are more optimizations involved in these algebraic ops than simple reassociation.

[bjoernager]

There had been some discussion about removing the f*_fast intrinsics in favour of these. We could merge the functions so that we use the fast name but with the current algebraic semantics. This would mostly (but not exactly) be equivalent to GCC's or Clang's -ffast-math option, and it could also be seen as more intuitive coming from those.

[tczajka]

To justify my "approximate" naming proposal:

IEEE-754 specifies the exact semantics of +, -, *, /, sqrt and that semantics is followed precisely to the last bit by the regular arithmetic operations.

The "algebraic" operations are "approximate" in the sense that they are not guaranteed to follow the IEEE-754 specification exactly.

[traviscross]

Not in direct reply to anything specifically here, but for our reference, the flags we're turning on are (quoting from the LLVM docs):

• nsz - No Signed Zeros - Allow optimizations to treat the sign of a zero argument or zero result as insignificant. This does not imply that -0.0 is poison and/or guaranteed to not exist in the operation.
• arcp - Allows division to be treated as a multiplication by a reciprocal. Specifically, this permits a / b to be considered equivalent to a * (1.0 / b) (which may subsequently be susceptible to code motion), and it also permits a / (b / c) to be considered equivalent to a * (c / b). Both of these rewrites can be applied in either direction: a * (c / b) can be rewritten into a / (b / c).
• contract - Allow floating-point contraction (e.g. fusing a multiply followed by an addition into a fused multiply-and-add). This does not enable reassociation to form arbitrary contractions. For example, (a*b) + (c*d) + e can not be transformed into (a*b) + ((c*d) + e) to create two fma operations.
• reassoc - Allow algebraically equivalent transformations for floating-point instructions such as reassociation transformations. This may dramatically change results in floating-point.

We're not turning on:

• afn - Approximate functions - Allow substitution of approximate calculations for functions (sin, log, sqrt, etc). See floating-point intrinsic definitions for places where this can apply to LLVM’s intrinsic math functions.

Nor are we turning on these flags, which would be implied (along with nsz) by fast (in LLVM):

• nnan - No NaNs - Allow optimizations to assume the arguments and result are not NaN. If an argument is a nan, or the result would be a nan, it produces a poison value instead.
• ninf - No Infs - Allow optimizations to assume the arguments and result are not +/-Inf. If an argument is +/-Inf, or the result would be +/-Inf, it produces a poison value instead.

[tczajka]

We're not turning on:

• afn - Approximate functions - Allow substitution of approximate calculations for functions (sin, log, sqrt, etc). See floating-point intrinsic definitions for places where this can apply to LLVM’s intrinsic math functions.

This would be a relevant consideration if there was algebraic_sin, algebraic_sqrt, etc, but seems immaterial to algebraic_add and friends.

[traviscross]

It's mentioned just for reference, in light of the point @hanna-kruppe made in #136469 (comment).

[hanna-kruppe]

@bjoernager The “fast math” terminology (also -Ofast) has proven to be a huge disservice to users and the Rust project should not propagate it further. If you call something the “fast” version, everyone’s like “of course I want my code to be fast” and that’s not something to encourage even with how relatively tame these operations are compared to the “funsafe-math” chimera.

[bjoernager]

I don't see why "fast" must inherently also equate to "exact" or "precise." The whole point of these functions is to optimise for execution speed, not accuracy. Just like I can run "fast" with a basket but I might drop some stuff from it, I can also take it slow and assure that its contents will be kept intact. Anyone that reads the docs would know these complications of fast arithmetic, and I don't see a reason to idiot-proof the language for people that won't bother... After all, there is a plethora of other pitfalls that can lead to junk logic or calculations etc. (which in and of itself does not break any safety guarantees).

[tczajka]

I agree that fast is a better name than algebraic.

"Algebraic" can mean many things. "Algebraic numbers" are roots of polynomials, so √2 is algebraic and π is not an algebraic number. There is also a related concept of "algebraic function". It's obviously not what is meant here.

The name "algebraic" tries to suggest what kind of optimizations are possible on this, but names shouldn't concentrate on what optimizations are allowed, they should talk about the semantics of the operation, and optimizations follow from that.

It's hard for me to interpret "algebraic" in any semantic way. real would be even worse, because that's just semantically wrong. The optimizer might be "assuming" these are exact operations on real numbers, but that's just its own internal incorrect assumption, no reason to expose that in the names.

I still think approximate is even better. fast concentrates on performance, approximate concentrates on the semantics that implicitly enables better performance.

I think the root of the naming issue is that there is no clearly defined semantics: "The exact set of optimizations is unspecified". So it's really kind of best_effort_add.

[hanna-kruppe]

@bjoernager Naming shouldn’t be constrained by the worst hypothetical misunderstanding someone can invent. But with this exact name, in this exact domain, we have decades of experience showing that it leads to misunderstandings and misuse by many users. And I don’t want to just blame users for it: it’s a maximally misleading name because it focuses on the aspect that needs the least attention. Sure, you can carefully interpret it as “fast as a trade-off against some other desirable property” but that’s not where most people’s minds go first. Especially not in Rust, which has “efficiency” right in its tagline and prides itself on not trading off reliability for it.

[tgross35]

I believe fast has been discussed in a number of threads and the point that kept coming up is what Hanna mentioned, that we don't want to direct users toward thinking "if these are fast, everything else must be slow; why would I use them?".

How about approximate_add, approximate_sub?

I strongly disagree with this naming. With the few exceptions of exactly representable input/output pairs, almost all floating point math is already an approximation. And it would imply optimizations that aren't permissible.

The response in #136469 (comment) resonates with me as well here. "approximate" would be relative to the default operations, which are as exact as possible given finite precision. I don't think there is any risk of a confusing implication that default operations act with infinite precision. That said, the logic holds less well if we wind up with something like approximate_sin since libm functions like sin tend to be inexact even within the available precision.

Personally I do like inexact_* a bit more than approximate_*, since IMO it connotes a smaller tolerance. We could also go the direction of naming based on what the compiler is allowed to do, e.g. foldable_*.

[tczajka]

Personally I do like inexact_* a bit more than approximate_*, since IMO it connotes a smaller tolerance.

inexact is also reasonable.

But I'm not sure how much tolerance is reasonable to imply because even a simple re-association such as (a+b)+c => a+(b+c) can in some cases cause 100% precision loss. It's essentially impossible to build anything reliable on these functions without having any bounds in the spec on the re-writings that can happen.