We Need Hardware Traps for Integer Overflow
blog.regehr.org
blog.regehr.org
With apologies to those tired of hearing about the new Mill CPU let me explain how the Mill traps on integer overflow:
For overflow-able arithmetic operations, we support four modes:
* truncate
* except
* saturate
* double-width
With excepting overflow, the result is marked as invalid (we term it "Not-a-Result (NaR)").
As these invalid results are used in further computation, the NaR propagates.
When you finally use the result in non-speculatively e.g. store it or branch on it then the hardware faults.
NaRs have lots of other uses.
This is described in the Metadata talk http://millcomputing.com/topic/metadata/
And http://millcomputing.com/topic/introduction-to-the-mill-cpu-... for a broader overview.
The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. I have none to hand either, but I'm going to predict that on a modern CPU with typical workloads it will be small enough that it would be very hard to measure.
The article speaks as though doing it in hardware would be free, but that's very far from true. The hardware solution might have a nominal cost of 'zero clock cycles' where overflow doesn't occur, but extra transistors in critical, heavily used parts of the CPU core would be burning a small but nonzero amount of energy all the time even on code that doesn't use the overflow check - i.e. the vast majority.
If you think overflow check is a great feature (of which personally I'm not at all convinced), go ahead and add it to a new language or provide it as a library function in an existing language. But imposing it as an inescapable tax on all hardware makes no sense whatsoever.
I write in a language that does (sort of) this (Python!), and I'd argue that I'd agree. Python gives, by default, integers that aren't bounded, so overflow doesn't happen. Of course, under the hood, it must be keeping track of all the bits of the number somehow, and determining when it can't store a section of the integer in the underlying uintxx_t; it must use some sort of overflow here, even if perhaps it's not truly overflowing. Integer objects (for those interested) are 28 bytes by default and more if they get larger; a rough test with multiplication just now seems to take ~25-50ns (compared to ~2-3ns for a int32t in C) and in my experience, most of the time, this doesn't matter.
With this flurry of new languages, I had hoped to see more of "integer" just being an integer, and fixed-sized integers being a special case. Often, I feel I really don't know what the bounds on the input will be. (Sometimes, there aren't, aside from available memory constraints.) Obviously, there will need to be code that needs to run fast and can use a more restrictive type.
Something like, `ranged_integer<0, 200>`, which I can use when I know my inputs should never exceed [0, 200], and has some well-defined behavior if I over/underflow. (Or even, configurable!) In the `ranged_integer<0, 200>` case, I'd expect the compiler/library to be able to easily optimize that into a `uint8_t`. (You could have `native::uint8_t`, which is just whatever the processor has, and you're on you're own, but it's more obvious that you're on your own.)
Also the current branches for overflow checks might be well-predicted, but only if it uses branch prediction resources that could go to other branches. Not to mention the extra codesize and issue resources taken.
While I agree with you that hardware overflow traps are a bad idea, I think the article's author is referring more to the general overhead of a software BIGNUM implementation. Specifically with his JavaScript example, I think it's very plausible that using integers instead of IEEE754 would incur a 10% overhead if you were throwing lots of big enough numbers around.
What the author really wants is a hardware BIGNUM implementation, not overflow trapping. I just don't think he really thought it through.
His contention that simply checking for overflow in C or C++ incurs a 5% overhead is unquestionably false though. Typically one would check for integer overflow in C like this:
unsigned int do_addition(unsigned int a, unsigned int b)
{
unsigned int tmp;
tmp = a;
a += b;
if (a < tmp)
asm volatile ("nop;" ::); /* Handle it here */
return a;
}
0000000000000000 <do_addition>:
0: 89 f0 mov %esi,%eax
2: 01 f8 add %edi,%eax
4: 73 01 jae 7 <do_addition+0x7>
6: 90 nop
7: c3 retq
I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.
Checking for overflow is just a matter of testing if the high-order bits are zero.
C has some interesting gaps for something that's long been described as a macro for assembly. A rotate operator would also be nice.
Here's an example where there is overflow, but your suggestion would not catch it:
mov eax, 0x7fffffff
mov ecx, 2
imul ecx ; edx:eax = eax * ecx
; edx = 0
; eax = 0xfffffffe
; overflow flag = 1
There are also issues with detecting overflow of SSE multiplies (signed and unsigned).
Yeah, you're absolutely right.
> I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.
I've never tried to implement this, but couldn't you look at the position of the most significant bit in the multiplicands to guess if the multiply will overflow? You'd have to be okay with false positives I suppose? Naively it would be slow, but if you have a hardware CLZ instruction it could be pretty fast.
I did find this on SO:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
If you're willing to not be non-portable, you could just do expanding multiplies and check the high word:
struct exmulres {
unsigned long hi;
unsigned long lo;
};
static inline __attribute__((always_inline)) struct exmulres do_one_expanding_multiply(unsigned long a, unsigned long b)
{
struct exmulres res;
#if defined(__x86_64__)
asm ("movq %0,%%rax; mulq %1; movq %%rdx,%1; movq %%rax,%0"
: "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%rax","%rdx");
#elif defined(__i386__)
asm ("movl %0,%%eax; mull %1; movl %%edx,%1; movl %%eax,%0"
: "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%eax","%edx");
#elif defined(__arm__)
asm ("umull %0,%1,%2,%3"
: "=r" (res.lo), "=r" (res.hi) : "r" (a), "r" (b) :);
#else
#error "No expanding multiply assembly has been written for your architecture"
#endif
return res;
}
EDIT: Typo
For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens):
uint64_t func(uint64_t a, uint64_t b)
{
unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b;
if (res >> 64) {
asm volatile ("nop;" ::); /* handle here */
}
return (uint64_t)res;
}
0: 48 89 f8 mov %rdi,%rax
3: 48 f7 e6 mul %rsi
6: 48 85 d2 test %rdx,%rdx
9: 74 01 je c <func+0xc>
b: 90 nop
c: f3 c3 repz retq
edit: and it probably suffers the same problem as described here: https://news.ycombinator.com/item?id=7848771 -- and also probably has general issues with signedness that would need to be further checked.
edit2: changed it to uints to simplify and avoid a whole class of problem. I still don't think you should go use this, though.
(inspiration from SO: http://stackoverflow.com/a/13187798)
[1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c
https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c#...
I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary duplication of computational effort. However, that is a lot of work and has the potential for hidden programmer introduced errors.
The real problem is that languages like C simply don't allow you to take advantage of hardware which already exists in the CPU without writing in-line assembler. A standard set of "checked" math macros which handled the portability issues would probably satisfy most C applications.
Edit: For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it (remembering to take signs into account). For division and modulus, check for division by zero. For multiplication, division, modulus, negation, and absolute value of signed values, check that you are not negating the maximum negative integer, as integer ranges are not symmetrical (e.g. one byte is -128 to +127).
If you are looping over arrays and have multiple checks for different cases (e.g. negative, positive, etc.), then you can have different loops for different cases and so avoid redundant checks for that data. I'm working on this sort of application, so the above works out best for that. If you're doing something a bit different, then different algorithms may make sense. Unfortunately, there's not universal one-size-fits-all solution to this problem in software.
Sure, but that calculation is CPU-dependent, since it depends on how the underlying hardware represents signed integers. By definition, it is impossible to portably check for signed integer overflow in C, as I'm sure you know.
I implemented a simplistic BIGNUM library in C once (that's where I pulled that expanding multiply code in the other comment from). The only truly portable way to do that is to make your bignums sign-magnitude and use exclusively unsigned arithmetic on them. That's what I was envisioning in my original point about performance degradation due to overflow checking.
Realistically of course, most CPU's these days are twos-complement, and you can make signed overflow defined by compiling with "-fwrapv", which I would guess is what you're doing.
If the code had to be portable to one's complement hardware, then I would create special cases for that type of hardware. Laying my hands on such hardware for testing would be the big problem, and if you haven't tested it, then how do you know that it works?
As for "-fwrapv", it's not portable either, and I need to cover both signed and unsigned math. It's also not compatible with what I need to link to (I've gone down this road already). I also need to cover the largest native word sizes, so the trick of using a larger word size won't work for me.
I'm only dealing with arrays of numbers though, so I can often amortize the checking calculations over many array elements instead of doing them each time. This is an example of knitting the checks into the overall algorithm instead of using a generic approach.
As things stand, there's currently no universal ones-size-fits-all answer to this problem in most languages.
I do like how Python has handled this - integers are infinitely expandable and simply can't overflow. This comes at the expense of performance though. What this type of solution needs is an option for unchecked native arithmetic for cases where you need maximum speed.
I'm actually really curious: exactly what issues did you run into with this? Intuitively I wouldn't think it would be a problem.
In decimal, that means that you compute the product of two-digit numbers using single-digit multiplications and shifts (= multiplications by 10):
23 x 67
= (20+3) x (60+7)
= (2x3) x 100 + (2x6) x 10 + (3x7) x 10 + 3x7I don't remember where I read it, but regarding multiplication: if you multiply two N-bit numbers together, the result will always fit in a 2N-bit number. For instance, the product of two 16 bit numbers will fit in 32 bits, the product of two 32 bit numbers will fit in 64 bits, etc. You can assign the product to an integer able to hold the larger size and then check if it would also fit in an integer of the smaller size.
AFAIK there isn't any notion of likely/unlikely in object code on most CPU architectures. I'm only really familiar with x86 and ARM though.
__builtin_expect() in GCC (the "likely()" and "unlikely()" macros in the Linux kernel use this) can do a lot of things to optimize branches, like prefetch instructions and decide whether or not the jump should be the usually taken or usually not taken side, but it can't actually emit instructions that directly tell the CPU "always predict this" AFAIK.
That's a fair point, although I think using a single function for all your checked addition like the one above would go a long way towards mitigating the resource waste you mention.
Maybe that's a naive assumption on my part: I suppose you could construct a branch predictor that maintains state based on the function call chain as opposed simply using the address of the branch... but that seems like it would be prohibitively complex.
The article does mention a 5-10% cost on JavaScript VMs, as one datapoint. And as another, that languages like Rust choose to allow overflow to avoid the overhead, despite preferring the security of not having silent overflows (implying they measured a slowdown they find unacceptable).
As for his numbers on the performance penalty of doing it in software it surely depends on micro-architecture. All intel x86 processors before HASWELL did only ONE branch per cycle, then in haswell they increased that to two. So the cost of doing it in software should of went down recently. And Intel is adding new instructions to speed up arbitrary precision arithmetics in broadwell so they probably have already thought about this and decided its not worth the cost in hardware.
Ditto for BOUND, which is useful for automatic array bounds-checking - it performs both lower and upper bounds checks.
Also, I don't really get why integers wrapping around should be "unexpected". It is only to those who don't understand how integers work. The saying "know your limit, play within it" comes to mind.
Also, you almost certainly don't want to just go back an instruction; you want to catch and handle the overflow.
They dropped this instruction for the 64-bit SPARCs.
For example, detecting integer overflow on x86 and x86_64 CPUs is easy: check the overflow flag after every arithmetic operation. It would only be slightly more difficult to detect overflow for SSE (vector) operations, which would require doing some bit masking and shifting.
For a language such as Swift, building it in is simple.
Now, it doesn't back these assertions with much data, but neither do you :)
This is similar to null-reference protection in various languages and runtimes, where null dereferences are caught by mapping guard pages at the beginning of memory. Dereferencing a pointer is optimistic and assumes that it will succeed, the same as arithmetic operations would in this proposal.
For data to back this, see your favorite computer architecture reference, particularly anything that discusses the consequences of highly-complex instructions in things like the VAX.
It means that your program contains a bug.
What's swift got to do with it anyway? A language that was launched last week is now a benchmark for including new features? Has it been open sourced since then? If not how is building it in simple?
Intel chips already detect overflow, that is what the OF (bit 11) flag in the flags/eflags register indicates. That the most recent operation overflowed.
Testing, and generating a trap, for an overflow is a single instruction (JO – jump if overflow and JNO – jump if no overflow).
This is true of almost all CPU’s. At the hardware/assembly programming level, overflow detection is handled by hardware, and detected by a single instruction. The reason all of your languages listed don’t have any sort of trap/etc. is simple. The language designers did not bother to check the result of their operations. Why, most likely because almost all of them are ultimately implemented in C, and C does not reflect the overflow status back into the C language level.
So the problem isn’t the hardware. It is the software architectural design(s) implemented above the hardware. They are not bothering to communicate to you the results of what the hardware already has available and tells them about."
(Qouting comment from Anon)
So yes, you can check for overflow by inspecting a flag, but that's not all that much better from coding around the potential overflow to see if your operands + operation combo will cause an overflow.
Imagine setting a flag on a divide by 0 instead of raising an exception.
So the author is most likely aware of the overflow flag (just like any other old timer that has programmed in assembly and that had a cursory look at the flags register, or in some cases more than a cursory look :) ), he's writing about hardware exceptions, not about how to write in javascript.
But inspecting a flag simply isn't on the same level as raising a hardware exception, right along with segfault, division by 0, FPEs and so on.
That instantly propagates through to any programming language executed on the machine. Checking a flag in a register is a decision by a compiler writer and many compiler writers (consciously!) ignore that (usually because the language specs are vague enough that wrapping is considered acceptable when it is in fact almost always simply wrong).
"Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap."
In short, he believes there's no hardware support and therefore Rust, GO and D don't have it.
There is however hardware support in every imaginable CPU -- overflow is important to be able to synthesize adds bigger than the native size (e.g. 128 bit add if your regs are 64-bits) . Except for the implementor of the HLL compiler you as the user wouldn't be able to see how it's implemented in the hardware unless you look at the resulting generated code (you'd see an "exception" triggered no matter how it's implemented).
I know: I had the opportunity to implement the language which has special behavior when the floating point compare involves NaN. Luckily, there is a flag in the Intel CPU for that too and as far as I know you can't access it from any popular high level language, but my code generator injects additional flag check in every FP compare and in the production code I haven't seen any negative performance impacts compared to the case where I don't do the stated injection. That's how good the current branch prediction in CPUs can be.
So no, you don't need "hardware traps" you need somebody to first try to implement the given behavior in any HLL language before before we argue further. As soon as you have "wrappable" and "unwrappable" types in the language, you can have all the crypto primitives that need wrapping use the "wrappables" without any performance impact.
In fact "unwrappables" were interesting mostly for the calculations of the limits, practically wherever you'd use, for example, Microsoft's SafeInt classes.
The example from their header:
void* AllocateMemForStructs(int StructSize, int HowMany) {
SafeInt<unsigned long> s(StructSize);
s *= HowMany;
return malloc(s);
}
The operative word there is trap.
There is no hardware support for traps on overflow, period.
You can detect overflow in software and then you can generate an exception (or deal with it in some other fashion) like you describe, this is not the same as a trap.
Feel free to stick to your definition if you want to but the accepted one is that a trap operates much like an interrupt would.
I also gave an example of the language (Visual C++) which already implements exceptions (the application programmers sees only exceptions, not traps) on integer overflows, provided the programmer specifies that he wants such a type (declares them as SafeInt).
Now whether or not the balance of burden (hardware/software) would favour a hardware solution or not is a different matter entirely. But I completely get what the author is trying to achieve and I'm well aware of the various bits in the flag registers of a whole pile of processors. I see having such a trap as a distinct advantage, just like I see division by 0 and floating point exceptions as advantageous.
The fact that you could do this in software right now has no bearing on his argument, that's a choice by the implementors of the various languages, which are usually built for speed rather than safety and where unchecked integer overlows are the norm. Retro-fitting a trap mechanism in hardware would likely turn up a whole pile of bugs in systems that we currently consider to be solid.
Even worse, Java's model doesn't allow anybody to reach to the hardware.
The author of IEEE 754, prof. Kahan lamented exactly that: that the languages of today effectively can't use a lot of the features he designed (in 2004, http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf Page 20: "Java lacks these flags and cannot conform to IEEE 754 without them.").
That was the FP domain, but is instructive. The traps are relatively "all or nothing" thing. To have a language where some integer variables behave one way and some another way (you know, the types are important now), you already have the hardware flags and they simply aren't used in the languages OP mentions.
Just changing the compiler behavior would be absolutely enough to "turn up a whole pile of bugs in systems that we currently consider to be solid" that you suggest. You certainly don't need to wait for some new CPUs.
So we return to what Anon said: "Those who do not understand the hardware are doomed to blog about it, poorly." If somebody wants to have the language types that trigger exceptions on overflows, he doesn't have to wait for the new processors. It's possible now, if there's interest in it. And even as the real "traps" as the very specific CPU feature for FP already exist, no language I know of uses them for types.
That isn't right: languages created before and after C exhibit the same behaviour. Some languages do explicitly check the overflow flag every time.
The reason for not always checking (or never checking) is that in a tight loop the extra instruction can significantly affect performance especially back when CPUs had a fraction of their current speediness capability. The reason for not exposing the value to the higher level constructs is similar: you have to check it every time it might change and update an appropriate structure, which is expensive given an overflow should be a rare occurrence so checking every time and saving the result is wasteful.
The linked article specifically mentions the performance effect of checking overflow flags in software. I believe what it is calling for is some form of interrupt that fires when the flag is switched on in a context where a handler for it is enabled - a fairly expensive event happens upon overflow but when all is well there is no difference in performance (no extra instructions run). Of course there would be complications here: how does the CPU keep track of what to call (if anything) in the current situation? Task/thread handling code in the OS would presumably need to be involved in helping maintain this information during context switches.
The reason it's not in standard C is to be portable with some odd old architecture which doesn't have the overflow flag at all. Some modern language can be clearly designed to depend on the overflow flag. The cost would happen only when the programmer really does access it (in a modern language: by using such a type) and the cost would be minimal, as there is a direct hardware support.
> I believe what it is calling for is some form of interrupt that fires when the flag is switched on in a context where a handler for it is enabled
And that is misguided, as it doesn't allow for fine grained control -- it's all or nothing, either all instructions generate "an interrupt" or none. If you want to change the behavior from the variable to variable, changing processor mode would cost. If you add a new instructions for all things that can overflow and trap, you'd add a lot of new instructions. So it's also bad. The simplest approach is: use what's already there. The flag is there in the CPU, it's not used by the languages OP mentions, but once the language supports it for the "safe" integer type, it will be checked only when it's really needed: for that type and nowhere else.
Finally, the maintenance of the exception handling code (what you name under "how does the CPU keep track of what to call") is something that modern compilers and even assembly writers must take care of and is very good understood among them: for example, Winx64 ABI expects every non-leaf function to maintain the stack unwinding information properly and even if I write assembly code I effectively have to support exceptions outside of my code for every non-trivial function I write. So this part is very good known, and the most is taken care of outside of the OS. The OS merely has some expectations, the compiler (in broader sense, that is, including native code generator and linker) writers must fulfill them.
TLDR: Not accidentally performing an undefined operation is really really hard.
the comment system on your blog eats comments, that become lost forever when submitted. You might want to know that.
Apart from that:
1) “2147483650f” is Java syntax. Also this number, written in C++ as 2147483650.0f, actually represents the number 2147483648 (assuming float is the single-precision IEEE 754 format). You might want to denote that number 2147483648.0f, which would be less confusing.
2) the line “const int min = 0x80000000;” does NOT contain undefined behavior. The overflows occurs during a conversion from an integer type to a signed integer type. Overflow during such a conversion is implementation-defined (or an implementation-defined signal is raised). Even an implementation-defined signal is not undefined behavior, but in practice, the compiler you use produces wrap-around behavior, and it will continue to do so, because it has been forced to document it.
The 2147483648 vs 2147483650 is actually kind of interesting. Visual Studio watch window prints floats with one less digit of precision they they need as it actually displays (from memory) 2.14748365e9 when it should display as 2.147483648e9. Thanks for the catch.
I'll have to check spec docs to if the unsigned to signed overflow is undefined or implementation defined. I think you're correct but I need to verify.
This code proved invaluable when writing binary parsers designed to support "unsafe" mesh data coming off of the network--the file might be garbage, but we could at least safely parse it.
I'd go so far to say that if you are dealing with a binary format--especially a sane one which has length headers and chunks for rapid seeking--and you aren't using something similar, you are doing it wrong.
EDIT:
For the curious, you may find some of these bit-twiddling hacks to be of some use.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerL...
http://blog.regehr.org/archives/1139
As you say, it is surprisingly different to it get right, especially if you want good performance. A common mistake is checking for signed integer overflow after the fact. It is too late when undefined behavior has already happened.
This seems more like a theoretical concern, as just about all the hardware out there is 2's complement and signed overflow wraps around in the usual way - because that's the simplest, most straightforward way to implement it. (This also means I think compilers that exploit this "loophole" in the language are seriously violating the principle of least surprise.) If you're working on the few exceptions to this, then integer overflow is probably going to be the least of your worries...
I'm surprised that something that necessary and tricky to implement still hasn't been considered for the C standard library.
Which is why the author wants support for integer overflow traps. He even mentions Python, which does what you describe, and suggests that other languages don't do this precisely because of the performance hit for which he's proposing a solution.
Don't get me wrong, they could be a useful feature, perhaps even one which should be enabled by default in Swift (I'd argue against them, but I wouldn't be entirely unsympathetic to their proponents). However, they aren't for everyone and they don't come cheap.
In the context of Swift, it would make a lot of sense to me for Int to be a bignum with no built-in limits on range. The common case of looping over a small set of values, computing indexes for UI elements, etc. will fall within the range of machine native integers and remain fast. If you blow out the limits, your code will still work. If you want control/speed, use one of the provided integer types with an explicit width.
1. There is a large class of languages where they do not make sense as a default.
2. The most sensible approach is to fastlane the all-int native case, but this comes at the cost of a preciptitous drop in speed the moment even a single bignum happens.
> Isn't the alternative introducing a thousand difficult-to-debug edge cases that cause your code to produce incorrect output, or crash?
Unintentional bignums are usually bugs, so incorrect output / crash is usually the best one could hope for anyway. People understand that programs have bugs and crash, but the combination of slowness with incorrect output is a special recipe for infuriated users (I waited 30 minutes for the file to load and then it crashed?!?!).
My experience with this has mainly been in languages like Python, where bignum performance is way down on the list of worries, and C, where you wrap if you're lucky and end up with exploitable security vulnerabilities if you're not. I don't believe I've seen a language at work which traps overflows.
My experience with C has been that overflows (which would be unintentional bignums in another environment) are almost always one of:
1. Underflow of unsigned values used for sizes, especially for memory allocation, which causes a request for vast quantities of memory.
2. Computations on large quantities without thinking about how large they can be. File sizes are a really common example of this, especially since they fit into 32 bits for so long.
3. Reading textual data containing integers that either doesn't specify how large they can be, or specifies it but the specification got ignored. A fun example of this was the Twitpocalypse, when Twitter collected enough tweets for the tweet IDs to overflow signed 32-bit integers and broke a ton of clients.
#1 is an error, and crashing would be fine. That's usually what happens in C anyway, just in a somewhat more confusing manner because you get an error trying to allocate 4 billion bytes of memory rather than the more obvious "can't put -1 in here" that actually happened.
#2 is pretty much the poster child for automatic bignums. The downside being potential slowness, but most aren't performance sensitive.
#3 is an interesting case. I'm not sure that using a language "integer" type is even the right way to represent an ID from a remote service, even if that ID happens to be an integer. But automatic bignums would have prevented this problem, even if the design wasn't necessarily right to begin with.
As far as I know (and I realize it's probably hard to tell), I haven't seen bugs where automatic bignums would produce the wrong answer. They can be bugs (e.g. #1 above, possibly #3) but they don't involve incorrect output.
Anyway, to me it just makes sense for the default behavior to be correctness. When you write "a + b" without taking special measures, the result should be the right answer in a mathematical context. If you want bounds checking, that should be made explicit. (A way to create configurable integer types with arbitrary bounds could be nice.) If you want wrapping, that should be made explicit too. And if you want performance at the potential expense of correctness at the edges (presumably because you either know you won't hit the edges, or they behave the way you want them to) then that ought to be opt-in, not opt-out.
So don't do either of those things until your arithmetic overflows the size of a word; until then, you can keep numbers in a register.
* Fixnums support (headless objects) needed for non-Java lanaguages on JVM is still unimplemented to my knowledge[0]
[0] http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6674617
Right, bignums need to be a language feature, not a library feature. Compilers with native bignum support often have ways of handling native unboxed single-register numbers, and then branching to full bignum routines when needed. Haskell can do that, for instance.
Also, you can use the standard trick of decreasing the maximum single-register size and using the extra bits to identify indirect objects.
That's given, you still pay the price (like mask/shift), though. That was the part the "languages like C/C#/Java have it easier" about. The point is mostly that even if built-in support (interrupts) exist in the hardware, bignums still need quite a lot of extra code in-place, plus a good optimizing/inilining compiler.
Personally I am happy with constrained integer types - else the entire stack (incl. storage) must support bignums and often (like almost always) going out of range would be a bug actually.
It makes more sense to me to have compiler writers check the flags if they care about overflow, and avoid the slow down if they don't.
[1] http://www.reddit.com/r/programming/comments/26s8iu/we_need_...
Nope.
But I like it a lot even so. For a general case it seems like it would help.
I'm not sure I've seen that in any other languages before.
and a sticky saturation flag in the status register
A google search for "wrapped integer types" gives me the Wikipedia article on Integer Overflow as its first result. The other hits seem to be related.
What else do you mean by "wrapped integer types" if not arithmetic modulo 2^n?
simcop2387 is correct that I assumed he was talking about boxing at first.
http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...
[1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c
I've been using -ftrapv with gcc for a long time, from here: https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.
From the code you posted, and the assembly[1] emitted in the pdf above I can't see the optimiser taking advantage of the carry bit. No mention of CF, OF:
[1]
lea ebx, DWORD PTR [edi+eax]
cmp ebx, edi
jae SHORT $LN4@unsigned_c
cmp ebx, eax
jae SHORT $LN4@unsigned_c
mov ecx, 1
jmp SHORT $LN5@unsigned_c
xor ecx, ecx
The gcc flag ftapv only works for signed integers, not clear what the carry bit behaviour is for unsigned integers.
For example, there was tag type DTP-GC-FORWARD. When the CPU loaded a word from memory with this value in the tag field, it would automatically indirect through the pointer contained in the word.