[프로그래밍 최적화 ⑤] 임베디드 프로그래밍 최적화 기법

1부 | 개발 환경의 변화와 대응하는 프로그래밍 최적화의 재발견 2부 | OPP적 개발을 위한 C++ 프로그래밍 최적화 기법 3부 | 리팩토링을 이용한 자바 성능 최적화 기법 4부 | 성능 이슈 해결을 위한 닷넷 프로그래밍 최적화 기법 5부 | ARM과 파워pc에 기반한 임베디드 프로그래밍 최적화 기법

과 거 8051과 같은 CPU 시절과는 달리 요즘 나오는 임베디드 형 CPU는 ARM, PowerPC, MIPS와 같이 한 때 유닉스 워크스테이션에서나 사용하던 RISC 방식은 물론이고 CISC 방식의 x86 코어를 점점 더 많이 사용한다. 때문에 과거 워크스테이션에서 사용하던 최적화 기법까지 다뤄야 하는 경우가 점점 더 늘어나기 시작했다. 한 술 더 떠 임베디드 장비에 들어가는 CPU 성능도 날로 높아지고 CPU 코어도 계속해서 판올림을 거듭하고 있는 탓에 프로그래밍 기법들도 날로 새로워지고 있다.

프로그래밍 분야에서 ‘최적화’만큼 다양한 의미로 사용되는 단어도 드물 것이다. 최적화란 개발 목적과 사용하는 언어, 애플리케이션의 특징 등에 따라 모두 다른 의미로 사용되는 탓이다. 다만 그 핵심만은 대부분 비슷하다.

프로그래밍 분야의 최적화는 요구 사항을 충족시키지 못하는 소프트웨어를 개선해서 원하는 결과를 얻도록 하는 작업이라는 점에서 동일하기 때문이다. 한마디로 개발자나 환경에 따라 최적화의 의미는 제각기 달라지지만, 최적화의 중심에는‘속도’와 ‘크기’가 있다.

하지만 이 또한 시대가 바뀜에 따라 조금씩 달라지고 있다. 시대가 바뀌면서 CPU의 성능이 좋아지고 메모리의 용량 또한 늘어나는 덕에 정량적인 ‘속도’와 ‘크기’가 차지하는 의미가 작아지는 탓이다. 대신 ‘사용 편의성’과 ‘즐거운 경험’ 같은 요소가 중요해지고 있다.

이런 상황은 어디까지나 프로그래밍 전반에 대한 것일 뿐 임베디드 소프트웨어는 좀 더 복잡한 제약 조건하에서 개발되는 탓에 여전히 속도와 크기가 중요한 역할을 차지한다.

일반 데스크톱 PC나 워크스테이션과는 달리 임베디드 장비에 들어가는 CPU는 성능도 떨어지고 메모리(램이나 플래시) 용량도 적다. 때문에 수행 속도, 반응 속도, 실시간 성능, 실행 전 펌웨어 이미지 크기와 실행 중 프로세스 이미지 크기를 확보하기 위해 적잖은 공을 들여야 한다.

물론 속도도 빠르면서 이미지 크기도 작은 요구 사항을 동시에 충족할 수는 없다. 어느 한쪽을 희생해서 다른 한쪽을 살려야 한다. 이런 과정에서 특정 하드웨어에 대해 얼마나 균형을 잘 맞추느냐에 따라 임베디드 소프트웨어 개발 승패가 판가름 나는 경우도 있다.

5부는 이런 배경을 염두에 두고 임베디드 분야를 중심으로 널리 사용되는 ARM(Advanced RISC Machine)과 파워PC 계열 CPU를 토대로 C와 어셈블리 언어 특성을 활용해서 효과적인 소프트웨어를 제작하는 방법에 대해 알아본다. 여기서 주의 사항이 하나 있는데, 워낙 변수가 많은 알고리즘과 특정 컴파일러 버전에 따른 최적화 특성은 설명에서 제외한다.

최적화의 기초와 잘못된 상식

세계 최초의 64비트 CPU로 등장한 알파(21x64 시리즈)를 설계할 당시에 핵심적인 팀을 네 개로 나누었는데, 그 중에 소프트웨어 팀이 하나 끼어있었다.

놀랍게도 이 팀이 담당한 업무는 바로 알파에 최적화된 컴파일러를 제작하는 것이었다. 높은 클럭 주파수로 움직이는 CPU를 제작하는 과정에서 조금이라도 하드웨어의 복잡성을 줄이기 위해 최대한 단순하게CPU를 설계했다. 원하는 성능을 얻기 위한 노력을 소프트웨어(즉 컴파일러)로 떠넘긴 것이다.

