10 ms·

The "C is Efficient" Language Fallacy (2006)

173 points by m_for_monkey 15y ago

unwind 15y ago
This is old (2006), and seems to base its argument around the problems with unrestricted pointers in C, that cause aliasing. 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.
- buff-a 15y ago
  And then there are SIMD compiler intrinsics. Not technically part of the C standard, but if you want them, C/C++ is where you find'em. Failing that there's inline assembly.
  - kabdib 15y ago
    Ding. It's amazing what you can do with a decent set of vector operations. 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 :-)
    - aaronblohowiak 15y ago
      if you use the Accelerate Framework on OSX or iOS, you have a very easy-to-use interface to vector ops (pass in pointers to your array..)
- m_for_monkey 15y ago
  At first I didn't include the date in the title, because I don't think it matters, the author's position seems even stronger now with many popular alternative languages, fast VMs and effective JIT compilers. Anyway, C99 was, of course, already 6-7 years old in 2006.
  - exDM69 15y ago
    And restricted pointers were probably available through compiler-specific language extensions way before that. You can still use them if you have legacy code that won't compile with c99.
- AlisdairO 15y ago
  Thank you. I see some variant of this argument somewhere on the web every few months, and it makes me want to bang my head on the table.
  - wickedchicken 15y ago
    Yeah, but you have to manually do that. Maybe I'm a purist, but I hate manual features that the compiler should just 'figure out.' At best it's an unneeded annoyance, at worst you can actively slow your program down or even cause it to be incorrect. Aliasing can be tricky even to experienced programmers, and it's nicer to just have a compiler figure it out for you. It will probably do a better job anyway.
    - kstenerud 15y ago
      While that would be nice, it's unfortunately not the reality. The computer falls into failed optimization traps all the time. The only difference is that with a human, you can detect it with a profiler and correct the problem by reordering a few things. With automatic optimization, you can't.
    - AlisdairO 15y ago
      I really don't mind seeing people say "it's easier to do this and make it run fast in another language" - that's a completely fair argument. It just really annoys me when I see "C can't do this", when it can (and has been able to do so for a long time). It makes the author appear completely ignorant.
- rbehrends 15y ago
  The problem with the C99 restrict is that its correct use is not (and cannot) be enforced by the compiler. For example, the following is legal C (in the sense that no compiler that I know of will issue as much as a warning): 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 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).
  - jmilloy 15y ago
    I don't know the first thing about FORTRAN. How does it enforce this?
    - rbehrends 15y ago
      This is independent of what FORTRAN does. The problem with the "restrict" keyword in C99 is that introducing it can make otherwise correct code incorrect and the compiler can't tell you. 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.
    - stonemetal 15y ago
      In C restrict says in this function assume pointers don't alias. Which may or may not be true. This gives the library author a hard choice to make: limit usefulness or performance. 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.)
- sharpneli 15y ago
  Exactly. The whole article seems to based on the writers ignorance about "restrict" keyword. However the article had been valid if it were published before C99.
