Integer overflow semantics

[plajjan]

In our last meeting we started talking about how to run tests, like should we compile stuff in release mode or development mode before running the test? There are multiple effects from the optimization mode, like debug symbols included or not, but the one I used as an example and that we ended up discussing to a fair extent in the meeting is the behavior of integer overflow. In dev / debug mode, integer overflow detection is enabled whereas in release mode, it is not. We don't do anything differently in the Acton compiler, rather we are just surfacing the behavior of Zig / C under different compilation flags. Integer overflow is performed somewhere in like the compiler_rt or similar, fairly low level but it adds considerable overhead to integer operations which is of course why it's not enabled in release mode.

One way of reasoning is that we should run test in dev mode so we catch integer overflows and can surface them.

@nordlander made the remark that for a pure function the behavior should be known merely by looking at the code, we shouldn't have even run it and that it certainly should not change behavior based on compilation flags... he also made the remark that integers should really be considered integer modulo, as to align the definition with their actual behavior.

My problem with this is that I think the wraparound semantics is essentially never what anyone wants in the real world. First off, we need to divide the two main use cases of integers, as actual natural numbers or for storing bitfields. In C, it's all just ints but I think we should treat them rather distinctly, perhaps with different operators / functions acting on them and similarly different semantics with regards to wraparound / overflow. For natural number integers, I would argue the wanted semantics is of not having wraparound. Unfortunately, this is not what common CPU architectures (primarily x86_64 & ARM) does today. Others, like MIPS and Alpha, actually do support non-wrapping integers, as a proper CPU should!

@sydow noted that we can't reasonably just change integer semantics since we are sort of bound by what the CPUs offer.

It seems to me that many consider the conceptual design of integers to be that they should not wrap but that CPUs do wrap is an implementation detail that gets glossed over. It naturally makes a huge difference in the end and are

• to not change behavior depending on compilation flags we need to either:
  • enable integer overflow detection in release mode or perhaps use ReleaseSafe rather than ReleaseFast mode in Zig? not sure what the impact is - is this an OK impact?
  • then what? throw Acton level exceptions for wraparounds or what?
  • disable integer overflow detection in development mode
  • I think this means fully embracing the integer overflow semantics, which like nobody really is looking for?

Not sure where we should take this.

https://blog.regehr.org/archives/1154

[sydow]

Here are my extended comments on this topic; sorry for the length.

One could certainly consider introducing separate types bits64, bits32 etc (or perhaps b64, b32… following our other terse names) that implement a protocol with bit operations, moving these from Integral. This would leave the protocol Integral to handle arithmetic. This could work well, but I am not convinced that we should take that road, since I do not believe that we should change the semantics of overflow for integers. I would like to expand on this a bit.

So, let’s consider the choice of type for a “real world” computational problem involving arithmetic. The first choice is between floating point (float) and integer arithmetic (int, i64, u64,…). The former is very fast, applies also to non-integers and covers such a vast range that overflow can essentially be ignored. The drawback is that it has limited precision. The precision for an individual operation (15-16 decimal digits) is enough for virtually any real-world application, but unfortunately errors accumulate in a large computation. Thus one may want to turn to integer arithmetic for situations where exact results are needed, typically when counting things.

The type int has unbounded precision and is the type to turn to for mathematical operations with really big numbers, such as in cryptography. For applications dealing with data from the physical world, I think it is extremely rare to deal with integer values larger than, say, 10^18. One possible example could be financial data for large corporations or countries. The national budget for Sweden for 2024 is only just over 10^13 SEK, but even this number is too big for people to grasp, so it is instead presented in kSEK, where the expenses come to 1 346 694 314, a number around 10^10. I think this point is generally valid. It is useless for practical purposes to do computations where you can distinguish between 473049138815483471 and 473049138815483472.

Unfortunately, int operations are somewhat slow also for integers of everyday size, so one may want to turn to a bounded integer type such as i64 or u64, which can only handle numbers up to ca 10^18. This should be the obvious choice for ints in program bureaucracy roles such as for loop counters, indexing, slicing etc, but also for integer-valued application data. For the rare cases that may deal with very large numbers, I believe that this is always predictable by the programmer, just since the gap to overflow sizes is so enormous in most cases. Thus, one knows when to use type int as a precaution.

