How good are compilers?

[bryanl]

How fast or small is compiled code vs. hand written assembly code for x86? What about RISC and VLIW?

 

[DanDaManJC]

a tangential place to start would be comparing the perf of c++ to java

http://en.wikipedia.org/wiki/Comparison_of_Java_and_C%2B+

 

[Ancalagon44]

C++ and Java are both compiled languages so that has nothing, at all, to do with what he is asking.

Regarding the OP's question, it depends on the particular problem. For some things, compilers produce really good code. For most things, they wont be as good as hand written assembler. Hand written assembler is smaller and faster in nearly all cases. The thing is, its often not much faster, and its ALWAYS 1) tied to a particular machine architecture, 2) difficult to write, 3) difficult to debug. This is why, despite its advantages, no one ever hard codes assembler. Games might use hardcoded assembler for performance critical sections but thats it.

 

[Drakula]

It is been a while so answers might be wrong.

As Ancalagon44 said, assembly code is generally faster and most of time smaller because they deal more directly with instructions, system calls, and work with registers for storing values and strings and such, it is the closest thing to machine language. However, sometimes assembly code can only work with specific type of CPU, like code that specifically coded for Intel CPU would not necessarily work with AMD CPU and vice versa, unless they have compatible instructions that allows the code to work.

Compiled code needs to be compiled and interpreted into machine language then run. Compiled code will not be as hardware dependent because compiler took care of all those things in the background, and all the programmer has to worry is about writing workable codes. Compiled code might be platform/compiler dependent, like Linux C codes might not work with Visual C++/C# and Visual C++ codes might not work with Borland C(are they still in business?), so adjustments might needed to be made. Java did not have that problem though. Also compiled codes are more suspectable to compiler fault, gcc compiler had that problem before. Another thing, for C++, it is called compiler, but Java is called interpreter as it runs the program directly, it does not compile, forgot the major difference between the two.

Most compiler these days are optimized to work at fairly good efficiency. Cannot really comment on how good the efficiency is, but normal user probably cannot tell much difference.

RISC and VLIW are dealing with CPU architecture. Cannot comment much on that. It seems that VLIW is type of architecture that uses instruction parallelism. RISC is Reduced Instruction Set Computing, which deals with simplified instructions. All taken from Wikipedia because it is something long forgotten.

 

[DanDaManJC]

C++ and Java are both compiled languages so that has nothing, at all, to do with what he is asking.

right, and that's why i said it's a tangential point.

however, the reason I even bring that up is because C can be a pretty low level language that can be used to directly interface with hw. this is compared to something like java where there is this layer of abstraction. thus my point is that well written C code can be comparable to ASM, and at that point he could extrapolate compiler performance based on that C code against higher level languages like java.

 

[William Gaatjes]

How fast or small is compiled code vs. hand written assembly code for x86? What about RISC and VLIW?

IMHO:
Assume the code generated by the compiler to be very good.
For example the Intel compiler is written by Intel (duh).
This means that in advance, the compiler if optimized for a certain generation of cpu, that the compiler will know in advance all limitations of that cpu and advantages of that particular cpu. This means that the compiler knows exactly which combination of instructions when executed after each other extract maximum performance. If you want to write better assembly, you have to study the specific processor architecture you are coding for in assembly in detail. You need to do this because you have to have full knowledge of the limitations of the cpu and of the advantages. The writers of the compiler have done all that work already for you. Thus in reality i think it is rare and of no use. However, the same optimized code created by the Intel compiler will not run as good as possible at all on an AMD CPU. Because the AMD cpu and the intel CPU when compared have different designs.

I am not going into details really, i apologize for that. It is because X86 is a very advanced architecture filled with tricks to hide any latencies. It all comes down to keeping the execution pipeline filled and using all available resources at once at maximum efficiency.

Another example :

I myself do some amateur coding for the ARM because i can extract some more performance by violating the ARM procedure(function) call standard AAPCS. This function call standard is to make sure that on average maximum performance can be achieved while maintaining compatibility between generated code. However, in certain cases it can be more handy to violate the arm function call standard as long as i make sure that the code does not create errors and breaks the GNU generated code.

On average, the GNU compiler generates better code then i ever could manage(it is just impossible really) when looking at the amount of generated assembly in the short time frame the compiler is busy.

 

