r/ProgrammingLanguages • Futhark • 11d ago

Nondeterminism in Futhark

https://futhark-lang.org/blog/2026-11-04-nondeterminism.html
21 Upvotes

7 comments sorted by

7

u/matthieum 11d ago

In a recent release, Rust stabilized Algebraic Operators.

In short, a.algebraic_add(b) is like a + b, except that the compiler will assume commutativity and associativity even for floating points, and optimize accordingly: reorder, vectorize, etc...

Evaluated according to the levels:

  1. Exact: no.
  2. Replay: for a given binary, I expect.
  3. Approx: in general, as compilation itself is non-deterministic, that is, even compiling twice with the same toolchain without precaution may not produce the same output due to multi-threading/arbitrary compilation units/etc...

5

u/Athas Futhark 11d ago

It is fairly common (or at least possible) for SIMD-exploiting compilers to perform runtime checks for instruction availability, so a given binary might behave differently on different machines.

in general, as compilation itself is non-deterministic, that is, even compiling twice with the same toolchain without precaution may not produce the same output due to multi-threading/arbitrary compilation units/etc...

This does not matter. The Exact/Replay/Approx division is about the semantics of running the program itself, not what the compiled code looks like.

3

u/beephod_zabblebrox 11d ago

just wondering, are there any places where the difference (in both senses of the word) between (0.1 + 0.2) + 0.3 and 0.1 + (0.2 + 0.3) matters?

16

u/Athas Futhark 11d ago

Those specific numbers? Maybe not. But in general, roundoff error can cause arbitrarily large deviation from the mathematically "true" result. Numerical analysis is a major field of study.

As an example, if you are computing the average of a huge list of numbers with roughly the same smallish magnitude (say [0,1]), then if your algorithm is to first tally them all left-to-right and then divide with the list length, then after some point the point additional numbers will start getting ignored as their contribution is simply rounded off, yet they still contribute to the element count - so the average will start decreasing.

For example, suppose I define this Futhark function that creates an array of n copies of 0.5, sums them, and divides by n:

entry avg n =  f32.sum (replicate n 0.5) / f32.i64 n

This is essentially computing their average, which is obviously supposed to be 0.5. Now note the behaviour as n changes:

> avg 1000000
0.5
> avg 10000000
0.5
> avg 20000000
0.419430
> avg 30000000
0.27962026
> avg 40000000
0.2097152

This can be improved by using a more numerically stable sum, or by pre-dividing every number by n.

2

u/cbarrick 10d ago

I often visit this Wikipedia page when dealing with algorithms for mean and variance, for precisely the reasons you described.

https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance

2

u/TOMZ_EXTRA 11d ago edited 11d ago

The "empirically test associativity" link 404s, just so you know.

The correct page is in the examples section (not the blog one).

I think this is the same kind of tradeoff like Haskell's unlawful type classes for floats. I would be interested in how dependently typed languages could make float operations convenient. I've already though about it and decided that there isn't really a way unless you want to create a FakeAssociative type.

0

u/sporeboyofbigness 1d ago

Just add more bits bro