이런 변화는 칩 제조사가 가장 골머리를 앓는 부분이 하드웨어 부문에서 소프트웨어 부문으로 바뀌어 버린 역사적인 전환점으로 생각해도 될 정도이다.

주로 CISC(Complex Instruction Set Computer) 기반으로 설계된 CPU를 다루던 프로그래머는 손으로 최적화한 어셈블리 코드가 월등히 뛰어나다고 생각하기 쉽다.

하지만, RISC(Reduced Instruction Set Computer) 환경이나 RISC와 CISC를 결합한 CPU에서는 그다지 큰 차이가 나지 않는다. 어떤 경우에는 컴파일러가 사람보다 더 우수한 기계어 코드를 생성하기도 한다. 연구에 따르면 프로그램을 작성하는 데 걸린 시간은 프로그래밍 언어와 상관없이 프로그램을 작성한 행의 수에 비례한다.

그러므로 그 만큼 많은 행을 담고 있는 어셈블리어 프로그램은 생산성이 낮을 수밖에 없는데, 최종 결과물마저 C 언어와 같은 고급 프로그래밍 언어와 비슷하다면 똑 같은 일을 하기 위해 시간과 노력만 낭비한 셈이 된다.

성능이 의심스러울 경우 수동 최적화를 하기 이전에 우선 컴파일러가 생성한 코드가 정말 최적인지 아닌지를 가려내야 하며, 현재 상태에서 얼마나 개선이 가능한지 평가해야 한다.

또한 성능이 중요한 프로그램을 작성할 경우 아키텍처에 맞춰 컴파일러가 해당 알고리즘을 위한 최적의 코드를 생성하도록 프로그램을 작성해야 한다. 컴파일러가 알아서 최적화된 코드를 생성하기를 기대해서는 안 된다는 말이다.

구체적인 최적화 기법 소개

자 그럼 이제부터 C 프로그래밍 언어를 활용한 본격적인 최적화 기법을 살펴보기로 하자. 우선 ABI(Application Binary Interface)를 사용한 최적화 기법부터 소개한다. 여기에서 먼저 짚고 넘어가야 할 것은 컴파일러가 좋아하는 방식으로 프로그램을 작성해야 최적화를 달성할 수 있다는 점이다.

그럼 어떻게 해야 컴파일러가 좋아하는 방식의 프로그램이 되는 것일까? 복잡한 어셈블리어로 코딩을 하지 않더라도 프로그램 작성 과정에서 조금만 공을 들이면 그럴듯한 효과를 얻을 수 있는 규칙들이 있다. 여기에서는 가장 범용적으로 사용할 수 있는 몇 가지 기본 규칙 들에 대해 알아보자.

ABI와 최적화
ABI(Application Binary Interface)는 응용 프로그램과 운영체제, 응용 프로그램과 라이브러리 사이에 필요한 저 수준 인터페이스를 정의한다. 또, 목적 파일과 관련되어 있어 원시 코드 컴파일 과정에 개입하는 API(Application Programming Interface)보다 저수준이다.

ABI는 아키텍처와 운영체제마다 조금씩 차이가 있으며, 인수 전달 방법과 반환 값 전달 방법을 포함한 함수 호출 규약을 정의한다.

고수준에서 생각해보면 함수를 정의하는 이유는 공통된 부분을 한 곳에 모아서 중복이 되지 않도록 만들어 코드의 유지 보수성을 높이는데 있다. 저수준에서의 함수는 코드의 크기를 줄이면서 연관된 코드를 한 곳에 모아 지역성을 높임으로써 캐시 적중률을 높이는 과정에 도움을 준다.

그렇다면 만일 함수 본체 길이가 길어서 컴파일러가 함수 본체를 호출한 곳에 인라인으로 확장하지 못하여 추가적인 속력 개선이 필요하다면 어떻게 해야 할까? 이 때 ABI 규칙을 알고 있다면 상당히 유리하다. 앞서 ABI가 아키텍처마다 다르다고 했으므로 여기서는 ARM과 파워PC로 나누어 생각해보자.

● ARM
ARM ABI 정의 규칙인 APCS(ARM Procedure StandardCall)에 따르면 컴파일러는 함수로 넘기는 인수를 담는 레지스터 네 개를(a1~a4) 할당한다. 즉 표준 C로 함수를 선언할 때 인수를 네 개 이하로 유지할 경우 인수를 넘기기 위해 스택을 사용하지 않고 레지스터만 사용하게 되므로 상당한 속도 개선의 효과를 얻을 수 있다.

