2

While it is hard to rank languages by speed, it is well accepted that, in practice, today, you can get the fastest programs using C. I've always taken as a dogma that no high-level language could be as fast as it at least for some time. Except I've just learned about the Stalin compiler for Scheme. Scheme, as we know, is a high-level functional language with no type annotation. Yet, that compiler claims to generate programs 1.5 to 100 times faster than their direct equivalent in C.

The fact I wasn't aware of its existence makes me worry about my beliefs. First, how can that be true? Second, this can't be a lone exception. Are there other compilers of high or low level languages that are producing faster-than-C code, that I am not aware of too?

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • what do you mean exactly with "faster than C code"? C code is always compiled using a compiler. What is the C compiler you refer to? – Gianluca Ghettini Sep 13 '13 at 10:32
  • @G_G, there are some things that are just hard to define. You know what I mean, and the average reader here will know too. Stalin generates code that is, in most cases, faster than an equivalent (another term complicate to define, but that you know what I mean) C program compiled with any C compiler (gcc, for example). I can't prove that, though: I've just got their claims. But I've done the research and many anedoctes around the internet confirm those, so I'm, at least initially, confident about it. – MaiaVictor Sep 13 '13 at 10:36
  • Yes and no. Yes in that if a very good C programmer sits down and looks at the code long enough be can probably find some way to make it at least as fast as anything else except assembly. However with average to good programmers for very long stretches of code it's quite possible that your one-off is good high-level language is on average faster than the C one-off. http://www.flownet.com/gat/papers/lisp-java.pdf – WorBlux Sep 13 '13 at 13:33

5 Answers5

8

You should read the comments...

Nice, but part of the reason the C version is slow is that you are using abs instead of fabs. abs takes an int as an argument (this should be a compiler warning!) – passing a double other than zero always returns a large number. The C version is basically iterating till the error is below double’s resolution.

printf(“%d,%d\n”,abs(0.0001)<0.001,fabs(0.0001)<0.001); outputs 0,1

and the response

Excellent point! Making the switch to fabs brings the gcc-inline speed down almost exactly to what Stalin is getting.

And the quote from the article:

Though in principle Stalin produces intermediate c code, it is utterly alien and low-level.

So Stalin isn't faster than C, because it compiles to C, Stalin is simply better at writing tight unreadable C code than you :-)

From the wiki page:

Stalin (STAtic Language ImplementatioN) is an aggressive optimizing batch whole-program Scheme compiler written by Jeffrey Mark Siskind. It uses advanced flow analysis and type inference and a variety of other optimization techniques to produce code (using C as an intermediate language) that is very fast, particularly for numerical code.[citation needed] In a number of tests it has outperformed hand-written C, sometimes by a considerable margin.[citation needed] Stalin is intended for production use in generating an optimized executable.

So let's see... It's a compiler that probably tries to infer the used types (the name is quite clear on this) and that has outperformed hand-written C.

In general, domain specific problems can be faster than C, because they can use tricks not present in C. A language that has as primitive objects vectors could more easily use vector instructions of the CPU, for example.

Community
  • 1
  • 1
xanatos
  • 109,618
  • 12
  • 197
  • 280
  • They get it to run up **as fast** as Stalin, which is still impressive considering Scheme is a dynamic language known to be a order of magnitude slower than C in most implementations. Also, I've heard several anedoctes that stalin-produced programs are actually much faster than their C equivalents, in general, so I'm pretty confident on this one. – MaiaVictor Sep 13 '13 at 10:34
  • 3
    @Viclib I'll add another quote from the article: `Though in principle Stalin produces intermediate c code, it is utterly alien and low-level.`. So the point isn't that Stalin is faster than C, but that Stalin writes better C code than you :-) – xanatos Sep 13 '13 at 10:36
  • 1
    @Viclib The fact that it's dynamic is irrelevant. If the types can be deducted at compile time, the compiled code is as much optimized as a static typed code. – xanatos Sep 13 '13 at 10:38
  • Sure, it is possible - I'm not disputing that. But hat are other compilers for higher level languages that, in average, generate faster than linguistic C code - as Stalin does? And, also, why C is often recommended for performance sensitive applications, when there is this seemingly better option? Why aren't more people using Stalin, that is? – MaiaVictor Sep 13 '13 at 10:41
  • @Viclib For the second question... Technically C++ is a separate language from C, but for the same code produces comparable machine code, so it should be as much fast. Through the use of template programming some types of problems can be even resolved at compile time, making C++ theoretically faster :-) – xanatos Sep 13 '13 at 10:55
  • @xanatos and because it's in CPS style before the C compiler gets to it, some more optimization may be available that if you used higher-level C to start with. – WorBlux Sep 14 '13 at 17:56
