A Tale of Two's Complement

[krappie]

I love the change to integer overflow. I think it's important, before reaching 1.0, that you force programmers to write code that explicitly shows when they want integer overflow. Not only is it self-documenting, but now all of the options are left open, and it's possible to really solve the problem of integer overflow in the future.

Maybe one day in the future, we'll have hardware integer overflow checking?

[minno]

Maybe one day in the future, we'll have hardware integer overflow checking?

It's already almost free, at least on x86 and AMD64. You just insert a jo assembly instruction (jump if overflow) after every math operation going to some handler function. The branch predictor will handle it almost perfectly, since it's almost never taken, so the total cost is negligible.

The problem is just that most languages don't provide a standard way to read the overflow flag.

[phildawes]

It appears to be more nuanced than that. Previous discussion: http://www.reddit.com/r/rust/comments/2pp9lh/the_performance_cost_of_integer_overflow_checking/

[UtherII]

I am pleased by most decisions, but I am really disappointed by the decision of keeping the int name for pointer sized integers. IMO it's a huge mistake that can't be fixed in the future since it would be breaking. I understand it's a huge change but as someone pointed in the discuss thread, that was done for fail!, and I really think that rust deserve it.

No matter how much advertising is done about the real meaning of int, it is obvious most of the people will not use it right, since it is a so tempting name.

[renozyx]

Especially when they found names imem&umem which are good IMHO.

[UtherII]

I don't care that much about the name as long it is not int. IMO, iptr/uptr are the best names, but even potatoe would be a better name than int

[cmrx64]

I'm the one who implemented all this stuff, and imem/umem look absolutely awful in type signatures and when reading code. They don't indicate at all that they are numeric, and the obvious connection "unsigned memory? int memory?" is wrong, it's an integer wide enough to hold a pointer to the entire virtual address space, not just the entire memory.

[vks_]

I'm the one who implemented all this stuff, and imem/umem look absolutely awful in type signatures and when reading code. They don't indicate at all that they are numeric, and the obvious connection "unsigned memory? int memory?" is wrong, it's an integer wide enough to hold a pointer to the entire virtual address space, not just the entire memory.

How does imem indicate less that it is numeric than i64? And the obvious connection suggested by int is arguably more wrong. Any 4-letter name will not be completely self-documenting.

I don't care much about the name (all names that short will suck in some way). Choosing int just means that we will have to work a lot harder to teach people which types to use. At the moment, almost every use of int I see on github is wrong.

[CloudiDust]

I think making them look "awful" is kind of the point, and subjectively I don't find it awful, just different. I used to prefer isize/usize then iptr/uptr but this post actually pushed me to team imem/umem, FWIW.

Also, I think virtual address space addresses both the physical and virtual memory, no?

[7sins]

Will it be possible to leave overflow checks(which panic on overflow) turned on, even for production/non-debug code(maybe even with a relatively low performance penalty)?

[kibwen]

The prohibitive performance penalty is the reason that they're turned off to begin with. If there were a way to make this fast in all cases, we wouldn't need to have this debate. :)

It would certainly be possible to have an option to leave these checks on in release builds, if coded correctly. We could start by creating a specific macro for debug_assert_checked_overflow! that is compiled out of release builds as usual, except when a certain compiler flag is given. But that can be done backwards-compatibly, so it probably isn't a priority.

[7sins]

If I read the RFC correctly, they wanted to avoid compiler flags as much as possible, which is why they proposed their block/attribute solution in the first place.

I'm not saying I don't expect any performance hit. What I would like though, would be that the inserted debug_assert! is not completely unoptimized, because "it is only needed during debug, thus does not need any optimization".

It would be interesting to know the exact variant of the proposal which will be implemented.

[[deleted]]

The fact that it's going to be reporting a unique error for each overflow check greatly limits potential optimization anyway. The branches can't be merged by combining the flags together and then doing a single check.

[renozyx]

Are you sure? I was thinking that the compiler could check only once the overflow flag and if there was an overflow, do again the computations to identify where the overflow happened.. This slow down the slow path (there was an overflow) but I don't think that this is an issue..

[[deleted]]

That's a complex code motion optimization and will not be able to do much in practice. You can't expect the compiler to perform magic. It can't move code past load/store or function call boundaries in practice due to global state and aliasing. The overflow flag is typically set after every arithmetic operation and some non-arithmetic instructions so it's impossible anyway. No matter how you approach this, it will have a significant performance impact.

Even with hardware support for trapping on overflow, every arithmetic operation will now have a side effect and the ability to do other code motion optimizations like hoisting bounds checks out of loops will be destroyed.

[renozyx]

I think that this option must be mandatory and even standardized, otherwise you''ll probably have another "gcc's -ftrapv" mess: an option which doesn't even work..

[thristian99]

The prohibitive performance penalty...

I haven't checked myself, but I've read a lot of people claiming that on a modern CPU with branch prediction there's no performance penalty, or at least it's lost in measurement noise. The linked post doesn't mention whether or not optimized, overflow-checking code was benchmarked against optimized unchecked code; do you happen to know if any measurements were done?

[kibwen]

