Rollup merge of #136457 - calder:master, r=tgross35

Expose algebraic floating point intrinsics

# Problem

A stable Rust implementation of a simple dot product is 8x slower than C++ on modern x86-64 CPUs. The root cause is an inability to let the compiler reorder floating point operations for better vectorization.

See https://github.com/calder/dot-bench for benchmarks. Measurements below were performed on a i7-10875H.

### C++: 10us ✅

With Clang 18.1.3 and `-O2 -march=haswell`:
<table>
<tr>
    <th>C++</th>
    <th>Assembly</th>
</tr>
<tr>
<td>
<pre lang="cc">
float dot(float *a, float *b, size_t len) {
    #pragma clang fp reassociate(on)
    float sum = 0.0;
    for (size_t i = 0; i < len; ++i) {
        sum += a[i] * b[i];
    }
    return sum;
}
</pre>
</td>
<td>
<img src="https://github.com/user-attachments/assets/739573c0-380a-4d84-9fd9-141343ce7e68" />
</td>
</tr>
</table>

### Nightly Rust: 10us ✅

With rustc 1.86.0-nightly (8239a37f9) and `-C opt-level=3 -C target-feature=+avx2,+fma`:
<table>
<tr>
    <th>Rust</th>
    <th>Assembly</th>
</tr>
<tr>
<td>
<pre lang="rust">
fn dot(a: &[f32], b: &[f32]) -> f32 {
    let mut sum = 0.0;
    for i in 0..a.len() {
        sum = fadd_algebraic(sum, fmul_algebraic(a[i], b[i]));
    }
    sum
}
</pre>
</td>
<td>
<img src="https://github.com/user-attachments/assets/9dcf953a-2cd7-42f3-bc34-7117de4c5fb9" />
</td>
</tr>
</table>

### Stable Rust: 84us ❌

With rustc 1.84.1 (e71f9a9a9) and `-C opt-level=3 -C target-feature=+avx2,+fma`:
<table>
<tr>
    <th>Rust</th>
    <th>Assembly</th>
</tr>
<tr>
<td>
<pre lang="rust">
fn dot(a: &[f32], b: &[f32]) -> f32 {
    let mut sum = 0.0;
    for i in 0..a.len() {
        sum += a[i] * b[i];
    }
    sum
}
</pre>
</td>
<td>
<img src="https://github.com/user-attachments/assets/936a1f7e-33e4-4ff8-a732-c3cdfe068dca" />
</td>
</tr>
</table>

# Proposed Change

Add `core::intrinsics::f*_algebraic` wrappers to `f16`, `f32`, `f64`, and `f128` gated on a new `float_algebraic` feature.

# Alternatives Considered

https://github.com/rust-lang/rust/issues/21690 has a lot of good discussion of various options for supporting fast math in Rust, but is still open a decade later because any choice that opts in more than individual operations is ultimately contrary to Rust's design principles.

In the mean time, processors have evolved and we're leaving major performance on the table by not supporting vectorization. We shouldn't make users choose between an unstable compiler and an 8x performance hit.

# References

* https://github.com/rust-lang/rust/issues/21690
* https://github.com/rust-lang/libs-team/issues/532
* https://github.com/rust-lang/rust/issues/136469
* https://github.com/calder/dot-bench
* https://www.felixcloutier.com/x86/vfmadd132ps:vfmadd213ps:vfmadd231ps

try-job: x86_64-gnu-nopt
try-job: x86_64-gnu-aux

6 files changed, 83 insertions, 2 deletions

diff --git a/library/std/src/lib.rs b/library/std/src/lib.rs
index 9dcedaa13f6..5c381181218 100644
--- a/library/std/src/lib.rs
+++ b/library/std/src/lib.rs
@@ -341,6 +341,7 @@
 #![feature(exact_size_is_empty)]
 #![feature(exclusive_wrapper)]
 #![feature(extend_one)]
+#![feature(float_algebraic)]
 #![feature(float_gamma)]
 #![feature(float_minimum_maximum)]
 #![feature(fmt_internals)]
diff --git a/library/std/tests/floats/f128.rs b/library/std/tests/floats/f128.rs
index b4a6c672bf0..df28e8129dd 100644
--- a/library/std/tests/floats/f128.rs
+++ b/library/std/tests/floats/f128.rs
@@ -985,6 +985,25 @@ fn test_total_cmp() {
 }
 
 #[test]
