Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #16782

Re: Optimisation questions

Show all headers | View raw

On 04-Feb-12 21:04, Kaz Kylheku wrote:
> On 2012-02-05, James Kuyper <jameskuyper@verizon.net> wrote:
>> On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
>>> On 04-Feb-12 17:44, James Kuyper wrote:
>>>> As a general rule, your compiler should generate exactly the same code
>>>> for x/8 and x>>3, because they're required to have exactly the same
>>>> behavior.
>>>
>>> That only holds if x is non-negative.
>>
>> You're right - the result is implementation-defined if x is negative.
> 
> Yes and the point is that this is what helps to optimize it better.

You missed the point.  If x is negative, they are not guaranteed to have
the same behavior, so the compiler is not allowed to make such an
optimization.  The human wins because (and _only_ because) he knows
something the compiler doesn't know.

Solution: tell the compiler what you know.

> Anyway, let's see how GCC (4.5.2, x86) weighs in on this:
> 
> int div8_0(int x)
> {
>   return x >> 3;
> }
> 
> int div8_1(int x)
> {
>   return x / 8;
> }
>
> [ asm elided ]

Your code appears to be amd64.  Unfortunately, all I have access to at
the moment is an i686 box with an older GCC, so I'll give the (slightly
different) code I get:

div8_0:
        movl    4(%esp), %eax
        sarl    $3, %eax
        ret

div8_1:
        movl    4(%esp), %eax
        testl   %eax, %eax
        leal    7(%eax), %edx
        cmovs   %edx, %eax
        sarl    $3, %eax
        ret

Note that the important bit, eliminating the division, still happens;
the performance loss due to the extra instructions will be minimal in
comparison and, most importantly, the result _will never be incorrect_,
unlike the human-optimized version that doesn't actually do what it says
it does.

> Two more instructions in the div case!

Three more for me.

> So the advice "use / 8; the compiler will generate the same code" is quite
> obsolete. It was that way on some compilers for the C90 language.

Those extra instructions are to deal with the possibility that x is
negative.

If I make x (and the return value) unsigned, I get this:

div8_0:
        movl    4(%esp), %eax
        shrl    $3, %eax
        ret

div8_1:
        movl    4(%esp), %eax
        shrl    $3, %eax
        ret

Presto, the code is identical.

> (For instance, if division has truncation toward negative infinity semantics,
> and the arithmetic bit shifter shifts through the sign and copies the sign,
> then such a reduction can be made.)

Isn't that what the extra instructions in the compiler's partially
strength-reduced version do?

> The reduction can also be made if you somehow make make it obvious to the
> compiler that the variable cannot be negative.

Indeed.  When I changed the functions like this:

int div8_0(int x)
{
  if (x<0) return 0;
  return x >> 3;
}

int div8_1(int x)
{
  if (x<0) return 0;
  return x / 8;
}


I got identical asm code, indicating the compiler was smart enough to
figure the full strength reduction was safe even for a "signed" operand:

div8_0:
        movl    4(%esp), %edx
        xorl    %eax, %eax
        movl    %edx, %ecx
        sarl    $3, %ecx
        testl   %edx, %edx
        cmovns  %ecx, %eax
        ret

div8_1:
        movl    4(%esp), %edx
        xorl    %eax, %eax
        movl    %edx, %ecx
        sarl    $3, %ecx
        testl   %edx, %edx
        cmovns  %ecx, %eax
        ret

> (Doing that by making it unsigned, however, has its downsides: like
> introducing bugs due to the discontinuity in unsigned in the neighborhood
> of zero, and surprising value changes on conversion.)

If you're worried about that, it means you're not really sure that your
x is as non-negative as your micro-optimization assumes it is.  IOW, the
optimization is invalid.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-04 22:30 +0000
  Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:44 +1300
    Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
      Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:55 +1300
      Re: Optimisation questions Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-21 18:41 +0200
  Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 22:44 +0000
    Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 23:41 +0000
  Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-04 17:51 -0500
  Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
  Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 18:44 -0500
    Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-04 18:00 -0600
      Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 21:18 -0500
        Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 03:04 +0000
          Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-06 09:40 -0800
            Re: Optimisation questions Willem <willem@toad.stack.nl> - 2012-02-06 18:51 +0000
            Re: Optimisation questions Markus Wichmann <nullplan@gmx.net> - 2012-02-07 14:19 +0100
              Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-07 14:25 -0800
          Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-06 17:29 -0600
            Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-06 23:52 +0000
            Re: Optimisation questions pete <pfiland@mindspring.com> - 2012-02-06 19:10 -0500
    Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 10:51 +0000
      Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-06 00:08 +1300
        Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 08:13 -0500
      Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 11:33 +0000
      Re: Optimisation questions Zoltan Kocsi <zoltan@bendor.com.au> - 2012-02-05 23:24 +1100
        Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 22:28 +0000
          Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 22:37 +0000
          Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 17:48 -0500
          Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-05 15:57 -0800
      Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 12:53 +0000
  Re: Optimisation questions Geoff <geoff@invalid.invalid> - 2012-02-04 16:07 -0800
  Re: Optimisation questions "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2012-02-04 15:37 -0800
    Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:26 -0800
      Re: Optimisation questions lawrence.jones@siemens.com - 2012-02-07 10:56 -0500
  Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:29 -0800
  Re: Optimisation questions Michael Angelo Ravera <maravera@prodigy.net> - 2012-02-05 23:24 -0800

csiph-web