● 파워PC
파워PC 32비트 ABI에 따르면 일반 변수를 위해 레지스터 R3에서 R10번까지를 사용하고, 부동소수점 변수를 위해 F1에서 F8까지를 사용한다. 따라서 표준 C로 함수를 선언할 때 인수를 여덟 개 이하로 유지한다면 속도를 개선할 수 있다.

물론 인수를 레지스터로 넘기는 방식이 늘 가능한 것은 아니다. 예를 들어, 가변 길이 인수(va_arg)를 사용할 경우에는 어쩔 수 없이 스택에 인수를 집어넣어야 한다. 따라서 속도 개선이 필요하다면 가변 길이 인수를 고정 길이 인수로 변경해야 한다.

또한 레지스터 길이를 초과하는 경우(예: 구조체를 인수로 넘긴다)에도 레지스터와 스택으로 나뉘어져서 인수를 전달하게 되므로 이 점도 고려 대상에 넣어야 한다.

함수 호출 과정에서 레지스터를 사용한다고 해서 크게 속도가 높아지지 않을 것처럼 보일지도 모른다. 하지만 함수 호출이 수십만 번에 걸쳐 일어난다고 가정할 때 코드‘크기’최적화 때문에 인라인이나 매크로가 불가능한 상황에서 속도 최적화를 가장 먼저 달성하는 좋은 수단이 될 수 있다.

다른 CPU에서의 최적화 작업 수행

비단 ARM이나 파워PC 뿐만 아니라 MIPS도 인수 전달에 레지스터 네개를 사용하며, x86_64도 인수 전달에 레지스터 여섯 개를 사용한다. x86의 경우 ABI 수준에서는 기본적으로 스택만 사용해서 인수를 전달하도록 정해져 있다. 물론 x86에서도 컴파일러에 따라 레지스터 두세개를 사용해서 조금이라도 속도를 높이는 옵션이 존재하는 경우도 있지만 표준은 아니다. 예를 들어 마이크로소프트 비주얼 C++은 인수 전달에 레지스터 두 개를 사용하며, 볼랜드 C++는 세 개, 왓콤 C는 네 개를 사용한다. 레지스터가 적은 x86의 경우에는 스택 프레임 포인터를 저장하는 EBP(Base Stack Pointer)를 다른 목적으로 활용하도록 컴파일러가 ESP 레지스터를 교묘하게 조작하는 방법을 사용하기도 한다. 일례로 gcc의 경우에는 -fomit-frame-pointer 옵션을 붙이거나 ?O2 최적화 옵션을 붙일 경우 프레임 포인터를 사용하지 않는다.

루프 최적화
구조화된 프로그래밍 기법에서 사용하는 주요 요소로 판단과 반복이 무척 중요하다. 우선 반복을 위한 루프 최적화부터 살펴보기로 하자.

● 불필요한 반복 제거
가장 기본적인 루프 최적화 기법으로 불필요한 반복을 제거하는 기법이 있다. 3~5회 정도만 반복하고 끝나는 경우 루프를 풀어서 사용한다면 크기를 희생해서 성능을 높일 수 있다.

하지만 코드 크기가 증가할 경우 캐시 적중률이 낮아져서 성능을 높이기는커녕 성능을 떨어트리는 원인이 될 수도 있으니, 반드시 루프내에 들어있는 코드 크기가 작을 경우에만 적용해야 한다.

루프를 완전히 풀지 않고 언롤링이라는 기법을 사용해서 크기와 성능의 균형을 맞추는 방법도 있다. ARM 플랫폼을 예로 들어보자면 ARM7이나 ARM9 프로세서에서 뺄셈을 처리하는 데한 사이클, 분기를 처리하는 데 세 사이클이 소요된다. 전체적으로 루프를 한번 도는 데에 네 사이클이 필요한 셈이다.

이럴 경우에 루프문의 몸체를 여러 차례 반복해서 같은 비율만큼 반복수를 줄이면 성능을 높일 수 있다. <리스트 1>과 <리스트 2>를 비교해 보자.

<리스트 1> 일반적인 방법의 예제

int checksum (int *data, unsigned int count) { int sum = 0; for (; count != 0; count--) { sum += (*data++); } return sum; }

<리스트 2> 언롤링 기법으로 작성된 예제

int checksum_unrolling(int *data, unsigned int count) { int sum = 0; do { sum += (*data++); sum += (*data++); sum += (*data++); sum += (*data++); } while (count != 0); return sum; }

