6 ms·

That looks pretty sweet, thanks for the link. This is where I feel functional languages will have a huge advantage in coming years. As side effects are reified

by zwegner 13y ago

That looks pretty sweet, thanks for the link. This is where I feel functional languages will have a huge advantage in coming years. As side effects are reified and put in the compiler's control, they can be modified and optimized automatically. While TFA is interesting, and a pretty good overview of designing programs with the cache in mind, it just shows me how far we have to go in language design. I don't want to manually make all of these modifications, let alone carefully profile each permutation of all the possible choices. We have fast, dumb computers, let them do that work.

skybrian 13y ago
Sure, this is the myth of the sufficiently smart compiler [1]. The problem is that such compilers generate fast code until you hit an edge case and then suddenly they're slow. Today, JavaScript is the canonical example; you never know how fast code will run without benchmarking, and it changes with each browser release. Or take SQL for another extreme example, where performance depends on the index you hit and the query plan the database comes up with. To counter this, people invent things like the asm.js specification, which tells you exactly what you need to do to make JavaScript fast, and then we're programming in assembly again. (Or perhaps C++.) So there is still plenty of room for languages that aim for predictable performance. I believe this is where Go and Rust are headed. [1] http://prog21.dadgum.com/40.html http://prog21.dadgum.com/40.html
- srean 13y ago
  The problem is not so bad if the compilers explain themselves. I run g++ or gcc with --ftree-vectorize-verbose=3. So even if gcc wasnt able to vectorize a loop I get to see which one it failed on and why. This is very valuable and you can often tweak the code to fix the problem. It saves me the trouble of writing intrinsics by hand. A "sufficiently smart programmer" could do better, but they are rare too.
  - userbinator 13y ago
    I would also like better feedback from compilers, and not just in the form of messages. It seems that throughout most of history compilers have been traditionally "one-way", i.e. you give them source and they produce a binary. To assist with code generation, what they should really be doing is some sort of "decompiling" of their optimiser's output back into e.g. C, maybe even with comments, so you can get an idea of what high-level optimisations it performed and where.
    - srean 13y ago
      Just for the off hand chance that you are unaware of this, the option -fdump-tree-optimized on GCC and the other -fdump-tree.* options will do some of what you are asking for. GCC isnt hipster hot nowadays but it has quite a few nice things. For C++ templates I still prefer G++ error messages over Clang++'s. I find the former a lot more informative, but without Clang breathing down their neck I doubt if they would have improved their error messages.
      - userbinator 13y ago
        You can't actually compile the output of -fdump-tree-optimized, so it's close but not quite exactly what I had in mind.
- zurn 13y ago
  Actually the problem is that compilers have dropped the ball on optimizing data representation. They generally don't even try. Some faint glimpses of light can be seen, like compressed references in HotSpot or this Halide. Rust and Go have nothing planned in this area.
  - kibwen 13y ago
    Not entirely. In Rust, the runtime representation of enums (tagged unions) is left deliberately unspecified in order to allow for arbitrary optimizations depending on shape. For example, The Option type in Rust (a.k.a. the Maybe type in Haskell) is a tagged union defined like this: [1] enum Option<T> { None, Some(T) } Now say I use this like so: let foo = Some(6); The runtime represenation of `foo` will be as follows: struct FooRepresentation { discriminator: u8, value: int } ...where `discriminator` is the field that determines whether the value is `None` or `Some`, and in the latter case `value` will contain the associated data. But let's say I declare foo a bit differently, using a pointer to a value rather than a raw value: let foo = Some(~6); // the tilde denotes a unique pointer Now the runtime representation of `foo` is only a single pointer, and in order to determine if `foo` is `None` it just checks to see if the pointer is null. Rust is smart enough to perform this optimization on any tagged union with two variants where only one of the variants has associated data, and the type of that variant is a pointer. On the flipside, if you want to guarantee a specific data layout then you can use a struct, which have the same layout rules as structs in C. [1] https://github.com/mozilla/rust/blob/master/src/libstd/option.rs#L150 https://github.com/mozilla/rust/blob/master/src/libstd/optio...
  - kristianp 13y ago
    Not go or rust, but I'm curious, in ocaml or haskell, I imagine it is not easy to change data representation without refactorings, because of the widespread pattern matching? e.g. in ocaml: let (x,y) = point;;
    - emillon 13y ago
      That's one of the reasons why record types are recommended instead of tuples. They don't cost anything at runtime but make it harder to shoot yourself in the foot.
