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

51–60 of 89 posts

Re: Beating the Compiler

#51

Post by kriro »

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…

I'd be interested in the results for std::qsort and std::sort for comparison.

Re: Beating the Compiler

#52

Post by qznc »

Vendan wrote: post #26
imauld wrote: post #22

Earlier quoted context omitted.

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?

You should always be comparing best case for this kind of thing. Slower cases are most likely "your thread got switched out by the OS to let something else run", and that's not really a fair test.

If you want to guard against context switches by the OS, don't use stuff that "most likely" works. Measure with perf and let it count the context switches.

Re: Beating the Compiler

#53

Post by bjourne »

_cbsz wrote: post #48
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.

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 eax, eax" is two bytes and "xor rax, rax" is three bytes. So that's why you should use the old GPR:s when you are able to choose.

Re: Beating the Compiler

#54

Post by bjourne »

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.

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.

Re: Beating the Compiler

#55

Post by zamalek »

Vendan wrote: post #26
imauld wrote: post #22

Earlier quoted context omitted.

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?

You should always be comparing best case for this kind of thing. Slower cases are most likely "your thread got switched out by the OS to let something else run", and that's not really a fair test.

Which is why you use 90th percentile.

Re: Beating the Compiler

#56

Post by wictory »

So I guess that the lesson to take from this post is that you can beat the compiler. We should also appreciate that the people who did similar analyses and did not get a speed up, most probably did not write a blog post about it.

Re: Beating the Compiler

#58

Post by chriswarbo »

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/profiler/tester/fuzzer/etc. designed to run for long periods, running all sorts of improvement-finding algorithms, building up a knowledge base about the code on disk (which can be updated incrementally when the code changes), and providing reports and messages to the user.

When we're about to embark on a deep dive, for optimisation/debugging/etc. we can fire up this assistant and have it running for the entire time we're devoting to the problem. It can even keep running overnight if we spend several days on the issue.

Re: Beating the Compiler

#59

Post by pkolaczk »

If he sorts 1 mln items, I guess he runs out of L1 cache and probably out of L2 cache. Therefore memory accesses may pay the biggest role here and that explains why he sees almost no improvement from recursion elimination.

Re: Beating the Compiler

#60

Post by to3m »

zamalek wrote: post #55
Vendan wrote: post #26

Earlier quoted context omitted.

You should always be comparing best case for this kind of thing. Slower cases are most likely "your thread got switched out by the OS to let something else run", and that's not really a fair test.

Which is why you use 90th percentile.

What's wrong with using the best result? If you're concerned the code could run faster than possible: don't be :)
Post reply on HN