<리스트 1>은 일반적인 방법으로 작성했으며, <리스트 2>는 언롤링 기법으로 작성했다. 언롤링 기법을 사용할 경우 루프 반복 회수가 4 * count 사이클에서 count 사이클로 줄어들기 때문에 상당한 이득을 얻을 수 있다. 물론 언롤링 양은 무작정 늘여서는 안 된다. 코드 크기가 커지게 되면 캐시 적중률이 떨어져 사이클을 절약해서 얻는 장점을 모두 상쇄시켜버리는 탓이다.

배열 크기가 언롤링 양에 비례할 경우, 가장 높은 성능을 달성하기 때문에 만일 배열 크기가 언롤링 양의 배수로 떨어지지 않으면 배수 크기만큼만 언롤링 루프로 만들고 나머지는 루프 바깥에서 언롤링하면 된다. 결국 배열 크기를 4나 8 배수로 정렬시킬 경우 코드를 어지럽히지 않고도 루프를 2, 4, 8배로 쉽게 언롤링할 수 있는 것이다.

● 루프 결합
루프는 아키텍처를 불문하고 값비싼 연산이 필요하므로 여러루프가 있을 경우 하나로 결합하는 편이 성능면에서 월등히 유리하다. <리스트 3>과 <리스트 4>를 살펴보자.

<리스트 3> 루프를 두 번 돌리는 예제

void foo(int count, int *x, int *y) { int b; for (b = 0; b < count; b++) { x[b] = b; } for (b = 0; b < count; b++) { y[b] = b; } }

<리스트 4> 루프를 한 번 돌리는 예제

void bar(int count, int *x, int *y) { int b; for (b = 0; b < count; b++) { x[b] = b; y[b] = b; } }

예제에서 알 수 있듯이 <리스트 3>의 foo는 루프를 두 번 돌리는 반면에 <리스트 4>의 bar는 한 번만 돌린다. 이럴 경우 루프 연산에 따른 사이클을 절약할 수 있을 뿐 아니라 경우에 따라서는 캐시를 좀 더 효과적으로 사용하여 성능을 높일 수 있다.

● 불변 코드 분리
코드 내부에서 바뀌지 않은 부분은 코드 바깥으로 분리시킴으로써 반복적인 계산을 막을 수 있다. 아주 단순한 논리인 듯하지만 조금만 신경 쓰면 상당한 효과를 얻을 수 있다.

<리스트 5> 다중 함수 호출 예제

void foo(const char *str) { int i; for (i = 0; i < strlen(str); i++) { … } }

비단 strlen 같은 함수 호출뿐만이 아니라 사칙연산과 같은 경우에도 고정된 상수 값을 루프 내부에서 매번 계산하는 대신, 변수를 하나 잡아 미리 계산한 뒤에 루프로 진입하여 상당한 개선 효과를 얻을 수 있다. 가독성이나 기타 이유로 몸체 크기가 작은 함수를 호출해야 한다면 매크로 확장이나 인라인을 고려하자.

<리스트 6> 단일 함수 호출 예제

void bar(const char *str) { int i; int len = strlen(str); for (i = 0; i < len; i++) { … } }

두 리스트 중 <리스트 6>의 bar은 매번 strlen 함수를 호출하는 foo와 달리 한번만 호출한다. <리스트 5>의 foo는 str의 길이가 길어질수록 눈에 띄게 속력이 느려지지만 bar는 항상 고정 시각에 루프를 돌릴 수 있다.

● 루프 증가를 감소로 대체
거의 대부분의 아키텍처에서는 0에 도달할 때 ZERO 플래그를 재설정한다. 때문에 줄어든 변수를 명시적으로 0과 비교할 필요가 없다. 이런 방법을 응용하면 for 루프 속도를 높이는 한 가지 힌트를 찾을 수 있다.

<리스트 7> 루프 증가 예제

void checksum_inc(int *data) { unsigned int i; int sum = 0; for (i = 0; i < 64; i++) { sum += *(data++); } return sum; }

<리스트 8> 루프 감소 예제

void checksum_dec(int *data) { unsigned int i; int sum = 0; for (i = 64; i != 0; i--) { sum += *(data++); } return sum; }

논리적으로는 큰 차이가 없어 보인다. 하지만 두 코드를 어셈블한 내용을 살펴보면 이야기가 달라진다. ARM의 경우를 예로 들지만 다른 아키텍처도 거의 유사하다.

<리스트 9> 루프 증가의 어셈블 예

checksum_inc MOV r2, r0 r2 = data MOV r0, #0 sum = 0 MOV r1, #0 i = 0 cheksum_inc_loop LDR r3, [r2], #4 r3 = *(data++) ADD r1, r1, #1 i++ CMP r1, #0x40 i와 0x40(십진수 64)를 비교 ADD r0, r3, r0 sum += r3 BCC checksum_inc_loop; (i < 64) 이면 loop 반복 MOV pc, r14 sum 리턴

