Lambda the Ultimate

In scientific computing, C++ has barely managed to catch up to Fortran, because Fortran compilers can assume that arrays aren't aliased, and standard C++ has no way to represent this notion. In one case, the OCaml compiler actually did better than gcc because it was able to merge an inner and an outer loop.

to get that compiler goodness? :-)

References? I know a lot of NA people & not many have used Fortran in 25 years. A few late stragglers switched to Matlab 10 years ago. I know there are still old Fortran hands at the National Labs and NASA Ames, but I'm pretty sure they're all older than dirt & not likely to change their minds about anything regardless of the evidence.

I speak as one who was in dirt's class in graduate school. Every time I change my mind, my wife looks up from her knitting and says "did you hear something downstairs?"

As for OCaml, one battle does not make a war.

Fortran compilers can assume that arrays aren't aliased, and standard C++ has no way to represent this notion. In one case, the OCaml compiler actually did better than gcc because it was able to merge an inner and an outer loop.

Well I'm glad you pointed that out. What other languages have desirable features to keep in mind when designing for high performance?

Because I was curious, I quickly checked the language benchmark for fortran (intel) vs c++ (gcc) and fortran (g95) vs c++ (gcc), but the results seem to refute your claim... Am I missing something?

I also think that scientific computing isn't the only place where high performance is desirable. I already named renderers and video codecs off the top of my head. Besides, it seems to me like the GPGPU programming is becoming quite widespread for the really high performance scientific computing. Anyone know of a GPGPU language based around a functional "oriented" design?

Shootout doesn't measure anything from "scientific computing" area.

Download NAS benchmark, rewrite them in your favorite language and get performance similar to Fortran. On multiprocessors, of course.

Aliasing in C code makes it hard to perform many forms of analysis (dataflow, range analysis) and so prohibits optimizations available for Fortran, for example, array privatization.

Nice. Am I correct in thinking that referential transparency also helps a great deal with optimization during static analysis? Why is it so difficult to get functional compilers up to par? Data structures are one common reason I'm guessing.
For example I know that clojure adds a few built-in data structures for this reason, but has anyone ever tried to infer what type of data structure to use by static analysis? What I have in mind is something similar to, but more powerful than memoization. It sounds difficult, I admit.

(Sorry, I feel like I'm completely hijacking this thread...)

Yes, it does: http://www.sac-home.org/

The most explored area of automatic parallelization is array processing, because it is hard to write correct Fortran code, it is easy to analyse (no recursion, for example) and there exists quite a volume of legacy code. It is very worthwhile.

Functional programs, on other hand, highly recursive and rarely operate on arrays, so those two worlds just do not connect.

SaC sounds very interesting and a nice source of info for a young pup like me. I will study it diligently. :)
The general picture I've constructed in my mind of a fast functional language is:
* Data structures with appropriate algorithmic efficiencies
* "Tail-call" optimizations or whatever else can be done to flatten recursive algorithms
* Enumerating the possible types used (for the dynamically typed languages)
* The language's susceptibility to various forms of static analysis
* A good methodology for handling task-parallel / data-parallel tasks

If I've missed something generally important, please let me know.

You've missed something generally important.

...I should have used more concise language. ;P
Still, if I said something incorrect please don't hesitate to correct me!

It's also worth seeing if you can dig up any of the public literature on the IBM PL.8 compiler (overview article here) One thing they worked on in that compiler was data layout optimization, though this was more oriented toward cache line packing and cache residency than toward unboxing.

There was a lot of stuff done in that compiler that doesn't seem to be widely known.

I read the overview, but unfortunately I wasn't able to find any references to data layout or cache optimization... (It was interesting none-the-less). The closest thing I could find was a reference discussing how one could manipulate layout of data in structures at bit-level. This appears to be a more flexible version of C's bit-fields and unions, but it's more or less the opposite of what I'm thinking. I am interested in taking away the programmer's control over layout and shifting the responsibility to the compiler.

Though in C it is assumed that pointers may be aliased unless marked otherwise, it's not entirely clear cut. C99 has the restrict modifier to declare that pointers are not aliased, Fortran 77 has the equivalence statement and common blocks which provide some kinds of aliasing, and many implementations of Fortran have extensions which are aliasing mechanisms. So if you're writing C code and have discovered that the compiler can't perform an optimisation due to it assuming that there is aliasing which isn't really there, you can tell the compiler otherwise, and so it should be able to apply the same optimisations that a Fortran compiler would do in code without aliases.

Because I was curious, I quickly checked the language benchmark for fortran (intel) vs c++ (gcc) and fortran (g95) vs c++ (gcc), but the results seem to refute your claim... Am I missing something?

Yes: the shootout is not a useful (let alone authoritative) way to judge performance of implementations. (I'm being a little harsh here, but that's intentional.)
Unless you have verified that the Fortran implementation is well-written, I'd not rely on that.

For an anecdotal description (rant?) of how those benchmarks are put into place, see http://groups.google.com/group/comp.lang.lisp/msg/5489247d2f56a848?pli=1 :-)
I've seen many cases where implementation X suddenly performed much better because very experienced users of X had decided to improve the benchmark implementations. I don't know about Fortran, but I do know that many non-mainstream languages (CL/Haskell/others) had some very inefficient entries not too long ago. The Haskell folks at least spent quite some time improving their versions, with very impressive results.

Well, sure. I've heard people on LTU add "disclaimer" whenever they reference the shootout, I was just too lazy. It's pretty obvious that the amount of time put into each benchmark is related to the popularity of the language. Hence, my inquiry whether I'm missing something. :)

I'm really not so much interested in which programming language is "the fastest" as I am in finding hints as to what kind of design leads to a nice "optimizable" AST. From the discussion I get the feeling that Fortran tends to perform very well for specific types of programs. Obviously I will take the time to investigate it further to increase my knowledge.

I think that in C++ it's most often a question of how much time you put into performance tuning that determines what you get. More so than with other languages at least because most other languages specifically (and understandably) avoid this "low level" of control. Obviously it would be very nice if we could get good automatic vectorization going for SIMD since the underlying hardware changes quite often. The only way I see this happening is if the compiler is handed the reins to control data layout and this seem completely implausible for C++ exactly because of its "low level" of control. But I was hoping others would have a few insights that I'm too inexperienced to know about. I've heard that there's some work in Haskell on data-parallel optimization for example.

Of course there's OpenCL and CUDA, but they really don't seem very interesting from a language design perspective.