Comment by bjourne | Hacker News Reader

Comment by bjourne | Hacker News Reader

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.

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!

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       ; <- stack alignment push
  sortRoutine_start:
        cmp esi, 2
        jb done
        dec esi

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       ; <- stack alignment push

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.

RSP needs to be aligned to 16 bytes at CALL sites. See f.e https://blogs.msdn.microsoft.com/oldnewthing/20040114-00/?p=...

See the first answer here

http://stackoverflow.com/questions/612443/why-does-the-mac-a...

I also checked similar manual for AMD and it doesn't seem to mention RSP alignment at all, except that "some calling conventions may require ...".

The CPU doesn't care. It only matters when you call functions which allocate 16B objects on the stack.* This function calls only itself and pushes only 8B words on the stack so it's fine with 8B alignment.

* Some functions generated by C compilers do and they segfault if you call them with wrong alignment. Ask me how I know.

edit:

OK, so I downloaded this code. Results:

  as-is:     78111us
  push rbp:  73093us
  sub rsp,8: 72332us
  sub rax,8: 72222us

Seems to be a matter of instruction alignment, nothing to do with the stack.

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

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)

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

Reply on news.ycombinator.com