<리스트 10> 루프 감소의 어셈블 예

checksum_dec 의 수정 MOV r2, r0 r2 = data MOV r0, #0 sum = 0 MOV r1, #0x40 i = 64 cheksum_dec_loop LDR r3, [r2], #4 r3 = *(data++) SUBS r1, r1, #1 i-- (자동 플래그 갱신) ADD r0, r3, r0 sum += r3 BNE checksum_inc_loop; (i != 0) 이면 loop 반복 MOV pc, r14 sum 리턴

checksum_dec와 checksum_inc를 비교해보면(밑줄 그은 곳을 참조) 플래그 설정을 위한 CMP 명령이 하나 줄어들었다는 사실을 발견할 수 있다.

● 분기 제거
루프문에 분기가 들어가면 성능이 떨어진다. 때문에 루프 내에서 분기를 어떻게 제거해야 할 지 고민해야 한다. 만약 최적화 컴파일러라는 것이 있어서 이런 일들을 개발자가 일일이 하지 않는다면 몰라도 일단 아직은 모두 수작업으로 해야 하는 일들이다. <리스트 11>을 살펴보자.

<리스트 11> 분기가 있는 루프문

do { printf("첫번째 출력\n"); if (--a < 0) break; printf("두번째 출력\n"); } while (1);

코드 논리상으로는 큰 문제가 없어 보인다. 하지만 <리스트11>을 <리스트 12>와 같이 수정하면 루프문 안에서 조건문을 제거할 수 있어 성능을 향상시킬 수 있다.

<리스트 12> <리스트 11>에서 분기가 제거된 코드

printf("첫번째 출력\n"); a--; if (a>=0) { do { printf("두번째 출력\n"); printf("첫번째 출력\n"); } while (--a<0); }

이번에는 <리스트 1>의 checksum 함수를 <리스트 13>과 같이 고쳐보자.

<리스트 13> <리스트 1>의 수정

int checksum_dowhile(int *data, unsigned int count) { int sum = 0; do { sum += (*data++); } while (--count != 0); return sum; }

코드를 이렇게 고치면 역시 처음에 count와 0을 비교하는 부분이 빠져서 두 사이클(비교에 이은 분기)을 절약할 수 있다. 물론 언롤링 기법에 비해 성능이 떨어지긴 하지만 코드 크기를 유지한 상태에서 처리 속도도 어느 정도 개선할 수 있으니 두 마리 토끼를 모두 잡아야 하는 경우에 유용하게 쓸 수 있다.

왜 이렇게 루프 최적화에 목숨을 거나?

다른 최적화 기법도 많은 상황에서 루프 최적화에 상당한 지면을 할애해서 다양한 방법을 소개하는 이유는 우리 주변에서 생각보다 루프와 관련된 성능 저하가 많이 일어나기 때문이다. 임베디드 장비를 개발할 때 시스템 속도를 개선하기 위해 사방팔방으로 뛰어다녀 보니 결국 루프 횟수를 줄이거나, 루프 하나를 돌 때 단 몇 사이클이라도 아끼는 방법으로 귀결됨을 여러 차례 목격했다. 지금도 기억나는 가장 극적인 성능 개선은 수천 번에서 수만 번을 반복하는 루프 내부의 불변식을 매크로로 정의해서 확장했을 때 성능이 자그마치 2배에서 10배까지 향상되었을 때였다. 앞서 strlen과 같은 값비싼 함수를 루프 내부에 넣은 예제를 보고 웃고 넘길지 모르겠지만, 주변 코드를 살펴보면 의외로 이런 사소하다고 보면 사소하지만 성능에 치명타를 입히는 코드가 많다. 최적화가 필요하다면 가장 먼저 루프와 루프 내부에 들어있는 분기문을 집중 공략하기 바란다.

분기 최적화
루프 최적화에 이어 이번에는 분기 최적화에 대해 알아보자. 루프 최적화는 조금만 손을 보면 상당한 성능 개선을 이룰 수 있는 반면 분기 최적화는 구현도 어렵고 성능 개선 효과도 미미하다. 하지만 몇 가지 규칙을 알고 있다면 프로그램 작성 과정에서 자연스럽게 성능을 높이는 출발점이라는 점을 염두에 둔다면 반드시 관심을 가져야 할 기법이다.

