Hacker Newsnew | comments | show | ask | jobs | submit login

Be careful: "x / 16" won't get converted to "x >> 4" by the compiler if x is a signed int. I lost an argument about this in a code review once. Look at the disassembly for the case that x is and is not signed if you don't believe me.

Odd. The code:

    int main(int argc,char *argv[])
      int x = strtol(argv[1],NULL,10);
      printf("result is %d\n",x/16);
      return 0;
The resulting assembly contained no division instructions, nor a call to a divide routine, but there is one instruction that does an arithmetic right shift by 4. Changing x to unsigned changed the instruction to a logical right shift by 4.

I think it really depends upon the compiler.


I got the following (-O6 -fstrength-reduce). A single arithmetic shift is no good, so the code adjusts the value first.

    movl	%eax, %esi
    sarl	$31, %esi  ; ESI = FFFFFFFF (-) / 00000000 (+)
    shrl	$28, %esi  ; ESI = 0000000F (-) / 00000000 (+)
    addl	%eax, %esi ; offset to cancel invalid values
    sarl	$4, %esi   ; shift
It first generates an offset value in ESI: 15 if the value to divide was negative, or 0 if it was positive.

Then it adds this to the original value. This is the cunning part - well I think so anyway. It ensures that for the values where x>>4 would give the wrong value (i.e., -15<=x<0), x is made positive and smaller than 16, so that x>>4 gives the correct value of zero. For all other values, the bottom 4 bits don't affect the result of the division, so it's fine to offset them as well.

(Don't think I've ever seen VC++ generate anything like this, but I'd pretty much always have an explicit shift rather than a divide by 16 so maybe it does and I'd just never noticed. The choice of 16 usually comes from having some 4-bit field somewhere, and when dealing with bitfields you're best off using bitwise instructions.)


Strangely, I can't reproduce the effect with a divide by 16. With GCC 4.5.2 -O2, I see a "shrl $4, %eax" for unsigned, and "sarl $4, %eax" for signed. However, if I divide by 2, the results are different; the function:

  int div_by_2(int x) {return x/2;}
compiles to:

    movl	%edi, %eax
    shrl	$31, %eax
    addl	%edi, %eax
    sarl	%eax
Meanwhile, the signed variant:

  unsigned int div_by_2(unsigned int x) {return x/2;}
compiles to:

    movl	%edi, %eax
    shrl	%eax
My conclusion remains that for hot loops, you should check the compilers assembly to make sure the compiler is applying the strength reduction you expect.


Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact