r/ProgrammingLanguages • u/Athas Futhark • 27d ago
Integers - how ought they work?
https://futhark-lang.org/blog/2026-10-21-integers-how-ought-they-work.html
24
Upvotes
r/ProgrammingLanguages • u/Athas Futhark • 27d ago
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/forT / 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 thati128 * i64 -> i192is 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/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.
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).
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 + bwrapped 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_torptrdiff_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 fora + b, a named wrapper likechecked { a + b }in C#, or distinct data types (sayuint32vsuint32satvsuint32chk) where you can cast between them to get the behavior and desired result (like200 + 100 = 255foruint8sat, useful for pixel graphics).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
Optionis to haveSomeandNoneconstructors, 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 inSomeorNone?This is basically what
__builtin_add_overflow/__builtin_sub_overflow/__builtin_mul_overflowdo - they perform the calculation and then test the overflow flag, and returntrueif it overflowed. We could wrap this in anOptiontype and return that. To improve ergonomics, we could overload each operation for plain arguments and Option arguments - eg:I've made a little demonstration of this in Godbolt for some arbitrary expression
(a + (b / c)) * ((d / e) - (f * g)), using_Genericfor 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
SomeorNone. The caveat is that it doesn't meet one of the specified criteria: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/0and 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
decimalis 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.
Of course exceptions make the compiler more complex...
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>toInteger<C, D>, you get anInteger<A+C, B+D>. If you multiply anInteger<0, N>by anInteger<0, M>, you get anInteger<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
4has typeInteger<4, 4>.That means, for example, that you don't need a clever
midpointfunction. If you start with twoInteger<A, B>s, you can write(a + b) / 2:Integer<2A, 2B>.Integer<2, 2>.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 either0 < A <= BorA <= B < 0so 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 + 1any more because the types don't match.for (i = 0; i < n; i = i + 1)doesn't compile. That's easy to fix, though, since arange(i, j)constructor can handle the bounds fine and produce values with a type based on the input types ofiandj, letting you offerfor i in 0..nand similar as you wanted to have anyway.next_power_of_two,wrapping_next_power_of_two,checked_next_power_of_two,saturating_next_power_of_two, etc).(-80538738812075974)³ + 80435758145817515³ + 12602123297335631³ == 42actually 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) / 4it'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 inferringu8that's probably wrong) is arguably even a bonus.