얼마전에 모바일기기에서 일정수준의 품질을 유지하면서 실행되는 JPEG라이브러리를 만드는 프로젝트를 진행한적이 있었다. 이 프로젝트를 진행하면서, 여러가지 방법으로 프로그램을 더 빨리 만들 수 있다는 사실을 경험적으로 알게 되었다. 이 문서는 C(:12)로된 코드를 속도와 메모리 양측모두에서 최적화하기 위한 경험적인 정보들을 포함하고 있다.
물론 여러분은 C 코드를 최적화 하는 방법에 대한 참고문서를 어렵지 않게 획득할 수 있을 것이다. 그러나 대부분의 문서가 팁수준에서 문제에 접근할 뿐으로, 컴파일러(:12)나 기계어(:12)수준에서 어떻게 프로그래밍을 해야 하는지에 대한 정보는 담고 있지 않다.
보통 프로그램의 속도를 높이게 되면 코드의 크기가 늘어나게 된다. 코드의 크기가 늘어나면 프로그램이 복잡해지고, 읽고 이해하기 어려워진다. 메모리 자원이 넉넉한 개인PC혹은 서버 컴퓨터라면 문제가 되지 않겠지만 PDA와 같은 제한된 메모리 자원을 가진 기기일 경우 심각한 문제가 될 수 있다. 1%의 속도향상을 위해서 코드의 크기가 10%만큼 늘어난다면 분명 문제가 될 것이다. 이런 이유로 속도와 코드크기 모두에 대한 최적화를 수행하기로 결정을 했다.
내가 진행하는 프로젝트가 ARM(:12) 플랫폼에서 진행된 관계로, ARM 최적화와 관련된 팁들이 필요했었다. 나는 인터넷을 통해서 ARM 최적화와 관련된 많은 문서를 검색하고 이중 유용한 것들 중심으로 수집해서 테스트를 했었다. 그러나 대부분의 문서들이 나에게는 도움이 되지 않았음을 고백한다. 이러한 실수를 줄이기 위해서 유용하고 효과적인 몇개의 팁만을 모으기로 결정했다.
토론의 주제를 명확히 하고 넘어가자. 컴퓨터 프로그램을 최적화하기 위한 가장 중요한 것은 프로그램을 이루는 각각의 모듈중 어느 부분이 느리게 작동하거나, 큰 메모리를 소비하는지를 찾아내는 것이다. 이들 각각의 부분을 최적화하면 프로그램이 전체적으로 빨라질 것이기 때문이다. 이러한 모듈단위의 최적화는 최적화를 위한 부분을 비교적 쉽게 찾고, 쉽게 해결할 수 있다는 장점을 가진다.
The optimizations should be done on those parts of the program that are run the most, especially those methods which are called repeatedly by various inner loops that the program can have.
일반적으로 경험이 풍부한 프로그래머들은 아주 쉽게 프로그램이 요구하는 최적화될 필요가 있는 핵심을 쉽게 찾아낼 수 있을 것이다. 가장 좋은 최적화 방법은 경험많은 프로그래머를 고용하는 것이다. 그러나 경험많은 프로그래머는 매우 드물며, 경험이 많다고 해도 더 좋은 결과를 위해서는 최적화를 위한 좋은 툴을 사용할 필요가 있다. Visual C++ 과 같은 통합 개발환경은 함수단위로 프로그램의 소비시간을 측정할 수 있는 profiler를 제공한다. 리눅스의 경우에는 gprof(:12)와 같은 profiler를 사용할 수 있다. 혹은 Intel Vtune와 같은 프로그램을 사용할 수 있는데, 이들 프로그램을 사용하면 프로그램의 어느부분이 가장 많은 시간을 소비하는지를 확인할 수 있다. 개인적인 경험으로 루프 혹은 third party 라이브러리(:12) 메서드를 호출하는 영역이 프로그램을 느리게 하는 경우가 많았다.
아래의 최적화 기법을 적용한다고 해서, 항상 빨라진다는 걸 보장할 수는 없다. 컴파일러의 버전과 종류, 만들고자 하는 애플리케이션의 특징에 따라서 결과가 달라질 수 있기 때문이다. 만약 임베디드기기에 올라가는 애플리케이션이 아닌, 고수준의 애플리케이션의 개발이 목적이라면 아래의 최적화 기법은 그다지 소용이 없을 것이다. 고수준 애플리케이션이라면, 미세한 성능최적화를 위한 노력하는 것 보다는 주요 데이터처리 알고리즘과 가독성에 신경을 쓰는게 더 나은 결과를 보여줄 것이다.
우리가 사용할 값이 음수가 아니라면 int 형대신에 unsigned int형을 사용해야 한다. 어떤 프로세스들은 unsigned integer의 연산이 signed 연산보다 매우 빠르다. 또한 나누기/나눗셈 작업의 경우에도 음수가 필요 없다면 unsigned 를 명시해주는게 좋다.
루프에 사용될 변수라고 한다면, 다음과 같이 깔끔하고 효율적으로 선언할 수 있을 것이다.
기억해야할 또다른 점은 floating point 연산은 매우 느리다라는 점이다. floating point 데이터 타입은 자바와 함께 하는 컴퓨터과학문서를 참고하기 바란다. 척 봐도 floating point 숫자는 다루기가 꽤나 복잡하다는 것을 알 수 있을 것이다. 만약 여러분이 소숫점 2자리까지의 정확도를 유지하는 회계프로그램을 만든다면, 모든 값에 x100을해서 int 형으로 바꾼다음 연산을 하도록 한다. 가능하면 외부의 수학라이브러리를 사용하지 않도록 한다. FPUs와 같은 라이브러리는 매우 느리다.
널리 쓰이는 버젼은 약 20+4.3N의 사이클을 보여준다. ARM 뿐만 아니라 프로세서를 막론하고 이런 연산은 피하는게 바람직하다. 나눗셈연산은 가능하다면 곱셈으로 대체해서 사용하기 바란다.
예를들어 (a/b) > c 는 b * c가 integer 범위안이라는 것을 안다면 a > (c * b)로 다시 쓰일 수 있다.
천재 수학자의 어린시절 이야기를 들은 기억이 있다. 자리를 비운 사이 얘들이 놀지 못하게 하려고 1부터 100까지 더하라는 문제를 냈는데, 5분만에 풀고 놀았더란 얘기다. (수학자 파스칼의 어린시절 얘기이던가 가물가물 하다.)
어떻게 풀었냐고 물어봤더니. "1+100, 2+99, 3+98"이게 50번 반복되더라는 것이어서 101*50 해서 답을 구했다고 대답했다고 한다. 이것을 대수로 나타내면 n(n+1) * 0.5 이 나온다.
약간만 수학적으로 머리를 굴리는 것으로 매우 큰 효과를 얻을 수 있다. 시간나면 대수학을 공부해보도록 하자.
나누기를 할 때 2의 배수를 분자로 함으로써, 코드를 더 효율적으로 만들 수 있다. 이경우에 컴파일러는 나누기 연산대신에 shift 연산을 할 수 있기 때문이다. shift 연산은 가장빠른 연산중의 하나다. 그러므로 가능하면 2의 배수로 나눌 수 있도록 스케일을 조절할 필요가 있다. (예를 들어 66으로 나누어야 한다면 64로 나눌 수 있도록 스케일을 조절하라).
전역 변수는 절대 레지스터에 할당할 수 없다. 포인터를 사용하여 간접적으로 할당하거나 함수호출을 이용해서 전역변수를 변환할 수 있다.
따라서 컴파일러는 전역변수의 값을 레지스터에 올려서 캐쉬할 수 없게 되고 때문에 글로벌 변수를 이용할 때마다 다시 읽어들이는 오버로드가 생기게 된다. 그러므로 가능하면 글로벌 변수를 직접 호출하는 대신에, 로컬변수를 이용해서 필요한 연산을 하고 그 결과를 글로별 변수에 할당하는 방법을 사용해야 한다.
가능하면 지역변수로 char 이나 short를 사용하지 않도록 한다. char와 short가 사용될 경우 컴파일러는 값을 저장하기 위해서 8bit 혹은 16bit를 할당한 후, 남는 크기를 줄이는 작업을 하게 된다. 이는 24bit, 16bit 만큼을 shift 시키는 연산을 하게 됨을 의미한다. 그러므로 입력되는 데이터가 8 혹은 16 비트라고 하더라도, 32bit로 연산을 하도록 함수를 만들 필요가 있다.
구조체를 그대로 넘길경우 구조체의 모든 값이 스택에 올라가기 때문에 느리게 작동한다. 그래서 구조체의 포인터를 넘기는 경우가 많다. 나는 수 kbyte의 구조체를 넘기는 프로그램을 본적이 있다. 이런 경우 포인터를 쓰도록 하자.
포인터를 통해서 구조체를 넘길때, 구조체의 멤버를 수정할일이 없다면 상수로 선언해서 넘기도록 하자.
첫번재 코드보다 두번째 코드가 더 빠른 수행능력을 보여준다.
두번째 코드는 i가 0이 아니면 i를 감소시키고 다음 코드를 진행하라의 의미인데, 조건 검사의 경우 0인지 아닌지를 비교하는데 더 작은 시간이 소비되기 때문이다. 그러므로 두번째 코드는 아래와 같이 재작성할 수 있다. 두번째 예제코드 보다는 아래의 코드가 더 보기 쉬우므로, 아래의 코드를 사용하는게 가독성 측면에서 유리할 것이다.
함수는 호출되기 위한 분명한 오버헤드가 존재한다. 실행해야될 함수가 있는 포인터만 변경하는게 아닌, 값들을 stack에 push하는 것과 새로운 변수의 할당과 같은 작업이 수행되기 때문이다. 때문에 루프에서 함수를 호출하는 등의 코드는 작성하지 않는게 좋다. 이런류의 코드는 반대로 함수에서 루프를 수행하도록 변경하는걸 추천한다.
아래의 코드는는 주어진 값에 1bit가 몇개인지를 검사하는 코드다. 0000 1010 이라면 2를 리턴하는 식이다. 이러한 비트필드는 일정한 범위의 값이 참인지 거짓인지를 빠르게 체크하기 위해서 널리 사용될 수 있다.
다음과 같이 1씩 오른쪽으로 쉬프트 하면서, & 연산을 한다.
프로세서에서 함수의 호출은 예상과 달리 그리 큰 비용이 들지는 않는다. 함수가 호출되면 register에 함수의 인자를 넘기게 된다. 이 인자들은 char, short, int, float, structure등이 올 수 있다. 이들 인자는 실제 4개만을 전달할 수 있다는 한계를 가진다. 이 이상으로 인자가 넘어가게 되면, stack를 이용해서 함수의 인자를 넘기게 된다. 당연히 함수를 호출함에 있어서 OverHead가 발생하게 된다. 함수호출시 발생하는 인자의 제한에 대해서는 Linux에서의 Assembly문서를 참고하기 바란다.
예제코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int f1(int a, int b, int c, int d) {
return a + b + c + d;
}
int g1(void) {
return f1(1, 2, 3, 4);
}
int f2(int a, int b, int c, int d, int e, int f) {
__inline키워드를 이용하면 함수를 인라인화 할 수 있게 된다. 이것은 일종의 매크로 처럼 작용을 하며, 함수가 호출되는 대신 함수의 본체가 직접 치환이 되어 버린다. 이렇게 함으로써, 함수를 호출하는데 드는 비용을 줄일 수 있게 된다. 반면 코드가 모두 치환되어 버리므로, 코드의 크기가 커지게 된다.
Contents
1. 소개
2. 선언
3. 어디에 필요한가
3.1. 정말 빨라지는 가 ?
4. 데이터 연산
4.1. 정수
4.2. 나눗셈 그리고 나머지
4.3. Combining division and remainder
4.4. 1 부터 n 까지 더하기
4.5. 짝수 홀수 확인
4.6. 2의 배수로 나누기
4.7. Binary Breakdown
4.8. 배열을 이용한 index 생성
4.9. 나머지 연산자의 대체
4.10. Using Aliases
5. 데이터 타입
5.1. 전역 변수
5.2. 지역변수
5.3. 포인터
5.4. Pointer chains
5.5. Switch 대신 lookup table 를 사용하라
6. 루프
6.1. Loop termination
6.2. 더욱 빠른 for 문
6.3. Loop jamming
6.4. 함수 루프
6.5. Population count - 비트 계수하기
6.6. Earyl loop breaking
6.7. Loop 사용하지 않기
7. 함수 디자인
7.1. 함수 호출 Overhead
7.2. 가능한 인자의 수를 줄여라
7.3. 인라인 함수
8. 참고문헌
1. 소개
2. 선언
3. 어디에 필요한가
3.1. 정말 빨라지는 가 ?
4. 데이터 연산
4.1. 정수
4.2. 나눗셈 그리고 나머지
4.3. Combining division and remainder
4.4. 1 부터 n 까지 더하기
4.5. 짝수 홀수 확인
4.6. 2의 배수로 나누기
4.7. Binary Breakdown
4.8. 배열을 이용한 index 생성
4.9. 나머지 연산자의 대체
4.10. Using Aliases
5. 데이터 타입
5.1. 전역 변수
5.2. 지역변수
5.3. 포인터
5.4. Pointer chains
5.5. Switch 대신 lookup table 를 사용하라
6. 루프
6.1. Loop termination
6.2. 더욱 빠른 for 문
6.3. Loop jamming
6.4. 함수 루프
6.5. Population count - 비트 계수하기
6.6. Earyl loop breaking
6.7. Loop 사용하지 않기
7. 함수 디자인
7.1. 함수 호출 Overhead
7.2. 가능한 인자의 수를 줄여라
7.3. 인라인 함수
8. 참고문헌
Recent Posts
Archive Posts
Tags