Optimizing the expression (x * 1000 / 1000)

P

pozz

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?
 
J

Jens Thoms Toerring

pozz said:
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
 
P

pozz

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);
 
J

James Kuyper

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

James Kuyper

I have the following code:

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

Willem

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
 
B

BartC

pozz said:
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.
 
J

James Kuyper

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

pozz

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

Jens Thoms Toerring

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
 
R

Roberto Waltman

Jens said:
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.
 
K

Keith Thompson

pozz said:
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.
 
K

Keith Thompson

BartC said:
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.
 
L

Lauri Alanko

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
 
B

BartC

Keith Thompson said:
BartC said:
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
 
K

Keith Thompson

BartC said:
Keith Thompson said:
BartC said:
On 23 Feb, 11:16, (e-mail address removed) (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.
 
K

Keith Thompson

pozz said:
Il 23/02/2011 21:27, Keith Thompson ha scritto:

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

BartC

Keith Thompson said:
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.
 
W

Willem

BartC wrote:
)
)> 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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top