컴퓨터를 덜 느리게 하는 방패 [CSAPP Chap 5]

앞의 글에서 다루었던 문제들은 명시적인 처리 내지 맥락에 맞는 작성으로 해결 할 수 있다. 컴파일러들이 이렇게 보수적으로 접근하는 것을 고려하면 TypeScript는 어쩌면 컴파일러 친절에 특화된 언어가 아닐까라는 생각이 든다. 한두줄 차이의 다른 최적화 기법을 논해보자.

---

코드 이동 (Code Motion)

가장 기본적이고 강력한 최적화 기법 중 하나이다.
루프 안에서 반복적으로 수행되지만 결과가 변하지 않는 계산을 찾아 루프 밖으로 빼내는 것이 주된 내용이다.

for (int i = 0; i < strlen(s); i++) {
    // ...
}

// 최적화 후
int length = strlen(s); // 계산을 루프 밖으로 이동!
for (int i = 0; i < length; i++) {
    // ...
}

예를 들어 아래와 같은 코드는 매번 같은 결과를 낼 x y를 반복문 밖으로 빼둠으로써 약간의 시간을 벌 수 있다.

// 2차원 배열의 모든 요소에 (x * y)를 곱하는 함수
void scale_matrix(int *matrix, int n, int x, int y) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i*n + j] *= (x * y);
        }
    }
}

void scale_matrix(int *matrix, int n, int x, int y) {
    int factor = x * y; // 계산을 한 번만 수행!
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i*n + j] *= factor;
        }
    }
}

 

계산 강도 감소

형태를 보면 임베디드 느낌도 들고.. 일반적으로 연산의 강도는 다음과 같은 순서를 따르고 있다.

곱셈/나눗셈 (비쌈) > 덧셈/뺄셈 > 비트 시프트 (저렴)

for (i = 0; i < n; i++) {
    sum += data[i * 8];
}

// 이러한 최적화를 시도 할 수 있다.
int index = 0;
for (i = 0; i < n; i++) {
    sum += data[index];
    index += 8; // 곱셈을 덧셈으로 대체!
}

 

이건 코드 이동이랑 병행 사용한 결과이다.

int sum_row(int *matrix, int n, int row) {
    int sum = 0;
    for (int j = 0; j < n; j++) {
        sum += matrix[row * n + j]; // 매번 곱셈과 덧셈
    }
    return sum;
}

int sum_row(int *matrix, int n, int row) {
    int sum = 0;
    int row_start = row * n; // 곱셈을 루프 밖으로 이동한다!
    for (int j = 0; j < n; j++) {
        sum += matrix[row_start + j]; // 덧셈만 수행
    }
    return sum;
}

 

불필요한 메모리 참조 제거

CPU가 레지스터에 있는 데이터에 접근하는 속도는 RAM에 접근하는 속도보다 수백 배 빠르다고 알려져 있다.

따라서 루프 안에서 같은 메모리 위치의 값을 반복적으로 읽어온다면, 그 값을 처음에 한 번만 읽어서 레지스터에 저장될 수 있는 지역 변수에 담아두고, 루프 안에서는 그 변수를 사용하는 것이 훨씬 효율적이다.

void overwrite(int *dest, int *src, int len) {
    for (int i = 0; i < len; i++) {
        // 매번 메모리 읽기 -> 덧셈 -> 메모리 쓰기
        *dest = *dest + src[i];
    }
}

void overwrite(int *dest, int *src, int len) {
    int acc = *dest; // acc는 지역 변수 (레지스터에 저장될 확률이 높음)
    for (int i = 0; i < len; i++) {
        acc = acc + src[i]; // 모든 연산은 레지스터에서 빠르게!
    }
    *dest = acc; // 최종 결과만 메모리에 딱 한 번 쓴다.
}

 

루프 펼치기

루프의 오버헤드를 줄이고, 프로세서의 명령어 수준 병렬성(ILP)을 활용하기 위한 기법이다.

• 루프 오버헤드 | for문을 실행할 때마다 i < len 같은 조건을 검사하고, i++ 처럼 인덱스를 증가시키는 부가적인 연산을 말한다.
• 명령어 수준 병렬성 | 파이프라이닝 등을 통해 여러 개의 명령어를 동시에 처리할 수 있는 능력을 말한다.

 

for (i = 0; i < len; i++) {
    sum = sum + data[i];
}
// 이걸 한 번에 두 개씩 처리
for (i = 0; i < len; i += 2) {
    sum = sum + data[i];
    sum = sum + data[i+1];
}

 

극단적으로 가면 이렇게도 가능하다. 기본적인 sum을 논한다면..

// 두 개의 변수로 나누어 합산
int sum1 = 0;
int sum2 = 0;
for (i = 0; i < len; i += 2) {
    sum1 = sum1 + data[i];
    sum2 = sum2 + data[i+1];
}
sum = sum1 + sum2; // 마지막에 합치기

루프 반복 횟수가 줄어들고, 데이터 의존성을 없애 CPU가 연산을 동시에 처리 할 수 있게끔 한다.