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

Groups > comp.lang.c > #16708

Re: Optimisation questions

Show all headers | View raw

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:
>>> On 02/04/2012 05:30 PM, Raj Pashwar wrote:
>>>> My current program runs too slow. It uses x/8 and x%8 many times, where x 
>>>> is an int in both cases.
>>>>
>>>> I have replaced x/8 with x>>3, as this is faster (pretty sure).
>>>> However, I am not sure whether this is faster than x%8 :
>>>> x-=(x>>3)<<3;
>>>
>>> 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.

> For my purposes, that's just about as bad as undefined behavior, so for

It is nowhere near as "bad". It must not be a failure, and it must be
documented by the implementation!

> precisely that reason I never use >> on values that could be negative.

In C90, that means you would also not use / on values that could be negative,
because yu could get truncation toward infinity or zero, and
implementation-defined is just about as bad as undefined ...

Speaking of division, whenever I see x/y, I tend to think that the programmer
must be assuming that y is not zero. Oh, and whenever I see x + y,
it must be that the programmer assumed that the sum of x + y is not greater
than INT_MAX ...

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;
}

.globl div8_0
        .type   div8_0, @function
div8_0:
.LFB0:
        .cfi_startproc
        movl    %edi, %eax
        sarl    $3, %eax
        ret
        .cfi_endproc
.LFE0:
        .size   div8_0, .-div8_0
        .p2align 4,,15
.globl div8_1
        .type   div8_1, @function
div8_1:
.LFB1:
        .cfi_startproc
        leal    7(%rdi), %eax
        testl   %edi, %edi
        cmovns  %edi, %eax
        sarl    $3, %eax
        ret
        .cfi_endproc
.LFE1:


Two more instructions in the div case!

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.

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

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

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

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