왜 정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 빠른가요?

C++ 코드에서 데이터를 정렬하는 것은 (시간 범위 앞에서) 주된 루프의 속도를 약 6배 빠르게 만듭니다.

#@!'#include

#include

#include

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(clock()-start) / CLOCKS_PER_SEC;

std::cout << elapsedTime << '\n';

std::cout << "sum = " << sum << '\n';

}

'#@!

!@##@!'std::sort(data, data + arraySize);'!@##@! 와 함께하면 코드는 11.54초에 실행됩니다.

정렬된 데이터로 코드 실행 시 1.93초가 걸립니다.

(배열을 한 번 훑는 것보다 정렬하는 것 자체가 더 많은 시간이 걸리므로, 알려지지 않은 배열에 대해 이를 계산해야 한다면 실제로 할 가치가 없다.)

처음에는 이건 단지 언어나 컴파일러의 이상일수도 있겠다고 생각해서 자바를 시도해보았습니다.

#@!'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);

}

}

'#@!

비슷하지만 덜 극단적인 결과와 함께. (Bisuthajiman deol geuktanjeogin jeonggyo wa hamkke)

내 첫 번째 생각은 정렬이 데이터를 미친 듯이 만든다는 것이었지만, 그건 어리석은 생각이다. 왜냐하면 배열은 방금 생성되었기 때문이다.

무슨 일이 일어나고 있나요?

왜 정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 빠른가요?

이 코드는 독립적인 항목들을 더하는 것이므로 순서는 중요하지 않아야합니다.

같은 효과에 대한 관련/추적 질문 및 답변들, 다른/나중에 사용된 컴파일러와 옵션에 관한 것들:

#@!'Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?'#@!

#@!'gcc optimization flag -O3 makes code slower than -O2'#@!

답변 1

당신은 !@##@!'branch prediction'!@##@! 실패의 피해자입니다.

지점 예측이란 무엇인가요?

철도 교차로를 고려해보십시오.

논쟁을 위해 가정해보자면, 이것은 1800년대로 돌아간 상황입니다 - 장거리나 라디오 통신이 없던 시대입니다.

당신은 교차로의 시각장애 운전사입니다. 열차가 다가오는 소리를 듣습니다. 그러나 어느 방향으로 가야하는지 전혀 모릅니다. 운전사에게 방향을 묻기 위해 열차를 멈추고, 그 후에 스위치를 적절히 세팅합니다.

기차는 무거우며 관성이 많기 때문에 가동 및 감속에 시간이 오래 걸립니다.

더 나은 방법이 있을까요? 기차가 어느 방향으로 갈지를 추측해 보세요!

만약 당신이 맞혀서 맞았다면, 계속 진행됩니다.

만약 당신이 틀렸다면, 선장은 멈추고, 뒤로 물러나서 당신에게 스위치를 뒤집으라고 소리질러 할 것이다. 그럼 다른 길로 다시 시작할 수 있을 것이다.

만약 당신이 매번 맞춘다면, 기차는 절대 멈추지 않아도 될 것이다.

만약 당신이 너무 자주 틀린다면, 기차는 많은 시간을 멈추고 뒤로 갔다가 다시 출발할 것입니다.

가정해보세요, if문: 프로세서 레벨에서는 분기 명령입니다.

당신은 프로세서이며 가지 한 가지를 볼 수 있습니다. 가지가 어느 방향으로 갈지 전혀 모릅니다. 그러면 무엇을 할까요? 실행을 중단하고 이전 명령문이 완료될 때까지 기다립니다. 그런 다음 올바른 경로로 계속합니다.

현대 프로세서는 복잡하며 파이프라인이 길어집니다. 이는 "따뜻해지는 데에 오랜 시간이 걸리고" "느려지는 데에도 오랜 시간이 걸린다"는 것을 의미합니다.

더 나은 방법이 있을까요? 가지가 어느 방향으로 갈지 추측해보세요!

만약 당신이 맞췄다면, 계속 실행해주세요.

만약 당신이 틀리게 추측했다면, 파이프라인을 플러시하고 브랜치로 되돌아가야합니다. 그런 다음 다른 경로로 다시 시작할 수 있을 것입니다.

만약 매번 정확하게 추측한다면, 실행은 절대 멈추지 않을 것입니다.

너무 자주 틀리면, 많은 시간이 소행, 되감고 재시작하는 데 소요된다.

이것은 분기 예측입니다. 기차는 깃발로 방향을 알릴 수 있기 때문에 이는 최상의 비유는 아닙니다. 그러나 컴퓨터에서는 프로세서가 분기가 어느 방향으로 갈지를 마지막 순간까지 알 수 없습니다.

기차가 뒤로 가고 다른 경로로 가야하는 횟수를 최소화하기 위해 전략적으로 추측하는 방법은 어떻게 할까요? 과거의 기록을 살펴봅니다! 기차가 대부분 왼쪽으로 가면 왼쪽으로 추측합니다. 번갈아 가면 번갈아 추측합니다. 3번에 한 번씩 가는 경우에는 동일한 방향으로 추측합니다...

다시 말하자면, 패턴을 인식하고 그에 따라 따라가려고 시도합니다. 이는 대략적으로 브랜치 예측기가 작동하는 방식입니다.

대부분의 애플리케이션은 잘 행동하는 분기를 가지고 있습니다. 따라서, 현대적인 분기 예측기는 일반적으로 90% 이상의 성공률을 달성할 것입니다. 그러나 예측할 수 없는 패턴이 없는 예측할 수 없는 분기와 마주하면, 분기 예측기는 사실상 쓸모가 없습니다.

자세히 읽기: !@##@!'"Branch predictor" article on Wikipedia'!@##@! .

