Stream: t-lang

Topic: floating point semantics


simulacrum (Apr 17 2020 at 21:53, on Zulip):

I'm working on writing up the (long) comment summarizing the state of the floating point to integer casts, and I'm having trouble nailing down exactly how to interpret what C++ does.

simulacrum (Apr 17 2020 at 21:54, on Zulip):

I believe https://en.cppreference.com/w/c/language/conversion#Real_floating-integer_conversions is a reasonable reference, and AFAICT given Rust's lack of support for rounding modes, we basically can boil that down to C++ rounding to nearest for imprecisely representable values and otherwise being undefined

simulacrum (Apr 17 2020 at 21:55, on Zulip):

(AFAICT, this differs from the behavior given by LLVM's fptoui which rounds to zero; as well as the behavior Rust currently has regardless of -Zsaturating-float-casts)

simulacrum (Apr 17 2020 at 21:57, on Zulip):

Also, does Rust require IEEE arithmetic to be supported? I somehow feel that the answer is yes... but maybe that's not true

eddyb (Apr 17 2020 at 23:03, on Zulip):

pretty sure Rust is iEEE-only

eddyb (Apr 17 2020 at 23:03, on Zulip):

cc @Hanna Kruppe

Josh Triplett (Apr 17 2020 at 23:22, on Zulip):

I would love to have options to not be, but yes, at the moment it is.

Josh Triplett (Apr 17 2020 at 23:22, on Zulip):

(cough FMA cough)

Hanna Kruppe (Apr 18 2020 at 08:55, on Zulip):

FWIW, I wouldn't say contraction (license to form FMAs from fadds and fmuls) is "not IEEE". The standard mostly describes a set of operations, how program source code in various languages maps to these operations is not really within its jurisdiction. When it does talk about language implementations, it is almost entirely non-binding (lots of "should" and "may"). In particular, §10.3 discusses "value-changing optimizations", even listing contraction as one example of such optimization (and the list there is explicitly not exhaustive).

Hanna Kruppe (Apr 18 2020 at 08:58, on Zulip):

@simulacrum First of all, I'm confused by the rounding mode stuff: Rust does not have support for users selecting non-default rounding modes, but certainly we can and should define certain operations to have a (fixed) rounding mode different from RNE.

Hanna Kruppe (Apr 18 2020 at 09:11, on Zulip):

As for "does Rust require IEEE arithmetic to be supported" ... it's complicated. The reference has long said our f32 and f64 types map to IEEE 754 (version unspecified) binary32 and binary64 formats, but that's technically a statement about storage layout, not how arithmetic is performed. On most targets, each Rust-source-level operation takes the results in the obvious format and rounds the result to the same format. But on a few targets (e.g. x86 w/o SSE2), multiple operation can and are performed in an intermediate format and rounded at the end, which can give different results. Some other hardware we support flushes denormal results to zero or otherwise is fuzzy around denormals (typically configurable, but we don't fiddle with it).

We don't have an official policy on these things one way or another, but they're certainly not what the average programmer will expect when told "Rust floats are IEEE 754, end of story".

simulacrum (Apr 18 2020 at 10:54, on Zulip):

Yeah, when I said lack of support I meant that there's no way to switch in std, and I seem to recall an issue saying that there was some undefined behavior involved

Josh Triplett (Apr 18 2020 at 19:04, on Zulip):

@Hanna Kruppe I agree that contraction should be perfectly fine, but the last time that came up, there was huge pushback against the idea on the grounds that it'd be somehow standards-violating.

Hanna Kruppe (Apr 18 2020 at 19:09, on Zulip):

Not only on those grounds, to be clear. But if this particular argument comes up in future discussions and I have the time to participate, I'll probably end up writing a very pedantic standards lawyering rebuttal. (Not that I expect it'll really change anyone's mind.)

Josh Triplett (Apr 18 2020 at 19:21, on Zulip):

I would appreciate that, thank you.

Josh Triplett (Apr 18 2020 at 19:21, on Zulip):

(And yes, I'm aware that there was pushback on other grounds as well.)

RalfJ (Apr 19 2020 at 07:53, on Zulip):

contraction is just one example of a "fast-math"-style optimization, right? I'd also be quite concerned if we did those by default, mostly because so far we barely know how to specify them formally in the context of a whole programming language, let alone argue that a compiler is following the spec. all I know of is a single work-in-progress unpublished proposal (by colleagues at MPI-SWS :D ), but the design space is big.

RalfJ (Apr 19 2020 at 07:53, on Zulip):

I saw some proposals for controlling these optimizations based on the types of the operands, and got to say I quite liked those :D

RalfJ (Apr 19 2020 at 07:53, on Zulip):

type-based toggles seem much more suited for this than global flags like C compilers use them

RalfJ (Apr 19 2020 at 07:57, on Zulip):

I should also mention that these aforementioned colleagues expressed interest in exploring their style of fast-math semantics for rust, and asked me how to best proceed with that. I told them to maybe start with a post on IRLO, maybe join here on zulip and start a discussion. not sure how their timetable for that looks.

Josh Triplett (Apr 19 2020 at 14:28, on Zulip):

@RalfJ In general, I'd suggest completely avoiding the term "fast-math", because it encompasses everything from optimizations that make math more precise (like contraction) to those that lose precision.

Hanna Kruppe (Apr 19 2020 at 14:41, on Zulip):

I have other qualms with the "fast-math" term (it suggests a performance advantage that is often barely there and does not convey the risks, incentivizing programmers to over-use it and get bitten by it later), but I do think it's justified to have a term that encompasses all of these optimizations. They have substantial overlap -- challenges for reproducibility and standardization, primarily enabled for performance reasons -- even if they differ on other axes and some subsets of them also deserve names.

As for better terms to replace "fast-math", I like the phrases "value-changing optimization" and "(changing/preserving) the literal meaning of the source code" used in IEEE 754-2019.

RalfJ (Apr 19 2020 at 14:44, on Zulip):

yeah, I used the term for lack of a better one

Josh Triplett (Apr 19 2020 at 14:44, on Zulip):

I think it's worth distinguishing between optimizations that add precision and those that lose precision, as well.

RalfJ (Apr 19 2020 at 14:44, on Zulip):

FWIW, I'd include using x87 float instructions in there, even though we already do that

RalfJ (Apr 19 2020 at 14:46, on Zulip):

Josh Triplett said:

I think it's worth distinguishing between optimizations that add precision and those that lose precision, as well.

in terms of user interface (compiler flags etc), definitely. in terms of specification, I am less sure. it is already really hard to specify the envelope of permissible program behavior under such transformations; also requiring that "precision has to increase" (whatever that even means, in general) is yet another can of worms...

RalfJ (Apr 19 2020 at 14:47, on Zulip):

I could totally imagine situations where contraction locally increases precision but globally decreases it

Josh Triplett (Apr 19 2020 at 14:51, on Zulip):

If you define precision in terms of how close you are to the true value, I don't see how that would work. I would love to see a sequence of operations that had that result.

RalfJ (Apr 19 2020 at 14:56, on Zulip):

Here's a really contrived example: take f1 and f2 to be twice the same function. Consider f1(x) - f2(x). If we now optimize f1 with contraction but leave f2 unchanged, the precision of the overall expression will decrease.

Hanna Kruppe (Apr 19 2020 at 15:02, on Zulip):

Another example of this (strongly related but not quite an instance of Ralf's template) is x²-y² when x = y, which is brought up every time the topic comes up. I'm starting to worry about how often this happens around FP things (not just contraction, also other FMF and anything related to fp environment access), discussions flaming up again once in a while and re-treading the same facts that were already discovered last time.

Hanna Kruppe (Apr 19 2020 at 15:03, on Zulip):

And so much of it is buried deep in chat archives where they're unlikely to be found again.

RalfJ (Apr 19 2020 at 15:08, on Zulip):

what's "FMF"?

Hanna Kruppe (Apr 19 2020 at 15:10, on Zulip):

fast-math flags, shortened primarily to avoid the evil "fast-math" substring

RalfJ (Apr 19 2020 at 15:10, on Zulip):

^^

RalfJ (Apr 19 2020 at 15:10, on Zulip):

it's not just chat archives luckily, there are a bunch of unresolved discussion threads in https://github.com/rust-lang/rfcs/pull/2686 that also pertain to this

RalfJ (Apr 19 2020 at 15:10, on Zulip):

would be good to get them incorporated in the RFC at some point

Hanna Kruppe (Apr 19 2020 at 15:10, on Zulip):

(Not really, the acronym is widely used by people who have no such qualms, but that's my personal reason to prefer it :D)

Josh Triplett (Apr 19 2020 at 15:37, on Zulip):

@RalfJ That's assuming correlation between the imprecision. And in any case, what about if you compile the entire program with contraction enabled?

Hanna Kruppe (Apr 19 2020 at 15:39, on Zulip):

Oh, but that reminds me: in that thread we discussed how some flags like "no NaNs" can produce undef-like behavior and thus could lead to UB, but I've since realized (and hastily jotted down here: https://github.com/rust-lang/rust/issues/21690#issuecomment-610459562) that the same concern applies to basically all value-changing optimizations. That is, %x = <some fp computations> with two uses (e.g. a bounds check and an array indexing) could get duplicated such that one of the uses gets one copy of the computation and the other use gets the other copy, and then the two copies can get optimized differently and result in the same fun effects you get from "every use of undef independently observes a non-det value".

The obvious solution if we're concerned with compiler correctness is "well don't duplicate instructions whose value might be non-deterministic" but given that such duplication is common in various optimizations (and undef/poison are specifically engineered to make them valid in the absence of freeze), this seems hard to swallow. So perhaps the conclusion is that all "fast-math" optimizations are unsafe? And it's not the kind of unsafe where a careful programmer can avoid UB.

RalfJ (Apr 19 2020 at 16:25, on Zulip):

Josh Triplett said:

RalfJ That's assuming correlation between the imprecision. And in any case, what about if you compile the entire program with contraction enabled?

I think we definitely have to assume correlation between the imprecision. Assuming they are uncorrelated sounds like a big stretch to me.

sure this particular contrived example is easy to fix. but it demonstrates the principle. precision (in the presence of uncorrelated imprecision) is fundamentally not a monotone or otherwise compositional property, so there is just no way to reason about how the precision of the final computation will change based on local precision changes.

Amanieu (Apr 19 2020 at 16:26, on Zulip):

One idea I had was to allow undef in the FP domain and freeze values when we convert them to integers. The idea is that we only directly rely on integers for memory safety. However I'm a bit uncertain of how that would work with implicit and explicit transmutes.

RalfJ (Apr 19 2020 at 16:26, on Zulip):

So perhaps the conclusion is that all "fast-math" optimizations are unsafe? And it's not the kind of unsafe where a careful programmer can avoid UB.

Agreed. the only formal model of fast-math I know is indeed using non-determinism as you also allude to, and to avoid UB the programmer needs some way to mark where the non-determinism has to "end" -- something like freeze. (As @Amanieu says they could be implicit in a cast, too.)

Hanna Kruppe (Apr 19 2020 at 16:46, on Zulip):

This is an interesting direction, but since branch/select conditions are also safety relevant and need to be frozen (artificial example: if x > y { free(ptr); } if x <= y { ptr.write(1); }), this seems to introduce a concerning number of freeze operations. If there's too many, their chilling effect on some optimizations might make "fast math" a net pessimization for a lot of code. Even if the freezes are programmer-controlled rather than automatic, the cognitive burden to figure out where it can and can't be omitted seems too great for people to use this ability correctly and precisely.

Hanna Kruppe (Apr 19 2020 at 16:57, on Zulip):

That example is actually pretty bad but waves hands

Hanna Kruppe (Apr 20 2020 at 10:08, on Zulip):

Hmmm, but some value-changing optimizations are licensed by default, specifically those that change the bits of NaN results (sign, signaling/quiet, payload). Wouldn't those technically be subject to the same problem? Only a few niche operations can transport those differences to the integer domain (variations of transmutes, is_sign_positive, and copySign) but hypothetically there should be soundness issues involving those lurking in current Rust.

RalfJ (Apr 20 2020 at 17:06, on Zulip):

NaN changes are easy, we can just say that typed copies of floats do not preserve NaN bits

RalfJ (Apr 20 2020 at 17:06, on Zulip):

so that's a lot like padding

Lokathor (Apr 20 2020 at 18:36, on Zulip):

People could get upset with you there. Some people use those NaN bits. Also, actually doing that in practice is more costly than just unconditionally copying all four bytes, so if you're never going to do it anyway, don't claim that it might happen.

RalfJ (Apr 20 2020 at 22:16, on Zulip):

but we do it sometimes. LLVM will clobber the NaN bits under some circumstances.

RalfJ (Apr 20 2020 at 22:16, on Zulip):

pretending this does not happen is just going to make people sad

RalfJ (Apr 20 2020 at 22:16, on Zulip):

so I'd rather make people defensively use u32 instead of f32 for moving their stuff around

RalfJ (Apr 20 2020 at 22:17, on Zulip):

see for example https://github.com/rust-lang/rust/issues/55131

RalfJ (Apr 20 2020 at 22:17, on Zulip):

so there's a high chance that those people that use these NaN bits just have broken code that happens to work with some luck.

Hanna Kruppe (Apr 21 2020 at 10:56, on Zulip):

LLVM will happily eliminate bitcasts and roundtrips through memory, so idk if focusing on typed copies will work. Like, let bits = f.to_bits(); ptr::write(p1, bits); ptr::write(p2, bits); should result in essentially the same IR as ptr::write(p1.cast(), f); ptr::write(p2.cast(), f); after a few cleanup passes.

RalfJ (Apr 21 2020 at 12:24, on Zulip):

LLVM will happily eliminate int-ptr-casts and it is wrong in doing so. maybe this is similar?

RalfJ (Apr 21 2020 at 12:25, on Zulip):

I mean we could just say that the NaN result of a division (or any other NaN-producing operation) has non-det sign and payload, but is that sufficient to explain all behavior?

Hanna Kruppe (Apr 21 2020 at 12:26, on Zulip):

It's not specifically divisions, it can happen with essentially any FP computation that results in NaN

Hanna Kruppe (Apr 21 2020 at 12:29, on Zulip):

While you could argue for a semantics where int->float bitcasts can't be removed because they have implications for per-use nondeterministism, realistically this is leading to far fewer actual miscompiles than int-ptr-casts, so I am not hopeful that this perspective will appeal to LLVM.

nikomatsakis (Apr 21 2020 at 16:56, on Zulip):

So...I skipped this thread. @Hanna Kruppe does this in any way represent a kind of "blocking objection" on your part to #71269?

Hanna Kruppe (Apr 21 2020 at 16:58, on Zulip):

Not at all. The thread started with a question related to that PR, but that was settled quickly and everything since then has been unrelated to saturating int->float casts.

Last update: Jun 05 2020 at 23:10UTC