News for hackers. Stuff that matters.
Re:Solutions to Integer Overflow by SamReidHughes on Saturday September 03, 2016 @05:08AM (#12418434)
Using bignums means that arithmetic operations would have to check their arguments for whether they're bignums and also check the result for overflow, and that's going to be a lot worse than some branch-on-OF, which I'd think any sane CPU should statically predict not to be taken. The needs for things like array indexes, sizes of things, and other stuff that isn't in-band user data, these janitorial integer values, are such that you don't need (or want) bignums for them.

If I ruled the universe, I would declare overflow-checked signed and unsigned types to be the ordinary numeric types, and then in-band user values -- the data the program's written to work with, like coordinates of stuff in video games, values in spreadsheets, data in strings that is going through a crypto algorithm -- are the sort of thing that would deviate from the ordinary. They might use bignums, or floats or doubles or float128's, or unchecked 2's complement integer types, depending on the needs of correctness and performance.

Most of the operations on janitorial integers can have the overflow checks be optimized away, anyway. On one 20k line C program I counted, and I forget the exact number of arithmetic operations where (1) the overflow check would be gratuitous and (2) where omitting the overflow check wasn't a trivial optimization, was less than 10.

(Edited to make clear I was talking about gratuitous checks, by which I mean the overflow check would provably never catch overflow, and where a human programmer might feel bad about doing the wasteful check. There were less than 10 provably unnecessary overflow checks that were not "trivially" provable. One example of an overflow check I would not consider gratuitous is a doubling in capacity of a std::vector<T> when adding an element, or multiplying by a sizeof before a malloc. It could be theoretically provable if you bound other integers globally that such an overflow could never happen, but a human editing the code would be OK with the check and its performance implications.)

Re:Solutions to Integer Overflow by ScottBurson on Saturday September 03, 2016 @07:46PM (#12421833)
Surprised no one has mentioned the TADDCC instruction that Sun put in the 32-bit SPARC ISA for Franz Lisp, short for "Tagged ADD and set Condition Codes". This instruction, along with performing a normal add, would also set the overflow bit if the two low-order bits of either operand were nonzero. Thus it had baked in the assumption that the fixnum tag was 00. A subsequent instruction could branch on the overflow bit to the bignum/overflow handler, or if the implementor wanted to use a trap instead, there was the TADDCCTV variant that also trapped on overflow.

The 64-bit SPARC ISA has no such instruction. I guess it was concluded that a superscalar CPU could do well enough with a short sequence of general-purpose instructions, and it was better not to build in assumptions as to how a Lisp implementation would want to represent numbers, and Lisp was no longer very commercially important anyhow at that point in Sun's existence.

Anyway, if I ruled the universe, I would declare arbitrary-precision integers to be the default, but provide ways for the programmer to turn off the overflow check for specific operations as needed. This is exactly what Common Lisp does, though its notation for suppressing the check is rather verbose.

Re:Solutions to Integer Overflow by SamReidHughes on Saturday September 03, 2016 @02:03PM (#12420268)
> Using bignums means that arithmetic operations would have to check their arguments for whether they're bignums and also check the result for overflow,

This is a bit thoughtless because you could code generate two parallel sides of a function -- one where everything is a small-value and you only need to check for overflow after the fact, and one where some values are big-values. The small-value side of the function then jumps to the big-value side once an overflow happens. The only overhead on the small-value side is that after calling a function that returns a bignum, the return value has to be tested to confirm that it's a small-value. Functions can also have separate entry points for when all parameters are known to be a small-value, versus when they're not.

Re:Solutions to Integer Overflow by junke on Saturday September 03, 2016 @05:24AM (#12418474)
That's the case in practice (both the internal limits and the optimizations). For example Common Lisp's ARRAY-TOTAL-SIZE-LIMIT is a fixnum. The default numeric type is not bignum, however, the numeric tower is here to use them only when needed.
Re:Solutions to Integer Overflow by SamReidHughes on Saturday September 03, 2016 @05:48AM (#12418535)
That distinction is a common lisp-ism. A "bignum" implementation in the context of this article won't allocate for the small values.
Re:Solutions to Integer Overflow by Dylan16807 on Saturday September 03, 2016 @05:35AM (#12418503)
Why is having two never-taken branches worse than one never-taken branch?
Re:Solutions to Integer Overflow by SamReidHughes on Saturday September 03, 2016 @05:43AM (#12418527)
Three, not two.

And it will be worse because the two extra are checks that'll require a test instruction too, instruction cache overhead, sometimes a shift to line up the bits right.