TODO: 소개 영상과 요약 영상을 추가합니다.
이 실습 과제는 분기 대상 예측 실패 횟수를 줄여 성능을 개선하는 데 초점을 둡니다. 이 실습에는 공통 기반 클래스를 상속하는 서로 다른 세 클래스의 객체 모음이 있습니다. 객체 배열이 임의의 순서로 생성된 뒤 반복해서 순회됩니다. 반복 중에 각 객체에서 가상 메서드가 호출됩니다. CPU는 정확히 어떤 메서드가 호출될지 미리 알지 못하며(호출의 대상을 알지 못하며), 이 때문에 실행 속도가 느려집니다.
여기서 여러분의 과제는 가상 메서드 호출을 더 예측 가능하게 만들어 분기 대상 예측 실패 횟수를 줄이는 것입니다.
작성자: Jakub Beránek (@Kobzol)
힌트
힌트 1:
InstanceArray(std::vector<std::unique_ptr<BaseClass>>)에
담긴 데이터는 어떤 성질을 가지고 있습니까? 이것이 왜 문제가 됩니까?
힌트 2:
다형성의 성질과 무작위성에 대해 생각해 보십시오. 무작위로 섞인 데이터에서는 CPU가 어떤 가상 메서드가 호출될지 미리 알 수 없습니다.
힌트 3:
하드웨어 예측기는 데이터가 대체로 일관되고 예측 가능한 방식으로 처리될 때 가장 좋은 성능을 낸다는 점에 유의하십시오. 입력 데이터에서 같은 가상 메서드를 호출하는 항목들을 가까이 모아 둘 방법이 있는지 찾아보십시오.
풀이:
배경:
다형성 객체를 담은 컨테이너가 있습니다. 이 컨테이너의 항목을
순회하면서 각 항목에 대해 가상 함수 handle을
호출합니다.
문제는 컨테이너가 ClassA, ClassB,
ClassC 타입의 다형성 객체로 무작위로 채워져 있다는
점입니다. 컨테이너 안의 이러한 무작위 분포는 다음 반복에서 어떤 가상
함수가 호출될지 예측하려는 분기 예측기를 어렵게 만듭니다. 그 결과 분기
예측 실패가 많이 발생하며, 이는 큰 페널티를 초래합니다.
원래 코드는 분기 예측 실패율이 21.5%로, 이는 매우 높은 수치이며 성능에 부정적인 영향을 미칩니다.
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
bench1/iterations:1000 589 us 589 us 1000
Performance counter stats for './lab':
601,822,974 task-clock # 0.996 CPUs utilized
7 context-switches # 11.631 /sec
1 cpu-migrations # 1.662 /sec
1,060 page-faults # 1.761 K/sec
698,155,664 instructions # 0.33 insn per cycle
2,144,081,553 cycles # 3.563 GHz
205,311,281 branches # 341.149 M/sec
44,134,143 branch-misses # 21.50% of all branches
0.604055757 seconds time elapsedperf record ./lab으로 핫스팟을 살펴보면, 주된 오버헤드가
invoke 메서드, 구체적으로는 가상 함수 호출인
item->handle(data)에서 발생한다는 것을 알 수
있습니다:
void invoke(InstanceArray& array, std::size_t& data) {
for (const auto& item: array) {
item->handle(data);
}
}하지만 문제의 근본 원인은 사실 입력 InstanceArray 안에서
다형성 객체가 무작위로 배치되어 있다는 데 있으며, 이 부분은 아래에서
다룹니다.
해결책:
런타임 다형성의 영향을 줄이는 일반적인 방법은 템플릿을 통한 정적 다형성(CRTP 관용구나 C++ 20 이상의 콘셉트 등)을 사용하는 것이지만, 여기서는 객체를 컨테이너에 담고 있어 동질성이라는 제약이 있으므로 이 방법을 쉽게 쓸 수 없습니다.
어쨌든 같은 파생 타입의 객체를 컨테이너 안에서 한데 모아 두면 하드웨어를 도울 수 있습니다.
generateObjects에서 ClassA,
ClassB, ClassC를 각각 담을 임시
InstanceArray 세 개를 만듭니다:
InstanceArray a;
InstanceArray b;
InstanceArray c;
for (std::size_t i = 0; i < N; i++) {
int value = distribution(generator);
if (value == 0) {
a.push_back(std::make_unique<ClassA>());
} else if (value == 1) {
b.push_back(std::make_unique<ClassB>());
} else {
c.push_back(std::make_unique<ClassC>());
}
}여기에도 분기가 있지만, 가상 함수 호출로 인한 분기 예측 실패보다는 영향이 적습니다.
그런 다음 이 데이터를 그룹별로 묶어 반환 배열에 삽입합니다.
InstanceArray는 이동만 가능하고 복사는 불가능한
std::unique_ptr의 컬렉션이므로, 이 반복자들을
std::make_move_iterator로 감싸야 한다는 점에
유의하십시오:
array.insert(array.end(), std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()));
array.insert(array.end(), std::make_move_iterator(b.begin()), std::make_move_iterator(b.end()));
array.insert(array.end(), std::make_move_iterator(c.begin()), std::make_move_iterator(c.end()));변경 사항을 반영한 generateObjects 함수 전체는 다음과
같습니다:
void generateObjects(InstanceArray& array) {
std::default_random_engine generator(0);
std::uniform_int_distribution<std::uint32_t> distribution(0, 2);
InstanceArray a;
InstanceArray b;
InstanceArray c;
for (std::size_t i = 0; i < N; i++) {
int value = distribution(generator);
if (value == 0) {
a.push_back(std::make_unique<ClassA>());
} else if (value == 1) {
b.push_back(std::make_unique<ClassB>());
} else {
c.push_back(std::make_unique<ClassC>());
}
}
array.insert(array.end(), std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()));
array.insert(array.end(), std::make_move_iterator(b.begin()), std::make_move_iterator(b.end()));
array.insert(array.end(), std::make_move_iterator(c.begin()), std::make_move_iterator(c.end()));
}이렇게 변경하면 코드가 약 세 배 빨라지고, 분기 예측 실패율도 0.12%에 불과합니다:
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
bench1/iterations:1000 186 us 185 us 1000
Performance counter stats for './lab':
214,844,475 task-clock # 0.989 CPUs utilized
11 context-switches # 51.200 /sec
0 cpu-migrations # 0.000 /sec
1,320 page-faults # 6.144 K/sec
697,751,364 instructions # 1.02 insn per cycle
682,564,050 cycles # 3.177 GHz
205,439,992 branches # 956.227 M/sec
252,241 branch-misses # 0.12% of all branches
0.217148628 seconds time elapsed