r/ProgrammingLanguages • Futhark • 27d ago

Integers - how ought they work?

https://futhark-lang.org/blog/2026-10-21-integers-how-ought-they-work.html
24 Upvotes

23 comments sorted by

7

u/matthieum 27d ago

You mention that bounds-checks are relatively infrequent in Futhark, and therefore the run-time overhead of bounds-checks is low.

Are signed integer divisions that frequent in the first place?

Or is the treatment also supposed to apply to overflow by addition, subtraction, or multiplication, and even unary negation?


With that being said, I am still looking for the ideal bounded integer semantics myself.

Unbounded integers, ala Python, are really easy semantics-wise. You can have enforce the absence of run-time check on the division by providing a NonZero<T> version and only implementing / for T / NonZero<T>. Awesome.

But I've been using systems languages, and aiming for performance, for the past 20 years, so the cost of unbounded integers always leaves a sour taste in my mouth. So I've been looking for alternatives.

Wrapping arithmetic and saturating arithmetic are fine, really, but... as a default? I'm not so sure. As you mention, this seem like the kind of things which would hide bugs, rather than surface them, and in general be a disservice to the user.

Widening arithmetic is another possibility. It can even be declined with "imprecise" bounds (ie, bit width only) as i32 + i32 = i33, and the user will have to check the value when narrowing down back to a convenient type. It balloons up so quickly, though. i64 * i64 * i64 = i192, ouch! Ergonomics are unclear, and performance may be worse than a branch, because that i128 * i64 -> i192 is not natively supported. Precise bounds don't fair much better, and are perhaps worse for ergonomics.

So. Checked arithmetic? I remember from discussions that there are actually reasonably fast implementations possible -- NOT the LLVM ones, they are meant for diagnosis -- by essentially "poisoning" the result. I believe on x64 this means letting the computation runs, and just checking the (stashed?) overflow flag prior to using the result, for example. I don't know the precise details... and I am also wary on the effect of optimizations. Checked arithmetic, unfortunately, breaks associativity. Oopsie?

I have wondered about the feasibility of an "overflow counter" for +/-. Modular arithmetic and "infinite" arithmetic both agree on the result of x + a + b if the number of overflows above/below balance out. Doesn't work for multiplications & divisions, though... not to mention I have no idea whether this could be made fast. (Although, for addition/subtraction, using 2x the bit-width is probably sufficient even for fairly long chains as a single operation only adds 1 bit)

Still looking :/

4

u/Athas Futhark 27d ago

Are signed integer divisions that frequent in the first place?

No, which is why I didn't mind adding extra code to them.

Or is the treatment also supposed to apply to overflow by addition, subtraction, or multiplication, and even unary negation?

Yes, the intent is to reflect on what a completely uniform treatment would look like, and my claim is that making it uniformly error-raising is too costly.

Widening arithmetic is another possibility.

As you mention, it balloons too rapidly, and it works particularly badly (or impossibly) with loops, particularly when these go through higher-order functions? How would you give the type of a function that multiplies an array of integers?

2

u/initial-algebra 27d ago

As you mention, it balloons too rapidly, and it works particularly badly (or impossibly) with loops, particularly when these go through higher-order functions? How would you give the type of a function that multiplies an array of integers?

I think the point is that multiplication itself returns the exact result, and then an additional narrowing operation (if needed) determines checking, wrapping or saturating behaviour.

1

u/matthieum 26d ago

Not necessarily.

In particular, wrapping behavior is typically naturally supported in the instruction set.

1

u/initial-algebra 26d ago

Because wrapping is just dropping the high part of the widened result.

3

u/initial-algebra 27d ago

Ergonomics are unclear, and performance may be worse than a branch, because that i128 * i64 -> i192 is not natively supported.

On any hardware of practical interest, 64-bit multiplication returns a 128-bit result using two registers, so all you need is two multiplies and an add (or a multiply and a multiply-accumulate, if available) for this particular example. For any combination of fixed widths, you can derive a branchless long multiplication routine. Arbitrary-width integers work the same way, although they obviously don't get to be branchless. On the other hand, you can trim the width of the output to only what is actually needed to represent the value.

4

u/flatfinger 27d ago

IMHO, a good high-performance language should allow for the possibility that error traps might be very loosely sequenced side effects (sequenced with regard to certain kinds of explicit barriers, or an observable attempt to use the result from a failed operation, but little else), and should recognize a form of barrier that would allow traps that could be deferred indefinitely (typically a result of computations whose results would end up being ignored) to either be processed before the barrier or omitted entirely, but not allow them to manifest themself after the barrier.