● 기본 switch ~ case 문 최적화
프로그램을 작성하다 보면 switch ~ case 문을 자주 사용하게 된다. 하지만 switch ~ case 문은 실행 중에 수많은 조건을 판별해서 분기해야 하기 때문에 CPU 입장에서는 상당히 난감한 구문이라고 보면 틀림없다. <리스트 14>를 살펴보자.

<리스트 14> switch ~ case 문 예제

switch (x) { case 10: case 12: case 14: case 16: case 20: foobar(); break; }

<리스트 14>와 같은 코드를 작성했을 경우 컴파일러는 10, 12, 14, 16, 20일 경우를 일일이 판단해야 하는 탓에 상당한 어려움을 겪는다. 파워PC의 어셈블리 코드인 <리스트 15>를 보면 <리스트 14> 코드가 얼마나 복잡하게 만들어지는지 알 수 있다.

<리스트 15> <리스트 14>의 파워PC 어셈블리 코드

lwz R3,x # x를 R3으로 cmpwi cr0,R3,10 beq cr0,lab10 # if (x == 10) goto lab10 cmpwi cr1,R3,12 beq cr1,lab12 # else if (x == 12) goto lab12 cmpwi cr5,R3,14 beq cr5,lab14 # else if (x == 14) goto lab14 cmpwi cr6,R3,16 beq cr6,lab16 # else if (x == 16) goto lab16 cmpwi cr7,R3,18 beq cr7,lab18 # else if (x == 18) goto lab18 cmpwi cr0,R3,20 beq cr0,lab20 # else if (x == 20) goto lab20 ... lab10: lab12: lab14: lab16: lab18: lab20: # foobar 호출

하지만 아주 간단한 수정만 한 <리스트 16>을 어셈블리 코드로 만들면 전혀 다른 결과를 얻을 수 있다.

<리스트 16> 수정된 switch ~ case 문 예제

switch (x) { case 10: case 11: case 13: case 14: case 15: foobar(); break; }

<리스트 16>을 어셈블리 코드로 만들면 <리스트 14>때 보다 코드의 양도 훨씬 적어지고 판단 횟수도 줄어드는 것을 확인할 수 있다. 별로 다르지 않은 코드지만 그 결과는 큰 차이를 나타내는 것이다. 그리고 이 차이의 중심에는 컴파일러가 좋아하는 방법으로 프로그램을 작성한다는 규칙이 있다.

<리스트 17> <리스트 16>의 어셈블리 코드

lwz R3,x # x를 R3으로 subic R4,R3,10 # tmp = (x - min) cmplwi cr3,R4,5 # 논리 비교 (tmp, max-min) bgt cr3,out # if tmp < 0 또는 tmp > 5, # x 는범위 [min,max] 바깥 # foobar 호출 out:

● 고급 switch ~ case 문 최적화
앞에서는 아주 기초적인 구성의 switch ~ case 문의 최적화 방법에 대해 알아보았다. 이번에는 조금 더 복잡한 형태의 Switch~ case 문을 이용해서 최적화 하는 방법에 대해 알아보자.

<리스트 18> 고급 switch ~ case 문 예제

switch(x){ case 0: code_for_case_0; case 1: code_for_case_1; case 2: code_for_case_2; case 3: code_for_case_3; case 4: code_for_case_4; case 5: code_for_case_5; case 6: code_for_case_6 case 7: code_for_case_7 default: code_for_case_d; }

감이 있는 개발자라면 <리스트 18>과 같은 코드가 테이블 검색법을 사용할 경우 제격이라는 생각이 들지 모르겠다. 이번에는 파워PC 어셈블리어와 ARM 어셈블리어를 동시에 제시해서 비교해보기로 하자. 먼저 <리스트 19>를 통해 테이블 검색 기법을 사용하는 파워PC부터 살펴보자.

<리스트 19> <리스트 18>의 파워PC 어셈블리 코드

lwz R4,x # x를 R4로 lwz R7,$TABLE # TABLE 주소를 R7로 slwi R5,R4,2 # 4를 곱함 (테이블 엔트리 당 4 바이트) lwzx R3,R7,R5 # TABLE[x]를 R3로 mtctr R3 # 카운트 레지스터 적재 bctr # 카운트 레지스터 내용으로 분기

<리스트 20>은 테이블 검색 기법을 활용하는 ARM 어셈블리어의 코드이다. code_for_case_?를 담은 TABLE을 정의하고, 오프셋을 계산해서 바로 프로그램 카운터를 적재하는 방법을 사용할 경우 최적화를 달성할 수 있다.

<리스트 20> <리스트 18>의 ARM 어셈블리 코드

