[C++ 성능 최적화 및 고급 테크닉] Day 7: 데이터 로컬리티와 캐시 친화적 코딩

데이터 로컬리티의 중요성

데이터 로컬리티는 CPU가 데이터를 더 빠르게 접근할 수 있도록 메모리를 배치하는 방식을 의미합니다. 데이터 로컬리티가 좋으면 캐시 히트율이 높아져 프로그램의 성능이 향상됩니다. 데이터 로컬리티는 시간적 로컬리티와 공간적 로컬리티로 나눌 수 있습니다.

1. 시간적 로컬리티 (Temporal Locality): 최근에 접근한 데이터에 다시 접근하는 경향.
2. 공간적 로컬리티 (Spatial Locality): 가까운 메모리 주소에 있는 데이터에 접근하는 경향.

 

캐시 친화적 코딩 기법

1. 연속된 메모리 할당

연속된 메모리 할당은 배열이나 벡터와 같은 연속된 데이터 구조를 사용하는 것입니다. 이는 공간적 로컬리티를 향상시킵니다.

 

예제 코드

#include <iostream>
#include <vector>

int main() {
    const int size = 1000000;
    std::vector<int> data(size);

    for (int i = 0; i < size; ++i) {
        data[i] = i;
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += data[i];
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

2. 구조체 배열 사용

연속된 메모리 블록에 구조체 배열을 사용하는 것이 좋습니다. 이는 데이터 로컬리티를 향상시킵니다.

 

비최적화 코드

#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    const int size = 1000000;
    std::vector<int> x(size);
    std::vector<int> y(size);

    for (int i = 0; i < size; ++i) {
        x[i] = i;
        y[i] = i;
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += x[i] + y[i];
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

최적화 코드

#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    const int size = 1000000;
    std::vector<Point> points(size);

    for (int i = 0; i < size; ++i) {
        points[i].x = i;
        points[i].y = i;
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += points[i].x + points[i].y;
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

3. 루프 최적화

루프 최적화를 통해 데이터 로컬리티를 향상시킬 수 있습니다. 루프 인터체인지, 루프 블록킹 등의 기법을 사용합니다.

 

예제 코드

#include <iostream>
#include <vector>

int main() {
    const int size = 1000;
    std::vector<std::vector<int>> matrix(size, std::vector<int>(size));

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            matrix[i][j] = i * j;
        }
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            sum += matrix[i][j];
        }
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

최적화 코드

#include <iostream>
#include <vector>

int main() {
    const int size = 1000;
    std::vector<std::vector<int>> matrix(size, std::vector<int>(size));

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            matrix[i][j] = i * j;
        }
    }

    long long sum = 0;
    for (int j = 0; j < size; ++j) {  // 루프 인터체인지
        for (int i = 0; i < size; ++i) {
            sum += matrix[i][j];
        }
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

실습 문제

문제 1: 데이터 로컬리티 최적화

다음 코드에서 데이터 로컬리티를 최적화하여 성능을 향상시켜보세요.

 

main.cpp

#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    const int size = 1000000;
    std::vector<int> x(size);
    std::vector<int> y(size);

    for (int i = 0; i < size; ++i) {
        x[i] = i;
        y[i] = i;
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += x[i] + y[i];
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

해답:

main.cpp (최적화)

#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    const int size = 1000000;
    std::vector<Point> points(size);

    for (int i = 0; i < size; ++i) {
        points[i].x = i;
        points[i].y = i;
    }

    long long sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += points[i].x + points[i].y;
    }

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

 

이제 일곱 번째 날의 학습을 마쳤습니다. 데이터 로컬리티와 캐시 친화적 코딩 기법을 이해하고, 실습 문제를 통해 성능 최적화를 적용하는 방법을 학습했습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일부터는 고급 C++ 기능 활용을 시작하겠습니다. 내일은 "Move semantics와 R-값 참조"에 대해 학습하겠습니다.