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

31–40 of 89 posts

Re: Beating the Compiler

#31

Post by Joky »

kayamon wrote: post #11
Joky wrote: post #5

This seems quite ridiculous to me, I have seldom seen "modern compilers are always faster than you" but rather "they are good enough that it is not worth it". It provides a very over-confident "conclusion" based on a single dubious test. The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example. Also, just moving from Sandy-Bridge to Haswell for example can h…

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…

Fair. As a compiler engineer (full-time on clang/LLVM), I wouldn't make such ridiculous claim (even though the compiler is capable of nasty tricks that "normal" humans wouldn't be able to pull).

Someone that pretends that it is not possible to beat the compiler should start by taking something like a GEMM routine (for example from there https://github.com/flame/blis/tree/master/kernels/x86_64 ) and reimplement it to show how a mainstream optimizing compiler can do better using C/C++ or Fortran.

A good starting point to understand the gap between hand-written optimized assembly and what you can get with C is http://apfel.mathematik.uni-ulm.de/~lehn/sghpc/gemm/index.ht...

Re: Beating the Compiler

#34

Post by mnarayan01 »

kayamon wrote: post #29
mnarayan01 wrote: post #23

Should the second assembler statement use `jle done` rather than `jbe done` to preserve the original semantics? (I know nothing about assembly so could be missing something obvious.)

Yeah, it probably should be. It doesn't affect the performance. The difference would only manifest if you passed in a negative count, which would be an error anyway.

If your version goes UB on a zero length input array, then I think the compiler not only wins, but wins by a lot.

Obviously you can easily fix it, but the statement people generally make is "You can't beat the compiler" not "(You, me, whomever else [that was as far as I got], and/or a huge time investment) can't beat the compiler". All that said...people categorically saying "You can't beat the compiler" annoys me too (though in my case they're right; I can't).

Re: Beating the Compiler

#35

Post by bastawhiz »

dalailambda wrote: post #21

While this may seem silly to some people, I definitely appreciate the sentiment. "The compiler is smarter than you" is thrown around often here, and on Reddit, and a lot of people consider it "common wisdom", but it's not really correct. Writing code is having a dialogue with the compiler, it can do better than you sometimes, and vice versa, but treating the compiler as a magic box that always spits out faster code t…

It's worth noting that the compiler does more than just make things fast. Even the smartest of people muck up things like keeping track of types and doing pointer math every now and then. Let's say you managed the OpenSSL project. If you knew, statistically, that every line of hand-written assembly reduced runtime by Y percent and increased the likelihood of a heartbleed-magnitude security issue (caused by that code) by Z percent, how much Y would you trade for Z?

If the compiler even averages out with a human with performance, the ability to get the sort of messages that, say, rustc generates is utterly invaluable.

Re: Beating the Compiler

#36

Post by Too »

flukus wrote: post #4
sweettea wrote: post #3

Bestcase seems like a poor metric when the CPU scheduler could certainly cause 7% variation. I would be interested to see, say, 100x the number of runs, and see mean rather than best, since one usually cares about average more than best. I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has.

> I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has. From the makefile: GCCFLAGS = -O3 --std=c++11 MSFLAGS = /nologo /Ox /Ob2 /Ot /Oi /GL

Would march=native and fstrict-aliasing do any difference?

It would be interesting to compare the compiled asm with the hand rolled one.

The code has some potential improvements also but maybe the compiler is smart enough to find them, such as reading pivot.key in the loop even though it doesn't change.

Re: Beating the Compiler

#37

Post by MaulingMonkey »

Joky wrote: post #5

This seems quite ridiculous to me, I have seldom seen "modern compilers are always faster than you" but rather "they are good enough that it is not worth it". It provides a very over-confident "conclusion" based on a single dubious test. The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example. Also, just moving from Sandy-Bridge to Haswell for example can h…

> The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example.

This. You will die of natural causes well before beating the compiler en mass, on a number of codebases I've worked with. And even when dealing with the tight inner loop, I often optimize with a mind to, not so much beat the optimizer, but aid it.

There are plenty of obscenely low level optimizations - optimizations I'd argue are operating at an even lower level than assembly - that one can apply without actually resorting to assembly. Avoiding cache line aliasing, for example:

https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathol...

Re: Beating the Compiler

#38

Post by kayamon »

mnarayan01 wrote: post #34
kayamon wrote: post #29

Earlier quoted context omitted.

Yeah, it probably should be. It doesn't affect the performance. The difference would only manifest if you passed in a negative count, which would be an error anyway.

If your version goes UB on a zero length input array, then I think the compiler not only wins, but wins by a lot . Obviously you can easily fix it, but the statement people generally make is " You can't beat the compiler" not "(You, me, whomever else [that was as far as I got], and/or a huge time investment) can't beat the compiler". All that said...people categorically saying "You can't beat the compiler" annoys me…

It only fails on a _negative_ count. Zero count works. If your program is passing around negative counts, it's already broken, and the exact specifics of where and when the brokenness manifests aren't particularly important.

Technically I should have used a size_t instead of an int for the count anyway, so it's kinda a moot point. I just picked int to make a simpler toy example program.

Re: Beating the Compiler

#39

Post by bjourne »

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.4.0/sort_cpp_recurse.cpp 70 ms/loop
Compiler flags: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native

So on my computer, the assembly code (barely) beat g++ but not clang++. From a cursory glance of the assembler code clang++ generates, the difference seem to be that it adds alignment to critical loops.

It is also smarter at using 32bit registers when it can get away with it. F.e the handwritten assembler code contains "xor r9, r9". An equivalent but faster variant that the compiler generates is "xor r9d, r9d".

There is also a slight error in the assembly code. rsp should be aligned to a 16 byte boundary when a call instruction is executed and the code doesn't ensure that. Likely it loses a whole bunch of performance by calling from unaligned addresses.

Re: Beating the Compiler

#40

Post by cbdfghh »

bastawhiz wrote: post #35
dalailambda wrote: post #21

While this may seem silly to some people, I definitely appreciate the sentiment. "The compiler is smarter than you" is thrown around often here, and on Reddit, and a lot of people consider it "common wisdom", but it's not really correct. Writing code is having a dialogue with the compiler, it can do better than you sometimes, and vice versa, but treating the compiler as a magic box that always spits out faster code t…

It's worth noting that the compiler does more than just make things fast. Even the smartest of people muck up things like keeping track of types and doing pointer math every now and then. Let's say you managed the OpenSSL project. If you knew, statistically, that every line of hand-written assembly reduced runtime by Y percent and increased the likelihood of a heartbleed-magnitude security issue (caused by that code)…

OpenSSL uses assembly not for speed but for security. You need to make sure algorithms don't "optimize" leaking data.

For example, a strcmp on a secret field is insecure because of timing attacks.

The only way to ensure the CPU takes a fixed amount of time is through assembler

Post reply on HN