삼성 SW 역량테스트 B형/Pro 대비 - 최적화 기법

삼성 SW 역량테스트 B형/Pro 대비 - 최적화 기법

 

1. 들어가기 앞서

 C, CPP 기준으로 -O 옵션이 없는 상태에서 기준으로 한다. Java 혹은 언어에 따라 다른 결과가 나올 수 있다.

 

 

2. 함수 인라이닝

 빈번하게 호출 되는 경우, 함수를 인라인화 하는 것이 좋다. 이때 inline 키워드를 통한 컴파일 타임의 인라이닝은 최적화 옵션에 따라서 동작하게 되므로, macro를 통한 인라이닝을 하는 것을 의미한다.

 

 // inline 키워드
 inline void MAX(int a, int b){ return a > b ? a : b };
 // 전처리문
 #define MAX(a, b) ((a) > (b) ? (a) : (b))

 

 문제에 따라서 TC당 한 두차례 호출되는 경우에는 인라이닝의 큰 효과를 보지 못한다.

 

2. 루프 관련 최적화 기술

  (1) loop 변수 접근

 

for(i = 0; i < b-a i++)
	something();

 위에서와 같이 루프를 수행함에 있어 항상 접근되어야 하는 변수들이 있다. 앞선 for루프에서는 i와 b-a가 그런 경우다. 

 이 경우에는 b-a를 (1) 하나의 변수에 담아 주는 것이 좋다.

 

 

for(i = b-a-1; i >= 0; --i)
	something();

 역순 순회가 가능하다면, for(i = b-a-1; i >= 0 ; --i)와 같이  (2) 역순으로 순회하여 비교 자체를 상수와 하도록 하는 것이 좋다. 물론 증감 연산자도 (3) 전위 연산자를 사용하는 것이 좋다.(증감 연산자의 경우 효율을 위하여 하드웨어적으로 구현된 명령어를 사용한다. 실제 테스트시에 전위, 후위 연산자가 차이 나지 않는다. 단, 후위 연산의 경우 옛날 값을 사용해야 하기 때문에 load 작업으로 인하여 느려질 수도 있다고 한다. 영원한 떡밥)

 

int i, j;
for(i = 0; i < 100; ++i){
	for(j = 0; j < 100; ++j){
		a[i+j] = a[i+j+2] + a[i+j+1];
        // i+j를 변수에 담아 처리하는 것이 좋다.
        // a[k] = a[k+2] + a[k+1];
	}
}

 또한 루프에서 어떠한 동작을 함에 있어 지속적으로 변수 값을 엑세스 하는 경우, 반드시 (4)치환해주는 것이 좋다.

 

 

for(int i = 0; i < 100; i++){
	a[i] = something(i);
}

// loop unrolling
for(int i = 0; i < 100; i+=4){
	a[i] = something(i);
	a[i+1] = something(i+1);
	a[i+2] = something(i+2);
	a[i+3] = something(i+3);
}

 또 다른 방법으로는 (5) loop unrolling 기법이 있다. 겨우 이거 루프를 풀어낸다고 뭐가 달라지겠나 싶겠지만, 최적화 옵션이 없는 상태에서 루프 언롤링은 생각보다 강력한 성능을 보여준다.

 일반적으로 4의 배수로 언롤링을 하며, 4, 8, 16 정도를 풀었을 때 가장 효율이 좋다고 한다. 반면 언롤링으로 인하여 계산되지 못하는 영역이 있다면 이는 루프 밖으로 빼어 별도로 처리해주어야 한다.

 

 

for(i = 0; i < (sz & ~15); i+= 16){
   do(i);
   do(i+1);
   ...
   do(i+15);
}

for(i = (sz & ~15); i < sz; ++i){
	do(i);
}

 만약 길이가 가변적이라면, 아래와 같이 특정 횟수에 가장 가까운 루프만큼 언롤링하고 그외 나머지 경우는 일반 루프로 처리할 수있다.

 

// 코드 이동
for(i = 0; i < 1000; ++i){
	a[i] = i*b + (c-d)*e;
    // (c-d)*e를 루프 밖으로 이동
}

// 루프 융합
for(i = 0; i < 1000; ++i) a[i] = 0;
for(i = 0; i < 1000; ++i) b[i] = 1;

for(i = 0; i < 1000; ++i){
	a[i] = 0;
	b[i] = 1;
}

// 루프 교환
for(i = 0; i < 100; ++i)
	for(j = 0; j < 200; ++j)
    	a[i][j] = i+j;
for(j = 0; j < 200; ++j)
	for(i = 0; i < 100; ++i)
    	a[i][j] = i+j;

 그외 (6) 루프와 관계 없는 계산을 루프 밖으로 이동하는 "코드 이동" 기법이나, 비슷한 루프를 하나로 합치는 (7) 루프 융합 그리고 호출 횟수나 메모리 참조 방식에 따른 참조 지역성을 이용한 (8) 루프 교환이 있다.

 

 

3. 변수 관련 최적화 기술

 변수 관련 최적화 기법으로는 (1) register 키워드가 있다. 레지스터 키워드는 컴파일러에게 여유 레지스터 공간이 있으면 해당 변수를 레지스터에 올려 달라고 알리는 키워드로 실제 레지스터에 올라갈지 여부는 불분명하지만, 만약 올라가게된다면 메모리에 해당 값을 위하여 엑세스하지 않아 접근이 빈번한 변수의 경우 좋은 성능을 끌어낼 수 있다.

 

 두번째로는 변수의 타입이다. 일반적인 시스템에서 가장 빠르게 처리되는 primitive 타입은 integer이며, 그 중에서도 unsgined integer가 가장 빠르게 처리된다고 한다. 따라서 루프 변수와 같이 음수가 필요하지 않은 경우는 unsigned int를 이용하자.