x RN 0 CMP x, #8 ADDLT pc, pc, x, LSL#2 B code_for_case_d B code_for_case_0 B code_for_case_1 B code_for_case_2 B code_for_case_3 B code_for_case_4 B code_for_case_5

<리스트 18>과 같은 방식은 아주 빠르게 실행되기 때문에 switch 문을 사용하더라도 비교에 따르는 부하가 거의 없다. 물론 최적화 컴파일러 종류나 문맥에 따라 범위 비교나 테이블 방식으로 코드를 생성하지 못할 수도 있다. 반면에 무작의 case처럼 100% 불가능한 상황이 아님에 주목하자.‘ 할 수 없다’와‘할 수 있다’는 하늘과 땅 차이기 때문이다.

고급 최적화 기법: ARM CPU 아키텍처에 밀접한 memcpy 루틴
지금까지는 구조화 프로그래밍에서 가장 많이 쓰이는 요소인 반복과 분기에 대한 C 프로그래밍 최적화 방안에 대해 알아보았다. 그럼, CPU 아키텍처에 밀접한 방식으로 어셈블리 프로그램을 작성해야 하는 경우는 어떨까? 물론 이 경우에도 최적화를 위해 사용할 수 있는 기법들이 있다.

그 중 가장 대표적인 것이 바로 메모리 관련 함수를 작성할 때이다. 실제로 최적화된 메모리관련 라이브러리는 대부분 어셈블리 언어로 작성되어 있다.

리눅스 커널 내부에서도 자주 사용하는 메모리 함수는 모두 아키텍처 별로 어셈블리어를 사용한다. 리눅스 커널 코드를 받아와서 arch/아키텍처/lib 아래를 보면 아키텍처 별 최적화 기법을 총정리한 어셈블리 코드를 확인할 수 있다.

논리 트리와 해시를 사용한 수동 switch ~ case 문 제작

case 문에 들어가는 값이 연속적인 고정 범위일 경우에는 컴파일러 차원에서 어느 정도 최적화가 가능하다. 하지만 일반적인 switch ~ case 문에서는 어떻게 할까? 크게 두 가지 방법을 생각해볼 수 있다. 하나는 선형 스위치 트리에서 벗어나 깊이가 얕은 트리를 구성하는 방법이다. 나머지 하나는 case 문에 들어가는 조건이 규칙성을 가질 경우 해시 테이블을 만들어서 대응하도록 하는 방법이다. 하지만 둘 다 어셈블리어를 사용해서 코딩을 진행해야 하므로 실제 적용 과정에서 투입한 비용에 비해 이익은 그다지 크지 않다. 결국 switch ~ case 문을 사용할 경우 최대한 case 문에 일관성 있는 조건을 지정해야 컴파일러를 사용한 자동 최적화 작업이나 어셈블리어를 사용한 수동 최적화 작업이 쉬워진다.

관련 라이브러리는 대부분 어셈블리 언어로 작성되어 있다. 리눅스 커널 내부에서도 자주 사용하는 메모리 함수는 모두 아키텍처 별로 어셈블리어를 사용한다. 리눅스 커널 코드를 받아와서 arch/아키텍처/lib 아래를 보면 아키텍처 별 최적화 기법을 총정리한 어셈블리 코드를 확인할 수 있다.

CPU 아키텍처에 밀접한 최적화의 좋은 예로 uClibc에서 구현하고 있는 memcpy(memmove, bcopy) 루틴을 들 수 있다. 이 함수를 작성하는 과정에서 사용하는 각종 최적화 기법을 이해하고 있다면 어렵지 않게 다른 부문에도 적용할 수 있을 것이다.

uClibc에 들어있는 memcpy 함수 구현부는 상당히 길고 복잡하기 때문에 모두 소개하기는 어렵다. 여기에서는 일단 내부에서 어떤 점에 주목해서 구현했는지에 대해 알아본다.

복사 과정에서 조금이라도 속력을 높이기 위해 다양한 조건을 고려한다.

● 방향: 정방향 복사인가 역방향 복사인가(복사 시작 주소와 복사 대상 주소 크기를 비교한다)

● 정렬: 복사 시작 주소와 복사 대상 주소 위치가 정렬되어있는가

● 크기: 12바이트나 32바이트 단위로 복사가 가능한가

각 경우를 모두 따져서 해당 조건에 맞는 서브루틴으로 분기하기 때문에 memcpy를 구현하는 어셈블리 코드 길이가 무척 길어졌다. ARM CPU에서 제공하는 LDM/STM 명령을 사용해서 한번에 블록 전송이 가능한 경우를 살피기 위해 크기를 따지며, 정렬의 경우 메모리 버스와 캐시 라인을 효과적으로 사용하기 위한 목적으로 따진다. ARM CPU의 경우 엔디안을 리틀이나 빅 양쪽 중 하나를 사용할 수 있으므로, 방향까지 잘 따져야 한다.

