這是一段 C 代碼，顯示了一些非常奇特的行為。
出于某種原因，對資料進行排序（在計時區域之前）奇跡般地使主回圈快了將近六倍：
#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
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; i)
{
for (unsigned c = 0; c < arraySize; c)
{ // Primary loop.
if (data[c] >= 128)
sum = data[c];
}
}
double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
}
- 如果沒有
std::sort(data, data arraySize);，代碼運行時間為 11.54 秒。 - 使用排序后的資料，代碼運行時間為 1.93 秒。
（排序本身比遍歷陣列花費更多的時間，所以如果我們需要為一個未知陣列計算它實際上不值得這樣做。）
最初，我認為這可能只是一種語言或編譯器例外，所以我嘗試了 Java：
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; i)
{
for (int c = 0; c < arraySize; c)
{ // Primary loop.
if (data[c] >= 128)
sum = data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " sum);
}
}
具有相似但不那么極端的結果。
我的第一個想法是排序將資料帶入
未排序
uj5u.com熱心網友回復：
這是一個分支預測失敗。您不需要對陣列進行排序，但只需要使用值對其進行磁區即可128。排序是n*log(n)，而磁區只是線性的。基本上，它只是快速排序磁區步驟的一次運行，其中的主元被選擇為128。不幸的是，在 C 中只有 nth_element 函式，它按位置而不是按值進行磁區。
這個問題的答案是它自動矢量化。像往常一樣，編譯器不會選擇完美的策略。（盡管 GCC 可能是 SSE2 或 SSE4 的最佳選擇。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/534988.html