Hacker News Reader

Comment by userbinator | Hacker News Reader

For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true".

If a programmer writes "X+1 > X", chances are this is an overflow check. Doing this is perfectly defined by the standard if X is an unsigned integer, but not if it's signed. That's what doesn't make sense, since they could've made the unsigned case undefined as well.

which allows a broad range of loop optimizations to kick in

What sort of optimisations exactly, and just how significant are they? I don't believe C should be a language where the compiler does all sorts of high-level optimisation; it should be a straightforward "do what I say" type of language where you get almost exactly what you write, and the only optimisations should be at the level of things like instruction selection --- the optimisations that a programmer would not be able to do at the source level.

View on HN

> I don't believe C should be a language where the compiler does all sorts of high-level optimisation; it should be a straightforward "do what I say" type of language where you get almost exactly what you write, and the only optimisations should be at the level of things like instruction selection --- the optimisations that a programmer would not be able to do at the source level.

In that case, you're asking for easily 3x-5x less performance in the software you use every day, if not more. You can get essentially this by turning on -O0 and compiling, say, Firefox. This is done in debugging, and it's a terrible browsing experience.

Compiler optimizations are really, really important. CSE, GVN, LICM, SROA, etc. aren't done for fun. They're done because modern software depends on them to be fast.

Writing low-level "post-optimized" code is at odds with good engineering practice. If you can't factor things out into functions and count on an inliner to inline them and then propagate away constants, SROA away intermediate structures, etc. then you're essentially telling programmers they can't factor code out into functions. If your compiler refuses to do the Hacker's Delight integer divide optimization (which, by the way, you need good constprop to make good use of a lot of the time), then you're telling programmers they have to get out their copy from their bookshelf and compute the magic number every time they want to integer divide fast (especially on ARM). This sort of thing puts a huge drain on developer productivity and maintainability.

IMHO aggressive optimization at compile time is an example of premature optimization. Let the hardware have access to a straightforward representation. Once the run-time hot-spots are identified, the hardware (firmware, VM, whatever) can rewrite the binary code to execute faster. Excessive compiler optimization makes this difficult or impossible (too much information thrown away.) Compilers should be designed for fast compilation speed.

That would work if most applications spent all their time in a few hot spots. But, contrary to popular wisdom, that's usually not the case. Most applications have flat profiles (to steal a quote from DannyBee—but it matches my experience as well). They have flat profiles because people have spent a lot of time optimizing them. In this context—which is the norm—eliminating optimizations to save compile time and deferring optimization to a few "hot spots" has the effect of turning off optimization for the whole program.

It's common to write off compiler optimizations as unimportant, because they're invisible and people don't see them. They're also complex, which makes people predisposed to get rid of them in the name of "simplicity". But, for better or for worse, optimizing compilers are necessary complexity.

Optimizing compilers are not ubiquitous because compiler engineers just like to play with technology. They're ubiquitous because you need them.

I agree optimization is important. So important that it should be pushed down into the hardware. Binaries should look almost like source code. But that's just my vision for what it's worth.

Hardware already does insane amounts of optimization. The modern superscalar out of order processor basically does it's own JIT from X86 into their own internal micro-ops. Reordering instructions on the go etc. That's another 2-10x speed difference on modern computers.

Completely agree :) But even better to push C code straight down to the hardware and let it crunch on that! Let it allocate a few thousand registers, or spawn off an FPGA compiler to create a few new instructions. Crazy?

Hardware doesn't work like this. You might want to read Hennessy and Patterson, and the original RISC I paper.

http://www.amazon.com/Computer-Architecture-Fifth-Edition-Qu...

http://www.cecs.pdx.edu/~alaa/ece587/papers/patterson_isca_1...

RISC created a huge local minimum by speeding up C code to the exclusion of other languages. I predict that eventually future processors will hide more features from the higher software levels (such as number of registers, instruction types and formats) in order to improve efficiency at the machine level. I think we are seeing this trend with GPUs already. Current CPUs don't do this because they have to maintain binary compatibility with a huge installed base. We can compare notes in a decade or so :-)

