Hacker News Reader

Comment by modeless | Hacker News Reader

I've recently been using http://halide-lang.org/, a language designed to separate the specification of an algorithm from the order of the computations and the layout of the data in memory. It allows you to first get an algorithm working and then quickly try a huge number of permutations of the options for data layout, parallelism, and vectorization. You can get incredible speedups vs. a naive series of C for loops.

View on HN

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.

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

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.

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.

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.

You can't actually compile the output of -fdump-tree-optimized, so it's close but not quite exactly what I had in mind.

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.

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/optio...

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;;

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.

> 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?

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...

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.

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

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...

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 :)

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?

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://link.springer.com/chapter/10.1007/978-3-642-19014-8_1... 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.

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 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.

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 .

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

For my masters thesis I wrote a program that annotated C++ code, ran it, then collected the memory reference patterns and tried to reorder loops by doing image analysis (mainly Hough transforms) on the data.

To be honest it wasn't a very successful approach, so you can probably take this as being a path NOT to try.

I will attempt to find the thesis and update this comment with a link if I can find it ...

That particular feature sounds awesome — but there's nothing about it on the language's front page; may be you have a link to an article or blog post about it? Sorry for asking, but my google-fu seems weak today.

You can see it a little bit in the blur example on the front page: the blur algorithm is described in two lines and the optimizations are described separately in the "schedule" below. In this case the schedule specifies that intermediate results should be computed in tiles of a certain size, and the whole thing is both vectorized and parallelized.

The best way to understand it is probably to watch the video, which is relatively long but explains things clearly: https://www.youtube.com/watch?v=3uiEyEKji0M

Truly impressed by Halide after watching the video. This could really be a game changer for writing e.g. deep-learning related code such as Convolutional Neural Network evaluation and training.

What kind of applications are you using it for? In my experience I've only seen research image processing using it (and even that totally dwarfed by OpenCL / other alternatives)

Reply on news.ycombinator.com