[C코드 최적화] 집합원소 저장의 효율적 방법
개요
해당 내용은 ‘임베디드 프로그래밍 C코드 최적화’ 책의 story 18에 내용을 정리하였습니다.
최적화에 필요한 다양한 방법을 알아보려 합니다.
어려운 내용은 없으나, 습관을 들이는게 중요할듯 합니다.
비용이 낮은 연산자 선택하기
같은 결과를 만들 수 있다면 비용이 낮은 연산자를 선택하여 코딩하는 것이 좋습니다. (근데 이게 참….어려움 ㅠㅠ)
예를 들어 나눗셈에 / 나 % 연산자를 쉽게 사용하지만, 이 연산자의 비용은 매우 큽니다.
좀 더 좋은 알고리즘을 고민하고, 한 라인을 코딩하더라도 어러 표현방법, 여러 연산자를 고민하는 것이 좋습니다.
#include <stdio.h>
void main(){
int x, y, z, k;
x = z = 10, y = k = 50;
y %= 12; // y와 k는 모두 12로 나눈 나머지 값을 갖는다
k &= 3;
x /= 8; // x와 Z는 모두 8로 나눈 몫을 값으로 갖는다.
z >>= 3;
printf("x=%d, z=%d, y=%d, k=%d \n", x, z, y, k);
}
objdump를 이용해 어셈블리를 확인해보면 다음과 같습니다.
void main(){
10408: e92d4800 push {fp, lr}
1040c: e28db004 add fp, sp, #4
10410: e24dd018 sub sp, sp, #24
int x, y, z, k;
x = z = 10, y = k = 50;
10414: e3a0300a mov r3, #10
10418: e50b3008 str r3, [fp, #-8]
1041c: e51b3008 ldr r3, [fp, #-8]
10420: e50b300c str r3, [fp, #-12]
10424: e3a03032 mov r3, #50 ; 0x32
10428: e50b3010 str r3, [fp, #-16]
1042c: e51b3010 ldr r3, [fp, #-16]
10430: e50b3014 str r3, [fp, #-20] ; 0xffffffec
y %= 12; // y와 k는 모두 12로 나눈 나머지 값을 갖는다
10434: e51b2014 ldr r2, [fp, #-20] ; 0xffffffec
10438: e59f3080 ldr r3, [pc, #128] ; 104c0 <main+0xb8>
1043c: e0c31293 smull r1, r3, r3, r2
10440: e1a010c3 asr r1, r3, #1
10444: e1a03fc2 asr r3, r2, #31
10448: e0411003 sub r1, r1, r3
1044c: e1a03001 mov r3, r1
10450: e1a03083 lsl r3, r3, #1
10454: e0833001 add r3, r3, r1
10458: e1a03103 lsl r3, r3, #2
1045c: e0423003 sub r3, r2, r3
10460: e50b3014 str r3, [fp, #-20] ; 0xffffffec
k &= 3;
10464: e51b3010 ldr r3, [fp, #-16]
10468: e2033003 and r3, r3, #3
1046c: e50b3010 str r3, [fp, #-16]
x /= 8; // x와 Z는 모두 8로 나눈 몫을 값으로 갖는다.
10470: e51b300c ldr r3, [fp, #-12]
10474: e2832007 add r2, r3, #7
10478: e3530000 cmp r3, #0
1047c: b1a03002 movlt r3, r2
10480: a1a03003 movge r3, r3
10484: e1a031c3 asr r3, r3, #3
10488: e50b300c str r3, [fp, #-12]
z >>= 3;
1048c: e51b3008 ldr r3, [fp, #-8]
10490: e1a031c3 asr r3, r3, #3
10494: e50b3008 str r3, [fp, #-8]
printf("x=%d, z=%d, y=%d, k=%d \n", x, z, y, k);
10498: e51b3010 ldr r3, [fp, #-16]
1049c: e58d3000 str r3, [sp]
104a0: e51b3014 ldr r3, [fp, #-20] ; 0xffffffec
104a4: e51b2008 ldr r2, [fp, #-8]
104a8: e51b100c ldr r1, [fp, #-12]
104ac: e59f0010 ldr r0, [pc, #16] ; 104c4 <main+0xbc>
104b0: ebffff8c bl 102e8 <printf@plt>
}
위의 예제를 볼때 연산자의 차이가 꽤 많이 나는것을 알 수 있습니다. 비트 연산은 나눗셈 연산에 비해 비용이 매우 낮기 때문입니다. 제가 어셈블리를 잘은 모르지만…. 사용되는 인스트럭션에 매우 적은것을 확인할 수 있습니다.
short circuit 원리의 활용
void f1{
int x = 10, y = 20;
if((x < 5) && (y = 10))
x += 10;
printf("x=d, y=%d", x, y);
}
위 코드의 실행 결과를 예상해봅시다.
x=10, y=20x=20, y=20x=10, y=10
답이 갈리는데는 이유가 있겟지만….
3라인에 교묘한 버그가 있다.
if((x < 5) && (y = 10))
원래의 의도는 y==10 일텐데, 하나를 빼먹었습니다.
그렇기 때문에 해당 부분은 y에 10이 대입되며, 10이 입력되어 해당 구문은 참이 됩니다.
하지만… 해당 코드의 답은 x=10, y=20 입니다.
(x < 5)가 거짓이기 때문에 그 뒤를 수행하지 않기 때문입니다.
if는 구문이 참일때만 실행되기 때문에 이미 거짓이면 그 뒤는 더이상 볼 필요가 없습니다.
short circuit 의 원리는 다음과 같습니다.
- && : 논리곱인 경우에 첫 비교문이 거짓이면 모두 거짓이므로 그 뒤의 비교문은 모두 수행하지 않는다.
-
: 논리합의 경우에는 첫 비교문이 참이면 모두 참이 되므로 그 뒤의 비교문은 모두 수행하지 않는다.
따라서 short circuit 최적화 방법은 다음과 같습니다.
- && : 논리곱은 거짓일 확률이 높은 문장을 앞쪽에 둔다.
-
: 논리합은 참일 확률이 높은 문장을 앞쪽에 둔다.
연관된 표현은 묶어서 처리하기
바로 예제를 보도록 합시다.
// Before
a = b / c + d / c;
// After
a = (b + d) / c;
위의 예제는 고등학교 수학시간에 배운 분배법칙(맞나?) 를 기억하시면 되겠습니다. After의 코드가 나눗셈을 한번 덜 하기 때문에 더 효율적입니다.
// Before
if((a >= 0 && a < 10) && (b >= 0 && b <10)){
f1()
};
//After
if( (unsigned) (a | b) < 10 ) {
f1();
}
Before의 코드의 조건을 한번 잘 보시기 바랍니다.
- a가 0 이상이거나 10 미만
- b가 0 이상이거나 10 미만
a와 b의 크기 조건이 같습니다. 양수이고 10 미만으로 정의할 수 있습니다.
그렇기 때문이 After 와 같이 바꿀 수 있습니다.
a | b 는 a와 b를 or연산하는 표현입니다. or 연산이기 때문에 a 또는 b가 10보다 크다면 a|b는 10이 넘게됩니다.
그리고 unsigned로 casting을 하여 음수인지 비교하는 연산을 제거할 수 있습니다.
만약 음수였다면 최상위 비트가 1이기 때문에 a|b는 매우 큰 수가 될 것입니다. (int형이라면 20억이 넘는 수가 될껍니다.)
그렇기 때문에 (unsigned) (a | b) < 10 으로 최적화할 수 있겠습니다.
// Before
if((x == 1) | (x == 2) || (x == 4) || (x == 8)){
fl();
}
//After
if( x & (x-1) == 0 && x!= 0) {
f1();
}
before 의 조건을 확인해보면 비트가 하나만 1인 수일때만 조건을 만족합니다.
그럼 이제 after의 코드를 보도록 합시다.
x & (x-1) 의 결과는 비트가 하나만 1일때만 0이 됩니다.
하지만 x 가 0일때도 역시 결과가 0이 됩니다.
x-1 은 0xffffffff 이기 때문에 0이랑 and 연산을 하면 0이 되기 때문입니다.
그래서 x!=0 조건이 추가로 넣어야 합니다.
이때 x가 0일 경우가 더 낮기 때문에 해당 조건은 뒤로 붙어야 합니다. (아까 위에서 보셧죠?)
또한 Before은 x의 값이 추가될때마다 조건이 하나씩 추가됩니다. 16, 32, 64 등의 값도 확인해야한다면 그 만큼 조건이 늘어나게 됩니다.
하지만 After 은 그럴 필요가 없어 더 좋은 표현이라고 할 수 있겠습니다.
실수 연산의 표현
실수의 나누기는 느리다.
// Before
x = x / 4.0;
// After
x = x * (1.0 / 4.0)
처음 이 코드를 보았을때는 ‘연산이 더 많은거 아닌가?’ 라는 생각이 들었습니다. 하지만 책의 설명을 보니 이해가 됬습니다.
최적화 옵션을 주어 컴파일하게되면 상수의 계산은 컴파일 단계에서 미리 수행하게 됩니다.
즉 1.0 / 4.0은 컴파일 과정에서 미리 계산하기 때문에 실제 실행할때는 나눗셈이 아닌 곱셈 연산을 하게 됩니다.
나누기 연산보다 곱하기 연산이 더 빠르기 때문에 위와 같이 최적화하는것이 좋습니다.
가능하면 double 보다는 float 사용하기
double은 8바이트이기 때문에 메모리 엑세스가 늘어나며 , 메모리 소비량도 늘어납니다. 또한 double에 비해 float의 정밀도가 낮기 때문에 계산 복잡도가 작아 double에 비해 빠르게 수행할 수 있습니다.
고정 소수점으로 변환하여 연산하기
부동 소수점은 고정 소수점에 비해 속도를 수십 배 떨어뜨릴 수 있습니다. 그래서 가능하다면, 고정 소수점을 사용하는 것이 좋습니다.
Leave a comment