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?
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.
ReplyDeleteEither way, it's simply more work because the two operations do entirely different things, even if the outcome of certain operations is the same.
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.
ReplyDeleteSource: years of experience + computer science education
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.
ReplyDelete