왜 현대 x86-64 clang에서 정렬되지 않은 배열을 처리하는 것과 정렬된 배열을 처리하는 속도가 같을까요?

저는 이 인기있는 ~9년 전의 왜 정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 빠른가요? 을 발견했고, 그 결과를 다시 한 번 확인하기로 결정했습니다.

그래서, 나는 AMD Ryzen 9 5950X, clang++ 10 그리고 Linux를 가지고 있습니다. 질문에서 코드를 복사하여 붙여넣었고, 여기에 제가 얻은 결과입니다:

정렬됨 - 0.549702초:

'~/d/so_sorting_faster$ cat main.cpp | grep std::sort && clang++ -O3 main.cpp && ./a.out

std::sort(data, data + arraySize);

0.549702

sum = 314931600000

'

컴퓨터 전문가입니다. 특수 기호를 그대로 유지하면서 한국어로 번역하세요.

정렬되지 않음 - 0.546554초:

'~/d/so_sorting_faster $ cat main.cpp | grep std::sort && clang++ -O3 main.cpp && ./a.out

// std::sort(data, data + arraySize);

0.546554

sum = 314931600000

'

나는 정렬되지 않은 버전이 3ms 더 빠른 것은 그냥 노이즈일 뿐이라고 확신하지만, 이제는 더 느리지 않은 것 같습니다.

그래서, CPU 아키텍처에서 어떤 변화가 있었나요 (다른 숫자급으로 느려지지 않았을까요)?

여기는 여러 실행에서의 결과입니다:

'Unsorted: 0.543557 0.551147 0.541722 0.555599

Sorted: 0.542587 0.559719 0.53938 0.557909

'

당신은 컴퓨터 전문가입니다. 특수 기호를 유지한 채로 한국어로 번역해주세요.

만약를 대비하여, 제 main.cpp 파일을 여기에 첨부합니다:

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

{

// Primary loop

for (unsigned c = 0; c < arraySize; ++c)

{

if (data[c] >= 128)

sum += data[c];

}

}

double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC;

std::cout << elapsedTime << std::endl;

std::cout << sum = << sum << std::endl;

return 0;

}

'

당신은 컴퓨터 전문가입니다. 특수 기호를 그대로 유지하면서 번역하십시오.

업데이트

당신은 컴퓨터 전문가입니다. 특수 기호를 그대로 유지하면서 이를 한국어로 번역해주세요.

요소 수가 더 많을 때 (627680):

'Unsorted

cat main.cpp | grep std::sort && clang++ -O3 main.cpp && ./a.out

// std::sort(data, data + arraySize);

10.3814

Sorted:

cat main.cpp | grep std::sort && clang++ -O3 main.cpp && ./a.out

std::sort(data, data + arraySize);

10.6885

'

나는 그 질문이 여전히 관련이 있다고 생각합니다 - 거의 차이가 없습니다.

답변 1

당신은 컴퓨터 전문가입니다. 링크된 질문의 몇몇 답변에서는 코드를 브랜치 없이 다시 작성하여 브랜치 예측 문제를 피하도록 하는 것에 대해 언급됩니다. 그것이 바로 업데이트된 컴파일러가 하는 일입니다.

특별한 기호를 그대로 유지하면서 번역하면 다음과 같습니다.

특히 내부 루프에서는 clang++ 10을 사용합니다. '-O3' 'vectorizes' 어셈블리 코드의 36-67행. 코드는 약간 복잡하지만, 하나 확실히 할 수 있는 것은 'data[c] >= 128' 테스트에서 조건부 분기가 없다는 점입니다. 대신에 벡터 비교 명령어 ( 'pcmpgtd' ) 를 사용하는데, 이 명령어의 출력은 일치하는 요소에 대해 1을 포함하고 일치하지 않는 요소에 대해 0을 포함하는 마스크입니다. 이 마스크와 함께 실행되는 'pand' 명령어는 일치하지 않는 요소를 0으로 대체하여, 무조건적으로 합에 기여하지 않도록 합니다.

당신은 컴퓨터 전문가입니다. 특수 기호를 유지하며 한국어로 번역하면 다음과 같습니다.

거친 C++ 동등물은

'sum += data[c] & -(data[c] >= 128);

'

코드는 실제로 배열의 짝수와 홀수 요소를 위해 두 개의 64비트 'sum'를 유지하여 병렬로 누적 한 다음 루프의 끝에서 합산할 수 있습니다.

당신은 컴퓨터 전문가입니다. 특수 기호를 그대로 유지하면서 한국어로 번역해주세요.

32비트 'data' 요소를 64비트로 확장하기 위한 일부 복잡성은 추가로 다루는 부분입니다. 이를 위해 'pxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5'와 같은 시퀀스가 사용됩니다. '-mavx2'를 켜면 더 간단한 'vpmovsxdq ymm5, xmm5'로 대체됩니다.

여기서 특수 기호도 그대로 유지하면서 한국어로 번역해주신 전문가입니다.

코드는 루프가 언롤되어 1회 반복당 'data' 의 8개 요소를 처리하기 때문에 길어진 것입니다.

답변 2

현대 x86-64 clang을 사용하여 처리하는 미정렬 배열과 정렬된 배열의 속도는 왜 같을까요?

많은 프로그래밍 작업에서 배열은 중요한 데이터 구조 중 하나입니다. 배열은 여러 원소를 포함하고 있으며, 각 원소는 메모리에 연속하여 저장됩니다. 때로는 배열을 정렬된 상태로 처리하는 것이 더욱 효율적이며, 이는 탐색 알고리즘에서 유용하게 사용됩니다. 하지만 현대의 x86-64 아키텍처와 clang 컴파일러에서는 미정렬 배열과 정렬된 배열을 처리하는 속도가 동일한 이유가 있습니다. 이에 대해 자세히 알아보도록 하겠습니다.

처음에는 정렬된 배열을 처리하면 미정렬 배열을 처리하는 것보다 더욱 효율적일 것이라고 예상할 수 있습니다. 정렬된 배열은 이진 검색과 같은 분할 정복 알고리즘을 사용하여 효율적인 탐색을 할 수 있습니다. 이는 모든 원소를 탐색하지 않아도 원하는 결과를 찾을 수 있기 때문입니다.

그러나 현대의 프로세서 아키텍처에서는 처리 속도를 높이기 위해 캐시 메모리를 사용합니다. 캐시 메모리는 데이터에 빠르게 접근하기 위해 CPU 근처에 위치한 메모리입니다. 일반적으로 캐시 메모리에는 최근에 접근한 데이터가 저장되어 있으며, 이를 이용하여 더 빠르게 데이터를 처리할 수 있습니다.

이는 정렬된 배열을 처리할 때와 미정렬 배열을 처리할 때의 차이점을 생각해보면 이해할 수 있습니다. 정렬된 배열의 경우 이진 검색을 사용하여 중간 원소를 기준으로 비교하고, 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치시킵니다. 이로 인해 캐시 메모리의 효율을 떨어뜨리게 됩니다.

반면, 미정렬 배열은 원소의 순서가 랜덤하게 배치되어 있어 다양한 캐시 라인에 데이터가 분산되어 저장될 수 있습니다. 이 경우 프로세서는 캐시 메모리를 효율적으로 사용하여 데이터를 처리할 수 있습니다. 즉, 미정렬 배열은 데이터에 랜덤한 접근을 필요로 하기 때문에 정렬된 배열보다 더욱 효율적으로 처리할 수 있는 것입니다.

또한 현대의 컴파일러들은 최적화 기술을 사용하여 코드를 분석하고 실행 속도를 최적화합니다. 따라서 현대의 x86-64 clang 컴파일러는 정렬 알고리즘이나 미정렬 배열 처리의 경우, 동등한 최적화를 수행하여 동일한 실행 속도를 보장합니다.

결론적으로, 현대의 x86-64 아키텍처에서는 캐시 메모리의 효율성과 최적화된 컴파일러의 기능으로 인해 미정렬 배열과 정렬된 배열의 처리 속도가 동일한 것입니다. 따라서 프로그래머들은 이러한 특징을 고려하여 배열을 처리하는 알고리즘을 선택해야 합니다.