[A5]

Modern compilers are good enough to where you would be wasting your time writing a real program in ASM. The only reason I can see to write a program in ASM would be in an embedded environment where you just don't have the resources to load libraries that you aren't using that would be included with compiled code, and even those are becoming more and more rare since RAM and ROM space are really cheap to add to almost anything.

Java is a completely different beast due to it being an interpreted language - the performance varies based on what VM you're running on. The nice thing with Java is that other people do the hard work (writing the VM to ensure universal compatibility) for you, but you trade some performance to get it.

 

[Crusty]

Modern compilers are good enough to where you would be wasting your time writing a real program in ASM. The only reason I can see to write a program in ASM would be in an embedded environment where you just don't have the resources to load libraries that you aren't using that would be included with compiled code, and even those are becoming more and more rare since RAM and ROM space are really cheap to add to almost anything.

Java is a completely different beast due to it being an interpreted language - the performance varies based on what VM you're running on. The nice thing with Java is that other people do the hard work (writing the VM to ensure universal compatibility) for you, but you trade some performance to get it.

Java is not interpreted.

 

[Abwx]

However, the same optimized code created by the Intel compiler will not run as good as possible at all on an AMD CPU. Because the AMD cpu and the intel CPU when compared have different designs.

.

Not exactly.
As you pointed it, Intel s compiler is made to produce the most
efficient code in respect of their CPU instructions execution efficency.

Nothing says that an AMD CPU will be slower executing this code
than an Intel CPU, and in fact, during the A64/P4 era , codes
optimised by intel compilers where generaly running faster on the
competitor s processor since this latter had better efficency
when executing the said instructions/code..

If the compiled code is CPU agnostic, then the CPU with
the most efficient architecture will execute it faster provided
it support all the relevant instructions.

 

[PsiStar]

My experience ... and it is dated ... compilers load all kinds of additional i/o libraries. If you can get to know your compilers & linkers well, you can probably figure out how to avoid all of the extra crap. The result will be small, tight, and optimized ... pretty well. Meaning that a human could always do better but at the cost of probably a lot of extra time.

Back when I was having fun, the compilers gave me access to the intermediate code to hand optimize just in case there was an operation that I knew about but the compiler did not get.

 

[William Gaatjes]

Not exactly.
As you pointed it, Intel s compiler is made to produce the most
efficient code in respect of their CPU instructions execution efficency.

Nothing says that an AMD CPU will be slower executing this code
than an Intel CPU, and in fact, during the A64/P4 era , codes
optimised by intel compilers where generaly running faster on the
competitor s processor since this latter had better efficency
when executing the said instructions/code..

If the compiled code is CPU agnostic, then the CPU with
the most efficient architecture will execute it faster provided
it support all the relevant instructions.

Indeed you are right, it is not a fact but a possibility.
To make clear, i was not bashing AMD ( I use both AMD and Intel myself). It was just an example. It of course also works the other way around. AMD compiler to Intel or Via x86 cpu can cause the same issues.

To take the intel compiler again as example(but this is/can be the case for any mcu/cpu compiler writer), a stream of assembly instructions generated for a particular cpu generation from Intel does not has to be the most ideal instruction stream for another CPU generation(can be older or younger) of the same manufacturer(Intel) Of course that does make sense, since the manufacturing of an CPU is a guided form of evolution. The manufacturer keeps on improving and adding functions to keep the competition under control in the cpu market. Thus it is obvious that better techniques are added (old techniques are removed unless compatibility must be maintained) and that the compiler must co evolve(read rewritten) with the new cpu generations to be able to use the new features of the cpu.

 

[Modelworks]

Compilers range from terrific to absolutely horrible. It all comes down to the platform and what you need to do. Sometimes compilers can make poorly written programs run well and sometimes they can make well written programs run poorly.

A good ASM programmer can equal or beat a compiler for execution speed of the final code. The reason is that while compilers have gotten better at figuring out what the programmer wants the program to do they still cannot totally understand the purpose of the program and what the intended result needs to be. For example there are a lot of quirks that exist in cpu that ASM programmers exploit to get more performance and those are things compilers don't handle well. A compiler would see the code as an error while the ASM programmer put it there because he meant to cause the error to achieve a result the compiler didn't expect.

 

