>> to accelerate division

[Michael Mair]

Any why should it do nothing?

Well, it does something -- but that has no effect for the rest
of the program (and probably will get optimised away), whereas
i >>= 1;
has an effect for i != 0.

Again?

Indeed.


Cheers
Michael

 

[CBFalconer]

Simply get them to show you experimental evidence that one is
quicker than the other. Or show them evidence that there is no
difference. Or compile via assembly and see what the compiler
does with those two statements.

Sounds to me like your organisation is placing an inappropriate
value on premature optimisation.

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.

What is your firm? I may want to sell its stock short.

 

[Chris Croughton]

Simply get them to show you experimental evidence that one is quicker
than the other. Or show them evidence that there is no difference. Or
compile via assembly and see what the compiler does with those two
statements.

On all possible compilers and output processors (that doesn't mean
'all', only all those which might be used for compiling our code)? They
say "Coding standards"...

Sounds to me like your organisation is placing an inappropriate value on
premature optimisation.

Yup. And there's so much other inefficiency that it makes no difference
at all...

Chris C

 

[Chris Croughton]

[ shift versus multiply/divide ]

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.

Not possible on the targets (embedded processors). But showing that the
code generated is the same (for various compilers/targets) doesn't seem
to convince them.

What is your firm? I may want to sell its stock short.

I'm taking the Fifth <g>. But I doubt you have any stock of theirs
anyway. I haven't either...

Chris C

 

[Andrey Tarasevich]

Not unlikely. There are a lot of processors that have signed preserved or
arithmetic shift operations.

That's still not enough. It is already been mentioned that
sign-preserving shift implements "modulo-preserving" division (for
example, -5 >> 1 gives -3) while regular '/' implements a "round to
zero" division, as required by C99 and recommended by C89/C90 and C++
standards (for example, -5/2 gives -2). That's what I meant in my
previous message.

 

[Thomas G. Marshall]

Chris Croughton coughed up:

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

This discussion on accomplishing division with shifts is a good one!

 

[Chris Croughton]

Chris Croughton coughed up:

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

Which, I suspect, is what they are thinking of. However any modern C
compiler which targets those chips should optimise correctly anyway (and
indeed optimisation is likely to be even more essential for those
platforms). Indeed, such platforms often don't even have a multiply
instruction and more of them don't have a divide (I spent many years
working on 8080, Z80, 6803, H8 and similar processors).

This discussion on accomplishing division with shifts is a good one!

Indeed, I hadn't heard of the "multiply by large number and adjust"
algorithms before (and even after reading some articles on them I'm not
convinced).

Chris C

 

[Keith Thompson]

Any why should it do nothing?

[...]

