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

41–50 of 89 posts

Re: Beating the Compiler

#41

Post by DannyBee »

Yes, you can pretty easily beat the compiler in simple cases when you do this.

I would seriously challenge anyone to try to, by hand, do what PLUTO+ does . http://dl.acm.org/citation.cfm?id=2688512 It is implemented in at least one real production C++ compiler. The analogue would be graphite in gcc, and polly in llvm, but they don't have the full cost modeling it does. Then try to do it for multiple architectures or even different cache models (IE newer vs older processors).

Even simpler things than that, like deciding when it is profitable to add runtime vectorization/alignment checks, etc, is really hard by hand. Hell, in larger functions, i doubt people can even optimally do register allocation (including live range splitting, remat, etc).

So yeah, stupid quicksort, sure, you can beat it.

I'm not sure what it's supposed to prove?

If you restrict yourselves to small cases that are easily optimizable without any thought, and not amenable to any even slightly advanced optimization, yes, you can beat the compiler.

Re: Beating the Compiler

#42

Post by kayamon »

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…

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.

Re: Beating the Compiler

#43

Post by DannyBee »

gfody wrote: post #30
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…

It's totally ridiculous - I spent several years coding almost exclusively in x86 assembly and the prospect that a compiler could best a human at optimizing a specific function is ignorant. The only exception I can think of so-called 'superoptimization' where the optimal sequence of instructions is determined by exhaustively testing every combination. And that's not an effective strategy for anything beyond a handful…

"optimizing a specific function is ignorant"

Depends entirely on the domain. Sorry, but i have never seen a programmer come up with the kinds of parallelizing transforms, cache blocking and iteration reordering, etc, that most polyhedral optimizers do.

Now, if you aren't doing these kinds of things, and are just trying to optimize the hot loop of some simple program, yeah, you can definitely win given enough time, because you'll just sit there with IACA or whatever, and superoptimize it by hand.

But you also are often starting with the output of a good compiler. If you had to start with nothing, i doubt you would do as well.

Here: http://repo.or.cz/pluto.git/blob/HEAD:/examples/jacobi-2d-im...

Please, without looking at the output of pluto, create a multi-threaded, fully cache-optimized version of this code, optimized for 4 cores, by hand.

pluto can generate C code to do it in 0.2 seconds.

The result is here: http://repo.or.cz/pluto.git/blob_plain/HEAD:/test/jacobi-2d-...

Please also take the following gauss seidel code, and generate both a cache optimized sequential version, and a parallel cache optimized version: http://repo.or.cz/pluto.git/blob_plain/HEAD:/examples/seidel...

Most people would probably not be able to accomplish either, better than icc + pluto, pretty much ever, let alone in some reasonable time period.

Re: Beating the Compiler

#44

Post by prestonbriggs »

It's easy to beat a compiler in the small - just takes time & patience. But such an approach doesn't scale. We don't write tiny routines and throw them away; instead, we write big programs made of lots of routines & classes, and we maintain them for years, probably porting them from machine to machine.

I encourage everyone to write some assembly; you'll learn a lot. But use a compiler for your work.

Re: Beating the Compiler

#45

Post by bastawhiz »

cbdfghh wrote: post #40
bastawhiz wrote: post #35

Earlier quoted context omitted.

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

That also brings about the risk of doing bad things that the compiler could otherwise prevent. Simply using a non-optimizing compiler with a timing attack-safe algorithm (and using the resulting machine code) would have the same effect. There's little reason to actually write assembly by hand, in that case, unless you're trying to milk performance.

Re: Beating the Compiler

#46

Post by Annatar »

unscaled wrote: post #25
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…

I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts. That used to work well enough for non-portable code targeting a limited range of CPUs, but nowa…

I can see where this received wisdom is coming from: a counter-reaction to the common tendency we had well into the 90s to hand-optimize every procedure considered to be even remotely on the hot path. It didn't even have to be inline assembly: it could just be C code sprinkled with registers, Duff's devices and bit shifts.

That's not it at all. The original problem was that the compilers generated several orders of magnitude larger and slower code than what we could code in the demo scene, and other than processor or memory, made zero utilization of the hardware or DMA. And in the demo scene, if you're not getting the maximum performance out of the hardware, you might as well be dead -- "demo or die", as Chaos of Sanity (now Farbrausch) so famously put it.

Compilers didn't really catch up with us: the fastest and best they can do using hardware instead of just the CPU and RAM is CUDA Fortran (pgi Fortran compilers). I know of no compiler taking advantage of DMA or audio hardware, let alone co-processors like for example the Copper and the Blitter. Even on systems like PS3, the GCC compiler took zero advantage of the RSX chip -- it was just a generic PowerPC compiler.

Surely a compiler will sometimes beat a human by generating a perfectly or near perfectly scheduled sequence of instructions for a particular processor, but a human can write a generic piece of assembler code that will get really good performance across a range of different chips in a given processor family, and so still beat a compiler overall.

Re: Beating the Compiler

#47

Post by pg314 »

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…

I agree with the gist of your post, but the pre-optimised libraries are often optimised for the general case. It can be quite worthwhile to dive deeper in some cases. Replacing e.g. the library malloc with your own pool based allocator or a general hash table with a hand-rolled one where you exploit certain knowledge about the data can be huge wins.

Re: Beating the Compiler

#48

Post by _cbsz »

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…

> 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.

Re: Beating the Compiler

#49

Post by kscz »

kayamon wrote: post #42
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…

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.

I think a big difference is the flags. At least for g++, if you don't specify -march=native -mtune=native you're going to take a performance hit. How much of a performance hit depends on the features.

The sorttest.zip Makefile has only the following flags specified: -O3 --std=c++11

Where bjourne has: -O3 --std=c++11 -fomit-frame-pointer -march=native -mtune=native

I might rerun your tests with bjourne's additions!

Re: Beating the Compiler

#50

Post by titzer »

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

Post reply on HN