gdalgorithms-list

[Algorithms] Shifting or Multiplication....

[Alex M. <Am...@Bw...>]

    I was wondering if anyone could clear up something. Algorithmically, =
is bitshifting or using multiplication faster?? Now, I know this sounds =
like a subjective question, as some will undoubtadly say, it depends on =
the compiler and what it translates the code into. Lets take it down to =
the ASM level.

    Shifting, to me, looks like a 1 cycle operation.

    In this age, if the CPU can handle most MUL's almost as rapidly, is =
there a place for bitshifts? If so, then for what kinds of algo =
applications? Do we still need them to mask off bits in pixels colors?

Re: [Algorithms] Shifting or Multiplication....

[Corrinne Y. <cor...@ho...>]

Floating point multiplication can be fast on PC based systems. Some
compilers can choose to turn all your * 2 into << 1 automatically for you
for integers.

IMO nothing to get too stressed about. Whatever is readable and debuggable.
:)

Corrinne

----- Original Message -----
From: Alex Morano
To: gda...@li...
Sent: Saturday, December 23, 2000 2:38 PM
Subject: [Algorithms] Shifting or Multiplication....


    I was wondering if anyone could clear up something. Algorithmically, is
bitshifting or using multiplication faster?? Now, I know this sounds like a
subjective question, as some will undoubtadly say, it depends on the
compiler and what it translates the code into. Lets take it down to the ASM
level.

    Shifting, to me, looks like a 1 cycle operation.

    In this age, if the CPU can handle most MUL's almost as rapidly, is
there a place for bitshifts? If so, then for what kinds of algo
applications? Do we still need them to mask off bits in pixels colors?

Re: [Algorithms] Shifting or Multiplication....

[Neil S. <ne...@r0...>]

>     I was wondering if anyone could clear up something. Algorithmically,
is
> bitshifting or using multiplication faster?? Now, I know this sounds like
a
> subjective question, as some will undoubtadly say, it depends on the
> compiler and what it translates the code into. Lets take it down to the
ASM
> level.

It is reasonable to expect that, on most (all, AFAIK) systems, shifting will
be as fast or faster than a multiply, especially as integer multiplies are
done with a "shift-add" sequence on older CPUs. Therefore, in cases where it
is natural to do a shift (eg. masking values in a compound type, like a
color), a shift is a good thing to use. In other cases, as Corrine has
stated, it is nothing to get too stressed about.

- Neil

Re: [Algorithms] Shifting or Multiplication....

[Conor S. <cs...@tp...>]

> Floating point multiplication can be fast on PC based systems. Some
> compilers can choose to turn all your * 2 into << 1 automatically for you
> for integers.

A compiler somewhere probably does the same thing for floats, except with
additions/subtractions to the exponent.

I think that for integers an addition is still better, but I may be wrong.
But now a days, it doesn't make much difference.

I still use shifts reasonable often, but then again, I have uses for 2^x :)

>
> IMO nothing to get too stressed about. Whatever is readable and
debuggable.
> :)

Bingo :)

Conor Stokes

Re: [Algorithms] Shifting or Multiplication....

[R. J. S. <rj...@be...>]

> I think that for integers an addition is still better, but I may be wrong.
> But now a days, it doesn't make much difference.

This is the case for all modern processors except the P4.  On the P4 shifts
and multiplies are much slower than adds.

R. Jason Sams

Re: [Algorithms] Shifting or Multiplication....

[Ville M. <wi...@hy...>]

Modern compilers will turn your constant integer multiplications into
sequences of shifts, additions and similar instructions (such as 'lea' on
the x86), if the strength-reduced sequence is faster than the
single multiplication. Back in the bad old days, _anything_ was faster
than a mul op, nowadays two adds for a mul is probably a fair deal (x86
again); however, there are tons of other things that must be taken into
account (code size, register dependencies etc.), so no exact rules can
be given even for a specific processor... Let the compiler worry about
such things as it has more knowledge of the situation...

Similar strength reduction  happens for constant divisions of
powers-of-two (such as foo/4 --> foo>>2). You just have to keep
in mind that dividing a negative integer by a power-of-two is not the same
as right-shifting (though it is for positive values), so the compiler
needs to generate some extra code. Even with the extra code, the sequence
is faster than performing the division. However, you can optimize such a
sequence by either hand-writing the equation with right-shifts or by
casting the integer to unsigned (assuming you know it is positive in the
first place). A similar thing happens with modulas, i.e. foo%8 --> foo&7
reduction cannot be done (without extra code) if 'foo' may be negative.

As a rule of thumb, I use multiplications, divisions and modulas for all
arithmetics (which are always done with signed integers). I use shifts and
logical ands/ors/xors for all bitmask manipulation (unsigned ints). I
think that this separation makes the code more readable.

So, to answer the original question: I would definitely use shifts etc.
for pure integer pixel manipulation (as this falls into the category of
bitmasks), just to improve the readability of the code.

