Why is processing a sorted array faster than processing an unsorted array?

In this C++ code, sorting the data (before the timed region) makes the primary loop ~6x faster: #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; // !!! With this, the next loop runs faster. std::sort(data, data + arraySize); // Test clo

[ABA]

C++やJavaで配列をソートしておくと同じ処理が劇的に速くなる場合。ソート後に配列を扱うループ内の分岐予測が容易になるコードだと起こる

[darwinia]

branch prediction

[pcod]

あとで

[fcicq]

branch prediction