Because it has no side effects (it doesn't modify i), and the result
of the expression isn't used. Perhaps you're thinking of
i >>= 1;

 

[Andrey Tarasevich]

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

If by "platforms" you really mean "implementations", i.e. C compilers
available for that hardware (which is actually what the word "platform"
really means in C lingo), then I can agree with you. A separate question
in this case would be whether better implementations are available on
these platforms.

However, the fact that you mention 8-bitness of chips suggests that
under "platforms" you really understand the actual hardware [platforms].
In this case I disagree. Bad performance of explicit
multiplication/division in comparison with shifts is purely
implementation's fault. Hardware doesn't define anything here. There's
nothing that forbids the existence of a compiler that is able to
implement multiplication/division in the most efficient way for this
bottom-dwelling hardware platform.

 

[Christian Bau]

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Tell them they shouldn't try to save nanoseconds, they should try to
save microseconds

If anyone asks you to replace x*2 with x<<1 because it is faster, just
ask them if they profiled it. If they haven't profiled it, write x*2.

 

[E. Robert Tisdale]

Also, depending on the hardware,
'i * 24' may be faster than '(i<<4) + (i<<3)' ... assuming that
your machine didn't optimize the code into the same thing...

> cat f5.c

int f(int i) {
return i*24;
}

> gcc -Wall -std=c99 -pedantic -S f5.c
> cat f6.c

int f(int i) {
return (i << 4) + (i << 3);
}

> gcc -Wall -std=c99 -pedantic -S f6.c
> diff --side-by-side --width=68 f5.s f6.s

.file "f5.c" | .file "f6.c"
.text .text
.globl f .globl f
.type f, @function .type f, @function
f: f:
pushl %ebp pushl %ebp
movl %esp, %ebp movl %esp, %ebp

> movl 8(%ebp), %eax
> sall $4, %eax

movl 8(%ebp), %edx movl 8(%ebp), %edx
movl %edx, %eax | sall $3, %edx
addl %eax, %eax <
addl %edx, %eax addl %edx, %eax
sall $3, %eax <
popl %ebp popl %ebp
ret ret
.size f, .-f .size f, .-f
.section .note .section .note
.ident "GCC: (GNU) 3 .ident "GCC: (GNU) 3

 

[Flash Gordon]

[ shift versus multiply/divide ]

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.

Not possible on the targets (embedded processors). But showing that
the code generated is the same (for various compilers/targets) doesn't
seem to convince them.

If seeing that the generated code is the same does not convince them
then it is probably a lost cause, so I suggest you start looking for a
job somewhere better.

However, you might want to point out that with a right shift for
division they could get rather unexpected results with negative numbers.

I'm taking the Fifth <g>. But I doubt you have any stock of theirs
anyway. I haven't either...

Possibly a good idea.

 

[Mark McIntyre]

we usually use <<n as a cheaper option to multiplication when its
factor of 2^n right,

We do, but its quite probable that these days, we're wrong. If your
compiler isn't capable of doing this optimization for you, its a poor
compiler.

 

[Stephen Sprunk]

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n

doubt is there a cheaper option to i/24 ==> i/(16+8) ==> ????????
or i/72.....

also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication

If you have a reasonably good optimizing compiler, it should do this
"strength reduction" for you. Keep your original intent (the division) in
the code unless you're sure you're using a broken compiler _and_ you'd done
some profiling to know it'll be worth the risks.

S

 

[Andrey Tarasevich]

That's still not enough. It is already been mentioned that
sign-preserving shift implements "modulo-preserving" division (for
example, -5 >> 1 gives -3)

It is worth noting that the above applies to 2's-complement platforms.

 

[Thomas G. Marshall]

Chris Croughton coughed up:

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

This discussion on accomplishing division with shifts is a good one!

PS. It is bad form to set followups to limit the scope of a crosspost
without announcing that you've done so.

 

[Thomas G. Marshall]

Andrey Tarasevich coughed up:

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh,
small 8 bit chips, etc.

If by "platforms" you really mean "implementations", i.e. C compilers
available for that hardware (which is actually what the word
"platform" really means in C lingo), then I can agree with you. A
separate question in this case would be whether better
implementations are available on these platforms.

However, the fact that you mention 8-bitness of chips suggests that
under "platforms" you really understand the actual hardware
[platforms]. In this case I disagree. Bad performance of explicit
multiplication/division in comparison with shifts is purely
implementation's fault. Hardware doesn't define anything here. There's
nothing that forbids the existence of a compiler that is able to
implement multiplication/division in the most efficient way for this
bottom-dwelling hardware platform.

I suppose you're right. I should have been more clear--this is what I meant
to say, being all wordy smurdy :

Learning bit shifts combinations for non power of 2 arithmetic is very
useful, and a strong understanding of it is desirable outside of any
particular language, and required in assembler on low-frills chips that know
neither how to multiply nor divide.

My 6502 and z80 background brings to mind all kinds of unavoidable
mathematical hoohah....

 

[Villy Kruse]

We do, but its quite probable that these days, we're wrong. If your
compiler isn't capable of doing this optimization for you, its a poor
compiler.

Such pinhole optimization has been common for at least 15 years.
Even multiply by 10 could be optimized as a couple of shifts and add
and this has been implemented by compilers. Perhaps computers these
days have very fast multiply instructions so such optimization would
actualy result in slower code.

Villy

 

[Charlie Gordon]

On Wed, 08 Dec 2004 09:09:03 +0100, Charlie Gordon wrote:

...


In C you can use >> on an unsigned integer type to achieve this. Java
doesn't have unsigned integer types so requires a different approach.

You are missing my point.
In order to force unsigned right shift on a signed type, you have to cast the
left operand to the corresponding unsigned type, but this cannot be done without
explicit knowledge of said type. If the type of the left operand later changes
to a different size (char/short/int/long/long long) the cast may go unnoticed
and will produce incorrect results. There is a similar issue when comparing
signed expressions to unsigned ones : you cannot force signed comparison
semantics without explicit casts where the type must be known and maintained.
There are ways to fix this:
- disallowing unsigned and signed to be used without a size specifier (too
strong)
- changing the semantics of (signed) and (unsigned) casts to only convert
between compatible types, not assuming int size.
- adding extra operators such as java's unsigned right shift operator: >>>

 

[Charlie Gordon]

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Here is THE solution :
- For the specific example above, where x is a variable, on can use "x + x".
- Using << instead of * is error prone because of precedence issues:
"y + x * 2 + z" is quite different from "y + x << 1 + z".
Using << when thinking multiplication is a good way to create bugs.
A well configured C compiler might emit a warning.
- Last but not least : x << 1 is undefined behaviour for x signed and negative !
Let me quote C99 6.5.7 verse 4:

"The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are
filled with
zeros. If E1 has an unsigned type, the value of the result is E1 x 2^E2, reduced
modulo
one more than the maximum value representable in the result type. If E1 has a
signed
type and nonnegative value, and E1 x 2^E2 is representable in the result type,
then that is
the resulting value; otherwise, the behavior is undefined."

For signed x with a negative value :
x << n is UNDEFINED BEHAVIOUR
the value of x >> n is implementation-defined.

Conclusion: Only use << and >> when dealing with bits on unsigned types.