cheers,
-wili

Ville Miettinen
http://surrender3d.com/umbra

On Wed, 27 Dec 2000, Corrinne Yu wrote:

> Floating point multiplication can be fast on PC based systems. Some
> compilers can choose to turn all your * 2 into << 1 automatically for you
> for integers.
> 
> IMO nothing to get too stressed about. Whatever is readable and debuggable.
> :)
> 
> Corrinne
> 
> ----- Original Message -----
> From: Alex Morano
> To: gda...@li...
> Sent: Saturday, December 23, 2000 2:38 PM
> Subject: [Algorithms] Shifting or Multiplication....
> 
> 
>     I was wondering if anyone could clear up something. Algorithmically, is
> bitshifting or using multiplication faster?? Now, I know this sounds like a
> subjective question, as some will undoubtadly say, it depends on the
> compiler and what it translates the code into. Lets take it down to the ASM
> level.
> 
>     Shifting, to me, looks like a 1 cycle operation.
> 
>     In this age, if the CPU can handle most MUL's almost as rapidly, is
> there a place for bitshifts? If so, then for what kinds of algo
> applications? Do we still need them to mask off bits in pixels colors?
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Shifting or Multiplication....

[Pierre T. <p.t...@wa...>]

On plain Pentiums, shifting was 0.5 cycle in the U pipe only (so there =
was a 0.5 cycle latency if in the V pipe). Integer multiplications were =
about ~10 cycles. Nowadays, even if rules have changed, you shouldn't =
discard bitshifts :

1) you never know where your program will run in the end
2) using a bitshift for masks and similar things is conceptually clearer =
anyway. Keep your code clean!
3) you probably code in C/C++, and most of the time the compiler handles =
this for you anyway (*)
4) there's more to optimization than this :)
5) you can't do the same as SHLD / SHRD with muls, ah!

(*) As a reminder, even "slow" things like:

    int Value;
    ...
    Value*=3D5;

...are cleverly compiled using the good old LEA instruction (that is: =
without shifts or muls). Nowadays I would leave all those things to the =
compiler.


Pierre Terdiman      *   Home: p.t...@wa...
Coder in the dark    *   Zappy's Lair:  www.codercorner.com


  ----- Original Message -----=20
  From: Alex Morano=20
  To: gda...@li...=20
  Sent: Saturday, December 23, 2000 9:38 PM
  Subject: [Algorithms] Shifting or Multiplication....


      I was wondering if anyone could clear up something. =
Algorithmically, is bitshifting or using multiplication faster?? Now, I =
know this sounds like a subjective question, as some will undoubtadly =
say, it depends on the compiler and what it translates the code into. =
Lets take it down to the ASM level.
  =20
      Shifting, to me, looks like a 1 cycle operation.
  =20
      In this age, if the CPU can handle most MUL's almost as rapidly, =
is there a place for bitshifts? If so, then for what kinds of algo =
applications? Do we still need them to mask off bits in pixels colors?

Re: [Algorithms] Shifting or Multiplication....

[Conor S. <cs...@tp...>]

>On plain Pentiums, shifting was 0.5 cycle in the U pipe only (so there was
a 0.5 cycle latency if in the V pipe). Integer multiplications were about
~10 cycles. Nowadays, even if rules have changed, you shouldn't discard
bitshifts :

I believe that it was actually 3 cycles. But you could execute 6 adds in the
time to do 1 mul. But you are pretty much right.

I think the LEA takes the same time - But there was some advantage or other
to it :)

Conor Stokes

1) you never know where your program will run in the end
2) using a bitshift for masks and similar things is conceptually clearer
anyway. Keep your code clean!
3) you probably code in C/C++, and most of the time the compiler handles
this for you anyway (*)
4) there's more to optimization than this :)
5) you can't do the same as SHLD / SHRD with muls, ah!

(*) As a reminder, even "slow" things like:

    int Value;
    ...
    Value*=5;

...are cleverly compiled using the good old LEA instruction (that is:
without shifts or muls). Nowadays I would leave all those things to the
compiler.


Pierre Terdiman      *   Home: p.t...@wa...
Coder in the dark    *   Zappy's Lair:  www.codercorner.com


----- Original Message -----
From: Alex Morano
To: gda...@li...
Sent: Saturday, December 23, 2000 9:38 PM
Subject: [Algorithms] Shifting or Multiplication....


    I was wondering if anyone could clear up something. Algorithmically, is
bitshifting or using multiplication faster?? Now, I know this sounds like a
subjective question, as some will undoubtadly say, it depends on the
compiler and what it translates the code into. Lets take it down to the ASM
level.

    Shifting, to me, looks like a 1 cycle operation.

    In this age, if the CPU can handle most MUL's almost as rapidly, is
there a place for bitshifts? If so, then for what kinds of algo
applications? Do we still need them to mask off bits in pixels colors?