[William Gaatjes]

Compilers range from terrific to absolutely horrible. It all comes down to the platform and what you need to do. Sometimes compilers can make poorly written programs run well and sometimes they can make well written programs run poorly.

A good ASM programmer can equal or beat a compiler for execution speed of the final code. The reason is that while compilers have gotten better at figuring out what the programmer wants the program to do they still cannot totally understand the purpose of the program and what the intended result needs to be. For example there are a lot of quirks that exist in cpu that ASM programmers exploit to get more performance and those are things compilers don't handle well. A compiler would see the code as an error while the ASM programmer put it there because he meant to cause the error to achieve a result the compiler didn't expect.

Indeed when given the chance, for now a programmer will always be able to find more ways to optimize the code and producer better optimized assembly than a compiler can produce when the factor time is not an issue.
Unfortunately in business this will only happen with the grace of having enough time and/or wanting a superior flawless final product. Because indeed that is something that humans are better at then current generation computers with current generation code : Planning ahead for a final outcome.
But of course, proper planning must always occur for a desirable outcome to happen with a minimized amount of errors.

However, searching for a serious debugging error can still take all the advantages away from a compiler because the programmer has to search through the assembly where and how the error is caused. JTAG support does ease the analysis a lot but it is by no means ideal. (Think of optimization errors or forgetting the word volatile in the c code at the right locations)

To the thread starter :

I think the moral of the story of all posts here is, if one wants to be good, learn to understand what the preprocessor, compiler, linker and assembler do. Then one will be able to find errors faster. And when one understands the architecture of the target cpu or mcu, this again will show in a benefit of finding errors faster while also being able to use the architecture close to the maximum achievable performance level.

 

[Ancalagon44]

right, and that's why i said it's a tangential point.

however, the reason I even bring that up is because C can be a pretty low level language that can be used to directly interface with hw. this is compared to something like java where there is this layer of abstraction. thus my point is that well written C code can be comparable to ASM, and at that point he could extrapolate compiler performance based on that C code against higher level languages like java.

A layer of abstraction is not really how I would refer to the virtual machine, since Java provides no access to the underlying machine at all. I think the only way it can is if you wrap a C or C++ library.

Anyway, yes C is pretty efficient, but then it will usually not be as fast as hand written ASM. Its still compiled at all. And since C is a subset of C++, you are pretty much asking the OP's original question.

OP, I suggest reading up on CISC and RISC architectures. Most modern CISC architectures use something similar to RISC in the background because it makes it simpler to pipeline instructions. VLIW is another approach for increasing instructions per cycle, read up on superscalar architectures to help with that one.

 

[exdeath]

Hand tweaked assembly will always be better in performance critical code on limited platforms like embedded microcontrollers. Software applications on PCs however are bound by API/syscall overhead and do not benefit from any particular optimization unless we are talking massive calculations on massive datasets. But anyone who can hand code for cache coherency, bus parallelism, max memory bandwidth, branch hits, instruction overlap, etc is also capable of writing a compiler that can also do all that. The catch is understanding the compiler and structuring your high level code such that its painfuly obvious to the compiler that it should implement a special case optimization.

Trying to out smart yourself can make things worse. For example using conditional moves to eliminate a branch that is going to hit 99 million times out of 100 and not penalize you anyway makes your code a few bytes bigger and cross a cache page.

The biggest limitation of a compiler is they tend to work serially one statement or block at a time as independant units, they can't grasp the bigger picture of an algorithm or abstract purpose of the code they are compiling and think outside the box and say "oh this is really what the developer is trying to do, I'm going to completely rewrite this to work fast on x CPU" like a human can. A compiler that can work like that and see the whole picture would be on par with computer vision and AI.

 

[exdeath]

A layer of abstraction is not really how I would refer to the virtual machine, since Java provides no access to the underlying machine at all. I think the only way it can is if you wrap a C or C++ library.

I like to think of Java and VB languages as "emulated". It's ok for application code where most of your heavy lifting is done in native API calls, but try writing anything serious in an emulated VM language like Java and it quickly falls flat on it's face (without JIT).

Personally I'm a low level guy, I like my IO ports, DMA registers, FIFOs, etc. =D

