Hacker News Reader

Comment by danso | Hacker News Reader

On the topic of compiler optimization, Peter Seibel's interview with Fran Allen, a Turing Award recipient for her "pioneering contributions to the theory and practice of optimizing compiler techniques", is a good read:

http://books.google.com/books?id=nneBa6-mWfgC&lpg=PA9&pg=PA5...

She considers the development of C to be a "big blow", saying that "C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers...are basically not taught much anymore in the colleges and universities"

Her whole interview is great...in fact the whole book is fantastic, one of the best books about programming I've ever read.

View on HN

"C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine."

She's right. As I occasionally point out on why C programs are so buggy, the three big problems in C are "how big is it", "who owns it", and "who locks it". The language doesn't help with any of those. Those problems also inhibit optimization.

One optimization that's been lost to history is optimizing subscript checking. This was done in some Pascal compilers, and about 95% of subscript checks can be optimized out. Where there's a loop involved, it's often possible to make one check at loop entry, rather than a check at every reference. Sometimes that one check can be proven true from FOR statement bounds, and can be eliminated. This is usually the case for numeric matrix work, where it really matters.

I had a talk with one of the designers of Rust about this last Wednesday. They're not optimizing subscript checks yet. They hope to do so. They're currently limited by being a front-end to LLVM, which doesn't really comprehend subscript checks. The Go compiler does some subscript check optimizations, but only on FOR statements of restricted form.

C, Go, and Rust all lack multidimensional arrays. This prevents a whole range of array-related optimizations which FORTRAN compilers have had all the way back to Backus's first FORTRAN compiler in 1956. This is part of why the supercomputer crowd still uses FORTRAN.

I was trying to push the Go crowd towards multidimensional arrays. People in love with the slicing syntax wanted to extend it to multidimensional arrays. There were long arguments over how far to take that. Should you be able to slice out an arbitrary sub-hypercube of an N-dimensional array? If you allow that, you have to have a slice representation which is general but inefficient. After much discussion, nothing happened.

Meanwhile, the number-crunching crowd is trying to compile Matlab, which has multi-dimensional arrays but not much else.

So much is right, in many senses about FORTRAN and SQL. Both are expressive and have a limited enough semantics that allows them to be very aggressively optimized for the underlying hardware and data.

I have removed thousands of lines of Python by putting the entire working set into sqlite, transforming and projecting it relationally. Optimizations are orthogonal to the algorithm, mostly by adding and index, partition or view.

Halide is a very interesting piece of research that makes this decoupling of algorithms and schedules a core tenet.

http://people.csail.mit.edu/jrk/halide12/

I'd really like to see a relational set theoretic fork of Rust with some Fortran thrown in. I have no idea how they would all mix, but goal seems interesting.

Julia is definitely worth a look as it has taken on some of these issues (multi-dimensional arrays, slicing, some bounds checking). Now that it has a good garbage collector its remaining achilles heals are multi-threading (there are multiple processes that can send messages though) and long start up times for some modules (no JIT caching yet). It does make a lot of really good decisions at the language level though and is faster than many native languages while being more flexible than many scripting languages.

> One optimization that's been lost to history is optimizing subscript checking.

Depends upon how you look at it. Most JIT compilers do this.

It's not a priority for Rust to hoist subscript checks in loops, because Rust uses iterators pervasively and iterators are guaranteed to check the bounds of the array no more than once.

LLVM (used by rustc) is perfectly capable of hoisting and eliminating subscript checks, although I believe rustc doesn't necessarily drive LLVM in the optimal way, yet: https://github.com/rust-lang/rust/issues/22987

E.g. this has no bounds checks, and is in fact vectorised:

  pub fn bad_sum(x: &[i32]) -> i32 {
      let x = x; // *
      let mut sum = 0;
      for i in 0..x.len() {
          sum += x[i]
      }
      sum
  }

The line marked * is needed because of https://github.com/rust-lang/rust/issues/22924 which is caused by https://llvm.org/bugs/show_bug.cgi?id=22786 .

Write a matrix multiply. Or a linear equation solver.

The bounds checks for matrix multiplication over fixed length arrays are completely optimized out by LLVM, and LLVM will also optimize the bounds checks for non-fixed-length arrays in many cases. The slice length is an SSA value, so it's subject to constant propagation and SCCP.

Julia and Python Numba are two fast (almost native) high level languages for multdimensional array programming.

Fran is right in the sense that C is a very very hard language to do these things for. But she's wrong in the sense that it caused massive amounts of funding to be poured into trying to make it happen anyway.

It's like saying Itanium was a complete failure for compiler optimization.

It is in the sense that they couldn't get compilers that produced good enough code for it (well, the could, just not compilers that ran fast).

But the amount of research and funding used to try to make it happen actually did advance the state of the art in compilers. The techniques we learned weren't all useless, and we discovered a lot about the limits of what can be done.

Fran, btw, is one of the smartest people you'll ever meet. Just last year I discovered, through some IBM Research colleagues, a really great algorithm that she came up with for region analysis, that solves a lot of the problems of common ones, cleanly, and nobody has rediscovered it in 35 years yet. (Sadly, this falls into the "i wish they had published more papers on stuff" area)

> It is in the sense that they couldn't get compilers that produced good enough code for it (well, they could, just not compilers that ran fast).

Can you elaborate on that? My last update is from 2002, from an Intel guy who was working on it and said they couldn't. I was under the impression that no much has changed since - but perhaps I am wrong? (and perhaps I misunderstood him in 2002)?

They could do it by ~2005.

In any case, it's always been possible. At worst, you make large integer linear programming based models of what you want to happen, and solve them. You can do optimal register allocation and scheduling, etc.

You can basically shove everything you want into the ILP model.

It's just going to take a ridiculous amount of memory and time to solve.

Can you share this algorithm?

It was given to me by Kenny Zadeck in the form of an an unpublished chapter of a book that they had been working on.

I was asked not to reshare it because of that, so i haven't.

The book, sadly, still has not been published.

Reply on news.ycombinator.com