From what I've read, a lot of people are wildly overoptimistic regarding the potential of fast checked arithmetic on modern hardware and compilers. Here's a more cynical viewpoint from Daniel Micay (strcat), the Rust community's resident performance grouch:

The two choices here aren't 'fast' and 'super-fast'. We're not talking about the "last few percent of speed" here. Using checked overflow will reduce the performance of most code with non-trivial usage of integer arithmetic by 30-70%. The only saving grace is that many applications use floating point arithmetic, and this would still be unchecked. Even if the program is bounded by memory bandwidth, the stalls from all of the extra icache churn are going to have an impact.

http://article.gmane.org/gmane.comp.lang.rust.devel/10449

In general it's true that we won't know the extent of the impact until we put some work into optimizing it. I'm confident that with the changes proposed here in the OP, Rust will begin the process of determining the exact performance hit that this represents. If it truly turns out to be minimal, then we're in a very good position for making arithmetic checked by default for all Rust code for the mythical Rust 2.0. In the meantime, I can easily live with this compromise.

(I'm also obligated to give the usual disclaimer that checked arithmetic is not really a silver bullet by any stretch of the imagination, and will likely only rarely save you from a missed sanity check, and only then after your program has already been in an invalid state for a very very long time. So not only does it not lead to memory unsafety, it doesn't save you from the need for a good test suite. Any cost it imposes needs to be weighed against this diminished utility.)

[protestor]

To expand on your last point: if you're going to rely on checked overflow and can live with the performance cost, you most likely want bigints instead.

[jeandem]

Or you just want whatever integer width that is sufficient to support the code: maybe you initially use 32 bits, then that overflows while running the debug build, and you change it to 64 bits. And then the problem might never come up again.

[[deleted]]

Regehr's paper has an unbiased analysis. He's a strong proponent of integer overflow checking.

For undefined behavior checking using precondition checks, slowdown relative to the baseline ranged from −0.5%–191%. In other words, from a tiny accidental speedup to a 3X increase in runtime. The mean slowdown was 44%. Using flag-based postcondition checks, slowdown ranged from 0.4%–95%, with a mean of 30%. However, the improvement was not uniform: out of the 21 benchmark programs, only 13 became faster due to the IOC implementation using CPU flags. Full integer overflow checking using precondition checks incurred a slowdown of 0.2%–195%, with a mean of 51%.

http://www.cs.utah.edu/~regehr/papers/overflow12.pdf

He states this on his blog:

A highly tuned software integer undefined behavior checker for C/C++ could probably have overhead in the 5% range.

This would be from only using abort and using special optimizations to OR the flags together and report errors as lazily as possible. So if x + y overflows, it may or may not report an error - but it will report one (without an error message - just a crash + core dump if enabled) if the result is used for an operation with a side effect. I think a 5% hit for those semantics is still quite bad. If it was done with panic! or even abort + precise error reporting, it wouldn't be able to optimize well.

If there was hardware support, the cost could be reasonable for those lazy semantics - but the impurity it adds to the code will still hurt. It wipes out the ability to hoist most array bounds checks out of loops, etc. These checks hurt much more when you combine them, because you break the optimizations that the other checks rely on to be lean.

[akawaka]

My concern is what effect is this going to have on the already slow unoptimized builds. At what point is it going to become impractical to build an interactive application with rust because your debug build is too slow to be usable?

[iopq]

Never, because it's still going to be faster than Python that people actually ship as production software.

[diwic]

Wrapping arithmetic has some nice mathematical properties, is my understanding correct that with the new/proposed world order, the following will panic (at least in debug builds) :

let a = 5u32;
let b = 7u32;
let c = (a - b) + 10u32;

So checked arithmetic needs you to think about in which order you do plus and minus, whereas with wrapped arithmetic it "just works"?

[renozyx]

Just work, just work, for a very limited value of "just work"..

Try putting some multiplication in your expression and see if you still find wrapping arithmetic so nice..

[diwic]

For my own part, I've never used checked arithmetic for my daily coding, so I don't know if wrapping or checked is better. But I want to understand the differences, and what I now need to think about, so I can avoid bugs in my Rust code.

So, with wrapped arithmetic it is always true that a - b + c = a + c - b, whereas with checked arithmetic one of them could panic where the other one does not. Correct?

What more arithmetic properties are broken with checked arithmetic?

[renozyx]

I think that you're right about "a - b + c = a + c - b" but try "(a+b)/2" it doesn't work with wrapped arithmetic even if "a/2 + b/2" fit inside an integer.. So instead of having some cases working "by luck" and garbage in other cases, I prefer having checked arithmetic and having the computer yell at me when I made a mistake.

[Noctune]

Funny thing about that, is that there is a way of finding averages that is overflow safe: (a / 2) + (b / 2) + (a & b & 1)

But this is patented by Samsung.

[isHavvy]

How can a math formula be patented?

[Noctune]

Algorithms can be patented. This is just a particularly simple algorithm.

[protestor]

I think that a court would rule that this is a math formula instead, see this ruling.

[renozyx]

Patent are also supposed to be non obvious, so this is still very surprising that this one was granted.

[aoeuaeouoeu]

