[CS] 컴파일러의 최적화 성능과 한계 (Optimizing Compilers)

최적화된 프로그램은 원본 프로그램이 겪게 될 모든 경우에 대해

C언어 표준이 제공하는 보장의 한계까지 정확히 동일한 동작을 가져야 하기 때문에

컴파일러는 오직 안전한 최적화만을 적용해야 한다.

 

gcc의 -Og 옵션은 기본 최적화 세트를 적용하고, -01 이나 -02 , -03 옵션은 보다 광 범위한 최적화를 적용한다.

프로그램의 성능을 개선할 수 있으나, 크기가 커질 수 있으며 표준 디버거를 사용 한 디버깅이 어려워질 수 있다.

책에서는 컴파일러의 최적화 영향을 보기 위해 -01 옵션으로 컴파일하여 제한한다.

 

컴파일러가 방어적으로 최적화 해야만 하는 이유에 대한 예시를 알아보자.

 

최적화 한계

예시 1

 

위의 코드에서 twiddle1() 은 포인터 역참조를 6번 하고 있다.

*xp = *xp + *yp;
*xp = *xp + *yp;

 

twiddle2() 는 같은 동작이지만 포인터 역참조를 3번 하고 있다.

*xp = *xp + 2 * *yp;

 

고로 우리는 컴파일러가 twiddle1() 을 컴파일 하면 twiddle2() 처럼 최적화할 것이라고 생각할 수 있다.

하지만, xp 와 yp 가 동일한 메모리인 경우를 생각해보자.

 

/*1*/ *xp += *xp;
/*2*/ *xp = *xp + *xp;
/*3*/ *xp = 2 * *xp;

 

twiddle1() 은 위와 같은 결과로 값이 4배가 될 것이고,

 

/*1*/ *xp += 2 * *xp;
/*2*/ *xp = *xp + 2 * *xp;

 

twiddle2() 는 위와 같은 결과로 값이 3배가 될 것이다.

 

따라서 컴파일러는 xp 와 yp 가 동일하다고 가정해야하므로, twiddle1() 을 twiddle2() 처럼 최적화할 수 없다.

 

예시 2

두 개의 포인터가 같은 메모리를 가리킬 수 있는 경우 메모리 연결(memory aliasing) 이라고 하는데,

안전한 최적화를 위해선 컴파일러는 서로 다른 포인터들이 연결될 수 있다고 가정해야 한다.

 

 

t1 으로 계산된 값은 포인터 p 와 q 가 연결되었는지 여부에 따라 달라진다.

이 것이 컴파일러가 최적화하기 위한 기회를 심각하게 제한할 수 있는 최적화 장애물이 된다.

 

예시 3

 

같은 계산을 하는 것처럼 보이지만, f() 가 어떤 함수냐에 따라 프로그램의 동작이 달라진다.

 

 

만약 f() 가 위와 같다면, func1() 의 경우 반환 값이 0 + 1 + 2 + 3 = 6 이 되지만,

func2() 의 경우 반환 값이 4 * 0 = 0 이 된다.

 

인라인 대체 (inlining)으로 함수 호출 최적화

함수 호출은 함수의 본체를 위한 코드로 교체된다.

 

func1() 을 위한 코드를 네 개의 f() 호출 사례로 교체해서 확장할 수 있다.

이러한 변환은 함수 호출의 오버헤드를 줄이고 아래와 같이 확장된 코드의 추가적인 최적화를 가능케 한다.

 

 

gcc의 -finline 이나 -01 이상을 사용해서 이런 형태의 최적화를 시도할 수 있 다.

하지만, gcc는 하나의 파일 내에서 정의된 함수들에 대해서만 시도한다.

디버거 이용 시, 브레이크 포인트 설정은 실패하게 되므로 주의!

 

 

프로그램 성능의 표현

CPE 라고 불리는 요소당 측정 사이클(metric cycle)을 프로그램 성능을 표시하는 방법으로 소개한다.

프로세서의 순차적인 동작은 GHz (GigaHertz)로 표시되는 일정한 주파수를 갖는 신호를 제 공하는 클럭에 의해 제어된다.

 

4GHz 프로세서로 나타내는 프로그램은 클럭이 초당 4.0 * 10^9 사이클로 동작한다는 것을 의미한다.

클럭의 주기는 0.25 나노초 또는 250 피코초이다.

 

하지만 프로그래머 입장에서 나노초나 피코초 대신에 클럭 사이클로 표현하는 것이 더 의미 있다.

클럭이 얼마나 빨리 도는가 보다 얼마나 많은 인스트럭션들이 실행되고 있는가를 표시할 수 있다.

 

 

psum1() 과 psum2() 는 동일하게 접두합을 계산하는 함수다.

하지만, psum2() 는 반복마다 두 원소를 계산하기 위해 루프 풀기(loop unrolling) 기법을 사용한다.

 

 

Elements 마다 요구하는 Clock의 Cycles의 수를 나타낸다.

psum2() 의 CPE는 6.0으로, psum1() 의 CPE인 9.0보다 더 우수하다

 

 

설명에 사용할 벡터 구조체

 

 

루프 비효율성 제거

예시 1

 

combine1()의 for 반복문 조건에서 vec_length()를 호출하는 것에 주목하자.

 

벡터의 길이는 루프가 진행될 때 변하지 않으므로 반복문 전에 지역변수에 저장하여 사용한다면 성능이 향상될 수 있으며,

추가적인 최적화를 시도할 때 병목이 될 비효율성을 제거할 수 있다.

 

 

이 최적화 기법은 코드 이동 (code motion) 최적화 기법이다.

컴파일러는 이러한 최적화를 수행하려 하지만, 앞서 소개한 여러 장애물들 때문에 수행하지 못한다.

 

예시 2

 

위의 lower1()은 반복문 조건마다 strlen()을 호출하며 문자열의 길이를 확인하고,

lower2()는 미리 지역변수에 저장하고 사용한다.

 

 

lower1()은 문자열의 길이가 증가함에 따라 실행 시간이 급격하게 상승하는 것을 볼 수 있다.

 

 

불필요한 메모리 참조의 제거

 

combine3()은 포인터 dest에 계산의 결과를 계속해서 역참조하여 누적한다.

combine4()는 지역 변수를 만들어 누적하고 마지막에 dest에 역참조하여 대입한다.

 

 

data의 i번째 원소를 %rdx에 유지하도록 코드를 변환한 모습이다.

이 포인터는 루프마다 8씩 증가한다.

 

combine3()은 포인터 dest를 %rbx에 저장하고, 계산 결과를 %rbx에 옮기는 모습을 볼 수 있다.

이러한 읽기와 쓰기 작업은 낭비다.

 

 

위의 표와 같이 프로그램 성능에 상당히 큰 개선이 있음을 알 수 있다.

 

불행히도 이 역시 컴파일러는 어떤 조건하에 함수가 사용될 수 있을지,

프로그래머의 의도가 무엇일지에 대한 판단을 할 수 없다.

 

따라서 컴파일러가 효율적인 기계어 수준 코드로 변환할 수 있도록 프로그래머가 더 노력하며 코딩해야 한다.

 

 

『Computer Systems: A Programmer's Perspective』 책을 읽고 정리한 글입니다.
검색을 허용하지 않고, 수익을 창출하지 않습니다.