Как умножение может быть быстрее, чем сдвиг бит влево?
Хорошо известно, что смещение битов влево происходит быстрее, чем умножение, поскольку бочкообразные переключатели реализуются непосредственно в оборудовании. Следовательно, этот простой тест должен быть неправильным:
$start = 1;
$timestart = microtime(1);
for ($i = 0; $i < 10000000; $i++) {
$result2 = $start << 2;
}
echo microtime(1) - $timestart;
$timestart = microtime(1);
for ($i = 0; $i < 10000000; $i++) {
$result1 = $start * 4;
}
echo microtime(1) - $timestart;
echo "\n";
Потому что я выполнял это несколько раз, и всегда умножение происходило быстрее, чем сдвиг битов влево. Например:
+0,73733711242676
+0,71091389656067
Следовательно, либо эталонный тест неверен, либо интерпретатор PHP что-то здесь делает. Тест выполняется PHP 7.0.32, работающим в Ubuntu:
PHP 7.0.32-0ubuntu0.16.04.1 (cli) (NTS)
Процессор: Intel® Core ™ TM процессор i5-4460 с тактовой частотой 3,20 ГГц
Редактировать:
Выполнение его в Windows-коробке с почти таким же процессором (Intel® Core® TM i5-4460S CPU @ 2,90 ГГц) дает ожидаемые результаты:
+0,24960112571716
+0,28080010414124
Версия PHP для этого случая отличается:
PHP 7.1.19 (cli) (сборка: 20 июня 2018 г., 23:24:42) (ZTS MSVC14 (Visual C ++ 2015) x64)
Решение
Ваши рассуждения об оборудовании в основном не имеют значения. Вы используете устный перевод, где большая часть расходов — накладные расходы переводчика.
Asm-версия любого цикла может работать со скоростью 1 за такт (при условии сдвига с фиксированным счетом), поэтому только 100 000 итераций потребуют (на процессоре 3 ГГц) 0,033 мс или 0,000033 секунды, что примерно в 250 раз быстрее, чем время PHP.
Кроме того, интерпретируемый цикл должен использовать сдвиг счетчика переменных (потому что он не может JIT-компилировать счетчик сдвигов в непосредственный в машинном коде), что на самом деле более дорого для пропускной способности (3 моп) в процессорах Intel из-за Базовый багаж x86 (семантика флага). Процессоры AMD имеют сдвиги по одной мопе даже при переменном числе сдвигов. (shl reg, cl против shr reg, imm8). Увидеть Инструкция INC против ADD 1: это имеет значение? больше о том, почему shl reg,cl 3 мопа в семействе Sandybridge и как он может создать ложную зависимость с помощью флагов)
Умножение целых чисел составляет 1 мегапиксель, пропускная способность 1 тактовая частота, задержка 3 цикла, для семейств Intel Sandybridge и AMD Ryzen. Я за 2 часа на AMD Bulldozer-семье, не полностью конвейерной. Так что да, умножение имеет большую задержку, но они оба полностью конвейерны для пропускной способности. Ваш цикл отбрасывает результат, поэтому цепочка зависимостей, переносимых циклами, отсутствует, поэтому задержка не имеет значения (и скрыта при выполнении вне очереди).
Но этой незначительной разницы (2 дополнительных мопа) недостаточно, чтобы учесть измеренную разницу. Фактическое смещение или умножение составляет всего 1/250 от общего числа циклов, которые проходит цикл. Вы говорите, что переключение порядка циклов не меняет результат, так что это не просто эффект разогрева, пока ваш процессор не разгонится до максимальной тактовой частоты.
Вы не упомянули, на какой микроархитектуре ЦП вы работаете, но ответ, вероятно, не зависит от того, как декодируются команды сдвига или умножения.
Другие решения
Других решений пока нет …
detector