B형에 필요한 최적화 코드 (1)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 B형 전체 링크

 

참고

- B형에 필요한 최적화 코드 (1)

- B형에 필요한 최적화 코드 (2)

- 함수의 매개변수와 배열의 register 속도 비교

- 삼성 B형 디버깅 Tip

- 비주얼 스튜디오 output.txt 설정하기

- 삼성 SW 역량 시험 환경에서의 인라인 함수

- Visual Studio LNK1168: 쓰기용으로 열 수 없습니다 해결방법

 

1) ++i (전위 증가) vs i++ (후위 증가) 비교.

2) register 변수를 사용하자.

3) 전역 변수(global) 접근을 최소화 하자.

---

1) ++i (전위 증가) vs i++ (후위 증가) 비교.

 

전위 증가는 값을 먼저 증가 시키고 return한다.

후위 증가는 원래 값을 먼저 받고 나중에 증가한다.

 

하지만 후위 증가의 경우는 임시로 변수를 복사하기 때문에 조금 더 느리다고 한다.

어셈블리어로 비교하면 차이가 난다.

 

하지만 Visual Studio에서는 그 차이를 확인하기 힘들다.

 

실제 삼성 SW 환경에서 시간을 확인해보자.

swexpertacademy.com/main/main.do 에서 아무 문제나 들어가서 실행하면 된다.

 

전위 증가를 실행한 경우 2.81124s

 

후위 증가의 경우 2.81942s

 

컴파일러 옵션이 다른 삼성 SW 환경에서는 큰 차이가 날 것 같았지만,

실제로 둘다 별 차이가 없다.

 

→ 결론: ++i나 i++ 편한대로 사용하고 마지막 시간이 남을 때, ++i로 고쳐주자.

 

실제 C형 시험에서는 ++i를 써서 10ms의 차이가 큰 역할을 하기도 한다. (아마도...)

 

test code는 아래를 참고하면 된다.

#include <stdio.h>
int main(void)
{
	int TESTCASE = 10000;
	int TIME = 0;

	for (int tc = 1; tc <= TESTCASE; tc++)
    //for (int tc = 1; tc <= TESTCASE; ++tc)
	{
		int a = 1;
		for (int i = 0; i < 100000; i++) a += i;
		//for (int i = 0; i < 100000; ++i) a += i;
	}
    
    printf("end\n");
    
	return 0; 
}

---

2) register 변수를 사용하자.

 

register는 변수를 선언할 때 사용하는데, 메모리 대신 CPU의 레지스터를 사용해서 매우 빠르다. (고 전해진다.)

Visual Studio에서는 그 위력을 확인할 수 없는데, 컴파일러 옵션에 따른 차이가 있기 때문이다.

 

실제 삼성 SW 시험에서 register의 위력을 확인해보자.

 

register가 없는 경우 : 2.87449s

 

register를 사용하는 경우 : 0.39411s

 

2.87449s vs 0.39411s로 시간이 확실히 줄어들었다는 것을 알 수 있다.

물론 전체 알고리즘이 잘못되었다면 큰 개선은 없을 수도 있다.

 

하지만 register를 달아주는 것만으로도 속도 개선이 명확하므로 반드시 사용하자.

register 변수는 for에서 사용하는 counter 변수나 자주 사용하는 변수에 무조건 선언하자.

 

아래는 참조 코드다. 실제 SW 사이트에서 실행시켜보자.

#include <stdio.h>
int main(void)
{
	int TESTCASE = 10000;
	int TIME = 0;

	for (register int tc = 1; tc <= TESTCASE;  ++tc)
	{
		register int a = 1;
		for (register int i = 0; i < 100000; ++i) a += i;
	}
    
    printf("end\n");
    
	return 0; 
}

---

3) 전역 변수(global) 접근을 최소화 하자.

 

먼저 아래의 코드를 실행해보자. 

#include <stdio.h>

 int cnt;

void makemap()
{
    int map[256][256];

	for (register int i = 0; i < 256; ++i)
		for (register int k = 0; k < 256; ++k)
			map[i][k] = cnt++;
}

int main() 
{
	for (register int i = 0; i < 10000;i++) makemap();
    
	printf("%d\n", 0);
    
	return 0;
}

약 1.685s 가 나온다.

 

이제 register int cnt = 0; 을 선언하고 실행해보자.

#include <stdio.h>

int cnt;

void makemap()
{
    int map[256][256];
	register int cnt = 0; /* 함수 안의 cnt가 증가하게 됨 */
	for (register int i = 0; i < 256; ++i)
		for (register int k = 0; k < 256; ++k)
			map[i][k] = cnt++;
}

int main() 
{
	for (register int i = 0; i < 10000;i++) makemap();
    
	printf("%d\n", 0);
    
	return 0;
}

약 0.629가 나온다.

 

이러한 성능 차이는 전역 변수의 특성 때문에 나타난다.

 

첫째, 전역 변수는 register를 선언할 수 없다.

둘째, 전역 변수는 stack이나 heap이 아닌 data 영역에 생성되므로, 

전역 변수에 접근할 때마다 성능 저하를 일으킨다.

(위의 코드에서는 성능상 큰 차이가 없지만, 실제로 전역 변수에 더 많은 접근을 하면 차이가 난다.)

 

따라서 함수가 시작할 때, global 변수를 stack 변수에 복사하고, 

함수 종료 전에 global 변수에 다시 stack 변수를 복사해야 성능에 도움이 된다.

int g; /* 전역 변수 */

void func()
{
	int a = g; /* stack 변수 a에 복사 */
    
    for(int i = 0; i < 1000; ++i) ++a;
   
    g = a; /* 전역 변수 갱신 */
}

---

+ 전역 변수를 초기화할 때는 ROM과 RAM에 모두 저장된다.

전역 변수의 값이 바뀌지 않는다면, const를 이용해 RAM에 복사하는 것을 방지할 수 있다.