<p>there is a simple answer in the case you mention, Python/C, not mentioned in answers so far. the Python interpreter is <em>written</em> in C but not vice versa. same with eg Ruby or Perl. </p>

<p>&amp; yes as you guess, another simple answer is that modern interpreted languages use a <a href="http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29" rel="nofollow"><em>garbage collector</em></a> which simplifies the programming experience and maintenance of the code at the expense of some runtime overhead.</p>

<p>a useful way of picturing language implementation complexity is to visualize <em>layers</em> of different systems or subsystems that run concurrently or "on top" of each other. for example interpreted code runs concurrently with a garbage collector. interpreted code is built "on top" of C interpreting code. etc.; the "higher level" language is written in terms of the "lower level" language. in a sense the higher level language is compiled into the lower level language.</p>

<p>however the question seems to suggest an unfamiliarity with the basic theory of <a href="http://en.wikipedia.org/wiki/Np_complete" rel="nofollow">NP completeness</a> which is the theoretical construct used to judge runtime complexity and in which there is indeed no substantial difference between compilers and interpreted code because it all runs within P-time factors of each other.</p>

CC BY-SA 3.0
2012-02-21T16:16:57.257Z
There's been a lot of interesting discussion, but this is the answer that directly addresses the core of it, by pointing me in the direction of NP-completeness. Thanks!
Cera
CC BY-SA 3.0
2015-05-27T04:56:38.033Z
@Cerales: There's been quite a bit of talk about garbage collectors being features of high-level languages that make them slow. But my impression is that a *well-implemented* garbage collector can actually make a program *faster* (not always, but in some cases), because handling the memory management by hand can be so difficult that a programmer is not likely to construct something as efficient as an industrial strength garbage collector.
Joshua Grochow
CC BY-SA 3.0
2015-05-27T05:32:56.997Z
"NP completeness which is the theoretical construct used to judge runtime complexity" what kind of nonsense is this!
Sasho Nikolov
CC BY-SA 3.0
2012-02-20T16:09:40.043Z
2012-02-20T16:09:40.043Z
vzn
<p>There is no deeper reason other than quality of compilers and interpreters.</p>

<p>Some languages are <em>not</em> designed with speed of execution in mind. For example, the <a href="http://python-history.blogspot.com/2009/01/personal-history-part-1-cwi.html">design goals of Python</a> did not include speed of execution at the very top. In such cases you should not wonder where speed has gone.</p>

<p>Some languages <em>are</em> intended to run fast but it takes time for people to produce good compilers and runtime environments. Typical examples are the so-called "high-level" languages. For example, early variants of ML were memory hogs that ran sort of fast until the garbage collector kicked in. Nowadays, 25 years later, a modern variant of ML, such as <a href="http://caml.inria.fr/">Ocaml</a>, runs with speeds <a href="http://www.ffconsultancy.com/languages/ray_tracer/comparison.html">comparable to those of C and C++</a>, and in most cases you don't even notice that there is a garbage collector.</p>

<p>Why is it harder to compile high-level languages to fast code? Well, because they are high level. Programs written in such languages operate directly with concepts that are far removed from the underlying hardware. In contrast, low level languages such as C, C++ and java are essentially glorified assembly languages and there is very little that the compiler actually needs to do.</p>

<p>Also, there are languages out there whose design is essentially screwed up in such a way that efficient compiled code is hard to obtain. Typically such languages have no or little compile-time type checking or unreasonable amounts of reflection, i.e., <code>eval &lt;string&gt;</code>, and an operational semantics which relies heavily on string replacement and manipulation of source code. Bourne shell comes to mind, TeX/LaTeX as well, and maybe Python to an extent. As long as such "features" are deliberate design choices that is ok, but there also seem to be languages out there whose design was based on ignorance of programming language theory.</p>

CC BY-SA 3.0
2012-02-20T13:44:20.437Z
2012-02-20T13:53:12.407Z
2012-02-20T13:53:12.407Z
Andrej Bauer
<p>(Not an answer, but a bit too long comment.)</p>

<p>One aspect that has not been covered in the other answers is the fact that "higher-level" languages typically provide additional <em>safety nets</em>, which may involve some run-time overhead.</p>

