# Is there a general theory for why certain algorithms are inefficient in high-level languages?

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?

• 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. Feb 20 '12 at 4:22
• 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. Feb 20 '12 at 9:00
• @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 whose amortized time complexity per operation is O(α(n)) is known. But I guess we are usually fine with a log factor. Feb 20 '12 at 13:59
• @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. Feb 20 '12 at 17:41
• @JɛﬀE "theoretical computer science" != "algorithm designers". PL folks might have something to say about that, and about this question. Feb 21 '12 at 7:03

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 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 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.

• 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
Feb 21 '12 at 16:16
• @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. May 27 '15 at 4:56
• "NP completeness which is the theoretical construct used to judge runtime complexity" what kind of nonsense is this! May 27 '15 at 5:32

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 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, runs with speeds comparable to those of C and C++, 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 <string>, 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.

(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?

• 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. Feb 20 '12 at 22:33
• Removing all checks is equivalent to the halting problem. ;) Feb 21 '12 at 12:28
• @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? May 27 '15 at 4:59
• 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). May 27 '15 at 6:13

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" 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, 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.

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)$ ...

• Ben-Amram and Jones' paper is available here and here. Feb 20 '12 at 14:53
• 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... May 27 '15 at 5:04

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.

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.