CODEWITHSUNDEEP
phpbit-shiftmultiplication
aki
aki

Reputation: 1241

shift bits vs multiply in PHP

I have the following code:

<?php
$start = 1;

$timestart = microtime(1);
for ($i = 0; $i < 1000000; $i++) {
    $result1 = $start * 4;
}
echo "\n";
echo microtime(1) - $timestart;
echo "\n";

$timestart = microtime(1);
for ($i = 0; $i < 1000000; $i++) {
    $result2 = $start << 2;
}
echo "\n";
echo microtime(1) - $timestart;
echo "\n";

This outputs: 

0.14027094841003

0.12061500549316

I found on the Internet a Google interview question (which I wanted to apply for a developer, but I realize I can't), and one of the questions asked what the fastest way was to multiply a number. My first thought was to use the * sign, so I tested it.

My question is, why is shifting bits faster than multiplication?

Upvotes: 21

Views: 1548

Answers (3)

ChrisWue
ChrisWue

Reputation: 19020

On Intel sandybrigde CPUs it seems a shift with immediate costs about 1 clock cycle while a multiplication takes about 3-4 cycles. Apparently the whole program performance is affected by more factors than just the raw multiplication but it is enough of making a difference. Most compilers these days optimize multiplication by constants 2^n to shifts (compiler writers love to optimize your code :)) but maybe the PHP interpreter doesn't.

Upvotes: 1

deceze
deceze

Reputation: 522250

Because bit shifting is something the computer does all the time in hardware, it's a no-brainer for the CPU. Multiplying arbitrary numbers is something more difficult, because it can't necessarily be done using simple bit shifting but requires actual work. Multiplying a small integer by 4 happens to be an operation that's identical to a left-shift by 2. But even if the compiler/runtime/CPU optimizes this operation down to a bit shift, some code first needs to recognize that it can be optimized this way, which is more work than a simple bit shift itself.

Either way, it's simply more work because the two operations do entirely different things, even if the outcome of certain operations is the same.

Upvotes: 16

taz
taz

Reputation: 1526

Because a bit shift is an operation that can be implemented directly in hardware, whereas hardware rarely has multiplication operations implemented directly. Multiplication by a power of two can be achieved with a few simple logic gates, whereas multiplication by arbitrary multiplicands requires at the very least several multiplications by powers of two plus an add-to-self operation stacked on top of each other (5 = 2 * 2 + 1). I don't know if the PHP language specifically implements a shift operation by using whatever low-level calls are available, but I would be surprised if it doesn't.

Source: years of experience + computer science education

Upvotes: 13

Related Questions