C++ performance; compiler challenge problems

[gusl]

I believe that C++ continues to be a standard because, for >99% of programs on >99% of machines, compiled C/C++ is faster than anything else (and C++ is nicer than C).

Why are compilers for high-level languages so much worse than human C++ programmers? My understanding is that you don't have to be a C++ programmer to write C++ code that can't be beaten by any other language. This is an AI question, but maybe also a systems question.

I would like to see a series of challenges for compilers, possibly in the style of a competition between programmers who work on compilers. Starting with really simple programs, make sure that they compile to something as fast as C++... and progressively, the test programs become more complex.

(1) Are all languages equally good at printing "Hello World" 1 million times?

Or better, a question that doesn't involve system calls:
(2) are all languages equally good at computing Fibonacci numbers, written with tail recursion?

Comments

[gustavolacerda.livejournal.com]

(2) Apparently not! How hard can it be to automatically translate code of such simplicity to C++??

[edanaher.livejournal.com]

It depends. Do you want to have the convenience of an interpreted language without regard for speed? That explains most of the languages near the bottom there. Do you want to have tagged/boxed types everywhere to make some language features simpler/more convenient/possible? I think that explains the languages in the middle.

In short, some languages just Don't Care about speed, and spend their time on things to make programming in them nicer. Others provide better abstractions and safety that can't generally be converted to C.

So yes, it's trivial to convert these short benchmarks to C. But it's not at all useful in a general compiler, since anything with any substance won't be as trivially converted, and it would take a tremendous amount of work to do so..

I can likewise look at the second example on this page, and ask "why does C not do tail recursion? We've shown in numerous languages how trivial it is and how tremendously useful it is!" That's not a design goal for the language/compiler, so they didn't bother with it. (Though I actually thought that gcc did do proper tail recursion, but it makes such a great point that I'll hope the page is right.)

[ikeepaleopard]

The ghc people added a lot of support for tail recursion to gcc, but I'm not sure how generally it works.

[neelk]

It doesn't do it right, because the C spec makes it impossible to do it right -- in C, you can take the address of stack variables and pass those addresses to functions. This means that in general you can't deallocate a stack frame until the function returns, which means no tail recursion in general. As a result, gcc only does tail call optimization in special cases, which means you can't count on it when it would be actually useful.

[gustavolacerda.livejournal.com]

Btw, I just added you last night. Somehow I hadn't before.

[gustavolacerda.livejournal.com]

<< So yes, it's trivial to convert these short benchmarks to C. But it's not at all useful in a general compiler, since anything with any substance won't be as trivially converted, and it would take a tremendous amount of work to do so.. >>

This is what I'm surprised about...
If you had a "bilingual parallel corpus" with programs in your high-level-language and C, doesn't the translation task become easy?

[ikeepaleopard]

Didn't you already have a thread about this?

[gustavolacerda.livejournal.com]

I am stubbornly idealistic about this.

[ikeepaleopard]

Do you distinguish between stubborn idealism and being knowingly wrong for ideological reasons? I don't remember exactly what was in that thread, but I feel like it was pretty conclusive. There is a difference between second guessing conventional wisdom in case it is wrong and ignoring basic facts.

I don't mean to be inflammatory (well maybe a little), but I feel like you have a blindspot for things that machine learning is poor at that you deliberately ignore to your own detriment.

[gustavolacerda.livejournal.com]

Not machine learning, but AI! I've felt this way long before I was interested in machine learning.

I won't deny having an ideology. I reserve the right to be unhappy as long as I'm required to write low-level code in order for it to be efficient.

I am stubborn because this is the kind of thing that would seem to be easy to automate... but evidently it isn't. And neither is computer vision, despite Marvin Minsky's early opinions. Which is why they say the proof is in the pudding: if you say it's easy, you should do it!

Here's the old thread: translating between programming languages

[gustavolacerda.livejournal.com]

... although I do maintain a slim hope that compiler designers just haven't got it together yet, and need some encouragement.
... a hope that is probably ridiculous and arrogant.

[roseandsigil.livejournal.com]

Because due to gold's theorem and similar things, you can never actually learn a language. And getting the compiler right is easier than producing the corpus.

I'm moderately..hmm.."irritated" is strong word, but maybe "perplexed" at your insistence on thinking about things this way? Why would you want a learned model when you can get an exact translation? I find your methods vaguely abhorrent--we should prefer exact solutions over heuristic ones when we have the capability to achieve them.

[gustavolacerda.livejournal.com]

I can totally picture your perplexity! Arms flailing in the air!

I have trouble thinking of C++ programming as intelligent behavior.

It's probably my machine learning bias... just like I suggested using samples for audio synthesis. Although you can always simulate the physics, it's often too hard.

[altamira16.livejournal.com]

and C++ is nicer than C

Elaborate on the word nicer please.

[gustavolacerda.livejournal.com]

uhm, classes... and explicit passing of arguments to functions.

[shaktool.livejournal.com]

Here is a website comparing performance of several algorithms in many languages.
http://shootout.alioth.debian.org/
Although the challenge is posed to the visitors, to create better source code implementations for the compiler, rather than posed to the compiler to compile better assembly.

[bhudson.livejournal.com]

I saw a graph of the languages in an earlier shootout that plotted both speed and complexity (gzipped size as a proxy for the entropy of the program's encoding). C++ and several other languages were all on the fast end, but C++ was way up there in code size.

It used to be that the site was about a natural implementation in each language, but now it seems to be fair game to throw various libraries at the problems. Seems that hacking hard gets you big rewards in C/C++, and less so in higher-level languages. But that's a lot less interesting than knowing what you get by writing pretty much normal code without heavy optimization. For the binary-trees benchmark, the natural haskell code is about 3x faster than the natural C/C++ code, and ocaml is also pretty fast. For the reverse-complement benchmark, all the language implementations are essentially identical (all the time is in I/O). But you can use non-standard memory allocation routines in the one case, or nonstandard I/O routines in the other case, and have the C end up quite a bit faster; the ocaml programs seem to play around with the garbage collector settings, which gives much less of a win.