Optimizing the expression (x * 1000 / 1000)

[Jens Thoms Toerring]

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

Mmmm, doesn't mean "left-associative" in this case that the
multiplication must be done before the division? That's at
least my understanding of the term which, of course, can be
quite wrong. But if my understanding is correct then saying
that the "expression is evaluated left to right" can be con-
sidered (as a sentence derived from this, and as that it was
meant) to be ok?

Note that this is a peculiarity of unsigned integer arithmetic, which
is required to be modular.

Yes, that was a additional information I perhaps should have
mentioned.

For signed integers, overflow behavior is
undefined, so the compiler is free to optimize the expression by
assuming that it won't overflow.

Since the behaviour on overflow for signed integers is undefined
I would think that the compiler can do whatever it likes, i.e.
it can optimize but also can do something completely different...

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.

I wouldn't be prepared to bet much money on that this is what
all compilers will do (and the OP is obviously using some em-
bedded system, so there's a non-vanishing chance that he's not
using gcc)...
Regards, Jens

PS: Finally again some nit-picking discussion on clc - I really
was missing them, always learned a lot from them;-) Thanks!

 

[Keith Thompson]

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

Concretely, suppose UINT_MAX == 65535:

unsigned int x = 100;
x = x * 1500 / 1000;

Mathematically, x * 1500 yields 150000, but this is reduced modulo
(UINT_MAX + 1), yielding 18928. Dividing that by 1000 yields 18.
The compiler may not perform any optimization that would cause x
to be assigned a value other than 18.

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.

Then the code needs to be written to avoid wraparound.

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

Or using a type that's sufficiently wide that the intermediate results
don't wrap around. (Doing the analysis needed to guarantee this can be
non-trivial.)

 

[Lauri Alanko]

Mmmm, doesn't mean "left-associative" in this case that the
multiplication must be done before the division?

Not directly. Left-associativity just means that that "a * b / c"
equals "(a * b) / c" instead of "a * (b / c)". An indirect consequence
of this is that with many implementation techniques a multiplication
will be executed before a division, but that's not obligatory since
the implementation is free to calculate the result in whatever way it
finds appropriate. For instance, it could do the equivalent of:

a * (b / c) + (b % c) * (a / c) + ((a % c) * (b % c)) / c

But this is not really relevant here.

But if my understanding is correct then saying
that the "expression is evaluated left to right" can be con-
sidered (as a sentence derived from this, and as that it was
meant) to be ok?

No. That implies that the operands (a, b and c) are evaluated from
left to right, which is not at all guaranteed. In the example code
this wasn't relevant since all the operands were variables and
constants so there were no side effects during operand evaluation.

Since the behaviour on overflow for signed integers is undefined
I would think that the compiler can do whatever it likes, i.e.
it can optimize but also can do something completely different...

The compiler can do whatever it wants as long as it produces correct
results for non-overflowing integers.

I wouldn't be prepared to bet much money on that this is what
all compilers will do (and the OP is obviously using some em-
bedded system, so there's a non-vanishing chance that he's not
using gcc)...

The C standard doesn't talk about performance, so optimization
questions are by their nature implementation-specific. As long as we
don't know the exact implementation in question, the best we can do is
give hints about what common and reasonable implementations are likely
to be able to optimize.


Lauri

 

[Jens Thoms Toerring]

Not directly. Left-associativity just means that that "a * b / c"
equals "(a * b) / c" instead of "a * (b / c)". An indirect consequence
of this is that with many implementation techniques a multiplication
will be executed before a division, but that's not obligatory since
the implementation is free to calculate the result in whatever way it
finds appropriate. For instance, it could do the equivalent of:

a * (b / c) + (b % c) * (a / c) + ((a % c) * (b % c)) / c

But this is not really relevant here.

No. That implies that the operands (a, b and c) are evaluated from
left to right, which is not at all guaranteed. In the example code
this wasn't relevant since all the operands were variables and
constants so there were no side effects during operand evaluation.

Thanks, I see what you mean and stand corrected for not being
precise enough. The intention of what I wrote with "evaluated
from left to right" was that in this case the result would have
been the same as if the OP had written "(x * HZ) / 1000" (with
the possible consequence of an overflow the compuler can't for-
see) instead of "x * (HZ / 1000)" for which the compiler might
have noticed that the "HZ / 1000" part is just 1, thus allowing
it to optimize the whole thing out.

The compiler can do whatever it wants as long as it produces correct
results for non-overflowing integers.

The C standard doesn't talk about performance, so optimization
questions are by their nature implementation-specific. As long as we
don't know the exact implementation in question, the best we can do is
give hints about what common and reasonable implementations are likely
to be able to optimize.

Complete agreement here;-)
Regards, Jens

 

[Thad Smith]

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?

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

 

[Ben Pfaff]

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

Unless the compiler is *really* brain-dead, you can just write an
"if" statement, which I find easier to read than preprocessor
directives:

if (HZ % 1000 == 0) {
return (HZ / 1000) * x;
} else {
return x * HZ / 1000;
}

 

[Keith Thompson]

Unless the compiler is *really* brain-dead, you can just write an
"if" statement, which I find easier to read than preprocessor
directives:

if (HZ % 1000 == 0) {
return (HZ / 1000) * x;
} else {
return x * HZ / 1000;
}

I find this clearer:

if (HZ % 1000 == 0) {
return x * (HZ / 1000);
}
else {
return (x * HZ) / 1000;
}

Though I wouldn't bother unless I had a good reason to believe
that the performance penalty of the division is significant.

 

[Seebs]

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.

This is not necessarily the case. The signature for main() in a
freestanding environment is whatever the implementation says it is.

However, it's certainly not unheard of for them to stick with the
canonical form, and in any event, people are quite justified in assuming
that your program is for a hosted implementation, since nearly everything
is.

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

The suggestion wasn't to post the full original program -- just a complete
and compileable example that actually illustrates your question.

And that's the other reason to declare main in a conventional form -- so other
people can compile your code on desktop systems to try it out.

-s