News for hackers. Stuff that matters.
Re:A bit of background on compilers exploiting signed overflow by akkartik on Sunday May 08, 2016 @03:51PM (#11655435)
There's been a lot of discussion about undefined behavior on HN recently, and I'm gradually starting to question if the conventional approach to compilers might be a giant dead-end. In this case, our conventional languages provide no way for a programmer to say "I care about overflow". Because face it, the vast majority of programs a compiler sees are written extremely sloppily. Most of the time there's this huge disconnect between the amount of effort the programmer and the ghost of the compiler writer are putting into considering such situations.

Now, most of the time this disconnect is a good thing. Division of labor ensures that the work of the compiler writer is amortized across many many programmers. But the discussion around undefined behavior is a sign that the load on the compiler writer has gotten too onerous, to the point that everybody is paying a cost (in reduced performance, in increased compiler complexity leading to reduced compiler stability, in compilers antagonistically interpreting standards like lawyers) for a level of correctness along one narrow dimension that only a tiny fraction of users actually care about.

What if we instead said, "compilers will never ever consider overflow" and let those who care about overflow fend for themselves in the source language? Among other things that would allow integers to always be the word size of the computer they're running on.

(My interest in these questions stems from trying to program in an idealized assembly language for the past year: http://github.com/akkartik/mu. After writing 10kLoC of assembly to build a simple text editor (http://akkartik.name/post/mu) I'm surprised to find it quite ergonomic. High level languages today seem to provide three kinds of benefits over traditional/ugly assembly: expressiveness (e.g. nested expressions, classes), safety (e.g. type checking) and automation (e.g. garbage collection). An idealized assembly language gives up some expressiveness, but doesn't seem to affect the other benefits. As such, it's at an extreme end of the trade-off I describe. I'm hoping my experience will largely translate even when Mu eventually implements a high-level language.)

Edit 21 minutes later: For reference, here's how I've been thinking about undefined behavior while building Mu: https://github.com/akkartik/mu/blob/5dd82a8a70/001help.cc#L4.... Comments most welcome.

Re:A bit of background on compilers exploiting signed overflow by mempko on Sunday May 08, 2016 @04:48PM (#11655741)
With every additional compiler check, you reduce the set of possible programs. It would be interesting if the checks could be easily programatically defined and inserted by those who care. I think Perl6 is probably the best modern compiler that allows this.

I agree, it should not be the compilers job to decide the set of possible programs. The hardware guys figured this out long ago. Afterall, CPU registers are untyped.

Re:A bit of background on compilers exploiting signed overflow by akkartik on Sunday May 08, 2016 @05:45PM (#11656056)
Can you elaborate on what checks Perl6 permits programmers to ask for?
Re:A bit of background on compilers exploiting signed overflow by raiph on Sunday May 08, 2016 @08:29PM (#11656785)
Aiui you can have any checks you want.

Aiui, simplifying, every operation is a function call so you just write a function body that corresponds to what you want the operation to be with the checks you want.

Re:A bit of background on compilers exploiting signed overflow by jmgao on Sunday May 08, 2016 @06:24PM (#11656277)
> In this case, our conventional languages provide no way for a programmer to say "I care about overflow".

GCC and clang have builtin operations that return whether they overflowed (bool __builtin_add_overflow(T a, T b, T* out), etc.). Similarly, Rust has wrapping, checked and saturating versions of all of the operations as methods on the integer types.

Re:A bit of background on compilers exploiting signed overflow by nkurz on Sunday May 08, 2016 @04:27PM (#11655615)
In this case, our conventional languages provide no way for a programmer to say "I care about overflow".

What if we instead said, "compilers will never ever consider overflow" and let those who care about overflow fend for themselves in the source language?

Does specifying an an unsigned type like size_t (as the author suggests in the last paragraph) achieve most of this? It's slightly backward, in that it's telling the compiler that overflow is not explicitly prohibited, but I think it usually has the same effect of preventing optimizations based on the assumption that signed overflow is not allowed.

Re:A bit of background on compilers exploiting signed overflow by akkartik on Sunday May 08, 2016 @04:37PM (#11655676)
Yeah, it's probably as reasonable a hack as you can hope to find in the context of C. The thing to watch out for is that you'd end up with different semantics in arithmetic operations. Right-shift wouldn't sign-extend, for example, that's the first one that comes to mind.

Weirdly enough, in my project above I ended up eschewing unsigned ints and just relying on signed numbers everywhere. I have to take a big hit on performance by adding a couple of asserts that consistently enable this without undefined behavior (and I might still be missing something), but performance hasn't been an issue so far. I just don't want to think about whether I might want to perform subtraction down the road when I create a new int. "Unsigned integer" is an oxymoron since integers are defined to include negative numbers.

Re:A bit of background on compilers exploiting signed overflow by nkurz on Sunday May 08, 2016 @05:06PM (#11655830)
"Unsigned integer" is an oxymoron since integers are defined to include negative numbers.

That's an odd definition of an oxymoron. While "integer" if unmodified does include negative numbers, isn't "unsigned" just an adjective, restricting the general category to the subset to the non-negative subset? For example, is "white swan" an oxymoron because swans can be both black and white?

Interestingly, my first reaction reading your linked code was that not all "integer overflow" is undefined, only signed integer overflow. Regardless of technical correctness, I thought about suggesting that it would read more clearly if you specified "signed" and "unsigned" rather than using "integer" to refer to what programmers refer to as "signed".

Re:A bit of background on compilers exploiting signed overflow by akkartik on Sunday May 08, 2016 @05:23PM (#11655913)
Yes, both are fair points. "Oxymoron" was a lazy jab I just came up with on the fly.

You're right that only signed ints admit undefined behavior. Unfortunately you can't get by using just unsigned ints. So for me the choice was between mixing signed/unsigned and just using signed everywhere. If use of signed ints is unavoidable and also leads to undefined behavior, I'd like to exercise it more often in hopes of learning faster what things I shouldn't be doing. This seems like the more antifragile choice (http://www.amazon.com/Antifragile-Things-That-Disorder-Incer...).