|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <algorithm> #include <ctime> #include <iostream> int main() { // Generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; // !!! コメントを外すと下のループ処理が速くなる // std::sort(data, data + arraySize); // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; } |
このプログラムは、コメントのsortを実行するようにすると、速く動くようになる。なぜなのか？
答えは、パイプラインの分岐予測だそうです。分岐予測は以前の実行から分岐を予測してパイプラインを組むため、ソートされていれば分岐予測は成功し、実行が早くなる。
ソートしていないと、分岐予測が多く失敗し、予測して組み上げたパイプラインを破棄しなければならなくなり、実行が遅くなる。
|
1 2 |
if (data[c] >= 128) sum += data[c]; |
上の部分を以下のように変えて、ifをなくす。
|
1 2 |
int t = (data[c] - 128) >> 31; sum += ~t & data[c]; |
そうすると分岐予測はなくなって、ソートしててもしなくても、同じくらいの速度で実行される。