질문 : 정렬되지 않은 배열을 처리하는 것보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?
다음은 매우 특이한 동작을 보여주는 C ++ 코드입니다. 이상한 이유로 데이터를 기적적으로 정렬하면 코드가 거의 6 배 빨라집니다.
#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 << std::endl;
std::cout << "sum = " << sum << std::endl;
}
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);
}
}
비슷하지만 덜 극단적 인 결과입니다.
첫 번째 생각은 정렬이 데이터를 캐시 로 가져 오는 것이었지만 배열이 방금 생성 되었기 때문에 얼마나 어리석은 지 생각했습니다.
- 무슨 일이야?
- 정렬되지 않은 배열을 처리하는 것보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?
코드는 몇 가지 독립적 인 용어를 요약하고 있으므로 순서는 중요하지 않습니다.
답변
당신은 분기 예측 실패의 희생자입니다.
철도 교차로를 고려하십시오.
이미지 : Wikimedia Commons를 통해 Mecanismo. CC-By-SA 3.0 라이선스에 따라 사용됩니다.
이제 논쟁을 위해 이것이 장거리 또는 무선 통신 이전 인 1800 년대로 거슬러 올라간다고 가정합니다.
당신은 교차로의 운영자이고 기차가 오는 소리를 듣습니다. 당신은 그것이 어느 방향으로 가야할지 전혀 모릅니다. 운전자에게 원하는 방향을 물어보기 위해 기차를 멈 춥니 다. 그런 다음 스위치를 적절하게 설정합니다.
기차는 무겁고 관성이 많습니다. 그래서 그들은 시작하고 느려지는 데 영원히 걸립니다.
더 좋은 방법이 있습니까? 기차가 어느 방향으로 갈지 짐작하세요!
- 맞았 으면 계속됩니다.
- 추측이 틀리면 기장이 멈추고 뒤로 물러나고 소리를 지르며 스위치를 뒤집습니다. 그런 다음 다른 경로로 다시 시작할 수 있습니다.
매번 맞으면 기차가 멈출 필요가 없습니다.
너무 자주 잘못 추측 하면 기차는 정지, 백업 및 재시작에 많은 시간을 소비합니다.
if- 문을 고려하십시오 . 프로세서 수준에서 분기 명령입니다.
당신은 프로세서이고 분기를 봅니다. 당신은 그것이 어느 방향으로 갈지 전혀 모릅니다. 너 뭐하니? 실행을 중지하고 이전 지침이 완료 될 때까지 기다립니다. 그런 다음 올바른 경로를 계속합니다.
최신 프로세서는 복잡하고 파이프 라인이 길다. 그래서 그들은 "워밍업"과 "슬로우 다운"에 영원히 걸립니다.
더 좋은 방법이 있습니까? 가지가 어느 방향으로 갈지 짐작하세요!
- 맞았다면 계속 실행합니다.
- 잘못 추측했다면 파이프 라인을 플러시하고 브랜치로 롤백해야합니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.
매번 맞히면 실행을 멈출 필요가 없습니다.
너무 자주 잘못 추측 하면 지연, 롤백 및 재시작에 많은 시간을 소비하게됩니다.
이것이 분기 예측입니다. 나는 기차가 깃발로 방향을 알릴 수 있기 때문에 이것이 최고의 비유가 아니라는 것을 인정합니다. 그러나 컴퓨터에서 프로세서는 마지막 순간까지 분기가 어느 방향으로 갈 것인지 알지 못합니다.
그렇다면 기차가 다른 경로로 후진하고 내려 가야하는 횟수를 최소화하기 위해 전략적으로 어떻게 추측 하시겠습니까? 당신은 과거의 역사를 본다! 기차가 99 %의 시간 동안 왼쪽으로 가면 왼쪽으로 추측합니다. 번갈아 가며 번갈아 가며 추측하십시오. 세 번에 한 번만 가면 똑같아요 ...
즉, 패턴을 식별하고 따르려고합니다. 이것은 분기 예측자가 작동하는 방식입니다.
대부분의 응용 프로그램에는 잘 작동하는 분기가 있습니다. 따라서 최신 분기 예측기는 일반적으로 90 % 이상의 적중률을 달성합니다. 그러나 인식 할 수없는 패턴이없는 예측할 수없는 분기에 직면하면 분기 예측자는 사실상 쓸모가 없습니다.
추가 읽기 : Wikipedia의 "분기 예측 자"기사 .
if (data[c] >= 128)
sum += data[c];데이터는 0과 255 사이에 균등하게 분포되어 있습니다. 데이터가 정렬 될 때 대략 반복의 전반부는 if 문을 입력하지 않습니다. 그 후에는 모두 if 문에 들어갑니다.
분기가 같은 방향으로 여러 번 연속적으로 이동하므로 분기 예측기에 매우 친숙합니다. 단순한 포화 카운터조차도 방향을 전환 한 후 몇 번의 반복을 제외하고 분기를 올바르게 예측합니다.
빠른 시각화 :
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
그러나 데이터가 완전히 임의적이면 임의 데이터를 예측할 수 없기 때문에 분기 예측기가 쓸모 없게됩니다. 따라서 아마도 약 50 %의 잘못된 예측이있을 것입니다 (무작위 추측보다 낫지 않음).
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
그래서 무엇을 할 수 있습니까?
컴파일러가 분기를 조건부 이동으로 최적화 할 수없는 경우 성능을 위해 가독성을 희생하려는 경우 몇 가지 해킹을 시도 할 수 있습니다.
바꾸다:
if (data[c] >= 128)
sum += data[c];
와:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
이렇게하면 분기가 제거되고 일부 비트 연산으로 대체됩니다.
(이 해킹은 원래의 if 문과 완전히 동일하지는 않지만이 경우 data[] 의 모든 입력 값에 대해 유효합니다.)
벤치 마크 : Core i7 920 @ 3.5GHz
C ++-Visual Studio 2010-x64 릴리스
자바-NetBeans 7.1.1 JDK 7-x64
관찰 :
- Branch와 함께 : 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.
- 해킹 사용 : 정렬 된 데이터와 정렬되지 않은 데이터간에 차이가 없습니다.
- C ++의 경우 데이터가 정렬 될 때 해킹이 분기보다 실제로 약간 느립니다.
경험의 일반적인 규칙은 중요한 루프 (예 :이 예)에서 데이터 종속 분기를 피하는 것입니다.
최신 정보:
-O3또는-ftree-vectorize하는 GCC 4.6.1은 조건부 이동을 생성 할 수 있습니다. 따라서 정렬 된 데이터와 정렬되지 않은 데이터간에 차이가 없습니다. 둘 다 빠릅니다. (또는 다소 빠름 : 이미 분류 된 경우,cmovadd대신 중요한 경로에 배치하는cmov가 2주기 지연이있는 Broadwell 이전의 Intel에서 cmov가 더 느려질 수 있습니다. gcc 최적화 플래그 -O3는 코드를 느리게 만듭니다. -O2보다 )/Ox하에서도이 분기에 대한 조건부 이동을 생성 할 수 없습니다.- 인텔 C ++ 컴파일러 (ICC) 11은 기적적인 일을합니다. 두 루프를 교환하여 예측할 수없는 분기를 외부 루프로 끌어 올립니다. 따라서 잘못된 예측에 영향을받지 않을뿐만 아니라 VC ++ 및 GCC가 생성 할 수있는 것보다 두 배 빠릅니다! 즉, ICC는 테스트 루프를 활용하여 벤치 마크를 무너 뜨 렸습니다.
- 인텔 컴파일러에 분기없는 코드를 제공하면 완전히 벡터화하고 분기와 마찬가지로 빠릅니다 (루프 교환 사용).
이것은 성숙한 현대 컴파일러조차도 코드를 최적화하는 능력이 크게 다를 수 있음을 보여줍니다.
출처 : https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
'프로그래밍 언어 > C++' 카테고리의 다른 글
| __name__ == “__main__”: 하면 어떻게 될까? (0) | 2021.07.02 |
|---|---|
| C ++에서 변수 데이터 타입을 출력 하는 법 (0) | 2021.07.01 |
| C ++ 코드 파일 확장자 .cc와 .cpp의 차이점 (0) | 2021.06.30 |
| C ++에서 구조체와 클래스의 차이점 (0) | 2021.06.29 |
| C ++ 표준은 초기화되지 않은 bool이 프로그램을 충돌시키는 것을 허용할까? (0) | 2021.06.27 |