Почему деление происходит медленнее, чем битхифтинг в C++?

Question

Я написал два фрагмента кода, один из которых делит случайное число на два, и тот, который сбрасывает одно и то же случайное число справа. Как я понимаю, это должно привести к такому же результату. Однако, когда я использую оба фрагмента кода, я последовательно получаю данные о том, что смена происходит быстрее. Почему это?

Shifting код:

double iterations = atoi(argv[1]) * 1000; 
int result = 0; 
cout << "Doing " << iterations << " iterations." << endl; 
srand(31459); 
for(int i=0;i<iterations;i++){ 
    if(i % 2 == 0){ 
     result = result + (rand()>>1); 
    }else{ 
     result = result - (rand()>>1); 
    } 
} 

Разделив код:

double iterations = atoi(argv[1]) * 1000; 
int result = 0; 
cout << "Doing " << iterations << " iterations." << endl; 
srand(31459); 
for(int i=0;i<iterations;i++){ 
    if(i % 2 == 0){ 
     result = result + (rand()/2); 
    }else{ 
     result = result - (rand()/2); 
    } 
} 

Сроки и результаты:

$ time ./divide 1000000; time ./shift 1000000 
Doing 1e+09 iterations. 

real 0m12.291s 
user 0m12.260s 
sys  0m0.021s 
Doing 1e+09 iterations. 

real 0m12.091s 
user 0m12.056s 
sys  0m0.019s 

$ time ./shift 1000000; time ./divide 1000000 
Doing 1e+09 iterations. 

real 0m12.083s 
user 0m12.028s 
sys  0m0.035s 
Doing 1e+09 iterations. 

real 0m12.198s 
user 0m12.158s 
sys  0m0.028s 

Addtional информация:

• Я не использую никаких оптимизаций при компиляции
• Я бег это на виртуализированной установку Fedora 20, керналь: 3.12.10-300.fc20.x86_64

Answer 1

Это не на самом деле медленнее. Я запустить тест, используя nonius так:

#define NONIUS_RUNNER 
#include "Nonius.h++" 

#include <type_traits> 
#include <random> 
#include <vector> 

NONIUS_BENCHMARK("Divide", [](nonius::chronometer meter) 
{ 
    std::random_device rd; 
    std::uniform_int_distribution<int> dist(0, 9); 

    std::vector<int> storage(meter.runs()); 
    meter.measure([&](int i) { storage[i] = storage[i] % 2 == 0 ? storage[i] - (dist(rd) >> 1) : storage[i] + (dist(rd) >> 1); }); 
}) 

NONIUS_BENCHMARK("std::string destruction", [](nonius::chronometer meter) 
{ 
    std::random_device rd; 
    std::uniform_int_distribution<int> dist(0, 9); 

    std::vector<int> storage(meter.runs()); 
    meter.measure([&](int i) { storage[i] = storage[i] % 2 == 0 ? storage[i] - (dist(rd)/2) : storage[i] + (dist(rd)/2); }); 
}) 

И вот результаты:

Как вы можете видеть, как из них шеи и декольте.

(Вы можете найти выход HTML here)

P.S: Кажется, я забыл переименовать второй тест. Виноват.

Answer 2

Это не; это медленнее в архитектуре, в которой вы работаете. Это почти всегда медленнее, потому что аппаратное обеспечение, связанное с переключением бит, тривиально, а разделение - это немного кошмар. В базе 10, что вам легче, 78358582354 >> 3 или 78358582354/85? Инструкции обычно принимают одинаковое время для выполнения независимо от ввода, и в вашем случае это компилятор задание для преобразования /2 в >>1; процессор просто делает, как сказано.

Answer 3

Кажется, что разница в resuls ниже, чем результат, поэтому вы не можете сказать, отличается ли это. Но вообще деление не может быть сделано в одиночной операции, бит сдвиг может, так что бит сдвиг обычно должен быть быстрее.

Но поскольку у вас есть буквальный 2 в вашем коде, я бы предположил, что компилятор, даже без оптимизации, создает идентичный код.

Answer 4

Отметьте, что rand возвращает int и делит int (подписанный по умолчанию) на 2 не совпадает с сдвигом на 1.Вы можете легко проверить сгенерированный ассемблер и увидеть разницу, или просто проверить полученный двоичный формат:

> g++ -O3 boo.cpp -c -o boo # divide 
> g++ -O3 foo.cpp -c -o foo # shift 
> ls -la foo boo 
... 4016 ... boo # divide 
... 3984 ... foo # shift 

Теперь добавьте static_cast патч:

if (i % 2 == 0) { 
    result = result + (static_cast<unsigned>(rand())/2); 
} 
else { 
    result = result - (static_cast<unsigned>(rand())/2); 
} 

и проверить размер снова:

> g++ -O3 boo.cpp -c -o boo # divide 
> g++ -O3 foo.cpp -c -o foo # shift 
> ls -la foo boo 
... 3984 ... boo # divide 
... 3984 ... foo # shift 

убедитесь, что вы можете проверить, что сгенерированный asm в обоих двоичных файлах одинаковый.