+fn test_algebraic() {
+    let a: f128 = 123.0;
+    let b: f128 = 456.0;
+
+    // Check that individual operations match their primitive counterparts.
+    //
+    // This is a check of current implementations and does NOT imply any form of
+    // guarantee about future behavior. The compiler reserves the right to make
+    // these operations inexact matches in the future.
+    let eps = if cfg!(miri) { 1e-6 } else { 0.0 };
+
+    assert_approx_eq!(a.algebraic_add(b), a + b, eps);
+    assert_approx_eq!(a.algebraic_sub(b), a - b, eps);
+    assert_approx_eq!(a.algebraic_mul(b), a * b, eps);
+    assert_approx_eq!(a.algebraic_div(b), a / b, eps);
+    assert_approx_eq!(a.algebraic_rem(b), a % b, eps);
+}
+
+#[test]
 fn test_from() {
     assert_eq!(f128::from(false), 0.0);
     assert_eq!(f128::from(true), 1.0);
diff --git a/library/std/tests/floats/f16.rs b/library/std/tests/floats/f16.rs
index ca0b8efbe83..1a90f00aecc 100644
--- a/library/std/tests/floats/f16.rs
+++ b/library/std/tests/floats/f16.rs
@@ -955,6 +955,27 @@ fn test_total_cmp() {
 }
 
 #[test]
+fn test_algebraic() {
+    let a: f16 = 123.0;
+    let b: f16 = 456.0;
+
+    // Check that individual operations match their primitive counterparts.
+    //
+    // This is a check of current implementations and does NOT imply any form of
+    // guarantee about future behavior. The compiler reserves the right to make
+    // these operations inexact matches in the future.
+    let eps_add = if cfg!(miri) { 1e1 } else { 0.0 };
+    let eps_mul = if cfg!(miri) { 1e3 } else { 0.0 };
+    let eps_div = if cfg!(miri) { 1e0 } else { 0.0 };
+
+    assert_approx_eq!(a.algebraic_add(b), a + b, eps_add);
+    assert_approx_eq!(a.algebraic_sub(b), a - b, eps_add);
+    assert_approx_eq!(a.algebraic_mul(b), a * b, eps_mul);
+    assert_approx_eq!(a.algebraic_div(b), a / b, eps_div);
+    assert_approx_eq!(a.algebraic_rem(b), a % b, eps_div);
+}
+
+#[test]
 fn test_from() {
     assert_eq!(f16::from(false), 0.0);
     assert_eq!(f16::from(true), 1.0);
diff --git a/library/std/tests/floats/f32.rs b/library/std/tests/floats/f32.rs
index bf7641986ad..d99b03cb255 100644
--- a/library/std/tests/floats/f32.rs
+++ b/library/std/tests/floats/f32.rs
@@ -915,3 +915,24 @@ fn test_total_cmp() {
     assert_eq!(Ordering::Less, (-s_nan()).total_cmp(&f32::INFINITY));
     assert_eq!(Ordering::Less, (-s_nan()).total_cmp(&s_nan()));
 }
+
+#[test]
+fn test_algebraic() {
+    let a: f32 = 123.0;
+    let b: f32 = 456.0;
+
+    // Check that individual operations match their primitive counterparts.
+    //
+    // This is a check of current implementations and does NOT imply any form of
+    // guarantee about future behavior. The compiler reserves the right to make
+    // these operations inexact matches in the future.
+    let eps_add = if cfg!(miri) { 1e-3 } else { 0.0 };
+    let eps_mul = if cfg!(miri) { 1e-1 } else { 0.0 };
+    let eps_div = if cfg!(miri) { 1e-4 } else { 0.0 };
+
+    assert_approx_eq!(a.algebraic_add(b), a + b, eps_add);
+    assert_approx_eq!(a.algebraic_sub(b), a - b, eps_add);
+    assert_approx_eq!(a.algebraic_mul(b), a * b, eps_mul);
+    assert_approx_eq!(a.algebraic_div(b), a / b, eps_div);
+    assert_approx_eq!(a.algebraic_rem(b), a % b, eps_div);
+}
diff --git a/library/std/tests/floats/f64.rs b/library/std/tests/floats/f64.rs
index cbbfcd15efd..611670751bb 100644
--- a/library/std/tests/floats/f64.rs
+++ b/library/std/tests/floats/f64.rs
@@ -894,3 +894,22 @@ fn test_total_cmp() {
     assert_eq!(Ordering::Less, (-s_nan()).total_cmp(&f64::INFINITY));
     assert_eq!(Ordering::Less, (-s_nan()).total_cmp(&s_nan()));
 }
+
+#[test]
+fn test_algebraic() {
+    let a: f64 = 123.0;
+    let b: f64 = 456.0;
+
+    // Check that individual operations match their primitive counterparts.
+    //
+    // This is a check of current implementations and does NOT imply any form of
+    // guarantee about future behavior. The compiler reserves the right to make
+    // these operations inexact matches in the future.
+    let eps = if cfg!(miri) { 1e-6 } else { 0.0 };
+
+    assert_approx_eq!(a.algebraic_add(b), a + b, eps);
+    assert_approx_eq!(a.algebraic_sub(b), a - b, eps);
+    assert_approx_eq!(a.algebraic_mul(b), a * b, eps);
+    assert_approx_eq!(a.algebraic_div(b), a / b, eps);
+    assert_approx_eq!(a.algebraic_rem(b), a % b, eps);
+}
diff --git a/library/std/tests/floats/lib.rs b/library/std/tests/floats/lib.rs
index ad82f1a44e7..de5a3cdbd0f 100644
--- a/library/std/tests/floats/lib.rs
+++ b/library/std/tests/floats/lib.rs
@@ -1,4 +1,4 @@
-#![feature(f16, f128, float_gamma, float_minimum_maximum)]
+#![feature(f16, f128, float_algebraic, float_gamma, float_minimum_maximum)]
 
 use std::fmt;
 use std::ops::{Add, Div, Mul, Rem, Sub};
@@ -10,7 +10,7 @@ macro_rules! assert_approx_eq {
         let (a, b) = (&$a, &$b);
         let diff = (*a - *b).abs();
         assert!(
-            diff < $lim,
+            diff <= $lim,
             "{a:?} is not approximately equal to {b:?} (threshold {lim:?}, difference {diff:?})",
             lim = $lim
         );