const unsigned arraySize = 10000;
int data[arraySize];
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned c = 0; c < arraySize; ++c)
{
if(data[c] >= 128)
{
sum += data[c];
}
}
}
- 만약 배열요소가 정렬된 상태라면 약 2.8초 만에 실행이 완료되지만, 배열 요소가 임의로 배치되면 실행 시간이 무려 약 7.5초에 달함.
- 리눅스의 perf 도구를 이용하여 프로그램 실행 상태에 대한 초기 단계를 분석해서 문제를 확인해 볼 수 있음.
- perf 를 이용하면 CPU와 관련된 모든 중요한 정보를 확인할 수 있음.
- branch-misses 항목이 있는데, 정렬된 배열을 이용한 프로그램에서 예측 실패율은 0.02%에 불과하지만, 정렬되지 않은 배열을 이용한 프로그램에서 최고 14.12%에 달함.
- CPU: 메가팩토리와 파이프라인
- CPU 자체를 하나의 메가팩토리로 볼 수 있음.
- 차량 공장이 차량을 생성한다면 CPU는 기계 명령어를 실행함.
- 기계 명령어를 처리하는 과정은 대게 네 단계로 구분할 수 있음.
- 명령어 인출(instruction fetch)
- 명령어 해독(instruction decode)
- 실행(execute)
- 다시 쓰기(writeback)
- 이 기계 명령어는 별도의 하드웨어로 처리됨.
- CPU 내부에서 기계 명령어 하나를 단계 수십 개로 분해해서 실행할 수도 있음.
- 현재 CPU는 기계 명령어를 초당 수십억 개 처리할 수 있는 능력을 갖추고 있음.
- 파이프라인(pipeline) 기술을 필수 불가결함.
- if가 파이프라인을 만나면
- 프로그래머가 작성한 if 문은 일반적으로 컴파일러가 조건부 점프 명령어로 변환함.
- 조건부 점프 명령어 실행하기 전까지는 우리가 점프해야 할지 알 수 없고, 이는 파이프라인에 영향을 미침.
- 분기 점프 명령어가 실행을 완료하기 전에 다음 명령어는 이미 파이프라인에 들어가 있어야함. → 그렇지 않다면 파이프라인에 빈 공간이 생겨, 프로세서의 리소스를 완전하게 사용할 수 없음.
- 분기 점프 명령어가 실행이 완료되지 않은 시점에서 CPU는 미리 예측을 해서 명령어를 파이프라인에 넣게된다.
- 분기 예측: 가능한 한 CPU가 올바르게 추측하도록
- 추측이 맞았다면 파이프라인은 계속 앞으로 흘러감.
- 추측이 틀렸다면 파이프라인에서 이미 실행 중이던 잘못된 분기 명령어를 전부 무효화함.
- → CPU 추측이 틀리면 성능 손실이 발생함.
- 프로그램은 실행 이력 기반으로 예측하는 등 여러 데이터를 기반으로 함.
- 그래서 배열이 정렬되어 있으면 CPU 추측이 거의 들어맞게 되는 거임.
- 높은 성능을 요구하는 코드를 작성하고 이 안에 if 문을 사용한다면 CPU가 높은 확률로 추측할 수 있도록 코드를 작성해야 함.
- 프로그래밍 언어에 likely/unlikely 매크로(macro) 가 있는 이유임.
- 컴파일러에게 가능성이 더 높은 분기를 알려 줄 수 있음.
- perf 같은 분석 도구로 분기 예측이 성능 병목 현상이 아닌지 확인해야 함.
- 여기서 문제가 없다면 분기 예측 실패와 관련된 성능 감소 문제는 거의 신경쓸 필요 없음.
- 최신 CPU는 분기 예측이 매우 정확하므로 앞의 예제에서 정렬되지 않은 배열을 사용하더라도 예측 실패율이 50%에 달하지 않음.