2

C - when using compiler optimizations - produces very fast code. I have post-optimized assembler code created by a good C compiler for a very time critical interrupt. It is still possible to make the code 25% faster when knowing constraints (e.g. an input value is always in a certain range) that the compiler does not know. However the Scheme compiler won't know either!!

This means it is theoretically possible to write code that is 1.3 times faster than the code generated by the C compiler. However it was impossible to speed up the code more.

Another language that is quite fast is Pascal so modern Pascal variants (like FreePascal) may have the same runtime and memory consumption as C compilers.

Scheme is a declarative programming language while C is an imperative programming language. The simple question is: What does "direct equivalent" mean?

Think about the following Scheme code:

(define (example a) (+ (if (> a 1)  (example (- a 1)) 0) (somefunc a)))

In C you may implement it like this:

double iffunc(int a,double b,double c)
{
    return a?b:c;
}
double example(int a)
{
    return iffunc(a>1,example(a-1),0)+somefunc(a);
}

But you may also implement it like this:

double example(int a)
{
    int i;
    double b;
    for(i=1;i<=a;i++) b+=somefunc(i);
    return b;
}

In C the second implementation would be the one used by 99% of all programmers. It is much faster than the first one. The first implementation is the "direct equivalent" to the Scheme variant. (It is impossible to write a"for"-loop in Scheme!!)

So if you compare the speed of the first implementation to the speed of the Scheme code you may in fact be 1.5 times faster or even more. Comparing the speed of the second implementation to the code generated by the Scheme compiler I'm sure the C compiler will be faster!

Martin Rosenau
  • 17,897
  • 3
  • 19
  • 38
  • "I'm sure the C compiler will be faster!" - that is a tasteful invite to test it! – MaiaVictor Sep 14 '13 at 04:45
  • 1
    @Viclib: I tested it (unfortunately the Scheme compiler seems to be integer only, so I had to test using integers): Scheme: 26 timer ticks (32 including interrupts), C: 6 timer ticks (-> C is 4 times faster than Scheme!) – Martin Rosenau Jan 07 '14 at 22:34
  • OK you win. Were those 4 months about Stalin compiling time? – MaiaVictor Jan 08 '14 at 00:44
2

Someone ought to mention Fortran, which often outperforms C in numerical applications. Maybe this is helpful:

Fortran vs C++, does Fortran still hold any advantage in numerical analysis these days?

Community
  • 1
  • 1
Lars Brinkhoff
  • 13,542
  • 2
  • 28
  • 48
1

A particular compiler for any given language may generate an output assembly program that is faster than the assembly output from a particular C compiler for a particular hardware target.

So yes, there exist implementations of programming languages that for some hardware, for some programs generate assembly that runs in less time than an "equivalent" C program.

There are no "high" level languages that I know of that generate better assembly than good C compilers for all programs written in C by expert C programmers...

So:

  • There exist compilers for high level languages for which there is at least one program that when compiled is faster than a C program.

  • There exist compilers for high level languages for which there is at least one program that when compiled is faster than an expert C program.

  • There exist compilers for high level languages that for more than a few programs when compiled are faster than C programs.

  • There are no compilers for high level languages that for most programs written produce code that is faster than equivalent expert C programs.

Things that make this question unanswerable:

  • Definition of "high level language"
  • Definition of "most programs" -- do you really mean >50% of all programs that may be enumerated in a language?
  • Definition of "better than C" -- better than naive C? better than expert C?
  • Definition of target -- on all architectures? some particular hardware?

References:

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • Don, while I agree with most of what you said, I think you are wrong, because Stalin fits that last description. Except you are stretching a little bit putting the term "expert" - a fair comparison involves two semantically similar programs, for which Stalin does, indeed, almost always outperforms C. – MaiaVictor Sep 13 '13 at 10:50
  • It would hardly be impossible that most programs which are written in a domain-specific language could outperform any reasonable C implementation, if the language in question is seldom used for any purpose other than those where it excels. For example, if a system has a GPU which requires clearing its pipeline whenever one switches buffers but not when setting a "master clipping rectangle", a domain-specific language might be able to examine the set of buffers an application is going to need use regions of a single larger buffer to handle them all. – supercat Sep 13 '13 at 15:50
  • The domain-specific language might be Turing-complete, and might allow code to specify buffer sizes dynamically (performing somewhat slowly when code does so), but nonetheless for most applications actually written for it be able to use static analysis to sequence things to an extent a C compiler could not. One might be able to have a C routine which would at run-time take a list of operations that would be necessary and figure out how best to handle them, but that would basically entail writing a GPU-operations compiler in C. – supercat Sep 13 '13 at 15:56
  • Yes, a DSL is a good exception. We presume here "high level" + "general purpose". – Don Stewart Sep 13 '13 at 16:04