The question Kristian raises is whether overflow should be reported (in the form of an exception) or not. As I discuss above, I believe that this is a question of little practical importance, since overflows just don’t occur. Therefore, if the overhead for checking for overflow is non-trivial, I believe that one should not do such checks. Then, of course, the language must prescribe what the result of an overflowing operation is. CPU’s implement arithmetic for bounded integer types as arithmetic modulo 2^wordlength for many reasons, so the natural choice is to specify integer arithmetic for bounded integer types to be modular. Thus, this choice is not mainly because it is particularly useful, but to give a precise semantics. But, in fact, modular arithmetic modulo 2^wordlength is essential for implementing arithmetic for the type int. (Modular arithmetic is also heavily used e.g. in cryptography, but there the modulus is a large prime number, so the modular nature of u64 arithmetic is of no help.)

Of course, overflows may happen because of programming errors, so it is certainly useful to be able to test programs in a mode where overflows are reported. But, this should be seen as a more convenient way of testing than adding assertions or check statements that report when a value becomes bigger than some threshold etc. Therefore I have no problems to have a testing mode where certain programs throw overflow exceptions which should not occur according to the official language definition. But the release mode must of course follow the language definition, which I believe should not fail on overflow.

Finally, we have smaller integer types like i16 and u16 where certainly overflow may occur for real-world data. But the programmers who choose to use these types for some space-saving reason should be trusted to know what they are doing, making careful analyses of the ranges of their data.

[sydow]

I know that some people consider public spending in Sweden to be too extensive, and I believe they would be right if really the budget was over 10^13 SEK. Since the population is around 10^7 this would mean 10^6 SEK per capita , well over our GDP. So the correct figure is 10^12 SEK or 10^9 kSEK. This only strengthen the point; the world GDP can easily be handled in u64…

[plajjan]

I don't really buy the "the programmers who choose to use these types for some space-saving reason should be trusted to know what they are doing". People make mistakes, even the most expert programmers make mistake. I think tests and sanitization are generally good things that benefit everyone.

You @sydow say it is OK to change behavior based on compilation flags, more or less because "overflow should not happen". It sounded like @nordlander was against this.

One option would be to have two operators:

• + which raises an exception on overflow, it always does overflow checking
• +% which has guaranteed twos-complement wrapping behavior and is thus faster

For those trusted programmers, they could just use the +% operator to write their fast programs, right?

[sydow]

I am well aware that programmers make mistakes and I am all for making it easy and powerful to test programs. This should be obvious from all the bugs I produce. The latest one, exposed today, was in the round function which must be implemented in all integer types and in Float. In Float and all bounded integer types one can make use of C’s round function in the implementation and use essentially the same code, but that doesn’t work in type int. I tested the function in Float and i64, but not in the obviously error-prone case int, and there was a bug. I take blame for not testing better; my only excuse is that I do this for fun without getting paid, and even if writing test cases is essential, it can hardly be considered fun.

I do not take blame for not introducing an exception to be raised when the result is malformed in some way. I am against using exceptions to handle programming errors in released code. Exceptions should protect against exceptional situations in the environment (file to be read does not exist, network errors, etc) that are out of the control of the programmer.

To give another example, if my program contains a sorting function for lists, and I use it to sort a list and then iterate over the result it seems wrong to raise an exception if the iteration code discovers that items do not arrive in sorted order.

Integer overflow is, I believe, analogous. If I decide to use a 16 bit type for some integer variable, then that must be based on an analysis of the possible values the variable can assume. If I cannot do this analysis, I should choose a larger type rather than raising an exception when things go wrong. Of course, my choice and the following implementation should be subject to thorough testing.

Here is a proposed analysis for i64, which is the only bounded integer type I would consider, since I do not work in space-constrained environments (but want the speed of bounded integers):

1. Am I convinced that the value of the variable in a correct program cannot exceed one billion? In most cases of integer variables, the answer is yes and I am happy to use type i64. I have a margin of a factor of one billion if I was mistaken and I will not use any overflow tests/exception. But of course I will test the code (well, you know I don’t).

2. If the answer in 1 is no, wouldn’t it be better to use type Float?

3. If the answer in 2 is no, can I give any bound for the maximal value of the variable? If the answer is no, use type int, otherwise work hard to do the analysis and see whether you have margin enough to use type i64. Else use type int or think again about 2.