Optimizing the expression (x * 1000 / 1000)

Discussion in 'C Programming' started by pozz, Feb 23, 2011.

  1. pozz

    pozz Guest

    I have the following code:
    ---
    #define HZ 1000
    unsigned int calc(unsigned int x) {
    x = x * HZ / 1000;
    }
    void main(void) {
    unsigned int y = calc(23);
    ...
    }
    ---

    When I compile it with a compiler for a 16-bit embedded
    microcontroller, I see the code for multiplication and division in
    calc function. The optimization is on.

    Is there any method to avoid the time consuming multiplication and
    division?
     
    pozz, Feb 23, 2011
    #1
    1. Advertising

  2. pozz <> wrote:
    > I have the following code:


    > #define HZ 1000
    > unsigned int calc(unsigned int x) {
    > x = x * HZ / 1000;
    > }
    > void main(void) {
    > unsigned int y = calc(23);
    > ...
    > }


    > When I compile it with a compiler for a 16-bit embedded
    > microcontroller, I see the code for multiplication and division in
    > calc function. The optimization is on.


    > Is there any method to avoid the time consuming multiplication and
    > division?


    I would try as a first step to put the 'HZ / 1000' bit into
    parentheses. The expression 'x * Hz / 1000' is evaluated
    left to right and 'x * Hz' could for example overflow, thus
    'x * 1000 / 1000' could have quite a different result from
    'x * ( 1000 / 1000 )'. Thus the compiler isn't allowed to
    optimize out the (for a human reader rather obviously)
    redundant multiplication and division. Telling the compiler
    what you really want will probably give it the information
    it needs to further optimize (but, of course, the compiler
    isn't in any sense required to optimize, that's just a
    question of the quality of the implementation).

    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, Feb 23, 2011
    #2
    1. Advertising

  3. pozz

    pozz Guest

    On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    > I would try as a first step to put the 'HZ / 1000' bit into
    > parentheses.


    Oh yes, in that way the compiler doesn't add multiplication and
    division instructions.

    But what happens if I declare HZ as 1500?
    x = x * (HZ / 1000);
     
    pozz, Feb 23, 2011
    #3
  4. pozz

    James Kuyper Guest

    On 02/23/2011 05:58 AM, pozz wrote:
    > On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    >> I would try as a first step to put the 'HZ / 1000' bit into
    >> parentheses.

    >
    > Oh yes, in that way the compiler doesn't add multiplication and
    > division instructions.
    >
    > But what happens if I declare HZ as 1500?
    > x = x * (HZ / 1000);


    That statement will be equivalent to
    x = x * 1;
    or
    x = x;
    or, since x is not volatile, it's also equivalent to doing nothing at
    all. Therefore, a decently optimizing compile will probably drop the
    statement entirely. If that's not what you want; if the calculation you
    actually want it to perform is (x*1500)/1000, separate multiplications
    and division are unavoidable (except insofar as the compiler finds other
    faster ways of achieving identical results).
    --
    James Kuyper
     
    James Kuyper, Feb 23, 2011
    #4
  5. pozz

    James Kuyper Guest

    On 02/23/2011 04:42 AM, pozz wrote:
    > I have the following code:
    > ---
    > #define HZ 1000
    > unsigned int calc(unsigned int x) {
    > x = x * HZ / 1000;


    Just a nit pick: isn't there a missing 'return' statement here?

    > }
    > void main(void) {
    > unsigned int y = calc(23);


    Without the return statement in calc(), the use of the return value from
    calc() to initialize y renders the behavior of your entire program
    undefined.

    --
    James Kuyper
     
    James Kuyper, Feb 23, 2011
    #5
  6. pozz

    Willem Guest

    pozz wrote:
    ) I have the following code:
    ) ---
    ) #define HZ 1000
    ) unsigned int calc(unsigned int x) {
    ) x = x * HZ / 1000;
    ) }
    ) void main(void) {
    ) unsigned int y = calc(23);
    ) ...
    ) }
    ) ---
    )
    ) When I compile it with a compiler for a 16-bit embedded
    ) microcontroller, I see the code for multiplication and division in
    ) calc function. The optimization is on.
    )
    ) Is there any method to avoid the time consuming multiplication and
    ) division?

    #define HZ 1000
    unsigned int calc(unsigned int x) {
    if (HZ != 1000) x = x * HZ / 1000;
    }


    Since the condition is a constant, the whole if should be optimized away.

    Alternatively:

    #define HZ 1000
    unsigned int calc(unsigned int x) {
    #if (HZ != 1000)
    x = x * HZ / 1000;
    #endif
    }


    By the way: your code won't work as-is, as it doesn't return anything.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Feb 23, 2011
    #6
  7. pozz

    BartC Guest

    "pozz" <> wrote in message
    news:...
    > On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    >> I would try as a first step to put the 'HZ / 1000' bit into
    >> parentheses.

    >
    > Oh yes, in that way the compiler doesn't add multiplication and
    > division instructions.
    >
    > But what happens if I declare HZ as 1500?
    > x = x * (HZ / 1000);


    This is equivalent (ignoring overflows) to x = x*3/2. I would guess that you
    compiler can multiply by , and divide by 2, more efficiently than by 1500
    and 1000.

    What are the likely values of HZ, anything? If in steps of 500, then:

    #define STEP 500

    x = x * (HZ/STEP)/(1000/STEP)

    might perhaps jog the compiler into generating better code: either x*2/2
    (HZ=1000), or x*3/2.

    --
    Bartc
     
    BartC, Feb 23, 2011
    #7
  8. pozz

    James Kuyper Guest

    On 02/23/2011 06:42 AM, Willem wrote:
    > pozz wrote:
    > ) I have the following code:
    > ) ---
    > ) #define HZ 1000
    > ) unsigned int calc(unsigned int x) {
    > ) x = x * HZ / 1000;
    > ) }
    > ) void main(void) {
    > ) unsigned int y = calc(23);
    > ) ...
    > ) }

    ....
    > By the way: your code won't work as-is, as it doesn't return anything.


    Not quite; the behavior is undefined by the C standard, which means that
    any behavior is permitted. In particular, a compiler is permitted to
    generate code that would make the program work as intended. It's not
    entirely implausible that it would do so, either. There's a decent
    chance, depending upon the ABI, that the same register would be used for
    both 'x' and the return value from calc().

    --
    James Kuyper
     
    James Kuyper, Feb 23, 2011
    #8
  9. pozz

    pozz Guest

    On 23 Feb, 12:42, James Kuyper <> wrote:
    > > I have the following code:
    > > ---
    > > #define HZ 1000
    > > unsigned int calc(unsigned int x) {
    > >    x = x * HZ / 1000;

    >
    > Just a nit pick: isn't there a missing 'return' statement here?


    You are right, I forgot to write the return statement, but it is
    present in my program.
     
    pozz, Feb 23, 2011
    #9
  10. pozz

    pozz Guest

    On 23 Feb, 12:42, Willem <> wrote:
    > Alternatively:
    >
    > #define HZ 1000
    > unsigned int calc(unsigned int x) {
    > #if (HZ != 1000)
    >   x = x * HZ / 1000;
    > #endif
    >
    > }


    Yes, I can code in this way. But it isn't a general method, because
    the
    "optimization" should be performed also if HZ is 2000 or 3000.

    I thought there was a way to always reduce a trivial calculation
    (1000/1000
    or 2000/1000 or similar) to a very simple operation (nothing or
    multiplication
    by 2) so avoiding multiplication *and* division by 1000.

    Of course, if the calculus is 1500/1000 the compiler should include
    both
    operations.
     
    pozz, Feb 23, 2011
    #10
  11. pozz <> wrote:
    > On 23 Feb, 12:42, Willem <> wrote:
    > > Alternatively:
    > >
    > > #define HZ 1000
    > > unsigned int calc(unsigned int x) {
    > > #if (HZ != 1000)
    > >   x = x * HZ / 1000;
    > > #endif
    > >
    > > }


    > Yes, I can code in this way. But it isn't a general method, because
    > the
    > "optimization" should be performed also if HZ is 2000 or 3000.


    > I thought there was a way to always reduce a trivial calculation
    > (1000/1000
    > or 2000/1000 or similar) to a very simple operation (nothing or
    > multiplication
    > by 2) so avoiding multiplication *and* division by 1000.


    > Of course, if the calculus is 1500/1000 the compiler should include
    > both operations.


    Then what about this

    unsigned int calc( unsigned int x )
    {
    #if HZ % 1000
    return x * HZ / 1000;
    #else
    return x * ( HZ / 1000 );
    #endif
    }

    If HZ can be divided by 1000 without a remainder the second
    version is used inwhich the compiler probably can optimize
    out the division. Otherwise the full calculation is done.
    Just be aware that in that case overflows are much easier
    to get when x is large enough...

    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, Feb 23, 2011
    #11
  12. Jens Thoms Toerring wrote:
    >pozz wrote:
    >> I have the following code:

    >
    >> #define HZ 1000
    >> unsigned int calc(unsigned int x) {
    >> x = x * HZ / 1000;
    >> }

    >
    >I would try as a first step to put the 'HZ / 1000' bit into
    >parentheses.


    It is correct as written. That change would produce the following:
    For HZ in [0..999], HZ/1000 = 0
    For HZ in [1000..1999], HZ/1000 = 1
    ....

    (HZ / 1000.0) is a different story, of course.
    --
    Roberto Waltman

    [ Please reply to the group.
    Return address is invalid ]
     
    Roberto Waltman, Feb 23, 2011
    #12
  13. pozz <> writes:
    > I have the following code:
    > ---
    > #define HZ 1000
    > unsigned int calc(unsigned int x) {
    > x = x * HZ / 1000;
    > }
    > void main(void) {
    > unsigned int y = calc(23);
    > ...
    > }
    > ---


    Since nobody else has mentioned it, main returns int, not void.

    Also, you mentioned in a followup that the missing return statement in
    calc() is present in your actual code. Please develop the habit of
    posting actual code, not a summary of it.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Feb 23, 2011
    #13
  14. "BartC" <> writes:
    > "pozz" <> wrote in message
    > news:...
    >> On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    >>> I would try as a first step to put the 'HZ / 1000' bit into
    >>> parentheses.

    >>
    >> Oh yes, in that way the compiler doesn't add multiplication and
    >> division instructions.
    >>
    >> But what happens if I declare HZ as 1500?
    >> x = x * (HZ / 1000);

    >
    > This is equivalent (ignoring overflows) to x = x*3/2.

    [...]

    No, it isn't. It's equivalent to
    x = x * (1500 / 1000);
    which is equivalent to
    x = x * 1;

    The parentheses matter a great deal in this case.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Feb 23, 2011
    #14
  15. pozz

    Lauri Alanko Guest

    In article <-berlin.de>,
    Jens Thoms Toerring <> wrote:
    > pozz <> wrote:
    > > #define HZ 1000
    > > unsigned int calc(unsigned int x) {
    > > x = x * HZ / 1000;
    > > }


    > The expression 'x * Hz / 1000' is evaluated left to right


    You mean that * and / are left-associative. The evaluation order is
    undefined.

    > and 'x * Hz' could for example overflow, thus
    > 'x * 1000 / 1000' could have quite a different result from
    > 'x * ( 1000 / 1000 )'. Thus the compiler isn't allowed to
    > optimize out the (for a human reader rather obviously)
    > redundant multiplication and division.


    Note that this is a peculiarity of unsigned integer arithmetic, which
    is required to be modular. For signed integers, overflow behavior is
    undefined, so the compiler is free to optimize the expression by
    assuming that it won't overflow.

    So, if you know that x is always non-negative, and that x * HZ won't
    overflow, you can do:

    x = (unsigned) (((int) x) * HZ / 1000);

    At least gcc seems to be able to optimize this properly.


    Lauri
     
    Lauri Alanko, Feb 23, 2011
    #15
  16. pozz

    BartC Guest

    "Keith Thompson" <> wrote in message
    news:...
    > "BartC" <> writes:
    >> "pozz" <> wrote in message
    >> news:...
    >>> On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    >>>> I would try as a first step to put the 'HZ / 1000' bit into
    >>>> parentheses.
    >>>
    >>> Oh yes, in that way the compiler doesn't add multiplication and
    >>> division instructions.
    >>>
    >>> But what happens if I declare HZ as 1500?
    >>> x = x * (HZ / 1000);

    >>
    >> This is equivalent (ignoring overflows) to x = x*3/2.

    > [...]
    >
    > No, it isn't. It's equivalent to
    > x = x * (1500 / 1000);
    > which is equivalent to
    > x = x * 1;
    >
    > The parentheses matter a great deal in this case.


    I meant for the original code, which doesn't have them. Then, when HZ is
    1500, the calculation x*1500/1000 can be the same as x*3/2

    --
    Bartc
     
    BartC, Feb 23, 2011
    #16
  17. "BartC" <> writes:
    > "Keith Thompson" <> wrote in message
    > news:...
    >> "BartC" <> writes:
    >>> "pozz" <> wrote in message
    >>> news:...
    >>>> On 23 Feb, 11:16, (Jens Thoms Toerring) wrote:
    >>>>> I would try as a first step to put the 'HZ / 1000' bit into
    >>>>> parentheses.
    >>>>
    >>>> Oh yes, in that way the compiler doesn't add multiplication and
    >>>> division instructions.
    >>>>
    >>>> But what happens if I declare HZ as 1500?
    >>>> x = x * (HZ / 1000);
    >>>
    >>> This is equivalent (ignoring overflows) to x = x*3/2.

    >> [...]
    >>
    >> No, it isn't. It's equivalent to
    >> x = x * (1500 / 1000);
    >> which is equivalent to
    >> x = x * 1;
    >>
    >> The parentheses matter a great deal in this case.

    >
    > I meant for the original code, which doesn't have them. Then, when HZ is
    > 1500, the calculation x*1500/1000 can be the same as x*3/2


    No, since x is unsigned, that's an invalid optimization unless the
    compiler can prove that the multiplication doesn't wrap around.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Feb 23, 2011
    #17
  18. pozz <> writes:
    > Il 23/02/2011 21:27, Keith Thompson ha scritto:
    >> pozz<> writes:
    >>> I have the following code:
    >>> ---
    >>> #define HZ 1000
    >>> unsigned int calc(unsigned int x) {
    >>> x = x * HZ / 1000;
    >>> }
    >>> void main(void) {
    >>> unsigned int y = calc(23);
    >>> ...
    >>> }
    >>> ---

    >>
    >> Since nobody else has mentioned it, main returns int, not void.

    >
    > In microcontroller environments, where an operating system lacks, the
    > main function never returns (it is THE operating system). So it returns
    > nothing and doesn't accept any arguments.


    Ah, ok. Let me clarify.

    In hosted implementations, main returns int *or* some
    implementation-defined type. An implementation can choose to support
    "void main(void)", but all implementations *must* support "int
    main(void)", and there's no good reason *in a hosted environment*
    to declare main as returning anything other than int.

    Some bad C references and tutorials wrongly declare main returning void.
    I assumed, incorrectly, that you had probably learned a bad habit from
    one of them. My apologies.

    In freestanding implementations, such as the one you're apparently
    using, the program entry point needn't return int -- and needn't
    even be called "main". "void main(void)" is perfectly correct in
    such an environment if that's what the implementation documents.

    (Most discussion here is about hosted environments; some of us tend
    to forget about freestanding environments.)

    >> Also, you mentioned in a followup that the missing return statement in
    >> calc() is present in your actual code. Please develop the habit of
    >> posting actual code, not a summary of it.

    >
    > I'm sorry. My code is complex and I had to simplify it just to show what
    > was my problem.


    Fair enough -- but it's still a good idea to compile, and test if
    possible, your simplified code before posting it.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Feb 23, 2011
    #18
  19. pozz

    BartC Guest

    "Keith Thompson" <> wrote in message
    news:...
    > "BartC" <> writes:
    >> "Keith Thompson" <> wrote in message


    >>> The parentheses matter a great deal in this case.

    >>
    >> I meant for the original code, which doesn't have them. Then, when HZ is
    >> 1500, the calculation x*1500/1000 can be the same as x*3/2

    >
    > No, since x is unsigned, that's an invalid optimization unless the
    > compiler can prove that the multiplication doesn't wrap around.


    It would only be invalid if the code is relying on overflow (or wraparound)
    to work properly, which sounds very unlikely.

    It sound more like they want to multiply a frequency expressed in Hz, by x,
    and have a result in kHz; wrapping around isn't really going to help things.

    In that case, scaling down the multiplier and divisor might well help out
    the compiler.

    --
    Bartc
     
    BartC, Feb 23, 2011
    #19
  20. pozz

    Willem Guest

    BartC wrote:
    )
    ) "Keith Thompson" <> wrote in message
    )> No, since x is unsigned, that's an invalid optimization unless the
    )> compiler can prove that the multiplication doesn't wrap around.
    )
    ) It would only be invalid if the code is relying on overflow (or wraparound)
    ) to work properly, which sounds very unlikely.

    The compiler doesn't know if the code is relying on overflow or not.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Feb 23, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kevin Flood
    Replies:
    0
    Views:
    1,034
    Kevin Flood
    Sep 8, 2004
  2. Kevin Flood
    Replies:
    1
    Views:
    2,771
    Kevin Flood
    Sep 13, 2004
  3. Corvus

    optimizing an expression

    Corvus, Oct 22, 2009, in forum: C Programming
    Replies:
    105
    Views:
    2,086
    Tim Rentsch
    Oct 28, 2009
  4. AMDx64BT
    Replies:
    2
    Views:
    1,016
    Peter Flynn
    Mar 8, 2011
  5. AMDx64BT
    Replies:
    0
    Views:
    882
    AMDx64BT
    Mar 8, 2011
Loading...

Share This Page