Code optimization

이번에는 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

---

Example of optimization

이제 앞서 언급한 전략에 맞춘 optimization에는 어떤 것이 있는지에 대해 그 예시를 들어 알아보겠습니다. code의 변화를 알아보기 쉽도록 assembly code가 아닌 c code를 통해 살펴보겠습니다.

• constant folding

// 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이라 합니다.

• strength reduction

long a = b * 5;
long a = (b << 2) + b;

위의 두 code의 연산 결과는 a = b * 5로 동일합니다. 둘의 차이점은 multiplication을 사용한 것과 logical shift를 사용한 것에 있습니다. hardware에서 multiplication은 매우 느린 연산 중에 하나인 반면 shift는 빠르게 수행할 수 있으므로 아래 code의 속도가 더 빠르게 진행됩니다. 이와 같이 heavy한 연산을 더 빠른 연산으로 바꾸어 동일한 결과를 만들어내는 것을 strength reduction이라 합니다.

• dead code elimination

// 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이라 합니다.

• common subexpression elimination (CSE)

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)라 합니다.

• code motion

// 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이라 합니다.

• inlining

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까지 줄어들어 더 좋은 성능을 얻을 수 있습니다.

• loop unrolling

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