Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The "C is Efficient" Language Fallacy (2006)

scienceblogs.com

Post reply on HN
Print view View original

91–100 of 133 posts

Re: The "C is Efficient" Language Fallacy (2006)

#91

Post by pjmlp »

jrockway wrote: post #16
exDM69 wrote: post #11

Earlier quoted context omitted.

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…

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.

If len is big enough your f() call will crash with a stack overflow.

Re: The "C is Efficient" Language Fallacy (2006)

#92

Post by jbooth »

ArbitraryLimits wrote: post #87
jbooth wrote: post #83

Earlier quoted context omitted.

Well ok, but someone sufficiently skilled could still hand-write code in C, using pthreads and SSE instructions, that will beat the fortran code every single time, because those constructs just aren't available in fortran and it's hard to claim that the compiler's always going to be better (as a Java guy most of the time, trust me, I'd love to believe it).

Why would pthreads and SSE instructions not be available in Fortran? Pthreads are just another library which Fortran programs can link to with no problem, and a modern Fortran compiler is perfectly capable of handling inline assembler.

I saw this link claiming that it was difficult/impossible to use threads in fortran due to surprisingly global variables: http://math.arizona.edu/~swig/documentation/pthreads/#fortra...

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.

Re: The "C is Efficient" Language Fallacy (2006)

#93

Post by cperciva »

attractivechaos wrote: post #89
chengl wrote: post #76

Earlier quoted context omitted.

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_prob... I agree that the author should post the code he used to benchmark different languages. Ot…

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.

Indeed, finding all LCSs requires exponential time: The strings "abcdefghijkl..." and "badcfehgjilk..." have the 2^(N/2) LCSs "[ab][cd][ef][gh][ij][kl]..." and no algorithm can ever run faster than the amount of time it takes to print its output.

Re: The "C is Efficient" Language Fallacy (2006)

#94

Post by ArbitraryLimits »

jbooth wrote: post #92
ArbitraryLimits wrote: post #87

Earlier quoted context omitted.

Why would pthreads and SSE instructions not be available in Fortran? Pthreads are just another library which Fortran programs can link to with no problem, and a modern Fortran compiler is perfectly capable of handling inline assembler.

I saw this link claiming that it was difficult/impossible to use threads in fortran due to surprisingly global variables: http://math.arizona.edu/~swig/documentation/pthreads/#fortra... 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.

FORTRAN's problems with rentrancy don't mean that FORTRAN programs can't be multi-threaded, it just means that each function has to be run from the same thread every time it's called.

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.

Re: The "C is Efficient" Language Fallacy (2006)

#95

Post by [deleted] »

ArbitraryLimits wrote: post #94
jbooth wrote: post #92

Earlier quoted context omitted.

I saw this link claiming that it was difficult/impossible to use threads in fortran due to surprisingly global variables: http://math.arizona.edu/~swig/documentation/pthreads/#fortra... 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.

FORTRAN's problems with rentrancy don't mean that FORTRAN programs can't be multi-threaded, it just means that each function has to be run from the same thread every time it's called. 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 im…

[deleted]

Re: The "C is Efficient" Language Fallacy (2006)

#96

Post by mturmon »

yummyfajitas wrote: post #46

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…

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.

Re: The "C is Efficient" Language Fallacy (2006)

#97

Post by dwc »

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.

Re: The "C is Efficient" Language Fallacy (2006)

#98

Post by microtonal »

wvenable wrote: post #84
microtonal wrote: post #58

Earlier quoted context omitted.

Simple in the sense that it is a small language. There are not a lot of constructs, abstractions, etc. C lets you allocate blocks of memory, and perform operations on those blocks of memory. That's mostly it. In my experience, this very much maps to the problem domain (number crunching). If you want to do performant number crunching with most other languages, you have to not only grasp the language, but also the unde…

> C lets you allocate blocks of memory It doesn't even let you do that -- those things are external library calls.

The C99 standard specifies that the stdlib.h header should be provided with amongst other things malloc()/free(). So, C99 provides heap allocation functions.

Also, some people will argue that 'asking' an array on the stack is also allocation ;).

Re: The "C is Efficient" Language Fallacy (2006)

#99

Post by KingMob »

wickedchicken wrote: post #32
Peaker wrote: post #22

Earlier quoted context omitted.

Matlab may be a pretty bad language, but it gives access to a huge (and growing) body of existing code.

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=... 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);

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.

Re: The "C is Efficient" Language Fallacy (2006)

#100

Post by haberman »

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);
  }
Post reply on HN