The “C Is Efficient” Language Fallacy (2006)
scienceblogs.com
scienceblogs.com
This guy also could have at least linked to a repo of his code... though none of that fancy github stuff was around, Sourceforge and CVSweb was around back then. Without the source we can't really accurately judge, well, much of anything. Compiler flags, JVM tunes (was it warm?), source code, data sets, or hell, even mention of compilers.
Edit: Though his point held hm, not quite 'true' categorically, but you could argue the point. Around '06, Fortran was still largely used, at least bioinformatics (sequencing, attempts at heuristic folding .. stuff), weather prediction, and was a perfect fit for linear algebra.[1] It was accessible and fast enough to be used by post-docs who didn't write software for a living, so presumably the ecosystem was founded then continued to develop within Fortran. Even if it was possible to outperform your simulations in C++ (I'm sure you could get at least fairly close), all of the work you were building off of (e.g. with your colleagues, advisors, etc) were Fortran-based.
[1] This is all hearsay from my father's / his doctoral students work from the late '90s/early '00s when I was in high-school, so I can't really offer sources on hand, but if someone really wants me to, I can fire off an email to him to gather specifics.
That's a valid gripe to have, but it should be said that most scientific papers that report simulation or algorithm results do exactly the same. Reproducing results is totally left to whomever feels like (and has the time to) dispute the claims.
Which is why you don't often see much in the way of disputation of performance claims, btw (yeah, ok, also because people take part in competitions where you get the chance to put your code where your mouth is).
I'm sorry if my comment upset you. I'm really not trying to advance any stereotypes and rather just report what my experience is so far, as a Masters student (rather than a researcher). I've also discussed this with one of my professors, who does research mainly in NLP and he told me the same thing.
Personally I find it hard to understand why it's not compulsory for academics to point to a public repository where anyone can find the code that goes along with their papers. I've heard arguments for and against sharing code and particularly data, so I'm not saying that I am necessarily right, but it's really just weird to read "our system beats the best results reported so far" with nothing but a few figures in a table to back that up. And with so much infrastructure and tools around to support sharing code (just think of github) I really don't see what's stopping people.
My area is in algorithmics, which is a lot less of a "hot topic" and there's less competition and more cooperation all-around. That may be an important factor in the willingness to share code.
I do agree with you on publishing code and have open-sourced the code to some of my research. Unfortunately I never heard back from anyone, maybe my topics just aren't hot enough ;) I'm a bit unsure whether to publish code for ongoing projects (where some aspects have been published, but others are still in the works for future publications) - in that case there is some incentive to keep the source closed until the project is finished.
(I work with a Physics group. Sometimes I found programs with an old part that still use numbered lines for the "do". We are still trying to get rid of numbered lines ...)
EDIT: Also, lattice QCD people are using C++ nowdays (frankly, I haven't seen them using anything else).
How has it gotten better? What has changed? And why are those changes relevant?
Why is this even worth pointing out? Well, in many languages communities (Common Lisp is a good example), the speed argument comes up, and it's pointed out that carefully working with the compiler (declares in all the right places and so on) makes the implementation competitive, and this is often dismissed as "too much work", ignoring the fact that even in C, there's no free lunch.
When one recognizes that good performance often requires a dialogue with the compiler, one starts to recognize that a criteria for performant language implementations is not "it's just like C" but rather "it's possible to tell the compiler to make this fast".
This makes many alternate languages viable choices for high-performance work (and eliminates some!), at least based on the current state of their implementations.
Imagine if as much work had gone into their compilers as has gone into the production C and Fortran compilers of today.
Deciding when to spend the energy and resources to optimize that one routine is the result of good benchmarks and code profiling. Identify your bottlenecks, and optimize the hell out of those. For everything else though, you need to ship a product, and the human effort is largely wasted on a less-called routine that makes the character blink every 173rd frame.
C compilers are fast in modern times, because of the amount of industry money spent in writing C optimizers since the industry adopted it.
If we're only talking about single-threaded, CPU-bound code, this is basically true of any imperative language without fancy data structures: even a fairly naive native compiler will produce "pretty fast" code in our modern times where the standard for pretty fast is pretty low.
It seems intuitive that the further a language is from the machine, the harder the compiler has to work to make that language's idiomatic constructs efficient on a machine.
The kicker here is that C is no longer so close to the machine. It's still a PDP-11, and today's machine is not. This idea is what I think is still useful about the original article, for all its other faults.
I admire compilers like MLton that actually deliver on the promise of higher-level languages without the usual performance compromises for abstraction. Hopefully we'll see more of this as time goes on, as well as more languages like Sequoia that are close to the new machine.
1. C99 has the restrict keyword to declare no aliasing.
2. there are still many places dropping down to assembly is better than what your compiler can do, mostly since C is too portable to provide access to processor flags directly (see strlen.s/asm for your platform for an example, e.g. http://lxr.free-electrons.com/source/arch/arm64/lib/strlen.S ).
3. (nitpick) Arrays are actually types distinct from pointers in C/++ (e.g. char a[5]; char * b="asdf"; a=b; will not compile, and arrays aren't interchangeable with const-value pointers like char * const either - try passing a pointer to a function accepting an array).
edit: spacing, fixed italics instead of pointers
As a benchmark it's probably OK, but language benchmarks in general are never very useful. Like, the op essentially makes the claim "you can't code this any faster in X language". Well, maybe you can't, but someone else can. Unless you have a way to run exactly the same code in n languages, or somehow produce exactly the same binary from n languages, then there's no real comparison, sadly.
But- we're programmers and that sort of thing is our favourite sport, innit.
But that's the point, isn't it? You can't ever compare two programs written in different languages claiming to test "the same program" written in different languages. Because in the end either they're not the same program, so there's no comparison, or they're the same program, so what are you really comparing?
""" `int x[1000]` in C or C++ doesn’t have much meaning. It’s semantically equivalent to declaring “x” as `int *x`. You can reassign X any time you want, to make it point to a different location. """
C is also a pretty different language style-wise than C++. Aside from that, they're both good languages for building runtimes since their memory model resembles physical memory and they can run in an unhosted (runtime-less) environment.
Just a childish rant really.
"While I know that C compilers are really conservative about this, doesn’t it matter as to how x and y are declared? After all if they are dclared as: int x[1000], y[1000];"
Those array declarations aren't function argument declarations (except in pre-C89), so not sure why he would talk about semantic equivalence in response to that if it only applies to function arguments.
Noting that the semantics of array access semi-equate to pointer dereference is well beside the point.
This fellow's "for" loop: for (int i=0; i < 20000) { for (int j=0; j < 20000) { x[i][j] = y[i-2][j+1] * y[i+1][j-2]; } }
shows that you don't even have to have unrestricted pointer access to have bounds violations - what's "y[i-2]" when i==0?
'C' is not for everybody. It's a systems programming language. As the space of activities related to computers grows, there's no good reason to continue to erect a strawman about the language and set fire to it.
1) Know the base address of the array.
2) Know the offset of the element(s) you're passing
2a) Know the declared length ( or other upper limit for the array ).
then you need never refer to any element of an array that doesn't exist.
What I appreciate about C in particular is that it seems harder to "program by accident" than it is in most languages. C was my first language. After I learned C, I programmed in a higher level language for a while later before discovering that its runtime threw exceptions on 'array subscript out of bounds.' I discovered it by looking over someone else's shoulder in a lab. I realized then that I had just learned not to do that because C was so unforgiving.
We can argue whether the kind of discipline of thought that you gain from that experience is good or even useful today, but I suspect it is. It's different from learning how to do mental math in a world full of calculators - that's just raw mental exercise.
C was more convenient than doing assembler, but not much more, compared to say Pascal. (Having learned BASIC, FORTRAN 77, Pascal, PDP-11 ASM, Lisp at school, and some dBASE at work, before we switched over to C at school, which seemed like a big step backward)
var s : string; multi : integer;
...
s := 'Hello' + ' ' + 'world';
multi := 616;
writeln( s, ' ', multi : 4);
char s[ 256 ]; int multi;
...
s = strcat( strcat( "Hello", " "), "world");
multi = 616;
printf( "%s %d4\n" s, multi);
This is fallacy #1 about C. C does have arrays which constitute a contiguously allocated piece of memory, it's just that the identifier decays to a pointer in most contexts. When dealing with arrays, there is no indirection involved.
In other words, this claim in the original article is incorrect: "But there's no way to write code in C or C++ that guarantees that. "
* C: 0.8 seconds.z
* C++: 2.3 seconds.
* OCaml: 0.6 seconds *interpreted*, 0.3 seconds fully compiled.
* Java: 1 minute 20 seconds.
* Python: over 5 minutes
Edit: numpy was available in 2006, and even earlier than that.
Recently I also investigated Go as my new "fast language", generating bindings for other languages such as Python is still very difficult though and many of the emerging tools (e.g. gopy) are not very well maintained our outright broken. If integration with other languages was easier I think Go would be a serious contender for this kind of scenario though.
It can be very fast by itself, and can also be written extremely high level & is very easy to form bindings to other languages, thanks to the multiple dispatch. Even small things such as having full unicode support is very nice to write maths code in a very 'pen and paper' kind of way.
http://benchmarksgame.alioth.debian.org/u64q/fortran.html
C seems to match Fortran on about half of them and be 2 or 3x quicker on the others.
Perhaps that was the last time you looked ;-)
Efficiency, as current situation (before true AI), are always specific. The compiler may implement certain specific optimizations that enable efficiency for certain specific applications -- inline here and there, vectorization for trivial cases, loop unwrapping for some patterns -- but hoping the compiler can work out the true efficiency is naive.
So true efficiency often requires true intelligence. I'll list one example, the famous platform specific linear algebra library blas. It is really efficient but FORTRAN is not the real reason; it is due to the human expert tweaking.
Under the context that real efficiency require human tweaking, there is some advantage of choosing C over most other language, in that C allows more room and more straight forward path for tweaking.
Comparing C against other language (not FORTRAN, which is very much like C), the efficiency of the language is achieved by its compiler doing less rather than doing more. Because the compiler is doing less, it is more straight forward on how to reach efficiency (if the coder sees the efficiency). With C, getting efficiency is programming. In comparison, for some higher level programming languages, efficiency is having faith in the language designers and compiler implementers; and tweaking often requires specific knowledge of the language and compiler. For example, knowing that using higher-order functions can be more efficient than a straight loop -- that is beyond general knowledge of programming.
On this, I would like to differentiate C from C++. C++ language (and compiler) is much more complicated than C and much of its efficiency is tweaked by the compiler. For example the '-O' flag is often not so significant for a C program but it is often day and night kind of different for a C++ program (often -O2 or even -O3 is necessary). For C++, significant portion of efficiency is dependent on the compiler, and as such, requires additional knowledge on the coder, therefore, more difficult to reach the efficiency. Of course theoretically, one can write C in C++; and many use that theory to derive that C++ is as if not more efficient than C. That is not the case in reality. Few can contain themselves in a C subset when writing C++ (if they can, why C++ instead of C?) So in reality, if you are using C++, you almost certainly are not writing C and often the efficiency path is more complicated comparing to C.
What we want is effectiveness.
The claim that Fortran arrays are easier for the compiler to optimise than raw pointers in C/C++ may well be true. But I imagine that there has been progress on compiler technologies to address auto-vectorisation in C/C++ since the post was written (and since C99, C has the restrict keyword too). Can anyone comment?
Auto-vectorization is a bit different, it uses mathematics of integer polyhedra to perform loop transformations allowing the compiler to replace scalar operations with SIMD vector operations. The Intel C compiler and IBM XL C compiler have been quite good at this for a long time (at least on simple loops that don't really require transformations). More recently GCC implemented the "Graphite" optimizer to handle this type of auto-vectorization, and LLVM has the the "Polly" optimizer. FORTRAN automatically benefits from these optimization improvements because all these compilers have FORTRAN front-ends that translate these languages to an intermediate representation, where the optimizer don't "know" what the source language was.
I think the pointer aliasing issue still haunts C because the "restrict" keyword may not be commonly used. So FORTRAN seems even today to have a reputation of being "faster" than C for numerical codes.
There is no compiler for any language, which can turn an arbitrary sequental algorithm into parallel, and will never be.
Whilst C based apps can be made to run efficiently, its not efficient to code with the usual tools compared to other languages and IDE's (think big customer development bills), and thats even before you get into the debate of whether some code runs faster with multiple threads on multicore cpu's whilst bearing in mind the ram & bus limits, cpu cache collisions, available cpu instruction sets and so on.
More people really should get over the "awesomeness" of the clockwork turk machine, unless they are easily pleased?
What am I missing?
The author wrote a naive loop in a bunch of languages, and, got a faster result in OCaml (0.3 sec) than in C(0.8 sec). Right, but the code was a totally naive loop:
for (int i=0; i < 20000) { for (int j=0; j < 20000) { x[i][j] = y[i-2][j+1] * y[i+1][j-2]; } }
The fact that C has a bunch of libraries for vectorization of such code, or that there are million compiler directives that can speed that code a lot is somehow missing from the article.
So, the conclusion is that a compiled OCaml code is twice as fast as a naively written unoptimized loop in C.
I recently learned that Knuth created a virtual instruction set (MMIX) specifically because he found that comparing algorithms with high level languages was too prone to problems. Using a direct instruction set that executes on a virtual machine means that algorithm analysis can focus on the algorithm.
Now, there is something to be said for languages which produce code that is nearly as efficient as the most efficient code you can produce with C, especially if it's easier to write it. But that's not the author's point.
That is the point of the author, you certainly can achieve the same speed in C but you have to do extra work because the compiler is unable to do things like discovering the absence of aliasing. So you have to manually build this into the code which in turn makes it more complex.
Whereas a higher-level language can truly abstract over of all these things, and perform target-specific optimizations where it sees them.
I don't care about the average case- I care about the maximum case (because I work on performance sensitive code).
Chances are good that even really good developers are not aware of the best implementation because it might depend on pipeline latencies, constraints on which instructions can execute in parallel and so forth. That is what compilers are good at and I don't think there is an in principle difference here between C and OCaml.
The other two points are more involved. On the one hand C offers, for example, things like intrinsics and seems generally more apt to control what machine code will get generated as compared to OCaml. On the other hand C is less expressive when it comes to conveying higher level semantics to the compiler to inform its optimization decisions.
So if you are aware of the optimal implementation - which, as mentioned above, you may not be - you are in a good position with C to get (close to) the desired result if you put in the extra effort to express the semantic details. On the other hand OCaml will certainly make it harder or even impossible to express your desired machine specific implementation. But then again the OCaml compiler can use information not (easily) available from C programs to guide its optimization and could come up with a sequence of instructions better than what the developer could think of.
In principle OCaml seems to have an edge over C because of the stronger semantics making it easier for the compiler to find a good implementation possibly beating the human. On the other hand, if the compiler does a bad job and you realize it, then C probably offers you the better tools to force the compiler to honor your will.
To finally answer your question, it seems highly unlikely that there are cases where one could in principle not write a C program as fast or faster than the equivalent OCaml program. On the other hand it seems not so unlikely that a developer might not be aware of what that C code would have to look like.
I can’t give you the code I did the LCS tests on – as I said, it was six years ago! It’s somewhere on a backup tape, and I’d need to get permission from my employer to release it.
At the time, I had just come off of a project where I was part of a team implementing a C++ compiler. C++ was definitely my strongest language at the time. The code in all of the languages was as carefully hand-optimized as I could make it.
And at the time, I had *never* used OCaml; I had used its predecessor, Caml-Light for some experiments about 4 years earlier. But I was *far* from a highly skilled Caml hacker.
http://scienceblogs.com/goodmath/2006/11/02/the-c-is-efficie...
An average C++ CPU-bound code isn’t radically faster compared to e.g. C#. I suppose that’s true for other higher-level compiled languages.
But the good thing about C++, after I’ve profiled which parts of the algorithm take most time, I can gradually replace my average C++ code with SSE or AVX intrinsics. Sure it’s harder to read, write and understand, but if done right, on modern hardware it can become several times faster.
But as for "being a viable choice instead", we intend for Rust to be so. The devil, of course, is in the details: for example, if you're on an obscure or proprietary platform, a C compiler may be your only choice. In the context of this article, while LLVM will autovectorize some things, direct control of SIMD hasn't made it into stable yet, and requires a nightly today. But as far as the language and its power goes, our goal is to be, yes.
https://benchmarksgame.alioth.debian.org/u64q/performance.ph...
I like this because anyone can try to prove their assertion that their language is faster!
There is no ISPC or Julia, the C and C++ benchmarks use SIMD intrinsics specific to gcc, the benchmarks are run on core 2 processors... etc. etc.
"If you're interested in something not shown on the benchmarks game website then please take the program source code and the measurement scripts and publish your own measurements."
(And remember to include the license file in your redistribution.)
"Why don't you include language X? … my favorite language implementation? … Microsoft® Windows® ?
Because I know it will take more time than I choose. Been there; done that."
I've added new language implementations and programs!