What's an example of a simple C function which is faster implemented in inline assembly?

Question

I'm having a hard time beating my compiler using inline assembly.

What's a good, non-contrived examples of a function which the compiler has a hard time making really, really fast and simple? But that's relatively simple to make with inline assembly.

Answer 1

My best win out over a compiler was on a simple memcpy routine... I skipped a lot of the basic setup stuff ( e.g., I didn't need much of a stack frame, so I save a few cycles there ), and did a few pretty hairy things.

That was about 6 years ago, with some proprietary compiler of unknown quality. I'll have to dig up the code I had and try it against GCC now; I don't know that it could get any faster, but I wouldn't rule it out.

In the end, even though my memcpy was on average about 15x faster than the one in our C library, I just kept it in my back pocket in case I needed it. It was a toy for me to play with PPC assembly, and the speed boost wasn't necessary in our application.

Answer 2

If you want to do stuff like SIMD operations, you might be able to beat a compiler. This will require good knowledge of the architecture and the instruction set though.

Answer 3

If you don't consider SIMD operations cheating, you can usually write SIMD assembly that performs much better than your compilers autovectorization abilities (If it even has autovectorization!)

Here's a very basic SSE(One of x86's SIMD instruction sets) tutorial. It's for Visual C++ in-line assembly.

Edit: Here's a small pair of functions if you want to try for yourself. It's the calculation of an n length dot product. One is using SSE 2 instructions in-line (GCC in-line syntax) the other is very basic C.

It's very very simple and I'd be very surprised if a good compiler couldn't vectorize the simple C loop, but if it doesn't you should see a speed up in the SSE2. The SSE 2 version could probably be faster if I used more registers but I don't want to stretch my very weak SSE skills :).

 float dot_asm(float *a, float*b, int n)
{
  float ans = 0;
  int i; 
  // I'm not doing checking for size % 8 != 0 arrays.
  while( n > 0) {
    float tmp[4] __attribute__ ((aligned(16)));

     __asm__ __volatile__(
            "xorps      %%xmm0, %%xmm0\n\t"
            "movups     (%0), %%xmm1\n\t"
            "movups     16(%0), %%xmm2\n\t"
            "movups     (%1), %%xmm3\n\t"
            "movups     16(%1), %%xmm4\n\t"
            "add        $32,%0\n\t"
            "add        $32,%1\n\t"
            "mulps      %%xmm3, %%xmm1\n\t"
            "mulps      %%xmm4, %%xmm2\n\t"
            "addps      %%xmm2, %%xmm1\n\t"
            "addps      %%xmm1, %%xmm0"
            :"+r" (a), "+r" (b)
            :
            :"xmm0", "xmm1", "xmm2", "xmm3", "xmm4");

    __asm__ __volatile__(
        "movaps     %%xmm0, %0"
        : "=m" (tmp)
        : 
        :"xmm0", "memory" );          

   for(i = 0; i < 4; i++) {
      ans += tmp[i];
   }
   n -= 8;
  }
  return ans;
}

float dot_c(float *a, float *b, int n) {

  float ans = 0;
  int i;
  for(i = 0;i < n; i++) {
    ans += a[i]*b[i];
  }
  return ans;
}

Answer 4

Unless you are an assembly guru the odds of beating the compiler are very low.

A fragment from the above link,

For example, the bit-oriented "XOR %EAX, %EAX" instruction was the fastest way to set a register to zero in the early generations of the x86, but most code is generated by compilers and compilers rarely generated XOR instruction. So the IA designers, decided to move the frequently occurring compiler generated instructions up to the front of the combinational decode logic making the literal "MOVL $0, %EAX" instruction execute faster than the XOR instruction.

Answer 5

I implemented a simple cross correlation using a generic "strait C" implementation. And THEN when it took longer than the timeslice I had available, I resorted to explicit parallelization of the algorithm and using processor intrinsic to force the specific instructions to be used in the calculations. For this particular case, the computation time was reduce from >30ms to just over 4ms. I had a 15ms window to complete processing before the next data acquisition occurred.

This was a SIMD type optimization on a VLWI processor. This only require 4 or so of the processor intrinsics, which are basically assembly language instructions that give the appearance of a function call in the source code. You could do the same with inline assembly but the syntax and register management is a little nicer with processor intrinsics.

Other than that if size matters, assembler is king. I went to school with a guy who wrote a full screen text editor in less than 512 bytes.

Answer 6

I have an checksum algorithm which requires words to be rotated by a certain number of bits. To implement it, I've got this macro:

//rotate word n right by b bits
#define ROR16(n,b) (((n)>>(b))|(((n)<<(16-(b)))&0xFFFF))

//... and inside the inner loop: 
sum ^= ROR16(val, pos);

VisualStudio release build expands to this: (val is in ax, pos is in dx, sum is in bx)

mov         ecx,10h 
sub         ecx,edx 
mov         ebp,eax 
shl         ebp,cl 
mov         cx,dx 
sar         ax,cl 
add         esi,2 
or          bp,ax 
xor         bx,bp

The more efficient equivalent hand-generated assembly would be:

 mov       cl,dx
 ror       ax,cl
 xor       bx,ax

I haven't figured out how to emit the ror instruction from pure 'c' code. However...
While writing this up, I remembered compiler intrinsics. I can generate the second set of instructions with:

sum ^= _rotr16(val,pos);

So my answer is: Even if you think you can beat the pure c compiler, check the intrinsics before resorting to inline assembly.