6

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?

Cera
  • 179
  • 4
  • 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. – Huck Bennett Feb 20 '12 at 02:57
  • 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. – David Eppstein Feb 20 '12 at 04:22
  • Or perhaps even between Java and C, because although C++ is higher-level it's still often considered relatively 'close to the metal'. – Cera Feb 20 '12 at 04:52
  • 5
    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ε Feb 20 '12 at 09:00
  • 8
    @JɛffE: 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. – Tsuyoshi Ito Feb 20 '12 at 13:59
  • 2
    @JɛffE: 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 Feb 20 '12 at 14:02
  • 2
    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ε Feb 20 '12 at 14:50
  • 2
    @JɛffE: 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 Feb 20 '12 at 15:22
  • 2
    What are these "practical purposes" of which you speak? – Jeffε Feb 20 '12 at 15:52
  • 4
    @JɛffE: 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 Feb 20 '12 at 17:41
  • 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 Feb 20 '12 at 21:48
  • @Raphel: PHP and Java do not reach high level of abstraction, and Scala tries. – Andrej Bauer Feb 20 '12 at 22:29
  • 3
    @JɛffE "theoretical computer science" != "algorithm designers". PL folks might have something to say about that, and about this question. – Suresh Venkat Feb 21 '12 at 07:03
  • @SureshVenkat: Fair point. – Jeffε Feb 21 '12 at 08:50
  • @SureshVenkat I think all six answers to this question are a testament to it not being a good TCS question. – Sasho Nikolov May 27 '15 at 05:36
  • are you really asking me to participate in a discussion after three years ? :) – Suresh Venkat May 27 '15 at 23:02
  • 1
    @SureshVenkat Sorry, I am not, I was probably feeling grumpy :) – Sasho Nikolov May 28 '15 at 21:20

6 Answers6

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

Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
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?

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
  • 1
    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 Feb 20 '12 at 22:33
  • Removing all checks is equivalent to the halting problem. ;) – Dmytro Korduban 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? – Joshua Grochow May 27 '15 at 04: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). – Andrej Bauer May 27 '15 at 06:13
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" 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)$ ...

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 1
    Ben-Amram and Jones' paper is available here and here. – Jeffε 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... – Joshua Grochow May 27 '15 at 05:04
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.

gaborous
  • 131
  • 4
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.

Raphael
  • 4,565
  • 28
  • 48
-3

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.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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. – Joshua Grochow May 27 '15 at 04:56
  • "NP completeness which is the theoretical construct used to judge runtime complexity" what kind of nonsense is this! – Sasho Nikolov May 27 '15 at 05:32