When people say things "C is slower than C++" or "C is slower than Fortran" or "C is slower than Haskell" they actually mean "C offers less opportunities for the compiler and the standard library implementations to optimize many types of constructions in code, mainly because of loose typing rules and loose aliasing rules. When you set out to execute a task computationally complex enough, you have a great probability that a well-written program in C will be slower than a well-written program in FORTRAN, or Haskell, or C++".
Posted Apr 7, 2013 14:13 UTC (Sun) by HelloWorld (guest, #56129)
[Link]
What specific optimisation opportunities are you talking about? The ones everybody knows about are related to pointer aliasing, but the restrict keyword has been around for ages now.
Rust
Posted Apr 7, 2013 17:59 UTC (Sun) by mathstuf (subscriber, #69389)
[Link]
So, in Haskell, because pure functions are guaranteed to not modify data, the compiler is allowed to "fuse" operations[1] instead of doing exactly what a naïve reading of the code implies (strict order of expressions to be evaluated). This allows the simple map function to act like C++'s std::transform and optimize the specific calls being made (usually via inlining then optimization), but GHC can optimize the calls on a single data structure being operated on across function boundaries and fuse the map calls together ((map (f . g)) list rather than (map f . map g) list where map f and map g are in different functions). I don't think C++'s std::transform gets optimized like this (and even if it did, f and g can't necessarily be called gfgfgf rather than gggfff).
[1]This is how Eigen gets a lot of performance: by storing expressions instead of evaluating additions immediately, Eigen can merge loops together to get one loop with 3 operations in it rather than 3 loops with one operation each which wins on cache access and in hot loops, matters a lot.
Rust
Posted Apr 7, 2013 18:08 UTC (Sun) by hummassa (subscriber, #307)
[Link]
The restrict keyword, by itself, does not add some opportunities for loop unrollings where aliased things are used inside the loops.
The lack of defining pure functions, without side-effects, also elide some opportunities for repeated code removal.
Rust
Posted Apr 7, 2013 18:11 UTC (Sun) by mathstuf (subscriber, #69389)
[Link]
GCC does have a pure attribute, but it's not verified that you're using it properly and no one uses it anyways…
Rust
Posted Apr 8, 2013 8:03 UTC (Mon) by nix (subscriber, #2304)
[Link]
It does get used for functions often used in very tight inner loops. Just looking at glibc, strcmp() is declared pure, for example, as are many related functions.
Rust
Posted Apr 7, 2013 21:50 UTC (Sun) by HelloWorld (guest, #56129)
[Link]
The restrict keyword, by itself, does not add some opportunities for loop unrollings where aliased things are used inside the loops.
I don't understand that, can you give an example?
The lack of defining pure functions, without side-effects, also elide some opportunities for repeated code removal.
Modern optimising compilers try to figure out whether a function is pure and optimise accordingly. Example:
#include <stdio.h>
int sq(int i) {
return i*i;
}
int main(int argc, char **argv) {
int i = strtol(argv[1], 0, 0);
printf("%d\n", sq(i) * sq(i));
return 0;
}
Compiled with gcc -O3 -fno-inline-small-functions -S -masm=intel (gcc 4.7.2) this yields
So gcc sees that sq is a pure function and only calls it once, even though it's called twice in the source code. Granted, this isn't quite the same as in Fortran as the compiler needs to be able to see the definition of the relevant function for this to work. But due to link-time optimisation this isn't as big a limitation as it used to be. I'm not convinced the Fortran way offers significant benefits in the real world.