<p>As a concrete example, I have occasionally compared the performance of C code and equivalent Java code (truly equivalent – forget about classes and objects, your high-level data structure is <code>int[]</code>), and I have also had a look at the machine code that is generated by modern compilers in each case. While the quality of compilers varies a bit, and just-in-time things have their usual advantages and disadvantages, it seemed that a major difference was related to the safety nets. In Java, array references such as <code>x[i]</code> involve two sanity checks: pointer <code>x</code> is not null, and array index <code>i</code> is valid.</p>

<p>Of course some of these checks can be optimised away, and some of them can be moved outside the inner loops. Modern CPUs also help tremendously, as these are branches that can be predicted well. Nevertheless, a number of these checks are there and they take a non-trivial amount of time.</p>

<p>I think now we are at a point where we can approach the question from a TCS perspective, especially from the perspective of the theory of programming languages: Would it be possible to, e.g., re-design Java so that <em>none</em> of these run-time checks are necessary, without losing any of the safety nets, and without putting any significant additional burden on the programmer?</p>

CC BY-SA 3.0
2012-02-20T22:33:46.207Z
You cannot hope to remove all such checks, but certainly you can remove very many with good language design. For example, Java should not have a `null` object, and that would immediately remove some checks.
Andrej Bauer
CC BY-SA 3.0
2012-02-21T12:28:52.330Z
Removing all checks is equivalent to the halting problem. ;)
Dmytro Korduban
CC BY-SA 3.0
2015-05-27T04:59:43.707Z
@AndrejBauer: Forgive a theoretician and programmer who is ignorant of, but interested in, PL theory. What would be the standard PL theory wisdom of how to re-engineer Java to not have null? Would it be to have the ability to check if a variable has been assigned a value? Something else?
Joshua Grochow
CC BY-SA 3.0
2015-05-27T06:13:42.757Z
When a variable is declared it must be initialized. Instead of `null` introduce option types and make sure with good syntax than whenever anyone uses a value of option type they check *both* possibilities (undefined and defined).
Andrej Bauer
CC BY-SA 3.0
2012-02-20T15:51:58.893Z
2012-02-20T15:51:58.893Z
Jukka Suomela
<p>Just an update on the issue: I think that the problem of efficiency of the constant factor is mainly qualitative, rather than quantitative. Indeed, a high constant factor is mainly caused by an inefficient interpretation of the programmer's intent by the language parser.</p>

<p>In this sense, we can say that it's more a problem of semantic linguistics rather than just technical implementation: with a low level language such as C, the language parser don't have to make any guess, since you have direct control of the most basic instructions, and thus are responsible for the whole program flow. With a high level language, you get a more abstract control of the program flow, which makes it easier and faster to design complex program, but at the expense that you delegate some of the program flow design to the language parser: it now has to make some guesses about what you meant, and it can be very costly if it's some kind of program flow that the language parser wasn't primarily made for (such as linear algebra in Python).</p>

<p>This is not because of a lack of investment of the language authors, but rather that, like with any level of abstraction, you choose a balance between the conciseness of your words and their preciseness. A word like "humans" is very abstract and describe a whole specie, but it doesn't account for the particularities and all the culture of each individual in this group. Just like scientific jargon, high-level language parsers are designed to concisely and efficiently describe operations of the targetted paradigm, but they cannot describe as concisely every other paradigms.</p>

<p>However, now it seems that a new class of languages are emerging: annotated languages, such as Julia or Cython or Numba. They are neither really interpreted nor compiled but in-between: you can write high-level code that the "interpreter" will have to guess how to run the most efficiently possible (and correctly of course), or you can almost compile your code by annotation or by using other specialized constructs such as dispatching or semi-automatic unrolling/vectorization of loops, so that your annotations avoid the need to make the language parser to guess what you were meaning to do at lower levels of abstraction: in short, annotations give you the ability to give precisions on your high-level abstraction. We will see in the future if this concept works out.</p>

CC BY-SA 3.0
2015-05-26T23:57:20.210Z
2015-05-26T23:57:20.210Z
gaborous
<p>I think that the gap between the performance of two programming languages highly depends on the type of the problem/algorithm and how you measure such "<em>performance</em>". </p>

