261
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, ...
97
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 ...
95
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 ...
90
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 ...
80
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 ...
68
To all those who said “yes” I’ll offer a counter-point that the answer is “no”, by design. Those languages will never be able to match the performance of statically compiled languages.
Kos offered the (very valid) point that dynamic languages have more information about the system at runtime which can be used to optimise code.
However, there‘s another side ...
60
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 ...
53
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 ...
52
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 ...
50
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 ...
33
The "assembly writer" in that book is a human software developer who writes code in assembler language.
32
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: ...
29
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
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.
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 call free() as soon as possible.
The problem of when to call free() in any C program as soon as the ...
22
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 ...
22
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 ...
20
if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y?
Yes. Take, as an example, PyPy. It is a collection of Python code that performs close to C in doing interpretation (not all that close, but not all that far away either). It does this by performing full-program analysis on the source code to assign each ...
19
Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.
The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not ...
18
The short answer is: we don't know, ask again in 100 years. (We might still not know then; possibly we'll never know.)
In theory, this is possible. Take all the programs that have ever been written, manually translate them to the most efficient possible machine code, and write an interpreter that maps source codes to machine codes. This is possible since ...
18
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 ...
17
JIT compilers compiles the code on the fly, right before their execution or even when they are already executing. This way, the VM where the code is running can check for patterns in the code execution to allow optimizations that would be possible only with run-time information. Further, if the VM decide that the compiled version is not good enough for ...
16
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 ...
16
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 ...
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 ...
15
Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser.
Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$ is of the form:
$\alpha \rightarrow \alpha \beta$
with $\alpha$ an element of $V$ and $\beta$ an element ...
Only top voted, non community-wiki answers of a minimum length are eligible
