한빛출판네트워크

저자: 한동훈

이전기사

• Trax, 그만의 코딩이야기(3) - 메모리를 고려한 최적화 1
• Trax, 그만의 코딩이야기(2) - 주석의 길이
• Trax, 그만의 코딩이야기(1)

DRAM에서 메모리를 접근하는 방법은 특정 바이트를 접근하는 방법이 아니라 특정 열에 접근하는 방법입니다. 따라서, 변수 a의 값을 읽는 다는 것은 변수 a가 있는 주소가 속한 열 전체를 읽어오는 것을 의미합니다. 이렇게 읽어온 데이터는 L2 캐시에 저장합니다. 보통은 이번에 접근한 위치 근처에 있는 것들에 접근하기 때문에 이렇게 합니다. 즉, 지역성(locality)을 높인다고 말합니다. DRAM에서 한 열을 읽어와서 L2 캐시의 한 라인에 데이터를 올려놓기 때문에 이를 캐시 라인이라고 말합니다. 아키텍처에 따라 다르지만 이 크기는 32 ~ 128바이트입니다. 코어2 듀오에서는 64바이트입니다. 아키텍처를 구분하지 않고 32 바이트로 얘기하겠습니다.

32 바이트 이상의 데이터에 접근해야 한다면 캐시 라인을 변경해야 합니다. 이를 캐시 분할(cache split)이라 합니다. 메모리에서는 읽어야 할 열을 선택하는 작업을 해야하며, 이는 느린 작업입니다. 따라서, 캐시가 분할되는 것과 분할되지 않는 것에 따른 성능 차이는 있습니다.

struct linked
{
  struct linked *next;
  int data[7];
  int big_data[1000];
};

이런 자료 구조가 있다고 해봅니다.

리스트 탐색을 위해 next 멤버에 접근하고, 처리를 위해 data 멤버만 접근한다고 한다면 64 바이트를 사용하는 것이므로 캐시 라인을 모두 사용하게 됩니다. big_data 멤버에는 접근하지 않기 때문에 성능에 큰 영향이 없을 것 같지만, 이를 포인터 형태로 바꾸는 것으로 최적화가 발생합니다. 즉, 구조체 크기에 대한 최적화인 셈입니다. 따라서, 다음과 같이 변경하면 코어2듀오에서도 30% 정도의 성능 향상이 발생합니다.

struct linked
{
  struct linked *next;
  int data[7];
  int *big_data;
};

그렇다면 data 멤버까지 포인터로 바꾸면 어떨까요?

struct linked
{
  struct linked *next;
  int *data;
  int *big_data;
};

이 경우엔 처음 최적화한 것보다 성능이 떨어집니다. 기억하세요. 리스트를 탐색하면서 next와 data 멤버에 접근한다고 얘기했습니다. data 멤버를 포인터로 변경할 경우 포인터 주소를 해석하는 과정이 추가로 발생하기 때문에 오히려 성능이 떨어집니다. 구조체의 크기가 매우 큰 경우에 배열 요소를 포인터로 변경하는 방법으로 크기를 최적화하면 성능이 향상됩니다.

이번에는 작은 구조체에 대해서 살펴보겠습니다.

struct linked 
{
  struct linked *next;
  int data;
}

이 구조체의 경우엔 모두 캐시 사이즈에 들어갑니다. 이 때에는 data 멤버 리스트를 분할해서 최대한 많은 개수의 next 멤버가 같은 캐시 라인에 올라가게 하는 방법을 사용합니다. 이 때에는 다른 멤버에는 접근하지 않는 경우에만 적용됩니다. 그러니, 매우 한정적인 방법입니다.

struct linked 
{
  struct linked *next;
  int *data;
}

이와 같이 선언하여 리스트를 두 가지로 나누는 방법을 사용합니다.

리스트를 접근하는 방법도 달리합니다.

list[ indx ].next = value;
list[ indx ].data = value;

와 같은 형태의 접근을 다음과 같이 변경합니다.

list.next[ indx ] = value;
list.data[ indx ] = value;

긴 리스트를 짧은 리스트로 바꾸는 방법으로 메모리 접근을 최적화하는 방법입니다. L2 캐시 라인은 최소 32 바이트입니다. 만약, 데이터가 32 바이트를 넘어간다면 다음 캐시 라인으로 이동하게 되는데 이는 메모리에서 라인을 변경하는 데 따른 지연시간이 있기 때문에 같은 캐시 라인을 접근하는 것에 비해 더 많은 시간이 걸립니다.

첫번째 방법의 연결리스트를 사용할 때 작성하는 코드는 보통 다음과 같습니다.

struct linked *list = malloc( 100000 * sizeof( struct linked );

와 같이 선언하고 10만개의 리스트를 탐색한다면 코드는 다음과 같습니다.(초기화는 생략했습니다)

struct linked *current = NULL;
current = list;
while( current = current[0].next );   // 리스트 탐색

두번째와 같은 형태를 사용하게 되면 다음과 같습니다.

while( current = current.next[0] );    // 리스트 탐색

이런 종류의 최적화는 CPU 아키텍처에 따라 편차가 큽니다. P-III 아키텍처에서는 70%의 성능 향상이 있지만, 코어2듀오에서는 10% 정도의 성능 향상이 있습니다.

싱겁게 끝나버렸나요?

가장 좋은 최적화는 점진적인 재설계입니다. 최적화가 필요한 경우가 있긴 합니다. 예를 들어, 데스크톱에서는 생체인증이 돌아가는데 2~3초 정도의 시간이 걸렸습니다. P4 1.8Ghz라는 오래된 시스템입니다. 같은 프로그램을 ARM CPU 400Mhz에 돌렸습니다. 실행시간이 너무 오래 걸려서 프로그램이 잘못된 줄 알았습니다. 그래서, 퇴근하면서 시간 측정과 함께 실행을 해뒀더니 7시간이라는 경이적인 기록이 나왔습니다. 스캐너로부터 얻어지는 영상이 고해상도이기 때문에 많은 시간이 걸리는 것은 알고 있었지만, 꽤 충격적인 결과였기 때문에 나름대로의 최적화작업을 했었습니다. 이건 좀 극단적인 예였습니다. 보통 임베디드라고 하면 ARM을 많이 쓴다고 생각하지만 ARM CPU의 단가는 꽤 비싼편이어서 8051이나 AVR을 사용합니다. 이런 환경은 메모리가 제한되어 있으며, 데이터 공간도 매우 작기 때문에 다양한 최적화를 고려합니다. 예를 들어, 3천원에 구입할 수 있는 최고급의 8051 칩이 있습니다. 메모리는 512 바이트이고, 데이터 공간은 플래시 메모리로 8k입니다. 이런 제한적인 환경이 아니라면 다양한 트릭을 이용한 최적화보다는 재설계를 통한 최적화와 컴파일러의 최적화를 이용하는 것이 가장 좋습니다.