- ketralnis 13y ago
  > and then we're programming in assembly again. (Or perhaps C++.) Is that so bad? The reason we're in JS in the first place in those environments isn't because it's the best language for the job, it's because it's the only language that can be used in that environment. If you can have the best of both worlds, why not?
al2o3cr 13y ago
Ah yes, the functionalist dream: "Given a sufficiently-advanced compiler, executing arbitrary code with ideal performance is trivial". Sadly, such a compiler has been "about ten years away" since the Lisp Machine days...
- modeless 13y ago
  That's what I like about Halide: it doesn't rely on a sufficiently-advanced compiler. The optimizations are specified explicitly, with full programmer control. The difference is in Halide the important optimization decisions (locality, parallelism, vectorization) are specified separately from the algorithm. It's usually impossible to express an algorithm without implicitly or explicitly specifying those things.
- reitzensteinm 13y ago
  This is both a straw man (OP asked for limited help, not omnipotence), and predicting the future by drawing a line from the past. Functional compilers that outperform hand tuned C++ on many core machines may be possible, but very hard. Just because everyone has previously underestimated the difficulty does not mean it's an idea worthy of derision. I think it's much more likely that it's perpetually ten years away, until one day it's not (like the current, possibly temporary end to Moore's Law). Watching Simon Peyton Jones' talk on data parallel Haskell, I'd not make a bet against high performance Haskell's eventual success, especially as core counts continue to climb, and NUMA gets more NU. http://www.youtube.com/watch?v=NWSZ4c9yqW8 http://www.youtube.com/watch?v=NWSZ4c9yqW8
  - SolarNet 13y ago
    We're already there [1] for vectorized code (Haskell vs. Hand written C). Note how they compare naive haskell solutions with their vector library vs. heavily optimized C code and using finely tuned libraries. And they are competitive, actually beating the finely tuned library in non-toy examples while still using naive haskell. [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.278.7377&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.278...
- 13y ago

by zwegner 13y ago

skybrian 13y ago

Sure, this is the myth of the sufficiently smart compiler [1]. The problem is that such compilers generate fast code until you hit an edge case and then suddenly they're slow. Today, JavaScript is the canonical example; you never know how fast code will run without benchmarking, and it changes with each browser release. Or take SQL for another extreme example, where performance depends on the index you hit and the query plan the database comes up with. To counter this, people invent things like the asm.js specification, which tells you exactly what you need to do to make JavaScript fast, and then we're programming in assembly again. (Or perhaps C++.) So there is still plenty of room for languages that aim for predictable performance. I believe this is where Go and Rust are headed. [1] http://prog21.dadgum.com/40.html http://prog21.dadgum.com/40.html

srean 13y ago
The problem is not so bad if the compilers explain themselves. I run g++ or gcc with --ftree-vectorize-verbose=3. So even if gcc wasnt able to vectorize a loop I get to see which one it failed on and why. This is very valuable and you can often tweak the code to fix the problem. It saves me the trouble of writing intrinsics by hand. A "sufficiently smart programmer" could do better, but they are rare too.
- userbinator 13y ago
  I would also like better feedback from compilers, and not just in the form of messages. It seems that throughout most of history compilers have been traditionally "one-way", i.e. you give them source and they produce a binary. To assist with code generation, what they should really be doing is some sort of "decompiling" of their optimiser's output back into e.g. C, maybe even with comments, so you can get an idea of what high-level optimisations it performed and where.
  - srean 13y ago
    Just for the off hand chance that you are unaware of this, the option -fdump-tree-optimized on GCC and the other -fdump-tree.* options will do some of what you are asking for. GCC isnt hipster hot nowadays but it has quite a few nice things. For C++ templates I still prefer G++ error messages over Clang++'s. I find the former a lot more informative, but without Clang breathing down their neck I doubt if they would have improved their error messages.
    - userbinator 13y ago
      You can't actually compile the output of -fdump-tree-optimized, so it's close but not quite exactly what I had in mind.
zurn 13y ago
Actually the problem is that compilers have dropped the ball on optimizing data representation. They generally don't even try. Some faint glimpses of light can be seen, like compressed references in HotSpot or this Halide. Rust and Go have nothing planned in this area.
- kibwen 13y ago
  Not entirely. In Rust, the runtime representation of enums (tagged unions) is left deliberately unspecified in order to allow for arbitrary optimizations depending on shape. For example, The Option type in Rust (a.k.a. the Maybe type in Haskell) is a tagged union defined like this: [1] enum Option<T> { None, Some(T) } Now say I use this like so: let foo = Some(6); The runtime represenation of `foo` will be as follows: struct FooRepresentation { discriminator: u8, value: int } ...where `discriminator` is the field that determines whether the value is `None` or `Some`, and in the latter case `value` will contain the associated data. But let's say I declare foo a bit differently, using a pointer to a value rather than a raw value: let foo = Some(~6); // the tilde denotes a unique pointer Now the runtime representation of `foo` is only a single pointer, and in order to determine if `foo` is `None` it just checks to see if the pointer is null. Rust is smart enough to perform this optimization on any tagged union with two variants where only one of the variants has associated data, and the type of that variant is a pointer. On the flipside, if you want to guarantee a specific data layout then you can use a struct, which have the same layout rules as structs in C. [1] https://github.com/mozilla/rust/blob/master/src/libstd/option.rs#L150 https://github.com/mozilla/rust/blob/master/src/libstd/optio...
- kristianp 13y ago
  Not go or rust, but I'm curious, in ocaml or haskell, I imagine it is not easy to change data representation without refactorings, because of the widespread pattern matching? e.g. in ocaml: let (x,y) = point;;
  - emillon 13y ago
    That's one of the reasons why record types are recommended instead of tuples. They don't cost anything at runtime but make it harder to shoot yourself in the foot.
ketralnis 13y ago
> and then we're programming in assembly again. (Or perhaps C++.) Is that so bad? The reason we're in JS in the first place in those environments isn't because it's the best language for the job, it's because it's the only language that can be used in that environment. If you can have the best of both worlds, why not?

al2o3cr 13y ago

Ah yes, the functionalist dream: "Given a sufficiently-advanced compiler, executing arbitrary code with ideal performance is trivial". Sadly, such a compiler has been "about ten years away" since the Lisp Machine days...

modeless 13y ago
That's what I like about Halide: it doesn't rely on a sufficiently-advanced compiler. The optimizations are specified explicitly, with full programmer control. The difference is in Halide the important optimization decisions (locality, parallelism, vectorization) are specified separately from the algorithm. It's usually impossible to express an algorithm without implicitly or explicitly specifying those things.
reitzensteinm 13y ago
This is both a straw man (OP asked for limited help, not omnipotence), and predicting the future by drawing a line from the past. Functional compilers that outperform hand tuned C++ on many core machines may be possible, but very hard. Just because everyone has previously underestimated the difficulty does not mean it's an idea worthy of derision. I think it's much more likely that it's perpetually ten years away, until one day it's not (like the current, possibly temporary end to Moore's Law). Watching Simon Peyton Jones' talk on data parallel Haskell, I'd not make a bet against high performance Haskell's eventual success, especially as core counts continue to climb, and NUMA gets more NU. http://www.youtube.com/watch?v=NWSZ4c9yqW8 http://www.youtube.com/watch?v=NWSZ4c9yqW8
- SolarNet 13y ago
  We're already there [1] for vectorized code (Haskell vs. Hand written C). Note how they compare naive haskell solutions with their vector library vs. heavily optimized C code and using finely tuned libraries. And they are competitive, actually beating the finely tuned library in non-toy examples while still using naive haskell. [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.278.7377&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.278...
13y ago