Comment by mpweiher | Hacker News Reader

Comment by mpweiher | Hacker News Reader

While the suggestions are definitely interesting, and the fact that compilation times are given proper attention is positive, it does seem to me that this is still pushing in the wrong direction, overall, of fully automatic optimization.

We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations.

On the other hand, performance critical routines tend to require human attention, and for these the approach of having the optimizations fully automated is generally less than helpful.

As Knuth put it, in 1974 nonetheless:

"For some reason we all (especially me) had a mental block about optimization, namely that we always regarded it a behind-the-scenes activity, to be done in the machine language, which the programmer isn’t supposed to know. This veil was first lifted from my eyes in the Fall of 1973. when I ran across a remark by Hoare [42] that, ideally, a language should be designed so that an optimizing compiler can describe its optimizations in the source language. Of course! Why hadn’t I ever thought of it?

Once we have a suitable language, we will be able to have what seems to be emerging as the programming system of the future: an interactive program-manipulation system ..." -- http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammin...

So let's have systems/languages that allow us to express performance constraints and performance-oriented transformations, and let the compiler/language assist us in doing this.

For what it's worth, the paper does acknowledge this view in the section 1.3 (and your quote of Knuth does appear in a Bernstein's talk, referenced from that section). The main reason the authors still pursue this direction is, to my best understanding, that:

* As you pointed out, we are moving to higher-level constructs and languages (this is directly addressed by a Pugh's talk as well); and

* "[...] in any case getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization".

In the other words, the widespread use of higher-level languages does not prove that the (automatic) optimization is not needed, but rather that the needs for higher-level languages are very high despite of the cost. And indeed, all languages you've mentioned have highly optimized interpreters or JIT compilers, albeit crafted by humans.

I also feel that the paper importantly discusses the speed and correctness of code optimization along with the resulting optimized code (Thesis 1), and it is not just for the fully-automatic optimizer as you detest. The correctness of such program transformations will eventually require many tools mentioned in the paper.

> section 1.3

I missed the reference to Bernstein (and Pugh), thanks! Though they seem to think he was kidding. I don't think so. A little tongue-in-cheek, maybe, but not kidding, because what Bernstein and Pugh discuss are very real.

Most code is cold, most optimizations here are a waste of compiler resources, better to compile to a simple/compact bytecode to keep code-densities high and memory clean. (See also Google's recent experience with re-implementing their JS engines).

Some code is hot, here most compilers are not good enough, though we will take what they can give us, not necessarily because you need assembler (as Bernstein says), but because higher level optimizations that do 100x - 1000x are needed when coming from high-level code.

Often, the "cold" code is setup code, whereas the hot code is in loops that get run once set up, see the Scripted Components pattern. Of course, once you follow that pattern, you run into the Two Languages problem that Julia is trying to solve.

> getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization".

If you (a) treat the compiler (or runtime) as a black box and (b) don't permit multiple levels (as per Knuth) than I agree, sort of. Except that you don't actually reliably get high performance that way. You may sometimes get high peak performance, if you're lucky.

Now they seem to argue that their approach would do away with the variability of that approach, by consistently/reliably burning through layers of abstraction.

"finding optimizations using aggressive search algorithms and SMT solvers that are, unlike humans, not easy to fool with superficial changes of representation."

I wish them cough sufficiently smart compiler cough luck, particularly when the goal is also to make/keep compile times reasonable. I also have a hard time with the phrase "unlike humans, not easy to fool", because what's easy to fool here is the compiler, and the "superficial changes of representation", as the changes needed are often not superficial.

To me, an alternative solution to the the Scripted Components / Two Languages problem with progressive refinement and the ability to specify constraints seems like the right path. So instead of, for example, writing high level (OO?) code and hoping that the compiler/runtime will do the escape analysis and put things in registers instead of allocating them on the heap, you write the same code and then (a) specify that you don't want heap allocations in a particular region (b) have the compiler tell you whether that was possible and (c) assist you in putting in annotations/transformations that accomplish this goal and remain visible in the code, possibly separate from the other other code.

We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations.

Only if you think that things like power savings and being able to run more on the same hardware are not important.

https://en.wikipedia.org/wiki/Wirth%27s_law

Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production.

So machines are fast enough that a lot of people are happy making that trade-off, and it's hard to argue that they're all wrong.

And of course they are also fast enough on single user machines (PCs, phones, tablets) that typical frameworks and 'best practices' often waste orders of magnitude of performance and developers don't even know or care to find out, and if they find out don't care enough to fix it.

> Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production.

Pretty much everyone agrees that climate change is bad but if you base your ... say, meat consumption or car usage on what others do you are going to wait a long time

This ignores the rule of thumb that 90% of CPU time is spent in 10% of the code. It is completely pointless to optimize most high-level glue logic, for instance: even making it run 10x faster produces insignificant performance and power savings.

That seems interesting in theory but I have a hard time imagining what it would look like in practice. In my experience micro-optimizing C code looks like what you describe: when you write your algorithm you have a pretty clear idea about what the machine code should look like. You compile it and check the assembly output to see if the compiler understood what you were going for. If it doesn't look like what you were expecting you need to make sure that the compiler didn't manage to actually generate better code than you exepected (because it might know things about the underlying architecture that you don't) and if it turns out that it's genuinely sub-optimal then you refactor your code a bit until you manage to get the compiler to do what you want. It can be a frustrating process.

Now we do have a few language constructs to help us here, although sometimes it's not enough. We have inline, restrict, register as well, although that one is not really used a lot in practice in my experience (at least not for its original purpose). We have compiler extensions for computed GOTOs, alignment constraints etc...

In this context what would "an interactive program-manipulation system" look like? Personally I think we could use more standardized constraints in languages like C to be able to annotate code in a way that could be useful to optimizer, such as tagging "cold" code, having control of the prefetcher and being able to write SIMD code without using intrinsics (a very complex problem admittedly). Standardizing computed gotos would be nice as well.

Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed ... Second-guessing the compiler is pretty hard if you don't have a lot of experience optimizing for a particular architecture.

> That seems interesting in theory but I have a hard time imagining what it would look like in practice.

This is one of the properties that makes an idea a worthy research direction.

Only to be taken under our feet the moment the code gets compiled by another compiler, or updated version of the same one.

It seems pretty clear that Knuth was not talking about instruction-level optimization, but about those activities/features that came to be known as metaprogramming, reflection, refactoring etc.

I imagine he was thinking about human-directed program transformations that are almost language and machine-independent, implicitly high-level, whole-program stuff, rather than aimed at writing "idiomatic" fast machine code. So I guess not the kind of optimization you have in mind.

What sounds more applicable for your use case would be profile-directed optimization, maybe based on mutating an initial fragment of assembler in ways that preserve its semantics but might improve performance. Like https://en.wikipedia.org/wiki/Superoptimization. But unless you wanted to create an instruction set that included reflection as a feature, this would most conveniently be written in another language.

Edit: I should clarify, obviously self-modifying code written in assembler is in some sense reflective, but it's hard work.

> Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed

Indeed, we need better abstractions, like cache-oblivious data structures.

Reply on news.ycombinator.com