<p>The introductory paragraph of the "<a href="http://shootout.alioth.debian.org/" rel="nofollow">The Computer Language Benchmarks Game</a>" page is clarifying:</p>

<p>... When the facts are about the performance of programs, the particular way each program does a task matters a lot. Obviously when programs implement different algorithms that difference may itself be enough to explain any difference in program performance. Less obviously, even when the same program is measured with different implementations of the same programming language, the particular way that program does the task may work better with one of the language implementations than the other - but slight changes to the program might reverse that performance difference. So there has to be some flexibility allowed in the way programs implement the same algorithm, and the tasks are kept simple enough for you to check the program source code. When the facts are about a wide range of different programming languages even more flexibility has to be allowed in the way programs implement the same algorithm - after all, the point of using a different language is for the different approach that language provides. ...</p>

<p>For example, if you look at the <a href="http://shootout.alioth.debian.org/u32/which-programming-languages-are-fastest.php" rel="nofollow">The Computer Language Benchmarks Game</a>, you can see that a gap often occurs between a compiled and an interpreted language, but it is not always true: in the <em>regex-dna</em> test, javascript performs better ... but only because it has a powerful and "native" support for regular-expressions. It is also clear that the gap between Java and C++ has greatly reduced thanks to its <a href="http://en.wikipedia.org/wiki/Just-in-time_compilation" rel="nofollow">JIT compilation</a>. </p>

<p>The <em>theory says</em> that different programming languages lead to execution times that differ only by a constant factor ... and the speedup theorem for Turing Machines says that constant factors are meaningless; but some efforts have been done to <strong>study computability and complexity from a programming-language point of view</strong> and the results are a little bit different.</p>

<p>See for example: <strong>Computational Complexity via Programming Languages: Constant Factors Do Matter</strong> (A. M. Ben-Amram and Neil D. Jones)</p>

<p>... Using the programming language described in this paper we prove a series of hierarchy theorems ... The main theorem, for deterministic time, states that for time-constructible functions $T(n)$, there is a constant $b$ such that more decision problems can be solved in time $bT(n)$ than in time $T(n)$ ... </p>

CC BY-SA 3.0
2012-02-20T14:53:35.953Z
Ben-Amram and Jones' paper is available [here](http://www2.mta.ac.il/~amirben/downloadable/acta.ps.gz) and [here](http://www.springerlink.com/content/jbatp9j0anhacfln/).
Jeffε
CC BY-SA 3.0
2015-05-27T05:04:05.390Z
I never particularly liked the constant-factor speedup theorem as an argument for constants not mattering. From a mathematical point of view it "makes sense" because one doesn't want to specify the underlying alphabet. From a research point of view it makes sense because it often makes our lives easier. But from a more practical (and even still somewhat theoretical) point of view, the alphabet is always {0,1}, and merely "decreasing" the running time by blowing up the alphabet is a cheat. Perhaps a cheat that we cannot formally avoid, but it still always felt like a cheat...
Joshua Grochow
CC BY-SA 3.0
2012-02-20T14:41:41.070Z
2012-02-20T14:41:41.070Z
Marzio De Biasi
<p>Interpretation vs. compilation issues aside, memory IO is indeed a big issue (maybe <em>the</em> issue) in my experience, in particular caches.</p>

<p>When writing a program in C or maybe even C++, you (can) control what ends up where in memory. You can not in languages like Java. This is fine for many purposes, but consider the following. </p>

<p>Imagine you want to store a (huge) matrix of objects, say pairs of numbers. In C, you can just create an array of those. Iterating over the matrix is about as fast as if the matrix contained single numbers. Now, in Java, pairs would be objects which would end up <em>somewhere</em> on the heap, the matrix containing only pointers. If the JVM is bad at recognising and acting on demand for locality¹, i.e. the object are scattered over the heap, this means cache becomes useless if you iterate.</p>

<p>The problem tends to explode if you have parallel algorithms, by the way.</p>

<p>[1] I do not know what it actually does in this regard, but my experience indicates it is not too clever about it.</p>

