Compilers can never generate even good code

Yes, because they are measurably slower than their equivalent primitive instruction sequences, and the space saved isn't really all that significant when you consider all the other loads and stores necessary to run them. I think they've been actually slower since either the 486 or Pentium days. I'm pretty sure, for instance, Watcom C++ would generate "rep movsd" sequences for memcpy back in the 386/486 days, back when it was actually an optimization to do so.

And even special machine instructions seem quite achievable with a pattern-matching code generator.

Overall I think the HN title is very misleading - the article seems more "compilers don't do this well yet", definitely not "compilers can never do this".

You'd need dependent types and a compiler that understood exactly how much information in bits was required for a particular proposition, I'm guessing. I think this is the sort of thing (not using tricky assembly instructions specifically, but using unboxed types with expressive type systems) that makes languages like ATS[1] possibly faster than C.

The point is: good code generation is possible in theory, even if "sufficiently smart" compilers are too hard to write. (Or are equivalent to general A.I.)

[1] http://en.wikipedia.org/wiki/ATS_(programming_language)

It is not responsibility of a compiler to recognize specific problems in specific domains and perform optimizations, it is a job for a human programmer. Sure, you can make compiler aware of Riemann zeta function values in specific ranges, but what's the use of that outside of very specialized programs? Optimizations mentioned in the article could be programmed in C and compiler would happily translate these savings into assembly.

The reasons why we don't really program assembly anymore is that _on average and on a large scale_ compilers generate vastly better machine code than humans. Take for example register allocation problem which is proven to be NP-complete. Obviously compiler does an approximated algorithm but save for a case of few registers, no human can match it.

Some architectures, like VLIW, actually rely on the compiler to generate well-performing machine code.

Because ARM.

There is the case that there is a solution is known to be algorithmically optimal, or there is only one leading contender for optimal and it's unlikely to be toppled and you have to have a PhD and a couple postdocs in theoretical CS to begin to approach a way to challenge it, in which case it would indeed be more worth your time to optimize the assembly code. I hear Adobe Photoshop uses an FFT written in optimized assembly because almost every CPU-intensive thing they do uses it. Has he taken a gander at that? Pretty sure the fastest known way to calculate prime numbers changes a couple times a year.

However, that is only the case with textbook CS problems, and I think most HN members would agree that in industry, software engineering is almost never actually about solving textbook problems, and tends to have quirks that lead to clever algorithmic optimizations that are continually being discovered.

But what about the features of a particular language? Mucking in assembly is great if you're trying to squeeze out every ounce of power, but it's much too verbose for building complex systems. If you're trying to build user-facing features, layers and layers of language abstraction is great. See http://www.paulgraham.com/hundred.html

If you're building a prime-number generator, go ahead and write in assembly. But if you're writing an application, like most of us on here (I assume?), use a high-level language. "[Taking] advantage of every idiosyncrasy of [the] instruction set" is a waste of time.

http://www.arnetminer.org/viewpub.do?pid=600808

http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=8A1C... [PDF]

"Abstract - People often write less readable code because they think it will produce faster code. Unfortunately, in most cases, the code will not be faster. Warning: advanced topic, contains assembly language code."

On tiny and contrived micro-benchmarks, it's nearly impossible for a (non-contrived) expressive language to beat less expressive languages like machine code, X86 assembly, or C. For real, large software projects, the case for a less expressive language is not nearly as convincing, because the shortcomings of the language mean that programmers aren't able to write the same quality of code. For example, compare the outright mess that is concurrency in C or Java to the much easier concurrency available in more expressive languages. As parallelism becomes far more important for people who need high performance (yes, I know concurrency and parallelism aren't exactly the same thing, but they're similar) this advantage of the less expressive languages is likely to diminish, if not disappear outright.

[Edit: Added-- This is analogous to the static/dynamic typing debate. Dynamic typing test drives extremely well but multi-developer projects in dynamically typed languages usually turn into outright nightmares, due to problems around interfaces. Static typing's better for large projects. Same with expressive languages: assembly's going to win on microbenchmarks, but writing good code in less expressive languages becomes impossible as the size and scope of the project gets large.]

Number 3 (output of a sequence of integers as the sequence of differences between consecutive elements) is a very common optimization for inverted indexes formats, IIRC lucene, written in java, does it.