이번에는 code optimization에 대해서 다뤄보겠습니다. 대부분의 compiler들은 CPU가 이해할 수 있는 machine code로 변환하기 위해 compile을 진행하는데, 이때 코드 그대로 단순히 변환하기 보다는 optimization을 통해 더 빠르게 실행될 수 있도록 만들어줍니다. compiler가 optimization을 진행하는 목표는 크게 다음과 같습니다.
Minimize number of instructions
반복되는 연산을 한 번에 할 수 있도록 바꾸고, 불필요한 연산을 줄이고, slow instruction(multiplication, division 등)을 최소화
Avoid waiting for memory
가능한 모든 data를 register에 유지시키고, cache friendly한 memory access로 변환
Avoid branching
불필요한 branch를 줄이고, branch prediction을 용이하게 하도록 변환
위의 세 가지는 모두 code의 실행 속도를 빠르게 만들어주는 방향의 optimization입니다. 하지만 optimization을 진행할 때 다음과 같은 한계점도 존재합니다.
Generally cannot improve algorithmic complexity
constant factor만 바뀔 뿐 asymptotic analysis(big-O, big-theta)의 결과는 변하지 않음
Must not cause any change in program behavior
programmer가 의도한 대로 program이 실행되어야 하므로 logic이 바뀌지 않아야 함
Usually only analyze one function at a time
전체 program을 한 번에 analyze하는 것은 expensive
이제 앞서 언급한 전략에 맞춘 optimization에는 어떤 것이 있는지에 대해 그 예시를 들어 알아보겠습니다. code의 변화를 알아보기 쉽도록 assembly code가 아닌 c code를 통해 살펴보겠습니다.
// example 1
long mask = 0xFF << 8;
long mask = 0xFF00;
// example 2
size_t namelen = strlen("Harry Bovik");
size_t namelen = 11;
위의 code는 동일한 결과가 나타나는 두 가지 code입니다. 두 개의 공통점은 compile을 진행하기 이전에 이미 그 값을 결정할 수 있다는 점입니다. mask = 0xFF << 8
과 namelen = strlen("Harry Bovik")
그 결과가 이미 정해져 있으므로 이를 각각 mask = 0xFF00
과 namelen = 11
로 바꾸어 instruction의 수를 줄일 수 있습니다. 이와 같이 constant value로 정해진 연산을 compile time에 미리 수행해 optimize하는 방법을 constant folding이라 합니다.
long a = b * 5;
long a = (b << 2) + b;
위의 두 code의 연산 결과는 a = b * 5
로 동일합니다. 둘의 차이점은 multiplication을 사용한 것과 logical shift를 사용한 것에 있습니다. hardware에서 multiplication은 매우 느린 연산 중에 하나인 반면 shift는 빠르게 수행할 수 있으므로 아래 code의 속도가 더 빠르게 진행됩니다. 이와 같이 heavy한 연산을 더 빠른 연산으로 바꾸어 동일한 결과를 만들어내는 것을 strength reduction이라 합니다.
// example 1
if (0) { puts("Kilroy was here"); }
if (1) { puts("Only bozos on this bus"); }
puts("Only bozos on this bus");
// example 2
x = 0;
x = 23;
x = 23;
첫 번째 example에서 if(0)
에 해당하는 line은 항상 false이므로 실행되지 않고, if(1)
에 해당하는 line은 항상 true이므로 무조건 실행되어 결과적으로 puts("Only bozos on this bus");
를 실행시키는 것과 동일한 결과를 나타냅니다. 두 번째 example에서는 x = 0;
의 결과에 x = 23;
을 overwrite하므로 x = 0;
을 실행하지 않은 것과 동일한 결과를 나타냅니다. 이와 같이 실제로 실행하지 않아도 결과가 동일한 code를 compile 과정에서 지우는 것을 dead code elimination이라 합니다.
norm[i] = v[i].x * v[i].x + v[i].y * v[i].y;
elt = &v[i];
x = elt->x;
y = elt->y;
norm[i] = x*x + y*y;
위의 code는 norm[i]
를 계산하기 위해 v[i]
에 총 4번 access하는 반면 아래의 code는 새로운 변수 x
와 y
에 v[i].x
와 v[i].y
를 assign하여 결과적으로 v[i]
에는 두 번 access하는 것을 알 수 있습니다. 이를 통해 memory에 access하는 횟수를 줄일 수 있어 성능 향상을 이룰 수 있습니다. 이와 같이 동일한 memory에 대한 access의 횟수를 줄이는 optimization을 common subexpression elimination(CSE)라 합니다.
// example 1
long j;
for (j = 0; j < n; j++) {
a[n*i+j] = b[j];
}
long j;
int ni = n*i;
for (j = 0; j < n; j++) {
a[ni+j] = b[j];
}
// example 2
void lower(char *s) {
size_t i;
for (i = 0; i < strlen(s); i++ {
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
}
void lower(char *s) {
size_t i, n = strlen(s);
for (i = 0; i < n; i++) {
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
}
위의 두 example의 공통점은 loop 내에서 매 iteration마다 연산이 진행되는 부분을 loop의 밖으로 빼주었다는 점입니다. example 1에서는 n * i
의 연산을 loop 밖에서 진행해 heavy한 연산을 매 iteration마다 진행하지 않고 실행하도록 했으며 example 2에서는 strlen(s)
를 loop 밖에서 실행해 function call의 횟수를 줄이도록 한 것입니다. 이를 통해 instruction의 갯수와 불필요한 branch를 모두 줄일 수 있어 속도의 향상을 이룰 수 있습니다. 이와 같이 code를 옮겨 성능을 높이는 optimization을 code motion이라 합니다.
int pred(int x) {
if (x == 0) return 0;
else return x - 1;
}
int func(int y) {
return pred(y) + pred(0) + pred(y + 1);
}
int func(int y) {
int tmp;
if (y == 0) tmp = 0; else tmp = y - 1;
if (0 == 0) tmp += 0; else tmp += 0 - 1;
if (y + 1 == 0) tmp += 0; else tmp += (y + 1) - 1;
return tmp;
}
int func(int y) {
int tmp;
if (y != 0) tmp = y - 1;
if (y != -1) tmp += y;
return tmp;
}
첫 번째 code는 func()
에서 pred()
를 call하도록 구현한 것이며 두 번째는 pred()
를 call하는 대신 func()
내에서 모두 해결하도록 구현한 것입니다. pred()
를 call할 때마다 code에 branch가 생기고 이로 인해 branch prediction이 틀린 경우 overhead가 크게 나타나는 등 매우 느려질 수 있습니다. 반면 이를 기존 function 내에서 모두 구현한 경우 control path의 변화를 줄여 전체적인 속도의 향상을 이룰 수 있습니다. 이와 같이 function call 대신 callee의 동작을 caller 내부로 옮겨주는 것을 inlining이라 합니다. 여기에 추가적으로 dead line elimination까지 진행해 세 번째 code와 같이 optimize 한다면 if
에 의한 branching까지 줄어들어 더 좋은 성능을 얻을 수 있습니다.
for (size_t i = 0; i < nelts; i++) {
A[i] = B[i]*k + c[i];
}
for (size_t i = 0; i < nelts - 4; i += 4) {
A[i] = B[i]*k + c[i];
A[i+1] = B[i+1]*k + c[i+1];
A[i+2] = B[i+2]*k + c[i+2];
A[i+3] = B[i+3]*k + c[i+3];
}
위의 예시는 loop invariant의 increment를 늘리고 한 iteration에서 더 많은 연산을 진행해 전체적인 iteration을 1/4로 줄이도록 바꾼 code입니다. 위와 같은 optimization을 통해 먼저 loop의 횟수를 줄일 수 있으므로 backward branch의 갯수가 줄어드는 효과를 얻을 수 있으며, 현재 예시에는 드러나지 않았지만 CSE, code motion 등 추가적인 optimization 까지 가능하다는 장점이 있습니다. 이와 같은 optimization을 loop unrolling이라 합니다.
reference
Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016