[32일차] | 컴퓨터 밑바닥의 비밀 | 책너두

Heechan Kang·2024년 5월 20일
책너두컴퓨터 밑바닥의 비밀
0
post-thumbnail

5.2 어떻게 캐시 친화적인 프로그램을 작성할까?

  • 캐시를 효과적으로 사용하기위해서는 높은 캐시 적중률을 가져야 한다.
  • 이를 위해 프로그램을 캐시 친화적으로 작성해야 한다.

5.2.1 프로그램 지역성 원칙

  • 프로그램 지역성 원칙(locality principle)은 프로그램이 실행될 때, 특정 부분이 자주 사용된다는 원칙이다.
    • 시간적 지역성(temporal locality)
      • 최근에 사용된 데이터는 미래에도 사용될 확률이 높다.
      • 오늘 학교에 간 학생이 내일도 학교에 갈 확률이 높다.
    • 공간적 지역성(spatial locality)
      • 최근에 사용된 데이터와 인접한 데이터가 미래에도 사용될 확률이 높다.
      • 학교에 다니는 학생은 학교 근처의 카페에도 자주 간다.

5.2.2 메모리 풀 사용

  • 일반적인 상황에서 malloc/new와 같은 메모리 할당자는 잘 작동한다.
  • 그러나 malloc은 상당히 복잡한 과정을 거쳐, 느리다.
    • 따라서 고성능의 요구사항이 있는 경우, 메모리 풀을 사용한다.
  • 또한 malloc을 여러 번에 걸쳐 사용하면 메모리의 흩어짐이 발생한다.
    • 이는 캐시 친화적이지 않다.
    • 따라서 메모리 풀을 사용하여 메모리를 한 번에 할당하고, 한 번에 해제하는 것이 캐시를 사용하는데에 효과적인다.

5.2.3 struct 구조체 재배치

  • 연결 리스트에 특정 조건을 만족하는 노드가 있는지 판단할 때, 아래와 같은 구조체를 사용한다.

    define SIZE 100000

struct List
{
  List* next;
  int arr[SIZE];
  int value;
};

bool find(struct List* list, int target)
{
  while (list)
  {
    if(list->value == target)
    {
      return true;
    }

    list = list->next;
  }

  return false;
}
    • 위 코드는 단순히 연결 리스트를 순회하며 값을 차례로 살펴본다.
    • 여기서 next 포인터와 value값이 주로 사용되며, arr는 사용되지 않는다.
      • 그러나 arr이 next와 value 사이에 위치하고 있어, 공간적 지역성이 나빠질 수 있다.
    • 따라서, 아래와 같이 최적화하는 것이 공간적 지역성을 높일 수 있다.
    struct List
{
  List* next;
  int value; // <-- HERE!!!
  int arr[SIZE];
};
    • 이렇게 하면 value와 next가 연속적으로 위치하게 되어, 캐시 친화적인 구조가 된다.

5.2.4 핫 데이터와 콜드 데이터의 분리

  • 위 구조체에서 arr를 거의 접근하지 않는 데이터라고 가정하자.

  • 노드가 많아지는 경우, 캐시의 공간 제약으로 인해 저장할수 있는 노드의 수가 줄어든다.

  • 따라서 자주 사용되지 않는 데이터를 다른 곳에 저장하고, 이에 대한 포인터만 저장하는 것이 효율적이다.

    define SIZE 100000

struct List
{
  List* next;
  int value;
  struct Arr* arr;
};

struct Arr
{
  int arr[SIZE];
};
    • 여기서 자주 사용되지 않는 arr를 콜드 데이터, 자주 사용되는 value와 next를 핫 데이터라고 한다.
    • 자주 사용되는 핫 데이터를 위주로 캐싱하고, 콜드 데이터는 필요시에만 메모리에서 읽어들이는 것이 효율적이다.
      • 물론, 이는 분석도구등의 방법으로 핫 데이터와 콜드 데이터를 식별하는 과정이 우선되어야 한다.

5.2.5 캐시 친화적인 데이터 구조

  • 배열과 연결 리스트 중, 당연하게도 배열이 보다 캐시 친화적이라고 할 수 있다.
    • 배열은 연속적인 메모리 공간에 데이터를 저장하므로, 캐시의 공간적 지역성을 높일 수 있다.
    • 따라서 std::vector가 std::list보다 캐시의 공간 지역성 관점에서 성능이 더 좋다고 할 수 있다.
  • 그러나 무엇보다도, 이러한 캐싱의 최적화는 시스템의 병목이 발생했을 때에만 고려해야 한다.
    • 이러한 최적화는 코드의 가독성을 떨어뜨리고, 유지보수를 어렵게 만들 수 있기 때문이다.

5.2.6 다차원 배열 순회

  • 아래와 같은 형태의 2차원 배열을 가정하고, 캐시에는 4개의 블록이 저장될 수 있다고 가정하자.

    [
  [0, 1, 2, 3, 4, 5, 6, 7],
  [8, 9, 10, 11, 12, 13, 14, 15],
  [16, 17, 18, 19, 20, 21, 22, 23],
  [24, 25, 26, 27, 28, 29, 30, 31]
]

  • 2차원 배열을 순회하며 합산하는 코드를 아래와 같이 작성했다고 하자.

    int matrix_summer(int A[M][N])
{
  int i, j, sum = 0;
  for (i = 0; i < M; i++)
  {
    for (j = 0; j < N; j++)
    {
      sum += A[i][j];
    }
  }

  return sum;
}
    • 이 경우 A[0][0]을 읽을 때 캐시 미스가 발생하고, 캐시에는 [1, 2, 3, 4]가 저장된다.
    • 이후 A[0][3]까지는 캐시 히트가 발생하나, A[0][4]를 읽을 때 다시 캐시 미스가 발생하고 다시 [5, 6, 7, 8]이 저장된다.
    • 위와 같이 총 32번의 조회 중 8번의 캐시 미스가 발생하고, 적중률은 75%이다.

  • 그런데 만약, 아래와 같이 순회의 순서가 바뀐다면 결과는 매우 달라진다.

    int matrix_summer(int A[M][N])
{
  int i, j, sum = 0;
  for (j = 0; j < N; j++)
  {
    for (i = 0; i < M; i++)
    {
      sum += A[i][j];
    }
  }

  return sum;
}
    • C는 메모리에 행 우선 방식으로 배열을 저장한다.
    • 이 경우 A[0][0]을 읽을 때 캐시 미스가 발생하고, 캐시에는 [0, 1, 2, 3]이 저장된다.
    • 이후 A[1][0]을 읽을 때 캐시 미스가 발생하고, 캐시에는 [8, 9, 10, 11]이 저장된다.
    • 다시 A[2][0]을 읽을 때 캐시 미스가 발생하고, 캐시에는 [16, 17, 18, 19]이 저장된다.
    • 이와같이 총 32번의 조회에 대해 모두 캐시 미스가 발생하고, 적중률은 0%이다.
profile
Heechan Kang
안녕하세요
이전 포스트

[31일차] | 컴퓨터 밑바닥의 비밀 | 책너두

다음 포스트

[33일차] | 컴퓨터 밑바닥의 비밀 | 책너두

0개의 댓글