Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beating the Compiler

codersnotes.com

Post reply on HN
Print view View original

61–70 of 89 posts

Re: Beating the Compiler

#61

Post by titzer »

titzer wrote: post #50

Nice job. Here's 900,000 lines of C++ code for you to now translate to assembly. And after you're done with that, I'd like to change a few lines and have you do it over again, preferrably 100 times a day. /sigh /compiler person

It'd be nice if people replied instead of just downvoting.

You're missing the point of a compiler. It does a huge amount of work to reliably get a very, very good solution to a huge problem in a reasonable amount of time. Depending on the optimization settings, of course it is not going to try its hardest to get the very best code out of every single function. Besides, you can always use the output of the compiler as your starting point for hand optimization.

Why don't you try your hand at some Fortran kernels where a compiler might spend a few minutes or hours optimizing the hell out of something extremely important? I doubt you'll beat a Fortran compiler at its main job.

No one is claiming that you can't beat the compiler some of the time. But you can't beat the compiler even 0.01% of the time, given how much code there is out there.

Re: Beating the Compiler

#62

Post by adrianb »

chriswarbo wrote: post #58

Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/…

Maybe like PGO? https://en.wikipedia.org/wiki/Profile-guided_optimization

Re: Beating the Compiler

#63

Post by Gracana »

titzer wrote: post #61
titzer wrote: post #50

Nice job. Here's 900,000 lines of C++ code for you to now translate to assembly. And after you're done with that, I'd like to change a few lines and have you do it over again, preferrably 100 times a day. /sigh /compiler person

It'd be nice if people replied instead of just downvoting. You're missing the point of a compiler. It does a huge amount of work to reliably get a very, very good solution to a huge problem in a reasonable amount of time. Depending on the optimization settings, of course it is not going to try its hardest to get the very best code out of every single function. Besides, you can always use the output of the compiler as…

Nobody replied because others made the same argument without being so smug about it.

Re: Beating the Compiler

#64

Post by Franciscouzo »

chriswarbo wrote: post #58

Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/…

There's this [1], there are also some superoptimizers that will save the optimizations they find for later use, such as [2]

[1] https://en.wikipedia.org/wiki/Superoptimization

[2] https://github.com/google/souper

Re: Beating the Compiler

#65

Post by gpderetta »

bjourne wrote: post #53
_cbsz wrote: post #48

Earlier quoted context omitted.

> An equivalent but faster variant that the compiler generates is "xor r9d, r9d". Can you explain why this is faster? I assumed the ALU would be 64 bits wide, and 32-bit operations would just leave half of it unused.

They are equivalent due to zero extension. See http://stackoverflow.com/questions/11177137/why-do-most-x64-... But the encoding for most instructions using 32bit operands are shorter than 64bit operands. And shorter code is better because it fits better in caches and jumps are closer and so on. Though I was wrong about that particular case because "xor r9d, r9d" and "xor r9, r9" are both three bytes long. But "xor ea…

CPUs special case xor r,r as clearing the register and breaking dependency chains. Do they do the same thing when relying on implicit zero extension? (Can't be bothered to check Agner)

Re: Beating the Compiler

#66

Post by qb45 »

bjourne wrote: post #54
kayamon wrote: post #42

Earlier quoted context omitted.

It's interesting that your clang and my clang give different results, even though we're using the same version. I suspect it's a result of differing CPU architectures. (i.e. my CPU is a different model to yours perhaps). I originally did put loop alignment in my asm version, but I took it out because it was actually ever so slightly slower on mine. Make of that what you will.

That's very likely. Mine is an AMD Phenom(tm) II X6 1090T. Though I changed your code a little so that the intro looks like this: sortRoutine: ; rdi = items ; esi = count push rbp ; The "cmp esi, 2; jb done; dec esi" corresponds to your "sub rdx, 1; jbe done". That improves it on my machine to 63 ms/loop. If you are interested I can put it online somewhere.

  push rbp       ;
This shouldn't be needed. 8 byte alignment is fine for the CPU itself. The purpose of 16 byte alignment is to facilitate making 16 byte aligned stack allocations.

Re: Beating the Compiler

#67

Post by emeryberger »

olzhas wrote: post #10

why the best-case was chosen instead of mean or median?

You should never do this. Best-case favors outliers and does not represent expected performance, which is what we care about. Just because the stars happen to align one time doesn't mean you report that run.

Consider the following runs of two systems:

system A: 10s, 10s, 10s, 10s, 10s, 10s, 10s, 5s

system B: 6s, 6s, 6s, 6s, 6s, 6s, 6s, 6s

Which one is faster? (Hint: don't say system A)

Re: Beating the Compiler

#68

Post by emeryberger »

imauld wrote: post #22
kayamon wrote: post #11

Earlier quoted context omitted.

On the contrary, I've often seen the "you can't beat the compiler" statement. This[1] recent reddit thread has it in the top comment, which is what prompted me to test it out. And while all those other points are fine points (and I mention all that in the conclusion), it doesn't change the fact that beating the compiler isn't always the rocket science it's made out to be. [1] https://www.reddit.com/r/programming/comm…

Are you the author of the linked post? If so I have a couple of questions: - Why not throw out the best and worst cases for each and then find the mean of run times? Seems like a more "fair" way to compare them. - Did you compare the assembly generated by the compiler to the assembly you wrote?

A note: every compiler writer should read this paper.

https://emeryberger.com/research/stabilizer/

Re: Beating the Compiler

#69

Post by stefantalpalaru »

bjourne wrote: post #39

I ported the recursive variant of the quicksort test and ran it on my computer. Changes I made was to replace the Windows specific timing functions with Linux-specific clock_gettime() calls. Then I also changed the rcx and rdx registers to rdi and rsi because those are what the Linux 64bit calling convention uses. Here are my results: sort_asm_recurse.asm 69 ms/loop clang++ 3.8.0/sort_cpp_recurse.cpp 65 ms/loop g++ 5…

> -march=native -mtune=native

The former implies the latter. From https://gcc.gnu.org/onlinedocs/gcc-5.4.0/gcc/x86-Options.htm... :

> Specifying -march=cpu-type implies -mtune=cpu-type.

Re: Beating the Compiler

#70

Post by refset »

chriswarbo wrote: post #58

Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/…

Your description of the assistant reminds me of a Clojure talk I watched recently[1] where the speaker outlines how a central pool of knowledge about invariant compilation properties could embody the scientific method.

[1] "Bare Metal Clojure with clojure.Spec" https://www.youtube.com/watch?v=yGko70hIEwk

Post reply on HN