위에서 암시한 것처럼, 범인은 이 if문입니다.

#@!'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)

'#@!

무엇을 할 수 있을까요?

컴파일러가 분기를 조건부 이동으로 최적화하지 못하는 경우, 성능을 위해 가독성을 희생하더라도 몇 가지 해킹을 시도해 볼 수 있습니다.

대체하다: So what did you replace it with?

#@!'if (data[c] >= 128)

sum += data[c];

'#@!

와 함께:

#@!'int t = (data[c] - 128) >> 31;

sum += ~t & data[c];

'#@!

이것은 가지를 제거하고 일부 비트 연산으로 대체합니다.

(주석:/이 필요한 해킹은 엄격하게 원래의 if 문과 동등하지 않습니다. 그러나 이 경우에는, # $!&@#&& $&#@!의 입력 값에 대해 모두 유효합니다.)

기준: Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 릴리스

자바 - NetBeans 7.1.1 JDK 7 - x64

관찰 내용:

지점이 있는 경우: 정렬된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.

해킹을 통해 정렬된 데이터와 정렬되지 않은 데이터 사이에는 차이가 없습니다.

C++의 경우, 데이터가 정렬되어 있는 경우 해킹은 사실 약간 더 느립니다.

일반적인 원칙은 중요한 루프에서 데이터 종속적인 분기를 피하는 것입니다 (이 예시와 같은 경우에).

업데이트:

GCC 4.6.1은 x64에서 !@##@!'-O3'!@##@! 또는 !@##@!'-ftree-vectorize'!@##@!를 사용하여 조건부 이동을 생성할 수 있으므로 정렬된 데이터와 정렬되지 않은 데이터 간에는 차이가 없습니다 - 둘 다 빠릅니다.

(또는 어느 정도 빠른 경우에는 이미 정렬된 경우에는, # $ * $ $! @ * $ & # @! 경우에는 느릴 수 있으며 특히 GCC가 비판적 경로에 두지 않고 말 그대로 # $ &! @ * @ # $ & # @!에 매우 고속으로 처리하는 인텔 브로드웰 이전의 경우에는 # $ * $ $! @ * $ & # @!이 2 사이클 대기 시간을 가지고 있습니다: # $ & ** #! $ & # @!))

VC++ 2010는 이 분기에 대해 조건부 이동을 생성할 수 없습니다. 심지어 !@##@!'/Ox'!@##@! 속에서도.

#$$!#!&#@! (ICC) 11는 기적적인 일을 합니다. 무언가를 #$$!&$&#@! 하여 예측할 수 없는 브랜치를 외부 루프로 이동시킵니다. 예측 실패에 면역이 되는 것뿐만 아니라, VC++와 GCC가 생성할 수 있는 것보다 두 배 빠릅니다! 다시 말해서, ICC는 벤치마크를 무력화하기 위해 테스트 루프를 활용했습니다...

만약 인텔 컴파일러에 분기 없는 코드를 제공한다면, 그 코드는 즉시 벡터화되며... 분기와 함께 루프를 교환한 경우와 동일한 속도로 실행됩니다.

이것은 심지어 성숙한 현대 컴파일러도 코드를 최적화하는 능력에서 크게 다를 수 있다는 것을 보여줍니다...

답변 2

정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 빠른 이유는 무엇일까요? 이 문제에 대한 일지한 한국어 에세이입니다.

제목: 정렬된 배열은 처리 속도가 더 빠른 이유

서론:

정렬된 배열과 정렬되지 않은 배열은 프로그래밍에서 많이 사용되는 자료 구조입니다. 그러나 정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 더 빠른 이유에 대해 알아보고자 합니다. 이 에세이에서는 정렬된 배열 처리의 장점과 그 이유에 대해 설명하고자 합니다.

본론:

1. 캐시 메모리 활용:

정렬된 배열을 처리할 때에는 메모리 캐시의 효율적인 활용으로 인해 처리 속도가 향상될 수 있습니다. 프로세서는 데이터에 접근할 때 메모리 캐시를 활용하는데, 정렬된 배열 처리 시 데이터의 지역적 연속성이 높아져 캐시 미스가 줄어들고 데이터를 더 빠른 속도로 읽어올 수 있습니다.

2. 이진 검색 알고리즘:

정렬된 배열은 이진 검색 알고리즘을 활용할 수 있습니다. 이진 검색은 배열을 반으로 쪼개어 탐색하는 효율적인 방법으로, 원하는 값을 빠르게 찾을 수 있습니다. 반면, 정렬되지 않은 배열의 경우에는 선형 검색방식을 사용해야 하므로 원하는 값을 찾는데 더 많은 비교 연산이 필요합니다.

3. 최적화된 알고리즘 및 연산:

정렬된 배열을 처리하는 알고리즘에는 최적화된 방식이 적용될 수 있습니다. 예를 들어, 정렬된 배열을 병합하는 작업은 병합 정렬 알고리즘을 이용해 효율적으로 수행할 수 있습니다. 같은 작업을 정렬되지 않은 배열에서 수행할 경우 추가적인 정렬 작업 등을 필요로 하며, 처리 시간이 증가할 수 있습니다.

결론:

정렬된 배열의 처리 속도가 정렬되지 않은 배열의 처리 속도보다 빠른 이유는 여러 가지 요인이 합쳐져 있습니다. 메모리 캐시의 효율적인 사용, 이진 검색 알고리즘, 최적화된 알고리즘 및 연산은 정렬된 배열 처리에 있어서 그 이유로 주목할 만한 요소입니다. 따라서, 정렬된 배열을 사용하는 경우에는 이러한 장점들을 고려하여 처리 속도를 향상시킬 수 있는 최적의 방법을 선택하면 됩니다.