Comment by zwegner | Hacker News Reader

Comment by zwegner | Hacker News Reader

Parent Full thread

> I'm pretty sure that generating perfectly efficient SSE from SSE intrinsics is an NP-complete problem. So a clever programmer will always be able to boost performance more than a compiler.

Being NP-complete doesn't really have anything to do with whether humans can solve a given problem better than computers or not. It just means that it (probably) takes exponential time to solve.

I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators). As such, it's only a matter of time before computers beat humans in compilation at every point, just like the situation in chess. People claimed for years that humans will always have some edge in chess, because they "understand" the game, or have "ingenuity", or something like that. Nobody claims that anymore, since computers absolutely massacre humans. And similarly to chess, computers have been getting better and better at a very fast rate, while humans have stagnated more-or-less.

As an aside, computer chess got quite boring for me, due to the homogeneity of current programs, but it did help to show me the limitations in current programming languages and compilers. So I'd like to do my part to put humans in their place in another field. My still very-much-not-even-close-to-finished contribution, that I haven't found much time to work on in a while, the Mutagen programming language: https://github.com/zwegner/mutagen

Often, the compiler cannot produce better code than humans because of the failings/features of the language being used. Even c/c++ has many gotchas, for example the assembly code might have to constantly dereference a pointer because the source code (in this case) does not guarantee that the data won't have been changed by others. Meanwhile, a programmer who hand-crafts the same assembly language might know that this won't happen, so they can keep the value in a register.

In theory, some of these shortcomings could be solved by a well-written aggressive whole-program optimiser that could deduce data usage & aliasing, but in practice they don't/can't, few people use WPO and it fails when you use library code.

In short, compilers probably don't have enough info to beat a skilled assembly programmer.

Absolutely--I see this as a failure of current programming languages and compiler technology, though, and not a fundamental barrier. We should aim to take away all the impediments to the compiler's job, like the aliasing problem you point out. Then, we can just sit back and let the blinding speed and precision of computers take over, trying all the different possible compilations of a given program.

This is the main goal of the Mutagen language. See the link above for a bunch of hand-waving about compiler technology that might exist some day :)

It's quite doable in C nowadays. Just use the restrict keyword which pretty much just gives the compiler a permission to assume that nothing aliases the pointer in question.

It's not that hard to write loops in C that vectorize well. And you get the benefit that those same loops also vectorize for ARM neon.

While the restrict keyword helps several cases, it's not a catch-all. Even worse, it is very easy to get wrong, leading to near-undetectable errors in your code at some future date.

Worse, it's almost impossible to retrofit into large existing code. Even turning on strict aliasing in the compiler might cause hideous problems. The compiler can't always warn you about these.

The 'holy grail' is still for a compiler that can infer this stuff from the code. With existing C code, that requires at least WPO and some very deep reasoning about pointer usage. The other approach is a different programming language that makes data/variable access control more explicit.

I agree that retrofitting existing codebase is a pain.

Turning on strict aliasing is a mixed bag as programs that break when it's on are explicitly breaking the C spec. But one must make amends to support badly written legacy code. The official way to handle the aliasing across types is to use unions.

In my opinion the default behaviour in C should have been what restrict does. And a keyword to allow alias and yet another to allow aliasing across types, because unions are bit tedious to use. As an example float *aliased foo. And warnings when you cast normal pointer into aliased one or cast across types if the pointer is not aliased across types.

In short, compilers probably don't have enough info to beat a skilled assembly programmer.

Isn't that what LLVM tries to solve dynamically?

> Isn't that what LLVM tries to solve dynamically?

No. And in fact, even writing directly in LLVM IR, there are certain kinds of code (high-speed interpreters like LuaJIT) that cannot even be expressed.

LLVM is awesome, but it's a language (LLVM IR) that does not support the full range of what can be computed efficiently with a particular CPU.

sillysaurus3 said "a clever programmer will always be able to boost performance more than a compiler." That's a much, much stronger claim than the mostly unobjectionable "a clever programmer can still typically boost performance more than a compiler (especially when they have the ability to look at the output of that compiler with various optimization settings)".

> I believe there is no distinction whatsoever, in principle, between computers and humans (our brains are just big, complicated calculators).

Our brains seem to be primarily an I/O processor attached to a device micro controller.

The reason you're wrong is because the semantics of C restrict what compilers can do. Humans know the actual semantics they require, and thus, when writing assembly language, can retain only those semantics, dropping everything else. Thus, "ingenuity" as you put it is a real advantage that humans actually posses over what a compiler can do—even if we gave that compiler an infinite amount of time.

This is quite unlike chess, where the rules are known up front, and are the same for both the computer and the human.

The reason you're wrong is that I wasn't talking about C :)

Yes, for any current programming language, humans do have some advantage by being able to utilize both low- and high-level semantic information that simply cannot be communicated to the compiler. The trump card, I believe, is coming up with new languages where this is not the case.

Reply on news.ycombinator.com