3 ms·

I'm not going to say it's trivial, but I will definitely claim that beating C is very doable, and will happen in less than ten years, if I have any say in the m

by zwegner 13y ago

I'm not going to say it's trivial, but I will definitely claim that beating C is very doable, and will happen in less than ten years, if I have any say in the matter. Obviously this claim should be taken with a grain of salt, but in ten years we'll see who was right :)

stephencanon 13y ago
Beating C today or beating C as it will be then? If the latter, what do you believe makes functional languages different such that C compilers (with large-budgeted industry teams behind them) won't be able to take advantage of the same techniques?
- srean 13y ago
  I will not be surprised if it beats C as it will be then, by generating C code itself, but C code that no human would write by hand. It has been done before in programming history (not just C, fortran has been beaten as well http://dl.acm.org/citation.cfm?id=200989 http://dl.acm.org/citation.cfm?id=200989 http://link.springer.com/chapter/10.1007/978-3-642-19014-8_11 http://link.springer.com/chapter/10.1007/978-3-642-19014-8_1... http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.640&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150... although the prior art focuses on Lisp I think Haskell and ML like languages are better equipped for this). Imperative code is a lot harder to reason about, and low level code is a lot harder to write if one cares about correctness and performance simultaneously. Specialized functional languages has a history of beating C implementations. It could be faster still if one removes the constraint that one has to generate C code, for example coroutines and proper tail calls become easier to implement. The bottomline is that correctness is easier to achieve with functional, and performance with imperative. So we would need both and they meet in a compiler. Take the example of Stalin and StalinGrad, they are Lisps. Their compile times are epic, but once done they have a history of generating faster code than C for specific applications (a specific example where it will excel is multidimensional numeric integration where the function to be integrated is passed as an input). The main reason why they would be able to generate faster code is that they are smarter about inlining. The reason they are smarter about inlining is that programmers intent is better preserved when encoded in a higher level language. Can a programmer not write the same code in C by hand ? Sure they can, but it will take longer and would be more error prone and likely to be costlier to produce, unless one takes the help of these higher level abstractions primitives, but then you aren't really writing in C anymore. Can the C compiler not be equally smart ? possibly, but it will be a lot harder to make a C compiler smart than a functional language compiler smart. Functional languages leave a lot of room for the compiler to do its thing, C while not as bad as Java still over-specifies how exactly something needs to be computed (my way or the highway). Add the fact that when code is written in a higher level, but optimization friendly language one can enjoy the benefits of compiler techniques yet to come. It future-proofs the code to an extent and amortizes the effort that went into writing the compiler. Now of course one can use C++ template metaprogramming to do much of the inlining that Stalin does, but then again you are essentially using a functional programming paradigm. EDIT: HN easy on the downvote. You may not agree with stephencanon but there was nothing in his comment that deserves a downvote, seriously ! @stephencanon compensated to the best of my ability.
- zwegner 13y ago
  As it will be then. Two big advantages are referential transparency and memory aliasing. The sort of reordering of loops/memory/whatever like described on the Halide page is just the beginning of the kind of optimizations that are possible. Perhaps static analysis could ameliorate this to some extent, but it will take far more computational power, and will always be subject to the halting problem. There's also current problems with the C standard that could change in a new standard, or maybe optionally ignored in the compiler, so it depends on your definition of "C". Examples of this are struct member ordering being fixed, or lack of tail call optimization (at least guaranteed TCO), and perhaps you might include calling conventions in that. There's also the huge advantages you can get in programmer productivity. Metaprogramming, better type systems, better (and more) abstractions, automatic memory management, automatic parallelization, there's really tons of room for improvement in so many areas. And a lot of these provide lots of room for optimization, in the sense that they put more of the program semantics into the compiler's hands. Compilers will probably be "stupid" for a long time, but at the very least they are very accurate and very fast, so they can try out many possibilities and measure what works best. Chess is a good analog here--computers are far superior to humans these days, and they got there by just trying tons of permutations of simple algorithms and running lots of tests. Writing compilers turns out to be a similar problem, so moving away from C/C++ can have advantages at multiple levels (so meta!). It's still in a very nascent stage, but the language I've been working on should eventually be the manifestation of lots of these ideas: https://github.com/zwegner/mutagen https://github.com/zwegner/mutagen Most of the ideas are just in my head at this point, and still rather fuzzy, but there's some specifics in the README about possible future directions.
  - dchichkov 13y ago
    As far as I know there are efforts to bring such techniques into C/C++. For example, see GCC Graphite framework - http://gcc.gnu.org/wiki/Graphite http://gcc.gnu.org/wiki/Graphite . And meantime, in the real life, if you really need your code to run really really fast (like, if you are doing nanosecond level realtimish staff in finance; or working on real-time computer vision; or anything else that really really needs low level optimizations) if you want to be competitive, you just have to go down to plain C level. And while at it, also have good understanding of your cache/memory/processors/bus architecture, cache interference, costs of system calls, compiler behavior, CPU behavior (microcode level, i.e. cache coherence or memory sync algos) and so on. You can try to not to do it, and attempt to use Haskel or Ocaml, but the cost would be two orders of magnitude. For a real-timish function that you are concerned about, in a relatively well written C/C++ you can have 200ns ± 100ns. The same function in a well written Ocaml will give you 5us ± 200us, and the same in Haskel or Python will give 20us ± 200us (when giving these numbers/example, I assume that the code is written using best possible at the current state of the art data structures and algorithms; all the aforementioned issues are well understood by the developer and the code is written at a greater guru level ;))

by zwegner 13y ago

stephencanon 13y ago

Beating C today or beating C as it will be then? If the latter, what do you believe makes functional languages different such that C compilers (with large-budgeted industry teams behind them) won't be able to take advantage of the same techniques?

srean 13y ago
I will not be surprised if it beats C as it will be then, by generating C code itself, but C code that no human would write by hand. It has been done before in programming history (not just C, fortran has been beaten as well http://dl.acm.org/citation.cfm?id=200989 http://dl.acm.org/citation.cfm?id=200989 http://link.springer.com/chapter/10.1007/978-3-642-19014-8_11 http://link.springer.com/chapter/10.1007/978-3-642-19014-8_1... http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.640&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150... although the prior art focuses on Lisp I think Haskell and ML like languages are better equipped for this). Imperative code is a lot harder to reason about, and low level code is a lot harder to write if one cares about correctness and performance simultaneously. Specialized functional languages has a history of beating C implementations. It could be faster still if one removes the constraint that one has to generate C code, for example coroutines and proper tail calls become easier to implement. The bottomline is that correctness is easier to achieve with functional, and performance with imperative. So we would need both and they meet in a compiler. Take the example of Stalin and StalinGrad, they are Lisps. Their compile times are epic, but once done they have a history of generating faster code than C for specific applications (a specific example where it will excel is multidimensional numeric integration where the function to be integrated is passed as an input). The main reason why they would be able to generate faster code is that they are smarter about inlining. The reason they are smarter about inlining is that programmers intent is better preserved when encoded in a higher level language. Can a programmer not write the same code in C by hand ? Sure they can, but it will take longer and would be more error prone and likely to be costlier to produce, unless one takes the help of these higher level abstractions primitives, but then you aren't really writing in C anymore. Can the C compiler not be equally smart ? possibly, but it will be a lot harder to make a C compiler smart than a functional language compiler smart. Functional languages leave a lot of room for the compiler to do its thing, C while not as bad as Java still over-specifies how exactly something needs to be computed (my way or the highway). Add the fact that when code is written in a higher level, but optimization friendly language one can enjoy the benefits of compiler techniques yet to come. It future-proofs the code to an extent and amortizes the effort that went into writing the compiler. Now of course one can use C++ template metaprogramming to do much of the inlining that Stalin does, but then again you are essentially using a functional programming paradigm. EDIT: HN easy on the downvote. You may not agree with stephencanon but there was nothing in his comment that deserves a downvote, seriously ! @stephencanon compensated to the best of my ability.
zwegner 13y ago
As it will be then. Two big advantages are referential transparency and memory aliasing. The sort of reordering of loops/memory/whatever like described on the Halide page is just the beginning of the kind of optimizations that are possible. Perhaps static analysis could ameliorate this to some extent, but it will take far more computational power, and will always be subject to the halting problem. There's also current problems with the C standard that could change in a new standard, or maybe optionally ignored in the compiler, so it depends on your definition of "C". Examples of this are struct member ordering being fixed, or lack of tail call optimization (at least guaranteed TCO), and perhaps you might include calling conventions in that. There's also the huge advantages you can get in programmer productivity. Metaprogramming, better type systems, better (and more) abstractions, automatic memory management, automatic parallelization, there's really tons of room for improvement in so many areas. And a lot of these provide lots of room for optimization, in the sense that they put more of the program semantics into the compiler's hands. Compilers will probably be "stupid" for a long time, but at the very least they are very accurate and very fast, so they can try out many possibilities and measure what works best. Chess is a good analog here--computers are far superior to humans these days, and they got there by just trying tons of permutations of simple algorithms and running lots of tests. Writing compilers turns out to be a similar problem, so moving away from C/C++ can have advantages at multiple levels (so meta!). It's still in a very nascent stage, but the language I've been working on should eventually be the manifestation of lots of these ideas: https://github.com/zwegner/mutagen https://github.com/zwegner/mutagen Most of the ideas are just in my head at this point, and still rather fuzzy, but there's some specifics in the README about possible future directions.
- dchichkov 13y ago
  As far as I know there are efforts to bring such techniques into C/C++. For example, see GCC Graphite framework - http://gcc.gnu.org/wiki/Graphite http://gcc.gnu.org/wiki/Graphite . And meantime, in the real life, if you really need your code to run really really fast (like, if you are doing nanosecond level realtimish staff in finance; or working on real-time computer vision; or anything else that really really needs low level optimizations) if you want to be competitive, you just have to go down to plain C level. And while at it, also have good understanding of your cache/memory/processors/bus architecture, cache interference, costs of system calls, compiler behavior, CPU behavior (microcode level, i.e. cache coherence or memory sync algos) and so on. You can try to not to do it, and attempt to use Haskel or Ocaml, but the cost would be two orders of magnitude. For a real-timish function that you are concerned about, in a relatively well written C/C++ you can have 200ns ± 100ns. The same function in a well written Ocaml will give you 5us ± 200us, and the same in Haskel or Python will give 20us ± 200us (when giving these numbers/example, I assume that the code is written using best possible at the current state of the art data structures and algorithms; all the aforementioned issues are well understood by the developer and the code is written at a greater guru level ;))