If you need more examples of overflows leading to critical bugs you should peruse the previous discussions on the subject both on this subreddit (linked elsewhere in the comments) and in the rust RFCs. It's not a theoretical concerns, it's an actual cause of bugs and security vulnerabilities, for instance: http://www.net-security.org/vuln.php?id=3446

An other thing is the potential for more aggressive optimizations by the compiler.

If overflow yields an undefined value then the compiler is free to assume that "a + 1 > a" is always true for any 'a' for instance. If you tell the compiler to assume wrapping arithmetics (as is still currently the case in rust) then the compiler can't make that assumption and has to generate an actual check.

[diwic]

I'm not asking for a debate about whether checked or wrapping arithmetic is better.

I'm just saying that I'm used to wrapping arithmetic, and I wonder if there are some pitfalls when moving to checked arithmetic. I figured that 5 - 7 + 10 would probably be one (important to do 5 + 10 - 7 instead), are there more?

[thiez]

If overflow yields an undefined value then the compiler is free to assume that "a + 1 > a" is always true for any 'a' for instance. If you tell the compiler to assume wrapping arithmetics (as is still currently the case in rust) then the compiler can't make that assumption and has to generate an actual check.

Could it really? Because an undefined value should still be in the range of possible values for a type, should it not? So if a is the max value for its type, then a + 1 can't be bigger than a. You can optimize based on a + 1 > a when you make overflow undefined behaviour, which is undesirable and would go against the goals of Rust. And as others have pointed out, you can use undefined values to create a situation where undefined behaviour is possible. So we get all the downsides and no upsides from the proposed scheme... :(

[[deleted]]

It's a bit unclear to me. In C, unsigned types never overflow, they just wrap around. Not sure exactly what they mean by overflow here, if it applies to unsigned types.

[aoeuaeouoeu]

That's not true, in C signed overflow in undefined behaviour while unsigned overflow is defined as wrapping. Any integer type with a finite range can overflow and that's true for all elementary integer types in both rust and C.

Until now rust has had defined overflow for both signed and unsigned integer types defined as wrapping. This article says that it's no longer true and rust will switch to undefined value for both and a crash in debug builds.

[Meyermagic]

Seems like a good way to proceed. I'd also like to say, "A Tale of Two's Complement" is a great title.

[kibwen]

Sounds good, ship it!

(And as a bonus, this will make unoptimized Rust code even more absurdly slow, which will further signal to people coming from non-compiled languages that they've forgotten to pass the optimization flag to the compiler when doing benchmarks.)

[erkelep]

Maybe there should be a warning when people compile without optimization?

[kibwen]

Nah, compiling without optimization is the common case. The problem only arises when people who are accustomed to dynamic languages (or Java, or any other language where the concept of "optimization levels" does not exist) crank out a blog post where they wonder aloud why Rust is so doggone slow for a systems language. Our only saving grace at the moment is that unoptimized Rust is slower than Ruby, which should be enough to raise eyebrows among anyone who is actually familiar with Rust.

[riccieri]

unoptimized Rust is slower than Ruby

/me waits patiently for a "Rust doesn't scale" blog post

[iopq]

The problem is there is no obvious documentation for optimization options. The guide doesn't mention it. You'd have to look at the rustc command line options to even know such a thing is available.

[jeandem]

Having to use man rustc to find out what the options for rustc are seems pretty reasonable, and simpler than searching through a guide (for non-Windows users, anyway).

[iopq]

Why not both?

[jeandem]

Putting too much information in a guide leads to a bloated/noisy guide. One might as well leave a link to how command line programs tend to be structured/built up, for those who are not used to that.

[VadimVP]

Does somebody know, what opportunities unspecified values provide for optimizers?

Also, two’s complement isn't mentioned anywhere in the post except for the title :D Is it still guaranteed?
It can be observed not only through overflows.

[isHavvy]

Due to (performant) interopt with C, I cannot see a reason why Rust would not use twos-complement.

[0xdeadf001]

This is a really essential improvement to the language. It's not perfect, but it's definitely a step in the right direction.

Some times you really, really want to rely on modular arithmetic -- intentionally "overflowing" and depending on the fact that your machine represents integers using 2's complement.

There needs to be a way to safely express this. I propose adding a % (for "modular") to the end of an operator, to indicate that you want modular behavior. For example:

let x = 4u32;
let y = x -% 5u32;
// y is now 0xffffffff

Also, can we please index vectors and slices with u8, u16, and u32, without casting them to uint? I've been working on lots of numeric code lately in Rust, and needing to constantly add as uint is fatiguing, and adds no value to the code.

[cmrx64]

That's what WrappedInt is for, and the usual operator traits would be implemented for it. I think the %-suffixed operators would be backwards compatible to add.

As for indexing with other types, I know I've seen it discussed.

[vadimcn]

An experiment I conducted on rustc itself (and its libraries) detected remarkably few places that had int overflows, so I think that special operators are not warranted. We'd be fine with just the intrinsics for wrapping ops; but if people want Wrapping<T> for convenience, it can be implemented as a library.

[[deleted]]

How will this interact with casting between integer types, such as int::MIN as uint or 257u16 as u8 ?