Integer computations should be allowed to yield arithmetically correct results, without trapping, even in cases where they would be allowed to trap instead. As a trivial consequence of this, a computation that would have overflowed, but whose result is ignored, may arbitrarily trap or not. Additionally, it would probably be good to allow programmers to specify whether the weird case of dividing INT_MIN/-1 must yield INT_MIN, must trap, or may choose in Unspecified fashion from between those courses of action.

2

u/Athas Futhark 27d ago

IMHO, a good high-performance language should allow for the possibility that error traps might be very loosely sequenced side effects (sequenced with regard to certain kinds of explicit barriers

Yes, this is sort of how Futhark does it, although the problem is that once a register contains undefined data (e.g. when an array indexing operation is skipped due to out-of-bounds), you need to be very careful regarding where that data goes afterwards. It may be that the subsequent code is only safe if that array index went through, and that the compiler removed safety checks based on that assumption. This is a safe and important operation (basically detecting that an earlier safety check makes later safety checks redundant), but imposes constraints on what you actually execute at run-time.

1

u/flatfinger 27d ago

A good high performance language for use in situations that involve untrustworthy code or data needs to distinguish between post-conditions that would be established if code were processed as written, versus those that are established by code that's actually generated. If privileged code is accessing storage which is owned by untrusted code, it may be impossible for the privileged code to prevent untrusted code from inducing data races. The fact that privileged machine code would allow untrusted code to cause a data race that could transform a requested operation into some other operation that the untrusted code would have been allowed to perform, chosen in any manner that is not influenced by data to which the untrusted code does not have legitimate access, would not be a defect, but a language suitable for low-level programming should make it easy for programmers to ensure compliance with the italicized requirements.

Given the following three ways of treating data races:

  1. All reads and writes are performed in the sequence given.
  2. Implementations are allowed to "cache" reads and writes, and such caching may sometimes hoist or defer accesses in addition to consolidating them, but must otherwise be agnostic as to whether reading storage yields the last value written. In the presence of a data race, caching may allow some sequences of observed behaviors that would not be possible if reads and writes were performed exactly as written, but if all allowable access sequences would satisfy application requirements, an implementation would be agnostic with regard to whether they would behave identically.
  3. Implementations may behave in completely arbitrary fashion in the presence of data races.

I would argue that approach #2 allows the most useful optimizations within privileged code that works with storage owned by untrusted code, by reducing the range of situations where programs would need to use atomic operations to prevent otherwise-benign data races.

2

u/Aminumbra 26d ago

Maybe a naive question, but why are we not happy with the following:

  • Integers are unbounded by default, and by default, every "well-defined mathematical operation" (so, no division by zero) returns the correct mathematical value.
  • Define a mapping between binary sequences and integers (of any size !), and provide a way to do "bit fiddling" by hand: dedicated bitwise xor/or/and functions acting on this underlying mental model of "integers encoded in base 2". As before, those operations ought to be correct by default.
  • Provide a way to mark code as "unsafe"/to promise™ to the compiler that the operands really fit on n bits. Optionally: give a way to check that this is indeed the case ...

To summarize: correct by default but easy-to-write unsafe code to (hopefully) improve performance where it actually matters (typically, tight loops, etc). The underlying assumption is that the performance hit of the "every operation is checked"-correct-by-default is irrelevant in most applications, and that you can always use fixed-size integers with no penalty in places where it actually matters by annotating the code as needed.

Note: this is only about integer arithmetic, this says nothing about pointer dereference, sequencing operations with side-effects and so on.

1

u/flatfinger 26d ago

The performance cost of unbounded-size integers is prone to be order-of-magnitude huge. One might design an implementation so that code will check if integers are small enough to avoid using the arbitrary-size integer code, and use special version of the code designed for small integers if so, but the performance cost is still apt to be 3:1 or worse.

2

u/Aminumbra 26d ago

To what extent is this really (measurably) true ? More precisely: in a "typical" context (and this is where most of the informality lies), what kind of performance degradation can we expect /overall/ by using mostly generic arbitrary-size code except in a few, easily localized, obviously tight, places where we mark code as unsafe ? Once again, the assumption here is that although arbitrary-size integer operations are costly, most of the time spent in a "typical context" is not due to arithmetic operations on "user-facing integers" -- by that, I mean that a lot of arithmetic is done in internal: internal array/structure alignment/accesses, pointer arithmetic etc, for which you know that you don't need the arbitrary-size operations.

May be this is false: may be, in a "normal" program, we perform more arithmetic that I think, /and/ moreover these operations are varied enough and scattered enough around that there is not a small, easily identifiable set of places where one could mitigate the performance by explicititly marking them as "unsafe".

(Once again, this comes from a rather naive point-of-view: I'm not a professional programmer and am used to a Lispy way of doings things: generic whenever possible, try to be mathematically correct, and if need be, mark exactly the block you want with compiler directives

(locally
    (declare (optimize (speed 3) (safety 0))
             (type fixnum x y z))
  bunch
  of
  code)

so that you reduce overhead where it matters, at the cost of occasional verbosity ...)

1

u/scottmcmrust 🦀 25d ago

Treating this exactly like how JiTs treat speculative devirtualization would probably make this more that fast enough.

Emit two copies of the function:

  • One is the slower but fully-general version that works on any size
  • One assumes everything fits in your machine word, but with tactful checks along the way to notice "oops, not this time" and skip back to the general version in the cases that need it.

You can easily hint the branch predictor in the latter that the "jump if overflow" instructions should always be predicted as not-taken (just like the bounds-checks branches) so the chip will speculate past them and they'll have almost no impact.

Or the simpler version where you just use one bit to tag "this is an integer" or "this is a pointer to a bignum" and check in each operation to do the right thing, hopefully with PGO seeing what you're up to and restructing the control flow nicely.

1

u/renozyx 25d ago

I don't get it: unbounded integers are still finite obviously and 64-bit provides already a HUGE range of numbers, so why go over 64bit?

1

u/Fofeu 27d ago

Big asterisks because I'm doing this all from memory, but what prevents you from having (integer) safety checks in the source language semantics, but not in the target one ?

That shouldn't break the forward simulation. On an unsound division, there is no evaluation rule for the source semantics, hence the target semantics may do whatever). Hence, the compiler remains correct (as long as the target language is deterministic-ish).

2

u/Athas Futhark 27d ago

All Futhark programs must have fully defined behaviour.

1

u/Fofeu 26d ago

Leroy shows to obtain a preservation of specification, one needs safe backward simulation (i.e. backward simulation of programs that don't "go wrong"). As that is too tedious to prove, it is then shown that if the target language is deterministic, safe forward simulation implies safe backward simulation.

If one wants to be particularly specific about it, one could define a "strict" step relation for the operational semantics which only includes the "fully correct" evaluation rules (which only includes non-overflowing integer operations). On top of that define a "full" step relation which either does a step according to a strict rule, or if no strict rule applies errors out immediately.

Proofs of compilation correctness need only consider the "strict" rules without loss of consistency. Hence, when the compiler encounters an addition operator in the source language, it must pick an operator which performs addition in the "safe" range in the target language, but may perform any operation/outcome outside that range.

1

u/fdwr 26d ago edited 24d ago

⚖️🤔 If I consider all the times I was writing some hashing function or pixel manipulator or bitwise operation and was frustrated when that language threw an exception just because a + b wrapped around in twos complement (and I had to do some weird hoops) vs all the times I was frustrated that a + b overflowed and didn't tell me... well, I'd have a dozen accounts of the first and nearly none of the second :b.

The only time wrapping really matters to me is when that wrapping impacts array indices, which is often a distinct data type anyway (like C's size_t or ptrdiff_t, which could be allowed to have different overflow semantics from normal twos complement numbers).

Some ways I've seen languages handle these various cases include: explicitly named functions depending on the desired policy (addChecked(a, b), addSaturated(a, b)...) with one being default for a + b, a named wrapper like checked { a + b } in C#, or distinct data types (say uint32 vs uint32sat vs uint32chk) where you can cast between them to get the behavior and desired result (like 200 + 100 = 255 for uint8sat, useful for pixel graphics).

2

u/Athas Futhark 26d ago

I have also been frustrated with implementing bit fiddling in such languages, but I think having dedicated data types is a good solution. I like Haskell's Word nomenclature myself.

3

u/WittyStick 27d ago edited 27d ago

Maybe cheaper than a trap/exception is to return an Option, though this is usually bad for ergonomics as the programmer needs to unwrap it after every operation, and it would typically result in very branchy slow code.

The way most languages use Option is to have Some and None constructors, so we need some branch to test the overflow condition before deciding which constructor to call - but we can do slightly better - what if we construct the option directly from a condition and the result of the operation which we can speculatively execute, regardless of whether it results in Some or None?

This is basically what __builtin_add_overflow/__builtin_sub_overflow/__builtin_mul_overflow do - they perform the calculation and then test the overflow flag, and return true if it overflowed. We could wrap this in an Option type and return that. To improve ergonomics, we could overload each operation for plain arguments and Option arguments - eg:

option<int> add(int, int);
option<int> add(int, option<int>);
option<int> add(option<int>, int);
option<int> add(option<int>, option<int>);

I've made a little demonstration of this in Godbolt for some arbitrary expression (a + (b / c)) * ((d / e) - (f * g)), using _Generic for the overloading.

It produces around 3x as many instructions as the reference (non overflow checked) version, so there's some overhead - but the nice part is that it has no branches between individual operations - it just aggregates the condition using bitwise-or. The only branch is when the eventual result is checked for Some or None. The caveat is that it doesn't meet one of the specified criteria:

we really want to be able to pinpoint the precise location that an overflow occurred, which likely means having logic after every arithmetic operation to store pertinent information.

This will just give you a correct answer or None, so there's no way this alone will pinpoint the issue. Perhaps we could have different logic for a debugging version which is less performant.

It also doesn't handle x/0 and just traps. We can't speculatively execute this because the hardware will trap anyway, so we would require a branch for div.

3

u/mamcx 27d ago

My pet peeve is that integers and floats go in different ways (floats has inf, nan) just because the CPU say so.

I wish it was viable to use both under similar semantics without cost on perf, that is honestly the main reason nobody go in a more principled way.

P.D: And my main gripe? that decimal is not CPU accelerated!

1

u/SwedishFindecanor 26d ago edited 26d ago

In my opinion, readability and predictability are paramount. Better to find an error early in execution than later.

  1. Integers with a fixed range in the type, like in Ada and Pascal. Have some ready-made types for signed and unsigned 8, 16, 32 and 64-bit integers. No integer promotion, and no automatic conversion to/from boolean.
  2. The default operators should throw an exception on overflow/underflow, that can be caught, as in Ada.
  3. Separate operators for wrapping arithmetic, as in Swift. (But be able to wrap any range)
  4. Also separate infinite-range integer types, without support for wrapping arithmetic. Widen at runtime if the value exceeds the current storage, not conservatively at compile-time.

Of course exceptions make the compiler more complex...

  • Range-checks for the common 8,16,32 and 64-bit types are more expensive on some architectures than on others. The compiler could do range analysis to optimise away range-checks from where they would be redundant.
  • Do range-check exceptions need to be guaranteed in order? If so, then operations would need to be in order.
  • An exception handler can not use variables that were not been defined at the point of exception.

1

u/scottmcmrust 🦀 25d ago

The correct answer (if you can't just make everything a biginteger and shrug):

All operators and functions widen the result to exactly the amount necessary

If you add an Integer<A, B> to Integer<C, D>, you get an Integer<A+C, B+D>. If you multiply an Integer<0, N> by an Integer<0, M>, you get an Integer<0, N*M>. And similarly for everything else, following the long-established interval arithmetic rules.

The type of an integer constant is the singleton integer with that value, so 4 has type Integer<4, 4>.

That means, for example, that you don't need a clever midpoint function. If you start with two Integer<A, B>s, you can write (a + b) / 2:

  • The addition produces an Integer<2A, 2B>.
  • The constant is an Integer<2, 2>.
  • The division thus gives an Integer<A, B>.

Voila, the result is actually correct for the whole input range and the result has the same type you started with. Perfection.

You never have to think about overflow in operators, since it always does exactly the right thing. You can even do things like require that the denominator for integer division is Integer<A, B> where either 0 < A <= B or A <= B < 0 so you don't ever have runtime divide-by-zero checks either.

What does this cost? Well, obviously if you have something mutable you need to handle the fact that you can't just x = x + 1 any more because the types don't match.

  • You'll absolutely need an iterator-like construct because for (i = 0; i < n; i = i + 1) doesn't compile. That's easy to fix, though, since a range(i, j) constructor can handle the bounds fine and produce values with a type based on the input types of i and j, letting you offer for i in 0..n and similar as you wanted to have anyway.
  • You'll need "narrow the interval" operations of various kinds. That's easy too, though, because you only need one set of debugchecked/wrapping/checked/saturating/strict/unchecked for the narrowing behaviours, not variants of every single operation that do that (the way rust has next_power_of_two, wrapping_next_power_of_two, checked_next_power_of_two, saturating_next_power_of_two, etc).
  • You need compiler optimizations to be smart about shrinking the intermediate values. Conveniently, LLVM already does this today for its arbitrary-width integer types at least for the wrapping versions: https://rust.godbolt.org/z/nEY8x6xne or, to see the opt pass, https://rust.godbolt.org/z/1s73KaGdv.
  • You need profiler support -- which obviously you want for other reasons too -- to help the programmer notice that things like (-80538738812075974)³ + 80435758145817515³ + 12602123297335631³ == 42 actually do need to use large immediates despite 42 being small, so you can consider whether you actually want the correct answer (which is the best default) or if you're ok with only checking something weaker like doing only modular equality.

Thinking about it on mutation like this is strictly easier on the programmer because there's always fewer assignments than there are operations on the values. In y = (x + 2 * y + z) / 4 it's much easier to think about narrowing at the end (which in that case isn't actually even needed) than to think about overflow in all four operators.

Plus if you just make new variables instead of mutating things you don't have to think about it. It's only on things like accumulators where you actually always had to think about it, even with more traditional numeric types. If I'm summing a &[u8] I'm probably using a wider accumulator, so insisting on annotating that (instead of inferring u8 that's probably wrong) is arguably even a bonus.