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

Groups > comp.lang.c > #16783

Re: Optimisation questions

Show all headers | View raw

On 2012-02-06, Stephen Sprunk <stephen@sprunk.org> wrote:
> 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.

The human usually knows something that the compiler does not know.  Languages
that require full disclosure of what the human knows are probably going to
be too impractical to be useful.

Often there are things that neither the compiler nor the human knows.

We write a computer program because we want to compute something we don't know,
and in many case the program can't be statically evaluated to give that to us;
it has to actually be run.

It /would/ be nice if assert (x >= 0) could be understood as as an optimization
hint by the compiler (and even with NDEBUG in effect).

> Note that the important bit, eliminating the division, still happens;

That depends on what you regard as the important bit. What if the programmer
takes it for granted that x / 8 will not actually emit a division, but still
wants to shave off these extra cycles from not worrying about a negative input.

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

Exactly, so if we know that it isn't, how can we express that to the compiler?

The least risky way is to let the compiler deduce it by itself. Explicit
promises are risky because they could turn out to be lies.

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

As you know, the way the language works is that if you make some things
unsigned, there is a "collateral damage": some other operands silently become
unsigned also.

What if x is never negative, but is involved in calculations with other
operands that may be negative?  Change x to unsigned, and now certain
unwanted conversions are happening which will render those calculations
incorrect.

Unsigned will cause a "contagion" that spreads in the assignment of types
to expressions in the parse tree.

So that would probably be the most risky way of telling the compiler "this
quantity is nonnegative".

You can confine the contagion with some casts. Convert the value to unsigned,
do the division and then convert back to signed. (That relies on the conversion
being a two's complement noop).

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