279
There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, ...
100
In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.
Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if ...
99
How can a machine built by a man be stronger than a man? This is exactly the same question.
The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not on the langauge used to implement it. You could write a really slow, inefficient compiler that produces very efficient code. There's nothing special about a ...
91
I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job.
There is no such thing as a slow or fast language.¹
On our way to the CPU actually doing something, there are many steps².
At least one programmer with certain skillsets.
The (formal) language they program ...
84
Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed. Even if you ensured ...
62
The distinction between interpreted and compiled code is probably a
fiction, as underlined by Raphael's comment:
the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...
The fact is that code is always interpreted, by software, by hardware
or a combination ...
57
It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:
Run M on input x;
print "Finished running input";
If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run ...
57
TLDR; this is possible but not practical.
(assuming the translator has access to the requisite libraries)?
This ends up being the tricky bit, and is part of why things like this don't end up being used in practice.
All compilers are translators. Translating from one language to another is definitely possible, and this is literally all a compiler is ...
56
As David Richerby rightly noted, the problem is undecidable in general. Object liveness is a global property of the program, and may in general depend on the inputs to the program.
Even precise dynamic garbage collection is an undecidable problem! All real-world garbage collectors use reachability as a conservative approximation to whether or not an ...
53
Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual ...
52
The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003. If you have access to a university library you should be able to borrow a copy.
In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input. For some of the ...
43
A JIT (Just-In-Time) compiler compiles code at run-time, i.e. as the program is running. Therefore the cost of compilation is part of the execution time of the program, and so should be minimized.
The opposite of this is an ahead-of-time (AOT) compiler which is basically synonymous with "batch compiler". This converts the source code to machine code and ...
41
Optimized program must have the same behavior as the original program. Consider the following program:
int main() {
f();
g();
}
, where it's guaranteed that $f$ is pure function. The only question is: does it finish its execution? If it does, then we can replace main()'s body with g(). Otherwise, we should replace it with an infinite loop. ...
33
The "assembly writer" in that book is a human software developer who writes code in assembler language.
31
I'd suggest you look into the wonderful world of Compiler Construction! The answer is that it's a bit of a complicated process.
To try to give you an intuition, remember that variable names are purely there for the programmer's sake. The computer will ultimately turn everything into addresses at the end.
Local variables are (generally) stored on the stack: ...
30
It's an incompleteness problem, not an undecidability problem
While it's true that the optimal placement of deallocation statements is undecidable, that's simply not the issue here. Since it's undecidable for both humans and compilers, it's impossible to always knowingly select the optimal deallocation placement, regardless of whether it's a manual or ...
24
There are many reasons that may be considered for choosing a language
X over a language Y. Program readability, ease of programming,
portability to many platforms, existence of good programming
environments can be such reasons. However, I shall consider only the
speed of execution as requested in the question. The question does not
seem to consider, for ...
24
When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?
The program tells it. Computers do not natively have a concept of "variables" - that's entirely a high-level language thing!
Here's a C program:
int main(void)
{
int a = 1;
return a + 3;
...
23
There is one forgotten thing about optimisation here.
There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers thought) and performance was tested based on same data.
The problem is, these languages differ, C allows pointers aliasing, while fortran does not.
So the codes ...
23
Currently, none of the posted answers are fully correct. It's not impossible to do this, but adding that feature would restrict mermory allocation patterns.
Why don't compilers automatically insert deallocations?
Some do. (I'll explain later.)
Trivially, you can call free() just before the program exits. But there's an implied need in your question to ...
21
Other reason for compilers to produce assembly rather than proper machine code are:
The symbolic addresses used by assemblers instead of hard-coding machine addresses
make code relocation much easier.
Linking code may involve safety checks such as type-checking, and that's easier
to do with symbolic names.
Small changes in machine code are easier to ...
19
What governs the "speed" of a programming language?
There is no such thing as the "speed" of a programming language. There is only the speed of a particular program written by a particular progammer executed by a particular version of a particular implementation of a particular execution engine running within a particular environment.
There can be huge ...
18
I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on any input, every input, all worst-case inputs or even on average?
I will show that all of them are impossible. The proof extends to optimising the length of the program.
Recall that the ...
18
An assembler translates assembly code to machine code. The translation is mechanical, and can be done in only one way. In contrast, a compiler has more freedom when it compiles the relevant programming language - it can optimize, for example, and even non-optimizing compilers produce different code. Also, compilers can be written in a way that separates the "...
18
It's called "loop fusion".
It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.
17
Actually, some languages (like C++, Lisp, and D) are Turing-complete at compile time, so compiling them is undecidable in general. For C++, this is because of recursive template instantiation. For Lisp and D, you can execute almost any code at compile time, so you can throw the compiler into an infinite loop if you want.
17
The question is not actually about compilation being impossible. If a language can be interpreted¹, then it can be compiled in a trivial way, by bundling the interpreter with the source code. The question is asking what language features make this essentially the only way.
An interpreter is a program that takes source code as input and behaves as specified ...
answered Sep 3 '14 at 9:32
Gilles 'SO- stop being evil'
39.8k7 gold badges105 silver badges170 bronze badges
16
The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.
The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and ...
16
A compiler does usually convert high-level code directly to machine language, but it can be built in a modular way so that one back-end emits machine code and the other assembly code (like GCC). The code generation phase produces "code" which is some internal representation of machine code, which then has to be converted to a usable format like machine ...
16
While everything is eventually run on the CPU*, there are various differences between different languages. Here are some examples.
Interpreted languages Some languages are interpreted rather than compiled, for example Python, Ruby and Matlab. That means that Python and Ruby code doesn't compile to machine code, but rather is interpreted on-the-fly. It is ...
Only top voted, non community-wiki answers of a minimum length are eligible
