The "C is Efficient" Language Fallacy (2006)
scienceblogs.com
scienceblogs.com
If your matrix manupuilation code performance becomes an issue, you, the C/C++ coder will have to parallelize it and take responsibility for whatever assumptions have to be made.
Im sure that the limit of what one considers as acceptable code alteration by the compiler/interpreter depends on the person. Personally I'd be very wary of a system trying to guess-parallelize my code - especially if I can do it myself whenever I see fit by adding a dozen boilerplate code lines. I'm sure most academics needing a numerical calculus system would be glad to have the system abstract away every possible optimization, so that they can stay as much as possible in the 'abstract math space'.
I am also kind of wary of the "look, I wrote the program in several languages and here is the perf comparison". Our skills with each language vary. What I liked was (i cant seem to find the link) a teacher who asked his class to write a program doing some text manipulation/indexing (iirc) in whatever language they wanted. The fastest code was in C, yet the worst C implementation was significantly slower than an average java code. To sum all this up - the speed depends on the skill of the person in the particular language, much more than on the language itself.
The idea is: if you use a tool that lets you describe your problem at a high level and let the computer worry about how to do the calculation efficiently, you'll beat your hand-rolled C++ every time. And, there is now the possibility of hiring a "Real Programmer" to hack your math library (Octave, Mathematica, Python + numpy, whatever), allowing you to delegate work. If every calculation was a brand new C++ program, you'd only be able to improve your application's performance by hacking on your application. Separating the problem description and the solution description allows the solution-finding code to be optimized without knowledge of the specific problem.
I think this approach scales to the work that practicing programmers, too. We don't see it a lot because writing tools is time consuming and we all have deadlines; so we pic k the "worse is better" solution and hard-code our applications in what amounts to glorified machine code.
Just because a practice is common doesn't mean it's a good idea.
Within no-time, we had an extremely fast estimator, that could also help answering my research question (what are the most discriminative features in our models).
Let me push this point somewhat further: C is a very simple language. It's something that someone with a certain level of intelligence can fairly quickly pick up. There is also a wealth of excellent libraries available. The problem with 'use high-level, the compiler/interpreter will take care of it' is that those languages are either a lot more complex (Haskell, OCaml) or a lot slower (Python, Perl, Ruby). In the latter case, you will end up implementing modules in C anyway.
It is? Out of curiosity, did you know about all the undefined behaviors described at http://blog.llvm.org/2011/05/what-every-c-programmer-should-... and did you understand how your C compiler takes advantage of them before you wrote that statement?
Yes, those are familiar and described in every decent C introduction. Of course, that doesn't mean people do not make those mistakes. Let the compiler be pedantic.
did you understand how your C compiler takes advantage of them before you wrote that statement?
At the very least, is fairly easy to understand how the compiler optimizes correct code. In say, Haskell (which I do like a lot), you often have to resort to reading ghc's Cmm output to see why something is not optimized.
Simple != Easy to use
If you want to do performant number crunching with most other languages, you have to not only grasp the language, but also the underlying virtual machine or compiler. The more layers you pile on top, the harder it becomes to identify bottlenecks.
Sure, you can use fast implementations of common algorithms in a high-level language. But they are often written in C or C++. So, if you want to modify or extend such algorithms (which is likely, or you could just use an off-the-shelf program), you will end up in C-land anyway.
You forgot "to free those blocks of memory." It's OK. We C programmers often forget this. :)
Embedded systems sometimes still frown upon willy-nilly memory allocation ;)
Of course, days when your build breaks and it's because someone, somewhere defined a piece of data as 8 bits, but your latest build has shifted some stuff around and suddenly two memory definitions have become one because of memory alignment...was probably more painful to track down than free() issues.
It doesn't even let you do that -- those things are external library calls.
Also, some people will argue that 'asking' an array on the stack is also allocation ;).
They don't have special syntax, but, then, neither does practically anything you do in Common Lisp, and that's standardized as well.
"Language" has slightly different meanings in different contexts. Perhaps he's talking about something in a theoretic context, as opposed to practice? Smalltalk has no special syntax for allocation (creating new objects) either.
Then he's still wrong. A standardized part of the language is a part of the language.
I find that… odd. Surely we all know here that number crunching wasn't C's domain to begin with. It was writing an OS (UNIX) on 2 slightly different machines.
But even more disturbing, are you seriously suggesting that being able to manage the freaking memory makes you closer to number crunching? Sorry for the emphasis, but I am astonished. Manual memory management (and unrestricted pointers for that matter) are about the hardware. They are about manual tweaking of implementations. They are definitely not about number crunching.
And even if they were, I take one goal of number crunching is to milk every single cycle out of your CPU farm. As far as I know, C loses that match to Fortran.
> If you want to do performant number crunching with most other languages, you have to not only grasp the language, but also the underlying virtual machine or compiler.
This is already the case with C. It has been a few years (decades?) since C code and assembly no longer match neatly at all. GCC optimized assembly code is such a mess that I see it as hermetic magic. Heck, even the performance model of modern CPU is half magic to me.
Now you are correct. I'm just saying that it applies to C as well.
But there is hope. The Viewpoint Research Institute, with their STEPS project, managed to write a complete compilation suite in about two thousands lines of code. It's not optimized for runtime speed, but it does suggest that it might eventually be manageable. Here is their last report: http://www.vpri.org/pdf/tr2011004_steps11.pdf
> Sure, you can use fast implementations of common algorithms in a high-level language. But they are often written in C or C++.
Of course. But the the OP did quite clearly talk about implementing those algorithms completely in those high-level languages. Either he was being dishonest, or your argument doesn't apply.
I mean this descriptively, not as a criticism. It is critical to understanding C and UNIX. It is also worth pointing out that while we might all prefer "the perfect compiler that hides all problems", that "letting the pointy bits stick the user but ensuring they can handle it" still beats "a compiler that badly hides the pointy bits, still lets them stick you, and doesn't give you any way to deal with it because the assumption that you couldn't be stuck was built in too deeply".
For the audience of this article, a good test is to compare a copy of Numerical Recipes in c versus the fortran edition, where the whole purpose of the book is to present numerical code to scientists. c (and c++) have to spend ages developing up notation and workarounds for the simplest matrix to correct c's deficiencies; the pointer manipulations (array pointers, function pointers, pointer pointers) make the code nigh-unreadable compared to the straightforward and understandable fortran.
Edit: I agree with your point with respect to interpreted languages, especially those with weak typing; I don't need to control where my number lives in memory, but I do need to control the bits of precision from the beginning.
Been there. Not pleasant.
Dynamic and weak are not the same thing.
Weak typing means you're allowed to break abstractions; C has weak typing, C++ is marginally less weak, and Python has strong typing for its built-in types.
You'd be surprised how much of it is actually fortran at the bottom. Lapack and FFTpack are two of the more important examples.
Lapack depends on a BLAS implementation for the primitive matrix and vector operations (the actual number crunching), and while the reference impl is in Fortran, the high-performance ATLAS implementation is written in C, and I believe Intel MKL is as well. These implementations parallelize the matrix and vector ops, leaving the single-threaded fortran code in more of a "controller" role.
There's also work being done to parallelize the LAPACK operations at a higher level than delegating to parallel BLAS, it's shown promise but isn't done yet, see the PLASMA package released by some oak ridge national labs people.
Now, if you're writing from scratch and if the Fortran compiler is capable of the right optimizations, then yeah, it's probably more worth it to use fortran. Especially if you can code directly to your problem domain. But I'm pretty sure ATLAS and MKL beat the standard compiled fortran, otherwise they wouldn't exist.
In short, just because the C compiler can't parallelize your code for you doesn't mean that you can't do that yourself. It's just a lot of work.
The point is that neither C nor the C compiler used to build ATLAS's output is what makes it fast. What makes it fast is essentially a different compiler which operates upstream of the C compiler.
Maybe it's wrong, I'm not knowledgeable about Fortran and certainly not horribly invested in this, go ahead and write a world-conquering BLAS library in Fortran if you want.
I'm not saying FORTRAN is great - clearly it has a bunch of problems which C mostly doesn't have, which is why people mostly use C instead. But this one single advantage (allowing the compiler to do optimizations on array work) is so important to some people that it will always be around.
(Also the all-caps spelling, FORTRAN, strongly hints that the link only talks about Fortran 77.)
my GOD what a breath of fresh air. Natural array expressions, operations slicing, sizing, etc. (talking about the core language not libraries) and incredible, incredible speed. Revolutionary, and makes me deeply regret those years I recited the "c is fast" mantra.
Mind you, the compiler that handles the optimizations is written in c. But you know - I don't need to know about that;in c, I always felt like I was half writing-the-compiler anyway. Thankfully, I'm not anymore.
Now the thing is, I tell people this and they look at me like I'm crazy ("fortran? no way!") This article... I love a little validation.
Libraries are very nice, but better to start with a suited base-language.
Edit: not to say that my years in that landscape were wasted; other fortran-only programmers look at me as crazy when I create the simplest "object" using the fortran-equivalent of struct; to them, life is nothing but wild unencapsulated matrices deserving to be free.
Should I happen to wander into a problem space that needs this stuff, my choice will be how many minutes to spend Googling for a decent free library, or whether to license a commercial one.
On the shoulders of giants...
And so, generations of game developers write matrix multiplication code. With quite nice performance results.
It'd be nice to see if some of that performance intensive code would benefit from being written in fortran. Anybody up for porting box2d as a small test case? ;)
That suggests that at least circa 2004, if aliasing were a serious problem for C compilers, restrict annotations were not the solution, which calls Chu-Carroll's claim into question. But there might be other explanations. Any thoughts?
[1] http://blog.regehr.org/archives/537
ETA: Just to clarify what the 2004 paper involved: the researcher took the SPEC code and ran it through a dynamic analysis tool that identified every single use of non-restricted pointers that did not alias any other in-scope pointer at the time. He then took all of those pointers and marked them as restricted in the source text. The result was a program with every possible pointer marked as restricted that could be so marked. That's way more than a human annotater will ever do. And all that got him a 1% performance improvement.
Also, I find it weird that the C99 committee, which was full of compiler vendors, got so excited about adding a fairly dangerous (and IMHO hard to use correctly) feature to the language without bothering to update their optimisers to make use of it. The only benefit that restricted pointers offer is better optimization; to add support for them without adding better optimization is a complete waste of everyone's time.
int *x = malloc(100), *y = malloc(100);
As of C99, of course, C has the "restrict" keyword which allows pointers to explicitly be declared to not alias, thus enabling all these optimizations in C, too.
Honestly, if you want balls-out performance, you probably need specialized hardware. In days of yore that meant you bought a vector box for your computer, or a Cray. These days you can just load up a PC with a bunch of high-end GPUs. A cow-orker of mine down the hall has a machine with six of them installed -- he's so giddy, it's kind of irritating :-)
void f(char * restrict p, char * restrict q); char * h() { static char s[10]; return s; } void g() { f(h(), h()); }
(Correctness of a program using restrict is, in general, not decidable.)
The tradeoff here is that while restrict can be used to allow for further aliasing, it is very easy to write code with undefined behavior as a result. Dennis Ritchie argued as much when he (successfully) kept "noalias", the precursor of "restrict", out of the C89 standard: http://www.lysator.liu.se/c/dmr-on-noalias.html (while "restrict" is not quite as dangerous as "noalias", it still has to be used with care).
As to program analysis, programming languages without pointer arithmetic have it a lot easier than languages with. The pair (array, index) holds more information than the address of array[index]. For example, it is trival to perform array bound checks if you have the former information, but very hard if you deal with arbitrary pointers. Pointer arithmetic loses information.
Fortran for the longest time(introduced in 90) didn't have pointers so there was no aliasing possible. With pointers in Fortran you have to specify what they may alias so the problem is much easier.(note: I have read about it but never actually worked in Fortran so I may be wrong.)
However the article had been valid if it were published before C99.
#pragma ivdep
Seems like pretty reasonable ways around the problem. Not to mention things like OpenMP.
assert(a+n < b || b+m < a);
I dare say this is more or less true of C, but following big improvements in the quality of C++ compilers (changes that happened well before 2006), C++ has proven itself as a language for high-performance scientific computing. Todd Veldhuizen provided a survey back in 1997 of the changing case in favour of C++ to accompany his Blitz C++ library: http://www.autistici.org/sens/inf/scientificcomputingcfortra...
Fortran still has considerable advantages, but it's been a long time since Fortran programmers could regard C++ as offering unserious performance.
I would also hesitate to say that C++ is lower level than Fortran. With a suitable coding style, C++ is a quite high-level language. In fact, it is precisely the abstractions that C++ offered (templates) that allow the optimisations to take place that have delivered these improvements in compiler performance. Was the author not aware that templates can be used in this way? The discussion of alias detection suggests so.
The high-level point is right, namely that abstractions make for safer languages and give compilers freedom to make optimisations that apparently more efficient, less safe languages cannot, and so deliver better performance. But it would have been a better article if it had not mentioned C++.
Another conclusion to draw is that benchmarks produced by people who are out to make a point are worthless.
One performance problem with Blitz was that the expression templates obfuscated the code enough that the compiler bailed on doing SIMD vectorization of the evaluation loops. That was fixed this year at least for the Intel compiler (gcc doesn't have pragmas to control vectorization), so now performance can even exceed Fortran for large-ish arrays.
I made some plots while fiddling with this if you are interested: http://governator.ucsc.edu/filer/blitzbench_r1845/blitzcomp....
EDIT: in his comments to another commenter, the author was saying this: "[The OCaml compiler] could do some dramatic code rewriting that made it possible to merge loops, and hoist some local constants out of the restructured merged loop." A good C programmer should be able to do all the above simply by instinct. The author was not good enough. I buy the argument that being really good at C/C++ is more difficult than at other languages, but this is not the same thing as arguing C is inefficient.
I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing
People otherwise rightfully challenge his conclusions.
There's a funny comment there about matlab: "MATLAB struck me as being the wrong tool for every problem."
The code to construct an LMS filter (http://en.wikipedia.org/wiki/Least_mean_squares_filter#LMS_a...) is effectively one line:
h = adaptfilt.filtxlms(L,muW,1,Hhat);I had to use Matlab for seven years in neuroscience, and it's a terrible language for everything other than matrix math, data plotting, and (if you cough up for the Parallel Computing Toolbox) easy parallelization.
I do, however, hope that Python will push out Matlab one day.
void f(array1, array2) { /* somehow guaranteed not to alias? */ }
void g() {
array my_array[50];
f(my_array, my_array);
}Short answer: they don't. What you wrote is an undefined behavior, just like dereferencing a null pointer in C. If the compiler can't tell statically, then it just assumes they're not aliased.
I'm basing this conclusion mainly on this statement from that piece on aliasing: Essentially, compilers are promised (by the standard and, therefore, by programmers who write code they claim to be standard-conforming) that if they cannot detect aliasing via static analysis of a single program unit's EQUIVALENCE and COMMON statements, no such aliasing exists. In such cases, compilers are free to assume that an assignment to one variable will not change the value of another variable, allowing it to avoid generating code to re-read the value of the other variable, to re-schedule reads and writes, and so on, to produce a faster executable
Fortran 77 doesn't allow recursion, and all arrays are fixed in size at compilation time. That means every array in the source code is allocated memory when the program starts; you can never allocate a new array during program run; either by allocating the memory dynamically, or by making a recursive call that has an array local. I don't believe there's a stack -- not the way C/C++ has a stack for locals and return values. So if we declare a main program and a subroutine, like so;
01 PROGRAM TEST1
02 REAL D(10)
03 REAL E(10)
04 CALL A(D,E)
05 CALL A(D,D)
06 END
07 SUBROUTINE A(F,G)
08 REAL F(*)
09 REAL G(*)
C 10 --- Do something with F and G
11 RETURN
12 END
So -- this limitation may explain the aliasing problem. A call which passes an array (line 04, line 05) always calls a particular array -- it's not just 'pass a pointer to an array' but 'pass a pointer to memory location 85349'.
So in
04 CALL A(D,E)
05 CALL A(D,D)
There are some notes on Fortram memory allocation and arrays here (http://www.ibiblio.org/pub/languages/fortran/ch2-4.html):
" When the array is declared in the 'outermost' procedure, the compiler allocates memory for it. When you pass the array with a CALL statement, the compiler actually passes the base-address of the same array to the called procedure. When the called procedure operates on the array it works on the same array - uses the same memory storage area, the array is not 'copied' to another memory area (But, it might be in some cases on some Fortran systems)."
Someone should inform the guys over at ffmpeg that the jig is up.
char x[100];
char* y = malloc(100*sizeof(char));
printf("Array: %ld\nPointer: %ld\n", sizeof(x), sizeof(y));Yes there is. `int a[10]` allocates 10 consecutive `int`s on the stack, and it's the only language construct to express that (with `alloca` but it's a builtin function).
void f(int len){
int array[len];
printf("sizeof len: %zu\n", sizeof(array));
}
On Windows the stack is one megabyte by default. We live in the future and we're still afraid of recursion without tail-call optimisation and arrays on the stack. Ridiculous.
So having a large stack will only consume virtual address space which we have plenty of (2^48 bytes in most x86_64's) but will not consume physical memory, which is a more limited resource.
I never heard of anyone suggesting we should use Fortfran for performance reasons, instead there was an ongoing movement to evolve the code, moving it to use the OpenFOAM solver that's written in C++.
The library is the real problem.
code.google.com/p/fridgescript - faster than C in some cases, only because it doesn't use the math library, but uses hardware without indirect calls and without caring for obscure edge cases.
I choose to write in C and Assembly, for example, and much of the code I write is provably as fast as possible on the targeted architecture. It is literally impossible that it would go faster if I wrote it in Fortran instead. All of these languages are just tools, and if you know your tool, you can do great things with it. The specifics of which tool you choose are often unimportant.
There are some syntactic niceties in fortran which make it more comfortable for people who don't want to think about certain low-level details. However, you cannot write software that runs as fast as possible without considering those details, so a programmer with that goal is forced to think about them no matter what tool he or she chooses.
Fortran does have a (slightly) more relaxed numerics model than standard C, which allows a compiler to make some optimizations that a C or C++ program would need to explicitly license. However, these optimizations are disallowed in standard C and C++ because they are unsafe. The fact that Fortran enables them does not make Fortran a better language for numerical computation (from my perspective as low-level library writer, they make it worse). Performance without correctness is absolutely meaningless.
Write software in the language that is comfortable for you. Use libraries written by experts for performance critical operations. Use a profiler to identify operations that are hotspots in your code. Don't complain about your (or someone else's) tools.
If you look at that loop, it can be parallelized or vectorized without any problem if and only if the array pointed to by x and the array pointed to by y are completely distinct with no overlap. But there's no way to write code in C or C++ that guarantees that.
double* doMath(double** y) {
double** x = allocateNew2DArray(20000, 20000);
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];
}
}
return x;
}
I don't think any C compilers actually do parallelize code like this, or at least they don't do much beyond using SIMD. But in principle they could.
Ah. In that case, I wonder how the author managed to get an infinite loop to complete in 0.8 seconds ;).
If you care about efficiency, you don't use pointers-to-pointers for rectangular matrices. You use 1D vectors and strides. For instance, this is how numerical linear algebra codes typically represent matrices. This approach also generalizes well to N-dimensional problems.
The pointers-to-pointers idiom is picked up by some people due to its use in Numerical Recipes. Of course, NR used it to make C look like Fortran, because they were comfortable with Fortran. Another NR artifact is the gyrations used to make C arrays appear to start at 1 rather than 0. Which is a hoot.
I agree with some comments above that the Fortran 90 matrix constructs are an improvement on C's capabilities.
This requires efforts but to be honest, there is currently no language that is a good fit for system programming and that is able to parallelize your code magically and automatically. Such a language would give a strong competitive advantage to programmers using it, as C did in the past over other languages, so would become mainstream soon or later, or its ideas would incarnate in some other "better C" language. If this is not happening IMHO there is something wrong in languages that currently are able to do more than C in this regard.
In programming ideas tend to take years to be accepted, but there is a very clear trend over decades: something that is really better (as in code that is faster, or simpler to write (very useful abstraction XYZ), or more easy to debug, or with higher quality libraries, or even much simpler to deploy (PHP I'm looking at you)) eventually becomes mainstream.
"C is Efficient" is largely true, but it's certainly not always true, and there are problem domains where it's seldom true. If you don't know that this is the case with any language then you're not qualified to be picking an implementation language anyway.
A 5minute run-time in Python might be acceptable if it takes you 1 hour to write it and are only going to use it once; whereas you may not even know how to program in OCaml even though it offers the best run-time.
C isn't an efficient language, C is just thin layer on top of assembly. You can write shit code in C, I know that from experience, but you can also write really fast code in C.
This is a pretty common fallacy. These days a C compiler does so much magic that calling it sugared assembly doesn't describe it accurately.
With a 1970's single pass compiler your argument may have been more true.
In the end, C has branching and memory access, and that's basically what our computers have too. The rest is details.
While there are ways to optimize machine code without extra debug information, no, what you've said is not true. It is not nearly as easy to optimize machine code as it is to optimize C.
http://scienceblogs.com/goodmath/2010/07/seed_conflicts_of_i...
Don't blame the author