Current processors already do that. You don't see the true number of registers or the true instruction set/format of any modern Intel processor. x86 instructions are translated into micro-ops, so x86 is really just a compatibility layer.

I do agree that current processors optimize for C/C++ (although of course there are niche systems like Azul which optimize for other languages). It would be nice to have processor extensions that allow us get better GC performance, or better handling of immutable values. There's a chicken-and-egg problem getting there.

> RISC created a huge local minimum by speeding up C code to the exclusion of other languages

Would you mind expanding this.

In the future I believe you are going to see less emphasis on the aggressive speedup of C code for traditional CPUs. Instead you will see many more gadgets with simpler processors that run C code slower in the effort to save power. GPGPUs and algorithm specific hardware (e.g. video, crypto, network, DSP, neural nets) will fill out the rest of the chip. At some point GPUs will have enough raw power and GP features for it to be possible to run an instance of a late-80's operating system within the working set of a single GPU processing element (perhaps with virtual memory emulated as in jslinux.) At that point the need for a power hungry CPU and artificial CPU/GPU distinction will start to fade away completely. Along with Peak Oil we will have Peak CPU.

So, in general I am saying that the road to better performance will not be in aggressive compiler optimization, but rather in higher level design tools to manage totally new software/hardware abstractions. Binaries will be specified at a higher level and look more like source code. At this point my crystal ball becomes admittedly a bit fuzzy.

Your claim was that RISC "created a huge local minimum by speeding up C code to the exclusion of other languages" and it's not at all clear to me what RISC has to do with c, and why other languages are worse off for this.