Speaking of there things a compiler can't do: know things like to insert two NOP cycles after starting a DMA transfer on the Gameboy Advance before altering the source/dest registers for the next transfer when you inline I got lucky when the epilogue/prologue of the C call provided ample time between successive DMA transfers This one was a pain in my ass for two days when my shit worked on VisualBoyAdvance emulator but not on a real hardware unit.

There will always be a need to hand write assembly. Even if a language like Java can be made fast because of native API libraries and JIT runtimes, someone has to write those native libraries and JIT compilers.

 

[Ross Ridge]

Writing assembly code that is smaller than the best compilers can generate when told to optimize for size is relatively easy. That is, it's relatively easy for an experienced programer who knows that kind of assembly very well.

Writing assembly code that's faster than the best compilers can do these days is a lot harder than most people realize. When you're just trying to generate the smallest code, basically it just comes down to choosing the smallest instructions. When you're trying to generate the fastest code, you can't just pick the fastest instructions in isolation, you need to to figure out what the fastest series of instructions is.

Modern CPUs are complex beasts. They can execute several instructions at once, even out of order, while still keeping the same semantics as if executed in order. They automatically prefetch memory in to the cache. They have branch predictors that keep a steady flow instruction down the pipeline even after decoding a coniditional branch who's result won't be known for several cycles. And when one of these things fails in it's job of trying to make the most out of every machine cycle, the CPU stalls.

Stalls are bad, very bad, so optimizing for speed, at least the instruction selection level, often comes down to avoiding stalls as much as possible. That can mean picking a sequence of instructions that individually look slower on paper, but in actuality are much faster because they avoid a stall that the individually faster instructions would generate. Figuring out where and how to avoid all these stalls isn't easy. Indeed, in general on a modern AMD or Intel CPU it's nearly impossible to do without running the program under an advanced profiling tool capable of recording where and when these stalls actually occur. Compilers are far from prefect at being able to predict them, but often they can do a better job than a human. And it's a heck a lot easier to let a compiler handle it.

This really only scratches the surface of the sort optimizations a compiler or programmer would need to do in order to generate the fastest possible code. There are all sorts of optimizations that can improve performance, including higher level ones like loop unrolling or inlining. Many of these are simple and obvious for a programmer, but some very much aren't, and all told can add up a lot of tedious error-prone work.

Then there one kind of "optimization" that no compiler's optimizer can help you with, but just using a high level language like C or C++ can make a huge difference. Choosing the right algorithims can be critical. A bad choice can make the best hand optimized assembly orders of magnitude slower than an interpreted JavaScript program doing the same thing but using a better algorithm. Unfortunately, programming in assembly often results in easy but bad choices being made. Even a simple data structure like a linked list can be a pain to implement in assembly. Coding something as complex as a balanced search tree is such a huge undertaking in assembly that most programmers would rather just avoid. In C++ it couldn't be simpler, just use the one included in the standard library.

What this all comes down to is that the only time you see programmers writting in assembly these days is on the smallest of embedded systems where space is at a premium, or tiny segments of much more complex programs written in traditional high level languages. In the later case this is generally only done where profiling (or past exprience) shows that compiler wasn't up to the task. Even then the results aren't always what they expect.

 

[William Gaatjes]

Trying to out smart yourself can make things worse. For example using conditional moves to eliminate a branch that is going to hit 99 million times out of 100 and not penalize you anyway makes your code a few bytes bigger and cross a cache page.

Yes, that would be a big fail. The whole idea of the cache is lost then.
The idea of having part of the cache as local scratch pad memory is also very handy. I can remember that long ago with the nintendo 64, all interrupt handlers where hand optimized and stored always in part of the cache for fast access. The advantage of having some manual control over part of the cache would be to conserve power. Because no logic would then be needed to check if that part of the cache(where all interrupt handlers are stored) has useless data or instructions and can be used to fill with useful data or instructions until it gets flushed again. Thus part of the cache is used as local storage with fast access when compared to slow main memory.

I think the cell processor of the PS3 also has some of these scratch pad ram abilities.

The biggest limitation of a compiler is they tend to work serially one statement or block at a time as independant units, they can't grasp the bigger picture of an algorithm or abstract purpose of the code they are compiling and think outside the box and say "oh this is really what the developer is trying to do, I'm going to completely rewrite this to work fast on x CPU" like a human can. A compiler that can work like that and see the whole picture would be on par with computer vision and AI.