1

It's not true!

C is never faster than Assembly on a specific platform since C uses assembly as an intermediate and therefore it is theoretical impossible for C to create more efficient code than it's implementors could do by hand.

For all other languages that compiles to C, you cannot expect that language to outperform C code written by the same author. Stalin is such language since it's output is generated C code. If the author of Stalin was to do the sqrt-iter in C, it would be an equally fast C as the generated C code by his Scheme compiler. That Stalin creates more efficient C code than Justin Domke does by hand, but it's not proof that Stalin is faster than C. It only proves that the author of Stalin is better in C than Justin Domke since his knowledge is within his Scheme compiler.

Today, the C compiler uses static analysis, dead code elimination, loop unrolling and all sorts of optimization techniques. For the average programmer the C compiler probably have better code than they would have produced of lower level code and it's shorter and more intuitive. The higher level languages abstract away unnecessary elements like memory management, register sizes, pointers and syntax making your code small and easier to debug. It comes with a cost and that is usually speed, but in many cases the speed and sometimes memory usage, but they are less important than efficiency. You have probably heard about the 3 rules of optimization?

In the end, different programming languages will be more suited for different task. The Blogs choice of algorithm is chosen as a good example. Would you really have done sqrt like that? I have once, but that was in a language that only has increment, decrement and while-true as math operators.

Last, I like Stalin. It's a nice peace of Scheme code from a guy who knows C very well. It should be studied, but if you really want to run Scheme, consider Ikarus instead.

Community
  • 1
  • 1
Sylwester
  • 47,942
  • 4
  • 47
  • 79
  • Assembly language is not a high-level language. – Eric Postpischil Sep 13 '13 at 20:01
  • @EricPostpischil true. But thats just because there is nothing between assembly and machine code. Newer assemblers also had macros and control flow like while, for, etc. What is C compared to Ruby? – Sylwester Sep 13 '13 at 20:37
  • The question asks about high-level languages. Assembly is not a high-level language. Therefore, its performance relative to C is not relevant to this question. This answer does not address the question. – Eric Postpischil Sep 13 '13 at 20:45
  • @EricPostpischil True, but it's a part of my answer anyway since Stalin is to C what C is to Assembly. It addresses the question since since nothing that uses an lower level language as a host can be faster. (Though theoretically you can make a scheme code that makes assembly code that is faster than C) – Sylwester Sep 13 '13 at 21:13
  • @EricPostpischil BTW the last sentence of the OP, with emphasis: "Are there other compilers of high or **low level** languages that are producing faster-than-C code, that I am not aware of too?" – Sylwester Sep 14 '13 at 00:21
  • Indeed, while I put an emphasis on high level languages, I preferred to leave the question open for low level languages too, as C is faster than most of those anyway. Still, while, @Sylwester, you seem to know what you are talking about, you are just throwing some statements without providing evidence. Saying that stalin doesn't outperform C after I just gave evidence of the opposite will need equivalent or stronger evidence, or else it will not make any sense and your whole argumentation will fade invalid. – MaiaVictor Sep 14 '13 at 04:49
  • @Viclib I prove by logic. Your proof is false since Stalin creates C code and that C code is equally or less efficent than what Jeffrey Mark Siskind whould have written by hand. Thus Justin Domke thinks Stalin is faster than C since Siskind's C code is faster than his. The same logic proves C is never faster than assembly and that ClojureJS is never faster than JavaScript. It's the curse of compilers. It cannot be faster than it's object code. – Sylwester Sep 14 '13 at 10:07
  • @Sylwester *"Your proof is false since Stalin creates C code and that C code is equally or less efficent than what Jeffrey Mark Siskind whould have written by hand."* Expect it is **not** less efficient. You are working with the wrong data. It is almost always faster. If you don't **believe** that, then it is another subject - a matter of gathering evidence. But if we don't agree with the data, the debate is meaningless. – MaiaVictor Sep 14 '13 at 10:12
  • @Viclib almost always?? The output of Stalin is C. How would you think that C file compiled will perform compared to the executable produced by Stalin? Do you think it's possible that such C file could be written by the author of Stalin? When doing something that Stalin is not good at, like array handling of bytes using pointer arithmetic. Do you think the author of Stalin would produce a faster version with pointer arithmetic or do you think Stalin will win over it's author? Is there a comparison requirement you haven't written perhaps? – Sylwester Sep 14 '13 at 13:14