GPU's don't do any OoO processing like modern CPU's do. They also don't do any register renaming. They execute things really literally, up to the point where one has to manually put delay slots for pipelined stuff if one really writes the raw asm (Which the manufacturers tend to keep really hidden, in order to avoid the binary compatibility trap, see https://github.com/NervanaSystems/maxas as an example for third party assembler for nvidia Maxwell arch)

On GPU's the binary compatibility issue is solved by having the driver compile the shader/compute kernel before it's used. As an example nvidia uses PTX (see http://docs.nvidia.com/cuda/parallel-thread-execution/) as an intermediate language in CUDA which is then compiled by the runtime into the actual ASM.

On modern CPU's the register renaming has already decoupled the physical registers from the instruction set register. As an example modern haswell has over 100 registers per core.

It doesn't really seem like this solves the problem of optimizers introducing bugs and vulnerabilities.

Take the canonical optimizer-created security hole: the hardware optimizer replaces a constant-time compare (which doesn't leak timing information) with a variable-time compare (which does).

I don't think this solves the problem we're setting out to solve, ie. the optimizer introducing bugs.

Maybe we are all better served by faster compilers that create straightforward binaries (and less bugs overall both in the compiler and application code.) Optimization researchers could focus on source-to-source transformation tools with intelligent human-in-the-loop guidance. Or else they can work at the hardware/JIT level if they prefer.

Right now compiler writers are playing in a kind of local minimum (premature optimization as I said.) This may produce 3x-5x faster binary code today but also forces CPU manufacturers to retain backward compatibility causing them to also stay stuck in this local well. Eventually a new architecture is created (with 10x the registers etc.) and the cycle continues.

That good point, replacing a constant time compare with a non constant time compare is a very terrible bug to introduce.

A more amusing issue I saw was an optimization that looked for places where it could replace manual memory copying with ca call to memcpy. Something that drove the guys writing libc nutzoid. Because it was replacing the code in memcpy with a call to memcpy. (On some platforms you can implement memcpy with special assembly language calls. On some you can't)

Personally I care little about speed, since if I need more speed I can get that. And frankly if you tell me the resulting binary is 20% faster for some things, I just do not care. But I worry a lot about losing the ability to reason about side effects.

> You can get essentially this by turning on -O0 and compiling, say, Firefox. This is done in debugging, and it's a terrible browsing experience.

Which says more about Firefox than it does about -O0. I've run Seamonkey on 3x-5x slower machines than I use these days and it's been fine.

Gecko is what mostly benefits from the optimizations, and Gecko is the largest component shared between SeaMonkey and Firefox. I don't believe SeaMonkey at -O0 is an acceptable experience.

What I want is for the semantics of the language to match the semantics of the physical machine I'm writing software for. If on x86 INT_MAX+1==INT_MIN, then that's what should happen on x86. If on ARM INT_MAX+1==INT_MAX, that's what should happen on ARM. No, I don't want portability. Portability means you're coding against the least common denominator. If I want it to be portable, I'll use a different compiler.

> If on x86 INT_MAX+1==INT_MIN [...]

There is no such thing as "+ on x86". "+" is an operator of the C language. Modern x86 has about two dozen instructions that can be used to perform additions, each with slightly different behaviour, and with different performance characteristics. Someone has to define how C's "+" maps to those instructions. That is what the C standard does. The way it does that is by specifying properties that any implementation of C's "+" needs to have, leaving the specific choice of instructions to the compiler writer.

There are integer additions of different size, but is there anything you could honestly call plain integer addition that has different behavior from wrapping?

What's your point? If you define a "plain integer addition" to be "wrapping binary two-complement addition", then there isn't, otherwise, there is.

But the C standard doesn't say "+ maps to what you could honestly call plain integer addition" anyway, so it's kindof pointless? And if you were to define your own language, you obviously could define "+" to have architecture-specific semantics, whithout appealing to any "plain integer addition".

>What's your point? If you define a "plain integer addition" to be "wrapping binary two-complement addition", then there isn't, otherwise, there is.

I'm not defining it that way. I used the word 'plain' because some instructions are specifically designed to be variants of normal instructions. It's in their name that they do thing abnormally, so they should be discarded when talking about normal behavior.

>But the C standard doesn't say "+ maps to what you could honestly call plain integer addition" anyway, so it's kindof pointless?

You originally said: There is no such thing as "+ on x86". "+" is an operator of the C language.

So I was explaining what "+" means in the absence of C rules.

+ means addition in general conversation, that's basic math and English skills.

That it's integer addition is obvious from context, because we're adding 1 to INT_MAX.

And I already explained why I used the word 'plain'.

There are architectures with normal integer add instructions that do not have twos-complement behavior. I'm just not aware of any such instructions on x86. Can you name one?

If there are none, then I am comfortable asserting that "+" on x86 exists and is twos-complement.

> + means addition in general conversation, that's basic math and English skills. > > That it's integer addition is obvious from context, because we're adding 1 to INT_MAX.

Well ... yeah, "+" usually means addition, sure. But there are so many types of addition that that's not really specific enough for a language definition. And adding 1 to INT_MAX? Well, you could interpret "INT_MAX" to indicate C code, and thus "+" to be C's addition operator. In which case, it's not integer addition, at least not the kind that basic math and English skills would suggest: Adding two positive integers is always defined (and also never gives a value lower than either of the two operands), very much unlike "+" for "int"s in C.

> There are architectures with normal integer add instructions that do not have twos-complement behavior. I'm just not aware of any such instructions on x86. Can you name one?

Sure, PADDSW, for example. At least if I understand your "twos complement" requirement correctly to mean a specific wraparound behaviour. Or, if you want to count that, DAA and AAA.

>PADDSW

As I see it that's a variant of PADDW, so whatever PADDW does is what matters, and PADDW does twos complement.

>DAA and AAA

I thought about calling those out, I think it's stretching too much to refer to an archaic instruction that works on 'ascii' or such when we're figuring the behavior of 'integers'. Even if it is one byte.

> As I see it that's a variant of PADDW, so whatever PADDW does is what matters, and PADDW does twos complement.

Nope, PADDW is a variant of PADDSW, so whatever PADDSW does is what matters, and PADDSW does saturating addition.

Or in other words: You are defining "normal" to mean "twos-complement with wrap-around" after all, which makes it rather unsurprising that every "normal" instruction according to your definition turns out to be doing twos-complement addition with wrap-around.

> I thought about calling those out, I think it's stretching too much to refer to an archaic instruction that works on 'ascii' or such when we're figuring the behavior of 'integers'. Even if it is one byte.

Well, packed BCD definitely is not ASCII. Nor twos-complement, nor ones-complement, nor IEEE754. And BCD quite definitely represents a range of the integers.

"ascii adjust after addition"

> Nope, PADDW is a variant of PADDSW, so whatever PADDSW does is what matters, and PADDSW does saturating addition.

That's like arguing that Red Sports Car is a variant of Red Sports Car with Stripes. The one that adds adjectives is the variant, the one without those adjectives is the base.

If PADDW did saturating arithmetic and PADDWW did wrapping, I would agree with you, but that's not how x86 works.

It is, however, what many DSPs do.

Many DSPs don't support byte addressing or arithmetic on 8-bit integers which a huge amount of non-DSP C code relies on. They're not exactly friendly to code not written specifically to run on the DSP. (Or C code in general, for that matter - the reason they have saturating addition and other oddball instructions is because it makes a lot of DSP code faster, but there's no C representation of any of those things.)

And now we get back to the initial quote: "What's your point? If you define a "plain integer addition" to be "wrapping binary two-complement addition", then there isn't, otherwise, there is."

Okay, well since it's my term, I'll make it absolutely clear. The definition is not circular. On those DSPs, plain integer addition is saturating. For x86, so far all evidence points to it being twos-complement.

So the original original quote, "on x86 INT_MAX+1==INT_MIN", is true. As far as I can tell.

> What sort of optimisations exactly, and just how significant are they?

Well, if you could remove one instruction per loop on most computers (especially conditionals that could cause a branch mis-prediction), the effect of that in terms of performance is pretty staggering. Instead of thinking of it as an optimization, think of it as a check that doesn't need to be inserted into the code. If you can tell the compiler "I promise I won't overflow this variable", that's a lot less error checking it needs to insert on every iteration.

Well, you could just compile with -O0 then. I don't necessarily agree with C on this, but it's pretty clear the community has made the decision to prioritize speed over safety. Nothing wrong with that, but if safety is your priority you should probably look at things other than C. Even if you were to define undefined behavior, it's a spectacularly dangerous language.

> but if safety is your priority you should probably look at things other than C

And those things are?

C is the low level language we have. Now compiler writers decided it'll work like a high level language, except for all the actual benefits.

We'll probably get usable C compilers that work (in fact, this already started), and some stuff only good for old code.

Rust or Go are possible alternatives, or Java if it doesn't need to be system level.

Java for performance critical or realtime things sounds like a feverish dreamed nightmare.

The question was about safety, and java is indeed safe.

> If a programmer writes "X+1 > X", chances are this is an overflow check.

If the programmer writes

    for (i = a; i < b; i++)

then it's not clear if you need to check 'i' for overflow; Assuming that 'i++' is greater than 'i' allows the compiler to, say, unroll the loop.

> Doing this is perfectly defined by the standard if X is an unsigned integer, but not if it's signed. That's what doesn't make sense, since they could've made the unsigned case undefined as well.

It does make sense if you understand the historical context: There was a time when some processors still used ones-complement representation for signed integers. That's why the highest performance choice of instructions for signed integer addition would give different results in the overflow case on different processors. Which is why the standard leaves the behaviour undefined, so that compiler writers can choose the instructions that make for the fastest signed addition on the respective target, while programmers can not rely on any specific behaviour.

None of that applies for unsigned integers, and also, the common overflow behaviour of unsigned integers is commonly used intentionally for many types of computations (such as in cryptography), so it is both useful and it doesn't cost anything in terms of performance to define the semantics of unsigned overflow.

As the article points out, weird looking comparisons like `x+1>x` tend to pop up when macros get expanded or functions get inlined.

Reply on news.ycombinator.com