C++ 코드 속도 향상 기법
제 주전공인 물리학과 특성상 시뮬레이션 같은걸 돌릴 경우 수 시간에서 수일, 크게는 몇개월 까지 돌리는 일이 많습니다.
이 때문에 교수님들이 포트란/C 시절의 극한의 코드 쥐어짜기를 은연중에 설파하시고, 저도 관련 자료들을 많이 찾아 봤습니다.
아래는 제가 경험적으로 알게 됬거나 구글링을 통해 찾아 본 방법이며, 하드웨어, 컴파일러마다 다른 결과가 나올 수 있습니다.
피드백은 언제나 환영합니다
본 내용은 제가 예전에 발표한 코드 최적화 프레젠테이션을 문서화 한 것입니다. (아직 덜 옮겨적었습니다)
PPT 에 다 못한 얘기들을 더 추가할 예정입니다.
목차
1. 서론
2. 일반적인 방법
3. 하드웨어 동작 기반
4. 그 외
1. 서론
(프로파일링 등을 하여) 정확히 어떤 곳을 최적화 할지 알아야 합니다.
코드 최적화는 언제나 모든 코드가 작성 완료 된 이후 하여야 합니다.
코드 최적화를 하기에 앞서 가장 중요한 마음가짐입니다.
괜히 가 ++i 이 빠르니 i++ 가 빠르니 일일이 테스트 해 보다가 시간 잡아먹는것 보다 일단 프로젝트에 대한 코드가 모두 작성되고 난 이후 하는게 효율적입니다.
그 다음, 프로파일링을 통해 어떤 부분이 느린지 정확히 알아내고 난 이후에 그 부분을 순서대로 최적화 해야 합니다.
예를 들어 코드 일부분의 속도를 10배 빠르게 최적화 시켜봤자, 정작 코드 전체에서 차지하는 비중이 1% 라면 실질적인 속도 향상은 거의 없다고 봐도 무방합니다.
그 보다는 속도가 1.2배 밖에 빨라지지 않더라도 전체 코드에서 비중이 30%인 부분의 코드를 먼저 고치는게 더 효율적입니다.
자꾸 효율을 강조하는데, 이는 제 경험이기도 합니다.
아직 비중이 큰 코드를 최적화 하지 않은 상황에서, 비중이 적은 부분의 코드를 보다 더 빠르게 짜겠다고 몇시간을 쏟아붓는건 매우 비효율적인 일입니다.
젤 처음에 말했듯이, 코드 최적화는 몇몇 너무 당연하면서(시간 복잡도가 바뀌는 등) 쉬운 최적화를 제외하면 이게 실질적으로 성능 향상이 있는지 없는지는 프로파일링을 하기 전까지 모릅니다.
솔직히 말해서 코드 대충 짜고 컴파일러 최적화 옵션을 최대치로 설정해 준 거나 10시간 들여서 최적화 한 코드나 성능상 별 차이가 없는 경우가 종종 있습니다.
그래서 본 글은 너무나 당연한 최적화 말고는 정말 극한의 성능을 뽑아내려고 하시는 분이거나, C/C++ 의 기법에 관심이 있으신 분들이 참고하셔서 사용하시는게 좋을 것 같습니다.
포스트의 아래로 갈수록 저수준에서의 최적화를 다루고 있습니다.
제가 테스트한 환경은 다음과 같습니다.
Apple MacBook Pro(16-inch, 2019)
2.6 GHz 6코어 Intel Core i7
16GB 2667 MHz DDR4
Apple clang version 11.0.3 (clang-1103.0.32.59)
Target: x86_64-apple-darwin19.4.0
Thread model: posix
2. 일반적인 방법
template<typename T>
void sort_bubble(std::vector<T> &data) {
for (int i = data.size() - 1; i > 0; --i)
for (int j = 0; j < i; ++j)
if (data[j] > data[j + 1]) {
int t = data[j];
data[j] = data[j + 1];
data[j + 1] = t;
}
}
template<typename T>
void sort_quick(std::vector<T> &data, int start, int end) {
if (start >= end)
return;
int pivot = start;
int i = pivot + 1;
int j = end;
T temp;
while (i <= j) {
T d_pivot = data[pivot];
while (i <= end && data[i] <= d_pivot) i++;
while (j > start && data[j] >= d_pivot) j--;
if (i > j) {
temp = data[j];
data[j] = data[pivot];
data[pivot] = temp;
} else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
sort_quick(data, start, j - 1);
sort_quick(data, j + 1, end);
}
func 라는 함수를 calc_count 횟수만큼 수행하는 코드 입니다. 이 작업이 독립적이라면, 즉 각각의 작업이 서로의 선행조건에 포함되지 않는다면 이는 병렬처리가 가능합니다.
for (int i = 0; i < calc_count; ++i)
func(args...);
std::vector<std::thread> threads;
threads.reserve(calc_count);
for (int i = 0; i < calc_count; ++i)
threads.emplace_back(func, args...);
for (auto &th : threads)
if (th.joinable()) th.join();
threads.clear();
double sum = 0;
for (int i = 0; i < calc_size; ++i)
sum += std::cos((double) i * 0.001);
const float LUT_COSINE_360[360] = {
1.000000000000000, 0.999847695156391, 0.999390827019096, ... };
double sum = 0;
int deg;
for(int i=0; i<calc_size; ++i){sum += LUT_COSINE_360[(int)(std::round((i * 0.057295779513082320)))%360];
}
Calculation
1000/ 1000 (100%): 8.44s (Average: 8.44ms)
827098.282
Lookup Table (size 360)
1000/ 1000 (100%): 3.76s (Average: 3.76ms)
827113.289
==============================
Calculation : Slowest ( 8.44ms )
Lookup Table (size 360) : 2.24x faster ( 3.76ms )
==============================
+ Tip최적화에 관심이 많으신 분들은 눈치채셨겠지만,값을 0.5˚, 1.5˚, 2.5˚, ... 359.5˚ 를 계산하여 저장해놓으면 std::round 없이 정수로 바로 casting 해서 사용할 수 있고,몫연산도 곱과 비트연산으로 치환할 수 있습니다. 그 경우에는 지금보다 더(2배 이상) 빠른 속도를 보여줍니다.몫연산을 곱과 비트연산으로 대체하는건 아래에서 다루겠습니다.
+ Tip 2일반적인 switch 구문도 실제로는 case 들의 값을 인덱스로 하는 배열(혹은 규칙에 알맞은 2차 배열도)을 만들어 그곳에 접근 히는 룩업 테이블의 형식을 취합니다.다만 case 가 100000, 200000, 300000 같이 큰 경우에는 저만한 크기의 배열을 만드느니 그냥 if 구문을 만들어서 돌아가게 됩니다.10만 20만은 예시로 든 거고, 실제로 컴파일러가 어떤 값 이상일때 if 로 대체하는지는 어셈블리어를 까보거나 프로파일링을 해야 알 수 있습니다. if 문으로 대체 해도 그냥 순서대로 if else-if else 쓰는게 아니라 최적화 해서 이진 탐색으로 만들어주긴 합니다(일반적으로).출처:
3. 하드웨어 동작 기반
int array[1000][1000] = { ... };
for(int i=0; i<1000; ++i){
for(int j=0; j<1000; ++j){
sum += array[j][i];}
}
'C++' 카테고리의 다른 글
초보도 따라하는 모던 C++ 튜토리얼 (0) | 2020.04.06 |
---|