CPU 캐시와 캐시를 활용한 효율적인 프로그래밍

박지찬·2023년 8월 31일

본 글은 대부분 https://medium.com/software-design/why-software-developers-should-care-about-cpu-caches-8da04355bb8a 의 글을 번역하여 작성했습니다.

캐시를 왜 사용하는가?

메인 메모리에 접근하면 발생하는 지연을 최소화하기 위해 속도가 빠른 캐시 메모리를 사용한다. 캐시 메모리는 비싸기 때문에 데이터는 메인 메모리에 저장하고, 일부분만 캐시에 저장하여 빠르게 접근할 수 있도록 한다.

L1, L2, L3 캐시

위 이미지는 4코어 CPU이다. 하나의 코어가 두 개의 캐시를 가지고 있다.

2 ~ 64 KB Level 1 (L1) 캐시: 가장 빠른 속도
~256 KB Level 2 (L2) 캐시: L1 캐시보단 느린 속도

그리고 코어들이 공유하는 8 MB의 Level 3 (L3) 캐시가 있다.

이 캐시들의 접근 속도는

L1 : 4 cycles
L2 : 11 cycles
L3 : 39 cycles
Main Memory : 107 cycles

L1 캐시는 메인 메모리보다 약 27배 빠르다, 따라서 캐시 미스가 많이 발생하지 않는 O(N) 알고리즘이 캐시 미스가 많이 발생하는 O(1) 알고리즘보다 빠를 수도 있다. 그러면 이러한 캐시 미스를 줄이는 것이 매우 중요할 것이다.

캐시 라인

캐시는 캐시 라인이라는 단위로 메인 메모리에서 데이터를 가져온다. 캐시 라인은 보통 64 Byte 이다. 메모리에 읽거나 쓸 때 64 바이트씩 가져온다는 의미이다.

그렇다면 이러한 캐시 라인이 어플리케이션 퍼포먼스에 어떤 영향을 줄 수 있을까?
그 답을 알기 위해 밑의 2차원 배열 예제를 살펴보자.

2차원 배열을 행별로 접근할 경우, 매 행의 첫번째 데이터를 접근할 땐 캐시 미스가 발생하지만, 그 다음 아이템을 불러 올 때는 캐시에서 바로 접근할 수 있을 것이다.

그러면 이제 열별로 접근할 때를 알아보자

열별로 접근하는 경우 매 데이터를 접근할 때마다 새로운 캐시 라인으로 넘어가기 때문에 계속해서 캐시 미스가 발생한다. 이런 경우 캐시를 효율적으로 사용하지 못하고 있는 것이다.

By Value

이러한 캐시의 성질 때문에 배열이나 vector 를 사용할 때 포인터(객체 주소)로 저장되어 있는게 아닌 값으로 저장되어 있는게 캐시를 더 효율적으로 사용할 수 있을 것이다.

위의 그림처럼 포인터로 저장되어 있을 경우 포인터가 가리키는 값이 메인 메모리의 떨어져 있는 곳에 저장되어 있어 각각 다른 캐시 라인을 차지할 것이다.

하지만 만약 배열이 값을 저장하고 있다면, Entity 값들이 순차적으로 저장되어 있기 때문에 캐시 라인을 더 효율적으로 활용할 수 있다.

Validity Check

또 객체의 엘리멘트로 validation check 을 하는 경우에도 캐시 라인을 효율적으로 사용하지 못할 수도 있다.

for (int i=0; i < 10; i++) 
{
   if (array[i].Valid)
   {
      /* Act on array entity */
      ...
   }
}

객체 전체를 캐시에 넣어놓고 validation 을 진행해야 하기 때문에 valid=false 여서 필요가 없는 경우에도 캐시를 잡아먹을 수가 있다.

for (int i=0; i < 10; i++) 
{
  /* The validity flags have been moved to a descriptor array */
  if (array_descriptor[i].Valid)
   {
      /* Act on array entity */
      ...
   }
}

하지만 위의 경우와 같이 별도의 배열에 valid 여부를 저장하면 필요한 객체만 캐시에 로딩하면 되기 때문에 좀 더 효율적으로 캐시 라인을 활용할 수 있다.

물론 이렇게 한다면 코드가 더 복잡해져 유지보수가 어려워 질 것이다. 그래서 속도와 유지보수성 사이의 적정선을 찾는 것이 중요하다.

예를 들어 하나의 배열에 첫번째 요소와 두번째 요소가 각각 다른 코어에서 접근되었다고 가정하자. 이렇게 되면 한 두 코어의 L1 캐시에 배열의 두번째 요소가 저장되어 있을 것이다. 만약 한 코어에서 arr[1]의 값을 변경하면, 다른 코어의 캐시에서는 캐시 일관성을 유지하기 위한 절차를 실행시킬 것이다. 1번 코어에서는 arr[1]의 값을 변경하지 않았는데도 이러한 작업이 이루어져야 한다. 이런 현상을 false sharing 이라고 한다.

이 false sharing 을 해결하는 방법은 여러가지가 있는데 그 중 하나는 padding 을 활용하는 방법이다.
패딩을 추가하여 하나의 cache line에 두 요소가 겹쳐서 저장되지 않도록 하는 것이다.

자바에서는 이러한 패딩을 자동으로 추가해주는 Java 8 에서 추가된 @Contended 어노테이션이 있다. 이 어노테이션을 추가하면 JVM 이 알아서 어노테이션이 추가된 필드에 패딩을 추가해주게 된다. 만약 클래스에 이 어노테이션이 붙어 있다면 모든 필드에 패딩이 붙게 된다.

이 @Contended 어노테이션은 Java 8 의 JDK 내부 라이브러리이다. 즉, 외부에서 사용할 수는 없다. 자바 내부의 ConcurrentHashMap 등과 같은 클래스 내부에서 사용되고 있다.