CC BY-SA 3.0
2012-02-20T21:44:41.113Z
2012-02-20T21:44:41.113Z
Raphael
<p>First of all, I apologise off the bat for my mangling of CompSci language. I have no real training or background in computer science or mathematics.</p>

<p>I've been wondering lately whether there's a 'general' explanation for the inefficiency of high-level languages in performing certain kinds of algorithms - from simple cases like the massive performance improvement in <code>C</code> over, say, <code>Python</code>, when looping over a set, up to complex mathematical algorithms.</p>

<p>Is it purely a quantitative matter - C is more efficient because it's not doing weird magic behind the scenes and the programmer directly interacts with main memory? And because it's not doing things like interrupts for garbage collection and other general housekeeping like a high-level language might?</p>

<p>Or is there some deeper ontological explanation for this? Is there some <em>qualitative</em> property of a low-level procedural language (or, at times, of a functional language) that makes it possible to express and compute a problem efficiently? Or is it simply a matter of brute resource and CPU cycle efficiency?</p>

CC BY-SA 3.0
2012-02-20T02:57:03.143Z
In practice, yes, C is faster than Python because it's statically typed, compiled, etc. You might find the "extended" Church-Turing thesis of interest: http://cstheory.stackexchange.com/questions/7528/extended-church-turing-thesis This asserts that any (reasonable) model of computation can be efficiently (in polynomial time) simulated by another, something which provides negative evidence for your question.
Huck Bennett
CC BY-SA 3.0
2012-02-20T04:22:25.253Z
I believe that the difference between C and Python is to a large extent due to the difference between compilation and interpretation, and is not really an issue for theory. Just-in-time compilers such as psyco can make Python much faster than its default behavior. A better comparison would be C vs C++ since both are generally compiled using the same compilers etc and the difference between them is limited much more tightly to the level of the language.
David Eppstein
CC BY-SA 3.0
2012-02-20T04:52:57.087Z
Or perhaps even between Java and C, because although C++ is higher-level it's still often considered relatively 'close to the metal'.
Cera
CC BY-SA 3.0
2012-02-20T09:00:17.243Z
Hmmm.  I'm not seeing the theoretical computer science content here.  One of the basic religious tenets in algorithm design is that one's choice of programming language only affects the constant factors in running times, which we don't care about.
Jeffε
CC BY-SA 3.0
2012-02-20T13:59:43.663Z
@JɛﬀE: I doubt your “basic religious tenet” as is stated, because sometimes it is difficult to find a persistent or purely functional data structure with the same time complexity as the best known non-persistent data structure up to a constant factor.  For example, I do not think that a persistent [disjoint-set data structure](http://en.wikipedia.org/wiki/Disjoint-set_data_structure) whose amortized time complexity per operation is O(α(n)) is known.  But I guess we are usually fine with a log factor.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-20T14:02:07.153Z
@JɛﬀE: surely cache hierarchies are fair game for algorithms designers, even though the relative speeds of hard disk seeks to register accesses is "merely" a constant factor...!
Neel Krishnaswami
CC BY-SA 3.0
2012-02-20T14:50:14.960Z
Neel: Of course cache hierarchies are fair game, but design and analysis of cache-efficient algorithms is independent of programming language.  Tsuoyoshi: Of course persistence is fair game, but design and analysis of persistent data structures is independent of programming language.  (Yes,  functional languages make persistence *easier*, but they're not required.  Purely functional stuff can be implemented in C with only a constant-factor loss of efficiency: Just write a LISP interpreter!)
Jeffε
CC BY-SA 3.0
2012-02-20T15:22:35.437Z
@JɛﬀE: You are talking about the wrong direction.  You can implement persistent data structures in imperative languages, of course, but you cannot use non-persistent data structures in purely functional languages unless you are happy to go outside functional programming.  For example, try to implement Kruskal’s algorithm in Haskell using an O(α(n))-time disjoint-set data structure; almost everything will be in an IO monad.  That would be technically still a Haskell code, but not a Haskell code for practical purposes.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-20T15:52:27.190Z
What are these "practical purposes" of which you speak?
Jeffε
CC BY-SA 3.0
2012-02-20T17:41:02.517Z
@JɛﬀE: The practical purposes for programmers.  I do not think that we can define them rigorously, but they are something which programming-language researchers always think about.  From the theory-of-computing viewpoint, C and Haskell are obviously equivalent.  From the programming-language viewpoint, they are not.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-20T21:48:00.500Z
A big issue is that people write code differently when the level of abstraction is higher, just because it looks nicer or because they are *bad* programmers (PHP!). For example, you can have horrible runtimes in Scala but do the very same thing as fast as Java -- if you know what to look for.
Raphael
CC BY-SA 3.0
2012-02-20T22:29:55.210Z
@Raphel: PHP and Java do not reach high level of abstraction, and Scala tries.
Andrej Bauer
CC BY-SA 3.0
2012-02-21T07:03:27.400Z
@JɛﬀE "theoretical computer science" != "algorithm designers". PL folks might have something to say about that, and about this question.
Suresh Venkat
CC BY-SA 3.0
2012-02-21T08:50:27.587Z
@SureshVenkat: Fair point.
Jeffε
CC BY-SA 3.0
2015-05-27T05:36:59.260Z
@SureshVenkat I think all six answers to this question are a testament to it not being a good TCS question.
Sasho Nikolov
CC BY-SA 3.0
2015-05-27T23:02:30.820Z
are you really asking me to participate in a discussion after three years ? :)
Suresh Venkat
CC BY-SA 3.0
2015-05-28T21:20:10.983Z
@SureshVenkat Sorry, I am not, I was probably feeling grumpy :)
Sasho Nikolov
<ds.algorithms>
Is there a general theory for why certain algorithms are inefficient in high-level languages?
Cera
# Is there a general theory for why certain algorithms are inefficient in high-level languages?