32비트 블록 전송을 위한 ARM 어셈블리 코드 조각을 보면 <리스트 21>과 같이 단순하면서도 무척 효율적이다.

<리스트 21> 32비트 블록 전송을 위한 ARM 어셈블리 코드

.Lmemcpy_bloop32: ldmdb r1!, {r3, r4, r12, lr} stmdb r0!, {r3, r4, r12, lr} ldmdb r1!, {r3, r4, r12, lr} stmdb r0!, {r3, r4, r12, lr} subs r2, r2, #0x20 bge .Lmemcpy_bloop32

앞에서 설명한 조건을 고려해보면 Lmemcpy를 사용할 경우에는 복사 시작과 복사 대상 주소가 정렬이 되어있고, 전체 자료 크기가 32비트 배수가 될 경우 최대의 효과를 올릴 수 있다. 이래서 우리는 때로 C만 사용하는 경우에도 별로 상관없어 보이는 어셈블리어로 구현된 라이브러리를 확인할 필요가 있는 것이다.

C 언어를 컴파일러가 좋아하는 방식으로 제대로 작성하기만 해도 상당한 성능 개선을 달성할 수 있다는 사실을 직접 확인했다. 물론 정말 좋은 컴파일러라면 이번 기사에서 소개한 내용에 맞춰서 프로그램을 작성하지 않더라도 개발자 의도를 파악해서 자동으로 처리해줘야 하겠지만 유감스럽게도 이렇게 훌륭한 컴파일러는 존재하지 않는다.

컴파일러 이론이 계속해서 발전하고 최적화 기능을 강화한 컴파일러 구현 결과물이 계속해서 나오고는 있지만 그 만큼 컴퓨터 아키텍처와 알고리즘이 복잡해졌기 때문에 효과가 반감되는 느낌이다.

결국 최고 성능을 달성하기 위해서는 개발자가 만든 함수를 어셈블리 코드로 바꿔서 어떤 문제점이 있는지 파악하고 속도를 높이기 위해 다른 코드들과 비교하며 어떤 제약점이 있는지 파악해야 한다. 이렇게 문제점과 제약점을 파악하고 나면 컴파일러가 좋아하도록 최적화한 코드를 C로 만들 수 있게 된다.

최적화와 관련해서 주로 C 언어적인 특성에 집중하다 보니 이번 기사에서는 CPU 메모리버스 특성, CPU 캐시 라인 정렬, 파이프라인, 부동소수점 루틴까지 고려한 최적화 방식은 다루지 않았다. 다음에 기회가 생기면 CPU 아키텍처와 관련해서 좀 더 깊이 있는 최적화 기법을 다루기로 약속하며, 쓸만한 참고 자료를 정리해 두었으니 참고하자. @


참고자료
1. ARM System Developer’s Guide, (주) 씨랩시스 역, Andrew N. Sloss, Dominic Symes, Chris Wright 저, 2005년 사이텍 미디어 출간.
2. 임베디드 메모리 최적화 기법, 여인춘 역, Kris Kaspersky 저, 2004년 에이콘 출간.
3. GCC 완전 정복, 김경헌 역, Kurt Wall과 William von Hagen 저, 2006년 에이콘 출간.
4. 리눅스 문제 분석과 해결, 박재호 역, 마크 윌딩 저, 2006년 에이콘 출간.
5. 리눅스 디버깅과 성능 튜닝, 박재호 역, 스티브 베스트 저, 2006년 에이콘 출간.
6. Inside the machine, John Stokes, 2007. No Starch Press 출간.
7. 위키피디아(최적화): http://en.wikipedia.org/wiki/Optimization_%28computer _science%29
8. PowerPC Compiler Writer’s Guide: http://openlook.org/blog/684
9. x86 ABI: http://www.caldera.com/developers/devspecs/abi386-4.pdf
10. x86_64 ABI: http://www.x86-64.org/documentation/abi.pdf
11. PowerPC 32bit ABI: http://www-3.ibm.com/chips/techlib/techlib.nsf/ techdocs/852569B20050FF77852569970071B0D6/$file/eabi_app.pdf
12. PowerPC 64bit ABI: http://www.freestandards.org/spec/ELF/ppc64/PPCelf64abi-1.9.html


* 이 기사는 ZDNet Korea의 제휴매체인 마이크로소프트웨어에 게재된 내용입니다.

출처 : ZDNet Korea