Lambda the Ultimate

1. Yes, it seems the answer might me some sort of JIT or compilation using stats, as mentioned in another reply.

2. Is there a good resource that goes into more details about the design of these specific parts of the OCaml compiler? Specially the "judicious choice of language features".

I suggest reading Leroy's design of the ZINC abstract machine, or get some highlights from these slides if you're already familiar with it, and see how OCamol evolved it.

Are there any languages that allow to select on of these axis? Without manually having to re-design the software.

Are there any languages that allow to select on of these axis? Without manually having to re-design the software.

That's one of our goals with Ecstasy.

It is true that GC does require more space in order to achieve efficiency in terms of execution speed, but that performance benefit is fairly significant over manual memory management (i.e. it is not "achieving parity", but rather achieving measurably better throughput). The rule of thumb that I use is a 2x memory footprint for a GC-based implementation, but that is just a rule of thumb. And this is still an area of computing that is evolving fairly significantly.

"That level of analysis could probably support a -04 compilation mode that virtually nobody would ever use."

In certain fields, I think it makes sense to have a final build that could even take a week or more, if it meant having the program be >20% faster. Simulations that run for months. Video games. The thing is, I don't know any language or compiler that gives you that option. Why is that?

It might seem like a week is a long time, but many times much more time is spent to write those optimizations by hand for similar gains.

"Why is that?"

Mostly they don't do it because compilers are a major undertaking to support and maintain and it's hard enough in most cases to keep up with moving-target language specs and produce correct code.

There are infrastructure limitations, like compiler suites where many different compilers all compile to a common intermediate representation and then use the same code generation module, like the GCC compiler suite, and sometimes the code generation module, by being suitable for languages that have good reasons to have, eg, more complex stack frames or procedure calls, etc, fail to take advantage of regularities or structural simplicity allowed by the language spec.

Another kind of infrastructure limitation happens when a lot of different languages are all supposed to run on the same virtual machine, and the virtual machine is optimized to serve languages simpler than the languages someone is trying to compile for it. This sort of thing happened with the JVM when people were trying to cram Scheme onto it. Scheme has a call tree instead of a call stack because of call/cc, and the specification requires tail call elimination because that is the language's primary looping construct. (there are explicit loops now, but the reference implementation of those always makes them syntactic substitution for recursive calls).

Trying to explain this to the JVM resulted in a lot of frustration and ugly hacks, exposing VM code in the middle, storing it in variables, and deliberately overwriting the stack. The whole thing violated safety guarantees the JVM was originally designed to enforce, and was generally a painful and inefficient exercise.

The JVM is better now, and, with some of its safety guarantees turned off, supports a broader class of languages. Current scheme-on-JVM efforts are nowhere near as ugly and inefficient. But hyperoptimizing the JVM to get absolute results on such languages is hardly a priority for its developers, and the compiler implementers in this case are focused on producing JVM code; the abstraction barrier between virtual-machine compilation and VM-code execution doesn't allow straight-through optimization noticeably better than they're getting now.

Next there is portability. People who write compilers would like to think that these compilers will work for a broad class of machines, and avoid optimizations that presume the existence of particular hardware such as an NVidia 1080 or better GPU, or AMD- or Intel- specific cache structures, or aliased addressing via an MMU, or .... The result is that if these features are available, the compiler is still producing code that does not take advantage of them. The compiler writers write to a "target" that they can define in a restricted language for describing hardware, and then want to believe that making their compiler work on new hardware amounts to writing a correct hardware definition file for it. It's never really that simple, but it can come close.

The point here is that the hardware definition is restricted by the set of features that the compiler can understand, and "describing enough features accurately enough to make the compiler work for new hardware" is never the same task as "describing the hardware so completely that every possible feature of it can be taken advantage of in optimizing the program." Further, they don't want it to be. This isn't the last machine they'll ever target, and if they abandon the constraints of their hardware description format in order to take advantage of every feature of it, they'll be doing a lot of work that doesn't apply to any future compilation target. So if some machine has a unique feature, they *could* extend their hardware description language to describe it, then extend their compiler to recognize and optimize for it. But they'd rather spend that time targeting three more different kinds of hardware.

After that you have peculiarities of the operating system and how well its underlying structures match the paradigms of the language. For example Scheme specifies call/cc in a way that can be read as a description of cooperative multitasking. Implementing a scheme compiler on an operating system that natively supports cooperative multitasking (like MacOS 7) had zero impedance, because continuations simply became processes. Implementing a scheme compiler on an operating system that natively supports pre-emptive multitasking (like OSX, UNIX, Linux, etc) you have to pass up on a whole lot of stuff that's available and would be a heck of a lot more efficient, to the point that you feel like you have one hand tied behind your back. And in some cases (Looking at you OSX) you have to do backflips to avoid operating system optimizations intended to take old cooperative-multitasking code and run it with pre-emptive multitasking semantics - good for a fair number of programs, very bad for standards conformance in scheme. And your backflips, inevitably, come with a performance cost well in excess of simply executing the code with cooperative-multitasking semantics.

And I could go on for days. Big projects like GCC, that have accumulated over a thousand years of human attention and craftsmanship, tend to be projects that try to support five hundred different languages on a hundred different kinds of hardware, and hyperoptimization on any single case is seen as a waste of resources. Small projects tend to be the work of a single person, and are limited to the hours and days that make up a single person's life - rarely more than 20 years of cumulative attention and craftsmanship, even assuming someone works full-time on it for a sixty-year productive lifespan. If they devote their efforts to hyperoptimization they can get a long way - with exactly one language on exactly one hardware target. It's likely not to be the combination you're interested in.