(Asked by: username_0 on 2012-02-20)

First of all, I apologise off the bat for my mangling of CompSci language. I have no real training or background in computer science or mathematics.

I've been wondering lately whether there's a 'general' explanation for the inefficiency of high-level languages in performing certain kinds of algorithms - from simple cases like the massive performance improvement in `C` over, say, `Python`, when looping over a set, up to complex mathematical algorithms.

Is it purely a quantitative matter - C is more efficient because it's not doing weird magic behind the scenes and the programmer directly interacts with main memory? And because it's not doing things like interrupts for garbage collection and other general housekeeping like a high-level language might?

Or is there some deeper ontological explanation for this? Is there some *qualitative* property of a low-level procedural language (or, at times, of a functional language) that makes it possible to express and compute a problem efficiently? Or is it simply a matter of brute resource and CPU cycle efficiency?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: In practice, yes, C is faster than Python because it's statically typed, compiled, etc. You might find the "extended" Church-Turing thesis of interest: http://cstheory.stackexchange.com/questions/7528/extended-church-turing-thesis This asserts that any (reasonable) model of computation can be efficiently (in polynomial time) simulated by another, something which provides negative evidence for your question.  
> **username_2**: I believe that the difference between C and Python is to a large extent due to the difference between compilation and interpretation, and is not really an issue for theory. Just-in-time compilers such as psyco can make Python much faster than its default behavior. A better comparison would be C vs C++ since both are generally compiled using the same compilers etc and the difference between them is limited much more tightly to the level of the language.  
> **username_0**: Or perhaps even between Java and C, because although C++ is higher-level it's still often considered relatively 'close to the metal'.  
> **username_3**: Hmmm.  I'm not seeing the theoretical computer science content here.  One of the basic religious tenets in algorithm design is that one's choice of programming language only affects the constant factors in running times, which we don't care about.  
> **username_4**: @JɛﬀE: I doubt your “basic religious tenet” as is stated, because sometimes it is difficult to find a persistent or purely functional data structure with the same time complexity as the best known non-persistent data structure up to a constant factor.  For example, I do not think that a persistent [disjoint-set data structure](http://en.wikipedia.org/wiki/Disjoint-set_data_structure) whose amortized time complexity per operation is O(α(n)) is known.  But I guess we are usually fine with a log factor.  
> **username_5**: @JɛﬀE: surely cache hierarchies are fair game for algorithms designers, even though the relative speeds of hard disk seeks to register accesses is "merely" a constant factor...!  
> **username_3**: Neel: Of course cache hierarchies are fair game, but design and analysis of cache-efficient algorithms is independent of programming language.  Tsuoyoshi: Of course persistence is fair game, but design and analysis of persistent data structures is independent of programming language.  (Yes,  functional languages make persistence *easier*, but they're not required.  Purely functional stuff can be implemented in C with only a constant-factor loss of efficiency: Just write a LISP interpreter!)  
> **username_4**: @JɛﬀE: You are talking about the wrong direction.  You can implement persistent data structures in imperative languages, of course, but you cannot use non-persistent data structures in purely functional languages unless you are happy to go outside functional programming.  For example, try to implement Kruskal’s algorithm in Haskell using an O(α(n))-time disjoint-set data structure; almost everything will be in an IO monad.  That would be technically still a Haskell code, but not a Haskell code for practical purposes.  
> **username_3**: What are these "practical purposes" of which you speak?  
> **username_4**: @JɛﬀE: The practical purposes for programmers.  I do not think that we can define them rigorously, but they are something which programming-language researchers always think about.  From the theory-of-computing viewpoint, C and Haskell are obviously equivalent.  From the programming-language viewpoint, they are not.  
> **username_6**: A big issue is that people write code differently when the level of abstraction is higher, just because it looks nicer or because they are *bad* programmers (PHP!). For example, you can have horrible runtimes in Scala but do the very same thing as fast as Java -- if you know what to look for.  
> **username_7**: @Raphel: PHP and Java do not reach high level of abstraction, and Scala tries.  
> **username_8**: @JɛﬀE "theoretical computer science" != "algorithm designers". PL folks might have something to say about that, and about this question.  
> **username_3**: @SureshVenkat: Fair point.  
> **username_9**: @SureshVenkat I think all six answers to this question are a testament to it not being a good TCS question.  
> **username_8**: are you really asking me to participate in a discussion after three years ? :)  
> **username_9**: @SureshVenkat Sorry, I am not, I was probably feeling grumpy :)  