This indeed. Imagine that the one who finds the secret ingredient to AI also will be able to write perfect compilers. How much possible scenario's can be created depends on how much possible input variables a system can hold and process in parallel. It is all about the parallel input processing and not about raw serial processing power. This can also be seen in humans when comparing "normal" persons with "idiot savants" geniuses who can calculate faster than a modern cpu.


At Ross Ridge :
Indeed you are right.
One of the strangest tricks of x86 is the register renaming.
Instead of having enough registers to work with, the cpu needs to use internal swapping of registers to circumvent the lack of registers for the processing of the code. With IA-64 this was solved by using a lot of registers(I think 128). But there seems to be a sweet spot with the number of usable registers. 16 seems to be that magic number(economy and efficiency trade off), although it all depends on the instruction set and the compiler.

Here is an idea (which i am sure mr Seymour Cray already figured out 50 years earlier) :

When thinking of the stack of an mcu or cpu that uses a c- compiler, i would think it would be a good idea if there was just some enhanced capability of shadowing registers during calls. That the cpu instead of storing registers on a serial stack, would use a parallel stack. Just shadow copying registers by swapping register banks in and out instead of serially pushing onto a stack. Of course in reality, both stack systems would be used. But a program having control of these features could when programmed correctly have a large speed advantage while saving a lot of power.

IMHO:
This would give 2 advantages that would conserve power but does cost real estate on the die :

When enough registers are present, then no register renaming would be necessary(with -86x,64bit with 16 registers solved i think).

Swapping of registers would take less time and less energy because of shadow banking register sets directly on die. No transferring to cache(on die but with more control lines).
Just switching internal address/ bank select enable lines. No register renaming and thus a simpler pipeline.

The power saving comes purely from not having to copy data and that a lot of registers are sitting idle. When the OS and the applications are written with a proper compiler taking advantage of such features, there would be a speed up and power saving.

But it is expensive to do, because a lot of transistors are standing by doing nothing(static power consumption only which is already solved). However, when looking at current generation processors with billions of transistors it is not really an issue. And speed and power binning can be done as well. Because defective registers means less parallel stacking and more serial stacking.

 

[William Gaatjes]

To give another example of a compiler not knowing everything in advance.

In the renesas rx core thread, i mentioned the set bit and clear bit registers in the ARM7TDMI mcu's from Atmel and NXP.

This design philosophy allows for not having to read the register first if you want to modify a bit(read-modify-write). The compiler i use, is not aware of this feature and thus uses the safe approach by doing a read modify write.

By writing a small macro with a bit of assembly, i can greatly improve the speed of my code. The compiler works fantastic. But you cannot expect a compiler to know everything in advance.

Another example is that the AAPCS advises to only push and pop and use register R0 to R3 between function calls. This to reduce the amount of registers that have to be pushed upon the stack and popped from the stack. If i would have a function that calls another function with more then 4 arguments, for as far as i am aware the stack will be used for other variables. If i would hand optimize, i could use more registers if i know in advance which ones i only use as scratchpad and are of no longer use. This way i can also gain some advantages in some situations.
Some compilers allow the amount of registers to be used for arguments to be modified by the use of special command line switches.

 

[velis]

Wow, this is exactly why I love highly technical A guy asks a simple question and before you know it, guys are talking cache pages, TLBs and stuff like that all over the place.

Still, I too want to have a go at answering, so here it goes, very layman-like as layman I am

First of all: the most difference in program size and speed is usually not contributed by choosing whether one should program in asm or in some interpreted language. They are in fact determined by choosing the algorithm for the job. Obviously a poor choice will result in a slow program. A simple example of this is choosing bubble sort to sort millions of records of data. Obviously quick sort (or something else) would be much more speed-efficient here, but "a bit" larger in code size. I quoted "a bit" because if that's all your program does, you've just more than doubled its size by choosing quick over bubble...

Anyway, only after choosing of appropriate algorithm should you look into other optimizations. Typically a loose-typed interpreted language, which I consider a representative winner in ease-of-coding will give you enough speed for your typical database application, but much less so for any calculation based algorithms and it may also use up too much RAM.

