9

Where it's possible to do so, I'm wondering if it's faster to replace a single multiplication with a bitshift followed by an integer division. Say I've got an int k and I want to multiply it by 2.25.

What's faster?

int k = 5;
k *= 2.25;
std::cout << k << std::endl;

or

int k = 5;
k = (k<<1) + (k/4);
std::cout << k << std::endl;

Output

11
11

Both give the same result, you can check this full example.

31
  • 4
    Is k an integer or a float?
    – user149341
    Jun 1, 2014 at 21:16
  • 3
    "What's faster": there is an easy way to find out... Jun 1, 2014 at 21:18
  • 6
    @Jongware: Plus impossible ;) Jun 1, 2014 at 21:22
  • 7
    Also, it you're willing to use bitshift, why not both ways? k = (k<<1) + (k>>2);?
    – AntonH
    Jun 1, 2014 at 21:23
  • 9
    Since this is highly architecture-dependent, I would let the compiler optimize the code. I am quite sure a compiler is smarter than most humans on modern architectures because of the many constraints from instruction set, pipelining, instruction units etc.
    – Jens
    Jun 1, 2014 at 21:27

4 Answers 4

10

The first attempt

I defined functions regularmultiply() and bitwisemultiply() as follows:

int regularmultiply(int j)
{
    return j * 2.25;
}

int bitwisemultiply(int k)
{
    return (k << 1) + (k >> 2);
}

Upon doing profiling with Instruments (in XCode on a 2009 Macbook OS X 10.9.2), it seemed that bitwisemultiply executed about 2x faster than regularmultiply.

enter image description here

The assembly code output seemed to confirm this, with bitwisemultiply spending most of its time on register shuffling and function returns, while regularmultiply spent most of its time on the multiplying.

regularmultiply:

enter image description here

bitwisemultiply:

enter image description here

But the length of my trials was too short.

The second attempt

Next, I tried executing both functions with 10 million multiplications, and this time putting the loops in the functions so that all the function entry and leaving wouldn't obscure the numbers. And this time, the results were that each method took about 52 milliseconds of time. So at least for a relatively large but not gigantic number of calculations, the two functions take about the same time. This surprised me, so I decided to calculate for longer and with larger numbers.

The third attempt

This time, I only multiplied 100 million through 500 million by 2.25, but the bitwisemultiply actually came out slightly slower than the regularmultiply.

The final attempt

Finally, I switched the order of the two functions, just to see if the growing CPU graph in Instruments was perhaps slowing the second function down. But still, the regularmultiply performed slightly better:

enter image description here

Here is what the final program looked like:

#include <stdio.h>

int main(void)
{
    void regularmultiplyloop(int j);
    void bitwisemultiplyloop(int k);

    int i, j, k;

    j = k = 4;
    bitwisemultiplyloop(k);
    regularmultiplyloop(j);

    return 0;
}

void regularmultiplyloop(int j)
{
    for(int m = 0; m < 10; m++)
    {
        for(int i = 100000000; i < 500000000; i++)
        {
            j = i;
            j *= 2.25;
        }
        printf("j: %d\n", j);
    }
}

void bitwisemultiplyloop(int k)
{
    for(int m = 0; m < 10; m++)
    {
        for(int i = 100000000; i < 500000000; i++)
        {
            k = i;
            k = (k << 1) + (k >> 2);
        }
        printf("k: %d\n", k);
    }
}

Conclusion

So what can we say about all this? One thing we can say for certain is that optimizing compilers are better than most people. And furthermore, those optimizations show themselves even more when there are a lot of computations, which is the only time you'd really want to optimize anyway. So unless you're coding your optimizations in assembly, changing multiplication to bit shifting probably won't help much.

It's always good to think about efficiency in your applications, but the gains of micro-efficiency are usually not enough to warrant making your code less readable.

