<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Jun 18, 2014 at 8:20 PM, Daniel Micay <span dir="ltr"><<a href="mailto:danielmicay@gmail.com" target="_blank">danielmicay@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 18/06/14 01:08 PM, Gábor Lehel wrote:<br>
> # Exposition<br>
><br>
> We've debated the subject of integer overflow quite a bit, without much<br>
> apparent progress. Essentially, we've been running in circles around two<br>
> core facts: wrapping is bad, but checking is slow. The current consensus<br>
> seems to be to, albeit grudgingly, stick with the status quo.<br>
><br>
> I think we've established that a perfect, one-size-fits-all solution is<br>
> not possible. But I don't think this means that we're out of options, or<br>
> have no room for improvement. I think there are several imperfect,<br>
> partial solutions we could pursue, to address the various use cases in a<br>
> divide-and-conquer fashion.<br>
><br>
> This is not a formal RFC, more of a grab bag of thoughts and ideas.<br>
><br>
> The central consideration has to be the observation that, while wrapping<br>
> around on overflow is well-supported by hardware, for the large majority<br>
> of programs, it's the wrong behavior.<br>
><br>
> Basically, programs are just hoping that overflow won't happen. And if<br>
> it ever does happen, it's going to result in unexpected behavior and<br>
> bugs. (Including the possibility of security bugs: not all security bugs<br>
> are memory safety bugs.) This is a step up from C's insanity of<br>
> undefined behavior for signed overflow, where the compiler assumes that<br>
> overflow *cannot* happen and even optimizes based on that assumption,<br>
> but it's still a sad state of affairs. If we're clearing the bar, that's<br>
> only because it's been buried underground.<br>
><br>
> We can divide programs into three categories. (I'm using "program" in<br>
> the general sense of "piece of code which does a thing".)<br>
><br>
>  1) Programs where wrapping around on overflow is the desired semantics.<br>
><br>
>  2) Programs where wrapping around on overflow is not the desired<br>
> semantics, but performance is not critical.<br>
<br>
</div></div>If performance wasn't critical, the program wouldn't be written in Rust.<br>
The language isn't aimed at use cases where performance isn't a bug<br>
deal, as it makes many sacrifices to provide the level of control that's<br>
available.<br></blockquote><div><br></div><div>People write GUI frameworks and applications in C++ and even in C. Just because a language is appropriate for low-level and performance-critical code doesn't mean it needs to be inappropriate for anything else. I think Rust is far superior as a general-purpose language to most of today's mainstream languages.<br>
<br>And even in applications where some parts are performance-critical, many parts may not be. I expect the ratios may be tilted differently for Rust code, but not the fundamental pattern to be different.<br></div><div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div class="h5"><br>
>  3) Programs where wrapping around on overflow is not the desired<br>
> semantics and performance is critical.<br>
><br>
> Programs in (1) are well-served by the language and libraries as they<br>
> are, and there's not much to do except to avoid regressing.<br>
><br>
> Programs in (2) and (3) are not as well-served.<br>
><br>
><br>
> # Checked math<br>
><br>
> For (2), the standard library offers checked math in the `CheckedAdd`,<br>
> `CheckedMul` etc. traits, as well as integer types of unbounded size:<br>
> `BigInt` and `BigUint`. This is good, but it's not enough. The acid test<br>
> has to be whether for non-performance-critical code, people are actually<br>
> *using* checked math. If they're not, then we've failed.<br>
><br>
> `CheckedAdd` and co. are important to have for flexibility, but they're<br>
> far too unwieldy for general use. People aren't going to write<br>
> `.checked_add(2).unwrap()` when they can write `+ 2`. A more adequate<br>
> design might be something like this:<br>
><br>
>  * Have traits for all the arithmetic operations for both checking on<br>
> overflow and for wrapping around on overflow, e.g. `CheckedAdd` (as<br>
> now), `WrappingAdd`, `CheckedSub`, `WrappingSub`, and so on.<br>
><br>
>  * Offer convenience methods for the Checked traits which perform<br>
> `unwrap()` automatically.<br>
><br>
>  * Have separate sets of integer types which check for overflow and<br>
> which wrap around on overflow. Whatever they're called: `CheckedU8`,<br>
> `checked::u8`, `uc8`, ...<br>
><br>
>  * Both sets of types implement all of the Checked* and Wrapping*<br>
> traits. You can use explicit calls to get either behavior with either types.<br>
><br>
>  * The checked types use the Checked traits to implement the operator<br>
> overloads (`Add`, Mul`, etc.), while the wrapping types use the Wrapping<br>
> traits to implement them. In other words, the difference between the<br>
> types is (probably only) in the behavior of the operators.<br>
><br>
>  * `BigInt` also implements all of the Wrapping and Checked traits:<br>
> because overflow never happens, it can claim to do anything if it "does<br>
> happen". `BigUint` implements all of them except for the Wrapping traits<br>
> which may underflow, such as `WrappingSub`, because it has nowhere to<br>
> wrap around to.<br>
><br>
> Another option would be to have just one set of types but two sets of<br>
> operators, like Swift does. I think that would work as well, or even<br>
> better, but we've been avoiding having any operators which aren't<br>
> familiar from C.<br>
><br>
><br>
> #  Unbounded integers<br>
><br>
> While checked math helps catch instances of overflow and prevent<br>
> misbehaviors and bugs, many programs would prefer integer types which do<br>
> the right thing and don't overflow in the first place. For this, again,<br>
> we currently have `BigInt` and `BigUint`. There's one problem with<br>
> these: because they may allocate, they no longer `Copy`, which means<br>
> that they can't be just drop-in replacements for the fixed-size types.<br>
><br>
><br>
> To partially address this, once we have tracing GC, and if we manage to<br>
> make `Gc<T>: Copy`, we should add unbounded `Integer` (as in Haskell)<br>
> and `Natural` types which internally use `Gc`, and so are also `Copy`.<br>
> (In exchange, they wouldn't be `Send`, but that's far less pervasive.)<br>
> These would (again, asides from `Send`) look and feel just like the<br>
> built-in fixed-size types, while having the semantics of actual<br>
> mathematical integers, resp. naturals (up to resource exhaustion of<br>
> course). They would be ideal for code which is not performance critical<br>
> and doesn't mind incurring, or already uses, garbage collection. For<br>
> those cases, you wouldn't have to think about the tradeoffs, or make<br>
> difficult choices: `Integer` is what you use.<br>
<br>
</div></div>A tracing garbage collector for Rust is a possibility but not a<br>
certainty. I don't think it would make sense to have `Gc<T>` support<br>
`Copy` but have it left out for `Rc<T>`. The fact that an arbitrary<br>
compiler decision like that would determine the most convenient type is<br>
a great reason to avoid making that arbitrary choice.<br>
<br>
There's no opportunity for cycles in integers, and `Rc<T>` will be<br>
faster along with using far less memory. It doesn't have the overhead<br>
associated with reference counting in other languages due to being<br>
task-local (not atomic) and much of the reference counting is elided by<br>
move semantics / borrows.<br>
<br>
With the help of sized deallocation, Rust can have an incredibly fast<br>
allocator implementation. Since `Rc<T>` is task-local, it also doesn't<br>
need to be using the same allocator entry point as sendable types. It<br>
can make use of a thread-local allocator with less complexity and<br>
overhead, although this could also be available on an opt-in basis for<br>
sendable types by changing the allocator parameter from the default.<br>
<div class=""><br>
> One concern with this would be the possibility of programs incurring GC<br>
> accidentally by using these types. There's several ways to deal with this:<br>
><br>
>  * Note the fact that they use GC prominently in the documentation.<br>
><br>
>  * Make sure the No-GC lint catches any use of them.<br>
><br>
>  * Offer a "no GC in this task" mode which fails the task if GC<br>
> allocation is invoked, to catch mistakes at runtime.<br>
><br>
> I think these would be more than adequate to address the concern.<br>
<br>
</div>I don't think encouraging tracing garbage collection is appropriate for<br>
a language designed around avoiding it. It would be fine to have it as a<br>
choice if it never gets in the way, but it shouldn't be promoted as a<br>
default.<br></blockquote><div><br></div><div>The idea is to pick the low-hanging fruit. For programs that use garbage collection, we can offer an integer type that requires neither ergonomic nor semantic compromises. So let's.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class=""><br>
> # Between a rock and a hard place<br>
><br>
> Having dispatched the "easy" cases above, for category #3 we're left<br>
> between the rock (wraparound on overflow is wrong) and the hard place<br>
> (checking for overflow is slow).<br>
><br>
> Even here, we may have options.<br>
><br>
> An observation:<br>
><br>
>  * We are adamantly opposed to compiler switches to turn off array<br>
> bounds checking, because we are unwilling to compromise memory safety.<br>
><br>
>  * We are relatively unbothered by unchecked arithmetic, because it<br>
> *doesn't* compromise memory safety.<br>
><br>
> Taking these together, I think we should at least be less than adamantly<br>
> opposed to compiler switches for enabling or disabling checked arithmetic.<br>
<br>
</div>I think compiler switches or attributes enabling a different dialect of<br>
the language are a bad idea as a whole. Code from libraries is directly<br>
mixed into other crates, so changing the semantics of the language is<br>
inherently broken.<br></blockquote><div><br></div><div>Even if checked arithmetic is only turned on for testing/debugging and not in production code, it's still a strict improvement over the status quo. Under the status quo, except where wraparound is the intended semantics, overflow is silently wrong 100% of the time. With the alternative, that percentage is smaller.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5"><br>
> Consider the status quo. People use integer types which wrap on<br>
> overflow. If they ever do overflow, it means misbehaviors and bugs. If<br>
> we had a compiler flag to turn on checked arithmetic, even if it were<br>
> only used a few times in testing, it would be a strict improvement: more<br>
> bugs would be caught with less effort.<br>
><br>
> But we clearly can't just add this flag for existing types, because<br>
> they're well-defined to wrap around on overflow, and some programs<br>
> (category #1) rely on this. So we need to have separate types.<br>
><br>
> One option is therefore to just define this set of types as failing the<br>
> task on overflow if checked arithmetic is enabled, and to wrap around if<br>
> it's disabled. But it doesn't necessarily make sense to specify<br>
> wraparound in the latter case, given that programs are not supposed to<br>
> depend on it: they may be compiled with either flag, and should avoid<br>
> overflow.<br>
><br>
> Another observation:<br>
><br>
>  * Undefined behavior is anathema to the safe subset of the language.<br>
> That would mean that it's not safe.<br>
><br>
>  * But *unspecified results* are maybe not so bad. We might already have<br>
> them for bit-shifts. (Question for the audience: do we?)<br>
><br>
> If unspecified results are acceptable, then we could instead say that<br>
> these types fail on overflow if checked arithmetic is enabled, and have<br>
> unspecified results if it isn't. But saying they wrap around is fine as<br>
> well.<br>
><br>
> This way, we can put off the choice between the rock and the hard place<br>
> from program-writing time to compile time, at least.<br>
><br>
><br>
> # Defaults<br>
><br>
> Even if we provide the various options from above, from the perspective<br>
> of what types people end up using, defaults are very important.<br>
><br>
> There's two kinds of defaults:<br>
><br>
> * The de jure default, inferred by the type system in the absence of<br>
> other information, which used to be `int`. Thankfully, we're removing this.<br>
><br>
> * The de facto, cultural default. For instance, if there is a type<br>
> called "int", most people will use it without thinking.<br>
><br>
> The latter question is still something we need to think about. Should we<br>
> have a clear cultural default? Or should we force people to explicitly<br>
> choose between checked and wrapping arithmetic?<br>
><br>
> For the most part, this boils down to:<br>
><br>
>  * If `int` is checked, the default is slow<br>
><br>
>  * If `int` wraps, the default is wrong<br>
><br>
>  * If there is no `int`, people are confused<br>
><br>
> Regarding the first, we seem to be living in deathly fear of someone<br>
> naively writing an arithmetic benchmark in Rust, putting it up on the<br>
> internet, and saying, "Look: Rust is slow". This is not an unrealistic<br>
> scenario, sadly. The question is whether we'd rather have more programs<br>
> be accidentally incorrect in order to avoid bad publicity from<br>
> benchmarks being accidentally slow.<br>
><br>
> Regarding the third, even if the only types we have are `intc`, `intw`,<br>
> `ic8`, `iw8`, and so on, we *still* can't entirely escape creating a<br>
> cultural default, because we still need to choose types for functions in<br>
> the standard library and for built-in operations like array indexing.<br>
> Then the path of least resistance for any given program will be to use<br>
> the same types.<br>
><br>
> There's one thing that might help resolve this conundrum, which is if we<br>
> consider the previously-described scheme with compiler flags to control<br>
> checked arithmetic to be acceptable. In that case, I think those types<br>
> would be the clear choice to be the de facto defaults. Then we would have:<br>
><br>
>  * `i8`, `u8` .. `i64`, `u64`, `int`, and `uint` types, which fail the<br>
> task on overflow if checked arithmetic is turned on, and either wrap<br>
> around or have an unspecified result if it's off<br>
><br>
>  * a corresponding set of types somewhere in the standard library, which<br>
> wrap around no matter what<br>
><br>
>  * and another set of corresponding types, which are checked no matter what<br>
><br>
><br>
> -Gábor<br>
<br>
</div></div><br>_______________________________________________<br>
Rust-dev mailing list<br>
<a href="mailto:Rust-dev@mozilla.org">Rust-dev@mozilla.org</a><br>
<a href="https://mail.mozilla.org/listinfo/rust-dev" target="_blank">https://mail.mozilla.org/listinfo/rust-dev</a><br>
<br></blockquote></div><br></div></div>