So you move to a strict typed compiler which will generate assembly code and also make sure you don't use up unnecessary RAM due to use of variant types. You must know that many compilers don't perform any optimization. For example, Borland's Pascal which was immensely popular only got optimization in Delphi (after 8 versions of Turbo / Borland Pascal) version 2 and above if I remember correctly.

So when you see your favorite compiler doesn't do any optimization for you, you move to an optimizing compiler - your safest bet here are C compilers.

And only after that if even an optimizing compiler is not satisfactory and you still need more speed, you move to hand written asm - if you have the knowledge.

Again - this all depends on your algorithm. There's no use programming a database app in asm because that super-fine tuned asm will wait for the DB server all the time. Mostly you would consider this for a HPC application.
Even then - you really have to know what you're doing when you go for asm. You will make 99% of progress by moving to optimizing compiler and only the remaining 1% when you make that last move to asm. Again - depending on your payload.
To top all of this off - you will gain very little moving to an optimizing compiler if your application is I/O bound. Any optimizations / asm coding is only relevant if you really need calculations - as many of them as possible.

 

[Ancalagon44]

I like to think of Java and VB languages as "emulated". It's ok for application code where most of your heavy lifting is done in native API calls, but try writing anything serious in an emulated VM language like Java and it quickly falls flat on it's face (without JIT).

Why would you ever run Java in a VM without a JIT component? Even Dalvik now has a JIT component. Real world benchmarks suggest that Java is not far behind C in performance, and orders of magnitude faster than Ruby and Python.

Emulated is probably more accurate than interpreted, but considering the use of a JIT compiler, its still not quite accurate. Heck, with a JIT compiler, it literally is native code.

VB is very different to Java, I wouldnt group them together. And there is a large distinction between VB6 and VB.Net, which I'm sure you know runs on the CLI.

 

[Merad]

OP's question has been answered, but one thing I think bears pointing out: while asm can be made faster and more efficient, it simply isn't viable to create modern programs in asm. They're too complex.

Modern OS's are tens of millions of lines of code (50+ mil for Windows 7, around 90 mil for OSX). Most games are at least a few million lines. IIRC Firefox is around 10 million.

And that's with most of those being written primarily in a combination of C and C++. Change them over to asm and you'd probably make the code base for each one at least 5-10x larger.

 

[William Gaatjes]

OP's question has been answered, but one thing I think bears pointing out: while asm can be made faster and more efficient, it simply isn't viable to create modern programs in asm. They're too complex.

Modern OS's are tens of millions of lines of code (50+ mil for Windows 7, around 90 mil for OSX). Most games are at least a few million lines. IIRC Firefox is around 10 million.

And that's with most of those being written primarily in a combination of C and C++. Change them over to asm and you'd probably make the code base for each one at least 5-10x larger.

Indeed you are right. It would be no use to write an OS as large as windows, OSX or a linux distribution completely in assembler.

But as Velis perfectly explained, small functions that are part of an algorithm can benefit from handwritten assembly optimization. Or parts of drivers can be optimized. But for most part of an OS, it is providing information as for example text to the user. It can hypothetically be handy to optimize some of the functions that are part of the library that prints the text to the screen.

But it is no use to write in assembly the printing of characters.

Example :C function

{
Some code...

PrintText("Print this");

Some more code...
}


This is much easier then to having manually enter a memory address which is the start of the string into a register and calling then the subroutine that performs the printing of characters. Which is what you do in assembly.

And this is just for printing text. Imagine what one must do for printing flexible graphics to a screen.
In another thread there is an interesting discussion about vector graphics... Imagine that...

 

[Modelworks]

If you really want to see what ASM can do in the hands of a capable programmer look at menuetOS. A complete OS coded only in ASM. It has networking, gui, mp3 and dvd playback and comes in at under 800KB.
http://www.menuetos.net/

 

[William Gaatjes]

If you really want to see what ASM can do in the hands of a capable programmer look at menuetOS. A complete OS coded only in ASM. It has networking, gui, mp3 and dvd playback and comes in at under 800KB.
http://www.menuetos.net/

Amazing. Die hard assembly programming. :thumbsup:
I would think they have first setup some serious subroutine calling standards and program only using defined protocols to let the modular written parts be exchanged easy when upgrading is needed. Something similar as an calling convention. Because otherwise i would think it would get a serious mess and very difficult to debug when something goes wrong.