9
  • You may just be testing the compiler's ability to recognize that only the final result from the loop is kept, throwing away the looping altogether. You need to check the assembly output for those cases too. Jun 2, 2014 at 18:19
  • @MarkRansom If you look at the code, it doesn't multiply the same value repeatedly. It does 100 million through 500 million sequentially and then repeats. Jun 2, 2014 at 18:30
  • 3
    @MarkRansom The performance that was measured is in the expected range for the loops being present. If the compiler had optimized them out, the runtime would have been much shorter. Jun 2, 2014 at 18:32
  • 1
    The assembler code in those two images looks like you compiled with -O0. Consequently, the bitwise multiply does more stack accesses as it manipulates more intermediate values. And that makes it slow, even though these stack accesses are completely unnecessary. If you compile with -O2 or -Os, the picture should change drastically. Jun 2, 2014 at 18:58
  • 3
    No, default is no optimization, which is the same as -O0. Jun 2, 2014 at 19:10
4

Indeed it depends on a variety of factors. So I have just checked it by running and measuring time. So the string we are interested in takes only a few instructions of CPU which is very fast so I have wrapped it into the cycle - multiplied the execution time of one code by a big number, and I got the k *= 2.25; is about in 1.5 times slower than k = (k<<1) + (k/4);. Here is my two codes to comapre:

prog1:

#include <iostream>
using namespace std;

int main() {

int k = 5;
for (unsigned long i = 0; i <= 0x2fffffff;i++)
 k = (k<<1) + (k/4);
cout << k << endl;

return 0;
}

prog 2:

#include <iostream>
using namespace std;

int main() {

int k = 5;
for (unsigned long i = 0; i <= 0x2fffffff;i++)
 k *= 2.25;
cout << k << endl;

return 0;
}

Prog1 takes 8 secs and Prog2 takes 14 secs. So by running this test with you architecture and compiler you can get the result which is correct to your particular environment.

0
3

That depends heavily on the CPU architecture: Floating point arithmetic, including multiplications, has become quite cheap on many CPUs. But the necessary float->int conversion can bite you: on POWER-CPUs, for instance, the regular multiplication will crawl along due to the pipeline flushes that are generated when a value is moved from the floating point unit to the integer unit.

On some CPUs (including mine, which is an AMD CPU), this version is actually the fastest:

k *= 9;
k >>= 2;

because these CPUs can do a 64 bit integer multiplication in a single cycle. Other CPUs are definitely slower with my version than with your bitshift version, because their integer multiplication is not as heavily optimized. Most CPUs aren't as bad on multiplications as they used to be, but a multiplication can still take more than four cycles.

So, if you know which CPU your program will run on, measure which is fastest. If you don't know, your bitshift version won't perform badly on any architecture (unlike both the regular version and mine), which makes it a really safe bet.

0
1

It highly depends on what hardware are you using. On modern hardware floating point multiplications may run way faster than integer ones, so you might want to change the entire algorithm and start using doubles instead of integers. If you're writing for modern hardware and you have a lot of operations like multiplying by 2.25, I'd suggest using double rather than integers, if nothing else prevents you from doing that.

And be data driven - measure performance, because it's affected by compiler, hardware and your way of implementing your algorithm.

16
  • 2
    "On modern hardware floating point multiplications may run way faster than integer ones"... really? Do you have a reference for this? I was never aware of this...
    – user541686
    Jun 2, 2014 at 7:16
  • Sure. Just made measurements on my Mac Book: gist.github.com/avshabanov/b4960e95c8b68575ad27 Note: For fair comparison I compared double multiplication vs long long multiplication+shift right to emulate non-integer multiplications with integer primitive types.
    – Alex
    Jun 2, 2014 at 17:35
  • 1
    @Mehrdad It's certainly possible if you consider auto-vectorization. At the extreme, a Haswell processor can do 8 DP-MUL/cycle via dual-issue AVX multiply. But Haswell can only do one 64-bit integer multiply each cycle. There is no SIMD for 64-bit integer multiply.
    – Mysticial
    Jun 2, 2014 at 18:47
  • @Mehrdad Yes, he is right that floating point multiplications can be faster than integer multiplications. Probably has to do with the fact that floating point multiplications are essential to get high machoflop... pardon, gigaflop numbers. Jun 2, 2014 at 18:49
  • @Mehrdad A 64-bit integer multiplication has to compute 128 bits of results. A double-precision multiplication only needs to compute a 53-bit significand. The influence of the exponent parts over the result is trivial to compute. Jun 2, 2014 at 18:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.