---

## 6 answers

### Answer by username_10 on 2012-02-20. Score: -3 | Accepted answer

there is a simple answer in the case you mention, Python/C, not mentioned in answers so far. the Python interpreter is *written* in C but not vice versa. same with eg Ruby or Perl.

& yes as you guess, another simple answer is that modern interpreted languages use a [*garbage collector*](http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29) which simplifies the programming experience and maintenance of the code at the expense of some runtime overhead.

a useful way of picturing language implementation complexity is to visualize *layers* of different systems or subsystems that run concurrently or "on top" of each other. for example interpreted code runs concurrently with a garbage collector. interpreted code is built "on top" of C interpreting code. etc.; the "higher level" language is written in terms of the "lower level" language. in a sense the higher level language is compiled into the lower level language.

however the question seems to suggest an unfamiliarity with the basic theory of [NP completeness](http://en.wikipedia.org/wiki/Np_complete) which is the theoretical construct used to judge runtime complexity and in which there is indeed no substantial difference between compilers and interpreted code because it all runs within P-time factors of each other.

> **Comments:**
> **username_0**: There's been a lot of interesting discussion, but this is the answer that directly addresses the core of it, by pointing me in the direction of NP-completeness. Thanks!  
> **username_11**: @username_0les: There's been quite a bit of talk about garbage collectors being features of high-level languages that make them slow. But my impression is that a *well-implemented* garbage collector can actually make a program *faster* (not always, but in some cases), because handling the memory management by hand can be so difficult that a programmer is not likely to construct something as efficient as an industrial strength garbage collector.  
> **username_9**: "NP completeness which is the theoretical construct used to judge runtime complexity" what kind of nonsense is this!  

---

### Answer by username_7 on 2012-02-20. Score: 10

There is no deeper reason other than quality of compilers and interpreters.

Some languages are *not* designed with speed of execution in mind. For example, the [design goals of Python](http://python-history.blogspot.com/2009/01/personal-history-part-1-cwi.html) did not include speed of execution at the very top. In such cases you should not wonder where speed has gone.

Some languages *are* intended to run fast but it takes time for people to produce good compilers and runtime environments. Typical examples are the so-called "high-level" languages. For example, early variants of ML were memory hogs that ran sort of fast until the garbage collector kicked in. Nowadays, 25 years later, a modern variant of ML, such as [Ocaml](http://caml.inria.fr/), runs with speeds [comparable to those of C and C++](http://www.ffconsultancy.com/languages/ray_tracer/comparison.html), and in most cases you don't even notice that there is a garbage collector.

Why is it harder to compile high-level languages to fast code? Well, because they are high level. Programs written in such languages operate directly with concepts that are far removed from the underlying hardware. In contrast, low level languages such as C, C++ and java are essentially glorified assembly languages and there is very little that the compiler actually needs to do.

Also, there are languages out there whose design is essentially screwed up in such a way that efficient compiled code is hard to obtain. Typically such languages have no or little compile-time type checking or unreasonable amounts of reflection, i.e., `eval` , and an operational semantics which relies heavily on string replacement and manipulation of source code. Bourne shell comes to mind, TeX/LaTeX as well, and maybe Python to an extent. As long as such "features" are deliberate design choices that is ok, but there also seem to be languages out there whose design was based on ignorance of programming language theory.


---

### Answer by username_12 on 2012-02-20. Score: 3

(Not an answer, but a bit too long comment.)

One aspect that has not been covered in the other answers is the fact that "higher-level" languages typically provide additional *safety nets*, which may involve some run-time overhead.

As a concrete example, I have occasionally compared the performance of C code and equivalent Java code (truly equivalent – forget about classes and objects, your high-level data structure is `int[]`), and I have also had a look at the machine code that is generated by modern compilers in each case. While the quality of compilers varies a bit, and just-in-time things have their usual advantages and disadvantages, it seemed that a major difference was related to the safety nets. In Java, array references such as `x[i]` involve two sanity checks: pointer `x` is not null, and array index `i` is valid.

Of course some of these checks can be optimised away, and some of them can be moved outside the inner loops. Modern CPUs also help tremendously, as these are branches that can be predicted well. Nevertheless, a number of these checks are there and they take a non-trivial amount of time.

I think now we are at a point where we can approach the question from a TCS perspective, especially from the perspective of the theory of programming languages: Would it be possible to, e.g., re-design Java so that *none* of these run-time checks are necessary, without losing any of the safety nets, and without putting any significant additional burden on the programmer?

> **Comments:**
> **username_7**: You cannot hope to remove all such checks, but certainly you can remove very many with good language design. For example, Java should not have a `null` object, and that would immediately remove some checks.  
> **username_13**: Removing all checks is equivalent to the halting problem. ;)  
> **username_11**: @AndrejBauer: Forgive a theoretician and programmer who is ignorant of, but interested in, PL theory. What would be the standard PL theory wisdom of how to re-engineer Java to not have null? Would it be to have the ability to check if a variable has been assigned a value? Something else?  
> **username_7**: When a variable is declared it must be initialized. Instead of `null` introduce option types and make sure with good syntax than whenever anyone uses a value of option type they check *both* possibilities (undefined and defined).  

---

### Answer by username_14 on 2015-05-26. Score: 2

Just an update on the issue: I think that the problem of efficiency of the constant factor is mainly qualitative, rather than quantitative. Indeed, a high constant factor is mainly caused by an inefficient interpretation of the programmer's intent by the language parser.

In this sense, we can say that it's more a problem of semantic linguistics rather than just technical implementation: with a low level language such as C, the language parser don't have to make any guess, since you have direct control of the most basic instructions, and thus are responsible for the whole program flow. With a high level language, you get a more abstract control of the program flow, which makes it easier and faster to design complex program, but at the expense that you delegate some of the program flow design to the language parser: it now has to make some guesses about what you meant, and it can be very costly if it's some kind of program flow that the language parser wasn't primarily made for (such as linear algebra in Python).

This is not because of a lack of investment of the language authors, but rather that, like with any level of abstraction, you choose a balance between the conciseness of your words and their preciseness. A word like "humans" is very abstract and describe a whole specie, but it doesn't account for the particularities and all the culture of each individual in this group. Just like scientific jargon, high-level language parsers are designed to concisely and efficiently describe operations of the targetted paradigm, but they cannot describe as concisely every other paradigms.

However, now it seems that a new class of languages are emerging: annotated languages, such as Julia or Cython or Numba. They are neither really interpreted nor compiled but in-between: you can write high-level code that the "interpreter" will have to guess how to run the most efficiently possible (and correctly of course), or you can almost compile your code by annotation or by using other specialized constructs such as dispatching or semi-automatic unrolling/vectorization of loops, so that your annotations avoid the need to make the language parser to guess what you were meaning to do at lower levels of abstraction: in short, annotations give you the ability to give precisions on your high-level abstraction. We will see in the future if this concept works out.


---

### Answer by username_15 on 2012-02-20. Score: 2

I think that the gap between the performance of two programming languages highly depends on the type of the problem/algorithm and how you measure such "*performance*".

The introductory paragraph of the "[The Computer Language Benchmarks Game](http://shootout.alioth.debian.org/)" page is clarifying:

... When the facts are about the performance of programs, the particular way each program does a task matters a lot. Obviously when programs implement different algorithms that difference may itself be enough to explain any difference in program performance. Less obviously, even when the same program is measured with different implementations of the same programming language, the particular way that program does the task may work better with one of the language implementations than the other - but slight changes to the program might reverse that performance difference. So there has to be some flexibility allowed in the way programs implement the same algorithm, and the tasks are kept simple enough for you to check the program source code. When the facts are about a wide range of different programming languages even more flexibility has to be allowed in the way programs implement the same algorithm - after all, the point of using a different language is for the different approach that language provides. ...

For example, if you look at the [The Computer Language Benchmarks Game](http://shootout.alioth.debian.org/u32/which-programming-languages-are-fastest.php), you can see that a gap often occurs between a compiled and an interpreted language, but it is not always true: in the *regex-dna* test, javascript performs better ... but only because it has a powerful and "native" support for regular-expressions. It is also clear that the gap between Java and C++ has greatly reduced thanks to its [JIT compilation](http://en.wikipedia.org/wiki/Just-in-time_compilation).

The *theory says* that different programming languages lead to execution times that differ only by a constant factor ... and the speedup theorem for Turing Machines says that constant factors are meaningless; but some efforts have been done to **study computability and complexity from a programming-language point of view** and the results are a little bit different.

See for example: **Computational Complexity via Programming Languages: Constant Factors Do Matter** (A. M. Ben-Amram and Neil D. Jones)

... Using the programming language described in this paper we prove a series of hierarchy theorems ... The main theorem, for deterministic time, states that for time-constructible functions $T(n)$, there is a constant $b$ such that more decision problems can be solved in time $bT(n)$ than in time $T(n)$ ...

> **Comments:**
> **username_3**: Ben-Amram and Jones' paper is available [here](http://www2.mta.ac.il/~amirben/downloadable/acta.ps.gz) and [here](http://www.springerlink.com/content/jbatp9j0anhacfln/).  
> **username_11**: I never particularly liked the constant-factor speedup theorem as an argument for constants not mattering. From a mathematical point of view it "makes sense" because one doesn't want to specify the underlying alphabet. From a research point of view it makes sense because it often makes our lives easier. But from a more practical (and even still somewhat theoretical) point of view, the alphabet is always {0,1}, and merely "decreasing" the running time by blowing up the alphabet is a cheat. Perhaps a cheat that we cannot formally avoid, but it still always felt like a cheat...  

---

### Answer by username_6 on 2012-02-20. Score: 1

Interpretation vs. compilation issues aside, memory IO is indeed a big issue (maybe *the* issue) in my experience, in particular caches.

When writing a program in C or maybe even C++, you (can) control what ends up where in memory. You can not in languages like Java. This is fine for many purposes, but consider the following.

Imagine you want to store a (huge) matrix of objects, say pairs of numbers. In C, you can just create an array of those. Iterating over the matrix is about as fast as if the matrix contained single numbers. Now, in Java, pairs would be objects which would end up *somewhere* on the heap, the matrix containing only pointers. If the JVM is bad at recognising and acting on demand for locality¹, i.e. the object are scattered over the heap, this means cache becomes useless if you iterate.

The problem tends to explode if you have parallel algorithms, by the way.

[1] I do not know what it actually does in this regard, but my experience indicates it is not too clever about it.


---