- CountHackulus 15y ago
  In addition to that, if you're using the Intel compiler, then you can say #pragma ivdep Which tells the compiler that the loop you're writing doesn't have any vector dependencies. Or -fno-fnalias to say that none of the arguments you're passing to a function are aliased. Seems like pretty reasonable ways around the problem. Not to mention things like OpenMP.
  - gillianseed 15y ago
    iirc the GCC equivalent of ICC's '-fno-fnalias' is '-fargument-noalias'. A pragma would be nice though.
  - tlb 15y ago
    Pragmas suck. What I want is to explicitly assert the condition: assert(a+n < b || b+m < a); (saying that a[0..n] and b[0..m] don't alias) and have the compiler generate code that first tests the condition and generates optimized code given the assumption.
gizzlon 15y ago
For me, the blinking and moving ads completely invalidate this site..
- z0r 15y ago
  Because I've read this blog before, I can point you to this: http://scienceblogs.com/goodmath/2010/07/seed_conflicts_of_interest_and.php http://scienceblogs.com/goodmath/2010/07/seed_conflicts_of_i... Don't blame the author
  - stonemetal 15y ago
    Given that you might like his new site better. http://scientopia.org/blogs/goodmath/ http://scientopia.org/blogs/goodmath/
- ww520 15y ago
  I didn't notice them. Was it because AdBlocker?
emillon 15y ago
> In C and C++, there's no such thing as an array 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).
- exDM69 15y ago
  The OP wants to point out that C hasn't got first class arrays the same way that Fortran does. The C kind of arrays get passed to and from functions using naked pointers and that makes lots of compiler optimizations more difficult because of aliasing issues while a Fortran compiler knows that two arrays cannot alias (use overlapping memory areas). By adding a "restricted" declaration to your pointer types in function signatures, the compiler assumes no aliasing occurs and goes on with the optimizations. It's the coders' responsibility to make sure no aliasing happens, but if it does, all hell can break loose.
  - jrockway 15y ago
    Sort of true. In C99, you can: void f(int len){ int array[len]; printf("sizeof len: %zu\n", sizeof(array)); } Yes, I was weirded out when I saw this for the first time. But C does in fact have arrays; they're just not very good arrays.
    - pjmlp 15y ago
      If len is big enough your f() call will crash with a stack overflow.
      - repsilat 15y ago
        I don't understand why stacks are still so small. On nice operating systems memory is only needed when it's touched, not when it's asked for, so making the stack large doesn't cost anything unless you need a large stack. On 64-bit systems you could make the stack a billion gigabytes and still have 95% of your process' virtual address space available for the heap. 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.
cks 15y ago
I was actually under the impression that Fortran was used simply because the experts (in this case in fluid dynamics) was familiar with Fortran. It was the language they learned and used while back at the university. At least this is the impression I got from working in the field. 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++.
- jmaygarden 15y ago
  Matrix operations can be faster in FORTRAN than C because of differences in the way arrays are defined/implemented in each language.
  - stephencanon 15y ago
    This is just totally false. You can lay out your C arrays in exactly the same way that Fortran does, if you choose to. Or you can do something else, if that will give better performance. Tools are just tools; they don't determine what you can do with them. (I write matrix operations for a living, generally in C or Assembly; much of what I write is provably as fast as possible on the target hardware, so it could not possibly be faster if written in Fortran).
nickolai 15y ago
Umm, yes C/C++ will not parallelize your code for you, whereas Language XYZ will. Im not sure how this is an argument against C/C++ being effective. C/C++ will not parallelize your code by design. It's was never meant to. I'd never blame my stick-shift car for not changing gears by itself - thats the first reason I didnt buy an automatic in the first place! 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.
- jrockway 15y ago
  You're missing the point. The target demographic for this article is someone who is not a computer scientist. He's someone who doesn't have time to deal with thread libraries and low-level matrix operations. He just needs to crunch his data quickly so that he can publish his valuable research. This person reads the same blog articles that computer scientists do, and comes to the conclusion that "I should learn C++ for my number crunching". That's simply not the case; you can use C++ to get good performance, but the amount of knowledge you need to acquire to do so is an entire field. You aren't going to be the world's best human genome researcher and C++ programmer; the time spent learning C++ could have been used to do research. 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.
jensnockert 15y ago
While a lot of Scientific computing is done in FORTRAN, much of the lower-level `plumbing' is written in assembly, C or C++. 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.
- exDM69 15y ago
  > C isn't an efficient language, C is just thin layer on top of assembly. 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.
  - jrockway 15y ago
    Yes, but it would be just as easy to write an "assembly compiler" that did the same optimizations on your program text. C provides a layer above the machine that acts as we imagine a machine to work; the compiler adjusts our expectation to reality. In the end, C has branching and memory access, and that's basically what our computers have too. The rest is details.
    - adgar 15y ago
      > Yes, but it would be just as easy to write an "assembly compiler" that did the same optimizations on your program text. 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.
zvrba 15y ago
C and C++ are efficient for general-purpose programming, if you know how to use them. C is here to stay because it is lingua franca of the computing world: OS APIs are defined in terms of C functions, and I know of no libraries in wide-spread use that do not offer a C or C++ interface. 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."
- Peaker 15y ago
  Matlab may be a pretty bad language, but it gives access to a huge (and growing) body of existing code.
  - wickedchicken 15y ago
    If you're an engineer (like an engineer engineer, not a software engineer) 90% of the time matlab has some module built-in or for sale that simply solves the problem you have. For example: http://www.mathworks.de/products/dsp-system/demos.html?file=/products/demos/shipping/dsp/adaptfxlmsdemo.html http://www.mathworks.de/products/dsp-system/demos.html?file=... The code to construct an LMS filter (http://en.wikipedia.org/wiki/Least_mean_squares_filter#LMS_algorithm_summary http://en.wikipedia.org/wiki/Least_mean_squares_filter#LMS_a...) is effectively one line: h = adaptfilt.filtxlms(L,muW,1,Hhat);
    - KingMob 15y ago
      You've hit the nail on the head. This is exactly why Matlab is so pervasive in science. Not because it's actually good, but because it has so many handy libraries. The Mathworks is the Microsoft of science. 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.
      - rcfox 15y ago
        Somewhat off-topic: Have you heard of the Neural Engineering Framework? http://ctn.uwaterloo.ca/~cnrglab/?q=node/10 http://ctn.uwaterloo.ca/~cnrglab/?q=node/10 It's got a Python (well, Jython) scripting interface and can also interact with Matlab.
jheriko 15y ago
Okay, so there are reasons why C is /difficult/ to make very efficient for numerical computations. Aliasing is not one of them since C99 for a sufficiently knowledgable programmer thanks to the restrict keyword. 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.
chalst 15y ago
C and C++ suck rocks as languages for numerical computing. They are not the fastest, not by a longshot. In fact, the fundamental design of them makes it pretty much impossible to make really good, efficient code in C/C++. 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/scientificcomputingcfortran.pdf 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.
- lutorm 15y ago
  I was going to post something similar, with one addition: 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.html http://governator.ucsc.edu/filer/blitzbench_r1845/blitzcomp....
MichaelSalib 15y ago
Putting aside his general point C efficiency, I'm curious about his specific claim that Fortran compilers outperform C specifically because aliasing conceals optimization opportunities. John Reghr points [1] to a really interesting paper from 2004 that used a special analysis tool to mark every single pointer as restrict as it safely could in the SPEC benchmark. The result was a 1% performance improvement. 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 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.
- lukesandberg 15y ago
  Well maybe the reason performance improved only slightly is because not a lot of effort has gone into optimizing situations involving restrict pointers because it is so rare. If it is common in fortran it would make sense that a lot of effort has gone into special optimizations for that case, the same effort would not have been spent in c compilers because it is so rare.
  - MichaelSalib 15y ago
    That might be true, but if so, then everyone below who is claiming 'ZOMG! The article is totally wrong because C99 added restricted pointers!' is wrong. 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.
akg 15y ago
Every language has it's pitfalls. There isn't one single greatest language for everything. Within an application domain one needs to consider the tradeoff between machine-time and human development-time and determine what the best tool for the job is. 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.
jpdoctor 15y ago
> Modern architectures have reached the point where people can't code effectively in assembler anymore Someone should inform the guys over at ffmpeg that the jig is up.
- ternaryoperator 15y ago
  The statement is overbroad but not wholly incorrect. The biggest challenge to writing good (I don't know about "effective") assembly language is indeed the complexity of processors and architectures which can greatly magnify the effects of imperfect instruction choices or instruction sequencing. Obviously, some people can code effectively within those constraints, but it's a very much more specialized skill than it used to be.
- dextorious 15y ago
  Someone should inform you about generic statements and exceptions that prove a rule.
attractivechaos 15y ago
The longest common substring problem (LCS) can be solved in O(n^2) time using dynamic programming, not O(n^3) as is stated by the author of that post. If the author is unable to get the basic fact right, I can hardly trust his benchmark. Also, I question the author's skill in C/C++: in my experiences, C is consistently faster than Java for such tasks and C++ is nearly as fast as C as long as we use it the right way. If we look at the computer benchmark games, OCaml never beats C in terms of speed. I doubt the conclusion was much different in 2006. The author should released the source code; otherwise the benchmark tells us nothing but his incapability in programming. 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.
- pandaman 15y ago
  Judging by the difference in his numbers between C and C++ he did not have a slightest clue of what he was doing. I could imagine a slight difference is possible if you use default compiler switches due to exception handling and difference aliasing rules, not 3x as he has.
- chengl 15y ago
  What the author mentioned is longest common SUBSEQUENCE (not substring). And it's true that LCS requires O(n^2) if only need to find ONE LCS, using dynamic programming. But if it's required to find ALL longest common subsequence, it definitely requires higher order. http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob... I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing
  - attractivechaos 15y ago
    Can you find the proof that finding all LCS is O(n^3)? The author was talking about "the standard algorithm for computing LCS". I was assuming the standard algorithm finds one LCS only.
yummyfajitas 15y ago
The author's point is well taken, but his example leaves a lot to be desired: 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; } All you need to do for this example is replace the fortran coding style doMath(double* x , double* y) with the c coding style doMath(double* y). 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.
- nitrogen 15y ago
  I think something may have been lost when you typed your code. y is a pointer to double, so can't accept two array subscripts (if it were "double * * y" it could, or you could keep it as a one-dimensional array and use something like y[(i - 2) * 20000 + j + 1]), and i and j don't appear to be incremented anywhere.
  - yummyfajitas 15y ago
    Thanks, fixed the "double * * y". The i and j not being incremented is actually an error in the original blog post - I'll leave it here for consistency.
    - nitrogen 15y ago
      The i and j not being incremented is actually an error in the original blog post - I'll leave it here for consistency. Ah. In that case, I wonder how the author managed to get an infinite loop to complete in 0.8 seconds ;).
- mturmon 15y ago
  The use in the blog post of this example, with 2d arrays in C implemented through pointers-to-pointers, perplexed me. 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.
gsg 15y ago
No mention of representation issues? Memory is a big optimisation target these days, and a weak point of languages like Java and OCaml.
antirez 15y ago
C does not offer parallelization automatically, but you can pick a model, and a library, that is a good fit for turning your app into a parallel one. In this regard the following slides are interesting: http://swtch.com/~rsc/talks/threads07/ http://swtch.com/~rsc/talks/threads07/ The model proposed here may not be the right one for your application, so you can design your own (including multiple processes exchanging messages for instance, or the usual threading with locks, and so forth, it's up to you). 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.
Locke1689 15y ago
Arrays and pointers are most certainly not the same thing in C. Check yourself here: char x[100]; char* y = malloc(100*sizeof(char)); printf("Array: %ld\nPointer: %ld\n", sizeof(x), sizeof(y));
dwc 15y ago
The missing meta lessons: don't fall for overly simple characterizations, and don't be a language bigot. "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.
haberman 15y ago
As someone who doesn't know Fortran, how does Fortran solve the aliasing problem? Even if pointers and arrays are different, how can you ensure two arrays don't alias each other? The only way I can think of to do this is to always copy arrays when they are passed to functions, but this seems expensive. Otherwise I don't see how you can avoid this pseudocode: void f(array1, array2) { /* somehow guaranteed not to alias? */ } void g() { array my_array[50]; f(my_array, my_array); }
- scott_s 15y ago
  I thought about it, and I realized I didn't know. This is the best discussion I found: http://gcc.gnu.org/onlinedocs/gcc-3.4.6/g77/Aliasing-Assumed-To-Work.html http://gcc.gnu.org/onlinedocs/gcc-3.4.6/g77/Aliasing-Assumed... 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
  - haberman 15y ago
    Interesting, that sounds equivalent to just assuming "restrict" on all function parameters. If that's true, then C and Fortran aren't fundamentally that different in this respect except that C assumes things can be aliased by default and Fortran assumes they can't.
    - deleted 15y ago
      [deleted]
- stevecooperorg 15y ago
stephencanon 15y ago
I write high-performance numerical software for a living. There are a lot of baseless claims in this post. You can write high performance software in C, C++, Fortran, Assembly, or a whole host of other languages. There are syntactic reasons to prefer one or another, but you should not choose among them for performance reasons. 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.
growingconcern 15y ago
What a dolt. It's possible to tell the compiler that two pointers aren't aliases: the "restrict" keyword. Unless I'm mistaken that is really his sole argument against "pointer-based languages".
duaneb 15y ago
Well argued... until I realized that his argument hinges on C/++ compilers not being able to guarantee non-aliasing. That's why they introduced the `restrict` keyword in C99....
losethos 15y ago
God gave us free will. Some women really like dead babies. Kinda sick. Not liking C? Bad childhood? Homos -- everybody is a homo. God says... C:\LoseThos\www.losethos.com\text\BIBLE.TXT s of Heman: Bukkiah, Mattaniah, Uzziel, Shebuel, and Jerimoth, Hananiah, Hanani, Eliathah, Giddalti, and Romamtiezer, Joshbekashah, Mallothi, Hothir, and Mahazioth: 25:5 All these were the sons of Heman the king's seer in the words of God, to lift up the horn. And God gave to Heman fourteen sons and three daughters. 25:6 All these were under the hands of their father for song in the house of the LORD, with cymbals, psalteries, and harps, for the service of the house of God, according to the king's
losethos 15y ago
"God made free will. Some women love dead babies." My point was, "Now that I think about it, why do you care so much?" Why is it so many women support abortion? Why do people hate C and want to stop others? Live and let live. People who crusade against C. What if it's a conspiracy? God says... C:\LoseThos\www.losethos.com\text\QUIX.TXT r when it comes to the promise of the island we must count from the day your worship promised it to me to this present hour we are at now." "Well, how long is it, Sancho, since I promised it to you?" said Don Quixote. "If I remember rightly," said Sancho, "it must be over twenty years, three days more or less." Don Quixote gave himself a great slap on the forehead and began to laugh heartily, and said he, "Why, I have not been wandering, either in the Sierra Morena or in the whole course of

173 points by m_for_monkey 15y ago

This is old (2006), and seems to base its argument around the problems with unrestricted pointers in C, that cause aliasing. 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.

buff-a 15y ago
And then there are SIMD compiler intrinsics. Not technically part of the C standard, but if you want them, C/C++ is where you find'em. Failing that there's inline assembly.
- kabdib 15y ago
  Ding. It's amazing what you can do with a decent set of vector operations. 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 :-)
  - aaronblohowiak 15y ago
    if you use the Accelerate Framework on OSX or iOS, you have a very easy-to-use interface to vector ops (pass in pointers to your array..)
m_for_monkey 15y ago
At first I didn't include the date in the title, because I don't think it matters, the author's position seems even stronger now with many popular alternative languages, fast VMs and effective JIT compilers. Anyway, C99 was, of course, already 6-7 years old in 2006.
- exDM69 15y ago
  And restricted pointers were probably available through compiler-specific language extensions way before that. You can still use them if you have legacy code that won't compile with c99.
AlisdairO 15y ago
Thank you. I see some variant of this argument somewhere on the web every few months, and it makes me want to bang my head on the table.
- wickedchicken 15y ago
  Yeah, but you have to manually do that. Maybe I'm a purist, but I hate manual features that the compiler should just 'figure out.' At best it's an unneeded annoyance, at worst you can actively slow your program down or even cause it to be incorrect. Aliasing can be tricky even to experienced programmers, and it's nicer to just have a compiler figure it out for you. It will probably do a better job anyway.
  - kstenerud 15y ago
    While that would be nice, it's unfortunately not the reality. The computer falls into failed optimization traps all the time. The only difference is that with a human, you can detect it with a profiler and correct the problem by reordering a few things. With automatic optimization, you can't.
  - AlisdairO 15y ago
    I really don't mind seeing people say "it's easier to do this and make it run fast in another language" - that's a completely fair argument. It just really annoys me when I see "C can't do this", when it can (and has been able to do so for a long time). It makes the author appear completely ignorant.
rbehrends 15y ago
The problem with the C99 restrict is that its correct use is not (and cannot) be enforced by the compiler. For example, the following is legal C (in the sense that no compiler that I know of will issue as much as a warning): 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 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).
- jmilloy 15y ago
  I don't know the first thing about FORTRAN. How does it enforce this?
  - rbehrends 15y ago
    This is independent of what FORTRAN does. The problem with the "restrict" keyword in C99 is that introducing it can make otherwise correct code incorrect and the compiler can't tell you. 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.
  - stonemetal 15y ago
    In C restrict says in this function assume pointers don't alias. Which may or may not be true. This gives the library author a hard choice to make: limit usefulness or performance. 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.)
sharpneli 15y ago
Exactly. The whole article seems to based on the writers ignorance about "restrict" keyword. However the article had been valid if it were published before C99.
CountHackulus 15y ago
In addition to that, if you're using the Intel compiler, then you can say #pragma ivdep Which tells the compiler that the loop you're writing doesn't have any vector dependencies. Or -fno-fnalias to say that none of the arguments you're passing to a function are aliased. Seems like pretty reasonable ways around the problem. Not to mention things like OpenMP.
- gillianseed 15y ago
  iirc the GCC equivalent of ICC's '-fno-fnalias' is '-fargument-noalias'. A pragma would be nice though.
- tlb 15y ago
  Pragmas suck. What I want is to explicitly assert the condition: assert(a+n < b || b+m < a); (saying that a[0..n] and b[0..m] don't alias) and have the compiler generate code that first tests the condition and generates optimized code given the assumption.

gizzlon 15y ago

For me, the blinking and moving ads completely invalidate this site..

z0r 15y ago
Because I've read this blog before, I can point you to this: http://scienceblogs.com/goodmath/2010/07/seed_conflicts_of_interest_and.php http://scienceblogs.com/goodmath/2010/07/seed_conflicts_of_i... Don't blame the author
- stonemetal 15y ago
  Given that you might like his new site better. http://scientopia.org/blogs/goodmath/ http://scientopia.org/blogs/goodmath/
ww520 15y ago
I didn't notice them. Was it because AdBlocker?

emillon 15y ago

> In C and C++, there's no such thing as an array 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).

exDM69 15y ago
The OP wants to point out that C hasn't got first class arrays the same way that Fortran does. The C kind of arrays get passed to and from functions using naked pointers and that makes lots of compiler optimizations more difficult because of aliasing issues while a Fortran compiler knows that two arrays cannot alias (use overlapping memory areas). By adding a "restricted" declaration to your pointer types in function signatures, the compiler assumes no aliasing occurs and goes on with the optimizations. It's the coders' responsibility to make sure no aliasing happens, but if it does, all hell can break loose.
- jrockway 15y ago
  Sort of true. In C99, you can: void f(int len){ int array[len]; printf("sizeof len: %zu\n", sizeof(array)); } Yes, I was weirded out when I saw this for the first time. But C does in fact have arrays; they're just not very good arrays.
  - pjmlp 15y ago
    If len is big enough your f() call will crash with a stack overflow.
    - repsilat 15y ago
      I don't understand why stacks are still so small. On nice operating systems memory is only needed when it's touched, not when it's asked for, so making the stack large doesn't cost anything unless you need a large stack. On 64-bit systems you could make the stack a billion gigabytes and still have 95% of your process' virtual address space available for the heap. 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.

cks 15y ago

I was actually under the impression that Fortran was used simply because the experts (in this case in fluid dynamics) was familiar with Fortran. It was the language they learned and used while back at the university. At least this is the impression I got from working in the field. 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++.

jmaygarden 15y ago
Matrix operations can be faster in FORTRAN than C because of differences in the way arrays are defined/implemented in each language.
- stephencanon 15y ago
  This is just totally false. You can lay out your C arrays in exactly the same way that Fortran does, if you choose to. Or you can do something else, if that will give better performance. Tools are just tools; they don't determine what you can do with them. (I write matrix operations for a living, generally in C or Assembly; much of what I write is provably as fast as possible on the target hardware, so it could not possibly be faster if written in Fortran).

nickolai 15y ago

Umm, yes C/C++ will not parallelize your code for you, whereas Language XYZ will. Im not sure how this is an argument against C/C++ being effective. C/C++ will not parallelize your code by design. It's was never meant to. I'd never blame my stick-shift car for not changing gears by itself - thats the first reason I didnt buy an automatic in the first place! 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.

jrockway 15y ago
You're missing the point. The target demographic for this article is someone who is not a computer scientist. He's someone who doesn't have time to deal with thread libraries and low-level matrix operations. He just needs to crunch his data quickly so that he can publish his valuable research. This person reads the same blog articles that computer scientists do, and comes to the conclusion that "I should learn C++ for my number crunching". That's simply not the case; you can use C++ to get good performance, but the amount of knowledge you need to acquire to do so is an entire field. You aren't going to be the world's best human genome researcher and C++ programmer; the time spent learning C++ could have been used to do research. 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.

jensnockert 15y ago

While a lot of Scientific computing is done in FORTRAN, much of the lower-level `plumbing' is written in assembly, C or C++. 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.

exDM69 15y ago
> C isn't an efficient language, C is just thin layer on top of assembly. 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.
- jrockway 15y ago
  Yes, but it would be just as easy to write an "assembly compiler" that did the same optimizations on your program text. C provides a layer above the machine that acts as we imagine a machine to work; the compiler adjusts our expectation to reality. In the end, C has branching and memory access, and that's basically what our computers have too. The rest is details.
  - adgar 15y ago
    > Yes, but it would be just as easy to write an "assembly compiler" that did the same optimizations on your program text. 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.

zvrba 15y ago

C and C++ are efficient for general-purpose programming, if you know how to use them. C is here to stay because it is lingua franca of the computing world: OS APIs are defined in terms of C functions, and I know of no libraries in wide-spread use that do not offer a C or C++ interface. 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."

Peaker 15y ago
Matlab may be a pretty bad language, but it gives access to a huge (and growing) body of existing code.
- wickedchicken 15y ago
  If you're an engineer (like an engineer engineer, not a software engineer) 90% of the time matlab has some module built-in or for sale that simply solves the problem you have. For example: http://www.mathworks.de/products/dsp-system/demos.html?file=/products/demos/shipping/dsp/adaptfxlmsdemo.html http://www.mathworks.de/products/dsp-system/demos.html?file=... The code to construct an LMS filter (http://en.wikipedia.org/wiki/Least_mean_squares_filter#LMS_algorithm_summary http://en.wikipedia.org/wiki/Least_mean_squares_filter#LMS_a...) is effectively one line: h = adaptfilt.filtxlms(L,muW,1,Hhat);
  - KingMob 15y ago
    You've hit the nail on the head. This is exactly why Matlab is so pervasive in science. Not because it's actually good, but because it has so many handy libraries. The Mathworks is the Microsoft of science. 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.
    - rcfox 15y ago
      Somewhat off-topic: Have you heard of the Neural Engineering Framework? http://ctn.uwaterloo.ca/~cnrglab/?q=node/10 http://ctn.uwaterloo.ca/~cnrglab/?q=node/10 It's got a Python (well, Jython) scripting interface and can also interact with Matlab.

jheriko 15y ago

Okay, so there are reasons why C is /difficult/ to make very efficient for numerical computations. Aliasing is not one of them since C99 for a sufficiently knowledgable programmer thanks to the restrict keyword. 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.

chalst 15y ago

C and C++ suck rocks as languages for numerical computing. They are not the fastest, not by a longshot. In fact, the fundamental design of them makes it pretty much impossible to make really good, efficient code in C/C++. 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/scientificcomputingcfortran.pdf 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.

lutorm 15y ago
I was going to post something similar, with one addition: 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.html http://governator.ucsc.edu/filer/blitzbench_r1845/blitzcomp....

MichaelSalib 15y ago

Putting aside his general point C efficiency, I'm curious about his specific claim that Fortran compilers outperform C specifically because aliasing conceals optimization opportunities. John Reghr points [1] to a really interesting paper from 2004 that used a special analysis tool to mark every single pointer as restrict as it safely could in the SPEC benchmark. The result was a 1% performance improvement. 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 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.

lukesandberg 15y ago
Well maybe the reason performance improved only slightly is because not a lot of effort has gone into optimizing situations involving restrict pointers because it is so rare. If it is common in fortran it would make sense that a lot of effort has gone into special optimizations for that case, the same effort would not have been spent in c compilers because it is so rare.
- MichaelSalib 15y ago
  That might be true, but if so, then everyone below who is claiming 'ZOMG! The article is totally wrong because C99 added restricted pointers!' is wrong. 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.

akg 15y ago

Every language has it's pitfalls. There isn't one single greatest language for everything. Within an application domain one needs to consider the tradeoff between machine-time and human development-time and determine what the best tool for the job is. 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.

jpdoctor 15y ago

> Modern architectures have reached the point where people can't code effectively in assembler anymore Someone should inform the guys over at ffmpeg that the jig is up.

ternaryoperator 15y ago
The statement is overbroad but not wholly incorrect. The biggest challenge to writing good (I don't know about "effective") assembly language is indeed the complexity of processors and architectures which can greatly magnify the effects of imperfect instruction choices or instruction sequencing. Obviously, some people can code effectively within those constraints, but it's a very much more specialized skill than it used to be.
dextorious 15y ago
Someone should inform you about generic statements and exceptions that prove a rule.

attractivechaos 15y ago

The longest common substring problem (LCS) can be solved in O(n^2) time using dynamic programming, not O(n^3) as is stated by the author of that post. If the author is unable to get the basic fact right, I can hardly trust his benchmark. Also, I question the author's skill in C/C++: in my experiences, C is consistently faster than Java for such tasks and C++ is nearly as fast as C as long as we use it the right way. If we look at the computer benchmark games, OCaml never beats C in terms of speed. I doubt the conclusion was much different in 2006. The author should released the source code; otherwise the benchmark tells us nothing but his incapability in programming. 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.

pandaman 15y ago
Judging by the difference in his numbers between C and C++ he did not have a slightest clue of what he was doing. I could imagine a slight difference is possible if you use default compiler switches due to exception handling and difference aliasing rules, not 3x as he has.
chengl 15y ago
What the author mentioned is longest common SUBSEQUENCE (not substring). And it's true that LCS requires O(n^2) if only need to find ONE LCS, using dynamic programming. But if it's required to find ALL longest common subsequence, it definitely requires higher order. http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob... I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing
- attractivechaos 15y ago
  Can you find the proof that finding all LCS is O(n^3)? The author was talking about "the standard algorithm for computing LCS". I was assuming the standard algorithm finds one LCS only.

yummyfajitas 15y ago

The author's point is well taken, but his example leaves a lot to be desired: 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; } All you need to do for this example is replace the fortran coding style doMath(double* x , double* y) with the c coding style doMath(double* y). 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.

nitrogen 15y ago
I think something may have been lost when you typed your code. y is a pointer to double, so can't accept two array subscripts (if it were "double * * y" it could, or you could keep it as a one-dimensional array and use something like y[(i - 2) * 20000 + j + 1]), and i and j don't appear to be incremented anywhere.
- yummyfajitas 15y ago
  Thanks, fixed the "double * * y". The i and j not being incremented is actually an error in the original blog post - I'll leave it here for consistency.
  - nitrogen 15y ago
    The i and j not being incremented is actually an error in the original blog post - I'll leave it here for consistency. Ah. In that case, I wonder how the author managed to get an infinite loop to complete in 0.8 seconds ;).
mturmon 15y ago
The use in the blog post of this example, with 2d arrays in C implemented through pointers-to-pointers, perplexed me. 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.

gsg 15y ago

No mention of representation issues? Memory is a big optimisation target these days, and a weak point of languages like Java and OCaml.

antirez 15y ago

C does not offer parallelization automatically, but you can pick a model, and a library, that is a good fit for turning your app into a parallel one. In this regard the following slides are interesting: http://swtch.com/~rsc/talks/threads07/ http://swtch.com/~rsc/talks/threads07/ The model proposed here may not be the right one for your application, so you can design your own (including multiple processes exchanging messages for instance, or the usual threading with locks, and so forth, it's up to you). 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.

Locke1689 15y ago

Arrays and pointers are most certainly not the same thing in C. Check yourself here: char x[100]; char* y = malloc(100*sizeof(char)); printf("Array: %ld\nPointer: %ld\n", sizeof(x), sizeof(y));

dwc 15y ago

The missing meta lessons: don't fall for overly simple characterizations, and don't be a language bigot. "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.

haberman 15y ago

As someone who doesn't know Fortran, how does Fortran solve the aliasing problem? Even if pointers and arrays are different, how can you ensure two arrays don't alias each other? The only way I can think of to do this is to always copy arrays when they are passed to functions, but this seems expensive. Otherwise I don't see how you can avoid this pseudocode: void f(array1, array2) { /* somehow guaranteed not to alias? */ } void g() { array my_array[50]; f(my_array, my_array); }

scott_s 15y ago
I thought about it, and I realized I didn't know. This is the best discussion I found: http://gcc.gnu.org/onlinedocs/gcc-3.4.6/g77/Aliasing-Assumed-To-Work.html http://gcc.gnu.org/onlinedocs/gcc-3.4.6/g77/Aliasing-Assumed... 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
- haberman 15y ago
  Interesting, that sounds equivalent to just assuming "restrict" on all function parameters. If that's true, then C and Fortran aren't fundamentally that different in this respect except that C assumes things can be aliased by default and Fortran assumes they can't.
  - deleted 15y ago
    [deleted]
stevecooperorg 15y ago

stephencanon 15y ago

I write high-performance numerical software for a living. There are a lot of baseless claims in this post. You can write high performance software in C, C++, Fortran, Assembly, or a whole host of other languages. There are syntactic reasons to prefer one or another, but you should not choose among them for performance reasons. 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.

growingconcern 15y ago

What a dolt. It's possible to tell the compiler that two pointers aren't aliases: the "restrict" keyword. Unless I'm mistaken that is really his sole argument against "pointer-based languages".

duaneb 15y ago

Well argued... until I realized that his argument hinges on C/++ compilers not being able to guarantee non-aliasing. That's why they introduced the `restrict` keyword in C99....

losethos 15y ago

God gave us free will. Some women really like dead babies. Kinda sick. Not liking C? Bad childhood? Homos -- everybody is a homo. God says... C:\LoseThos\www.losethos.com\text\BIBLE.TXT s of Heman: Bukkiah, Mattaniah, Uzziel, Shebuel, and Jerimoth, Hananiah, Hanani, Eliathah, Giddalti, and Romamtiezer, Joshbekashah, Mallothi, Hothir, and Mahazioth: 25:5 All these were the sons of Heman the king's seer in the words of God, to lift up the horn. And God gave to Heman fourteen sons and three daughters. 25:6 All these were under the hands of their father for song in the house of the LORD, with cymbals, psalteries, and harps, for the service of the house of God, according to the king's

losethos 15y ago

"God made free will. Some women love dead babies." My point was, "Now that I think about it, why do you care so much?" Why is it so many women support abortion? Why do people hate C and want to stop others? Live and let live. People who crusade against C. What if it's a conspiracy? God says... C:\LoseThos\www.losethos.com\text\QUIX.TXT r when it comes to the promise of the island we must count from the day your worship promised it to me to this present hour we are at now." "Well, how long is it, Sancho, since I promised it to you?" said Don Quixote. "If I remember rightly," said Sancho, "it must be over twenty years, three days more or less." Don Quixote gave himself a great slap on the forehead and began to laugh heartily, and said he, "Why, I have not been wandering, either in the Sierra Morena or in the whole course of