먼저 읽어보기 - Sparse Table
Sparse Table 포스팅을 작성하고 관련 피드백을 하나 들었습니다.
관련해서 이 포스팅 한번 참고하시면 좋을 것 같아요!
바로 CPU Cashe 때문에 배열의 선언 방법에 따라 TLE가 날 수도 있다고 합니다. 관련 이슈 및 개념을 정리하면서 이를 확인해보기 위해 최소 공통 조상에서 어떻게 성능 차이가 나는지 알아보겠습니다.
CPU 캐시(Cache)란?
캐시에 대해서 간단하게 먼저 짚고 넘어가겠습니다.
캐시 메모리(Cache Memory)는 데이터를 저장하는 임시 저장소로, CPU가 데이터를 더 빠르고 효율적으로 액세스할 수 있도록 돕습니다. 이는 CPU와 메모리 사이에 위치하며, 속도가 빠른 SRAM 기반으로 설계된 저장 장치입니다. 캐시는 특히 동일한 데이터에 반복적으로 접근하거나 많은 연산이 필요한 경우 컴퓨터 성능을 크게 향상시킵니다.
캐시 메모리의 동작 원리
- 시스템이 데이터 요청 시, 먼저 캐시에서 해당 데이터를 찾습니다.
- 캐시에 데이터가 있으면(Cache Hit), 해당 데이터를 바로 제공합니다.
- 데이터가 없거나 오래되어 최신성을 잃은 경우(Cache Miss), 원본 데이터 소스에 접근합니다.
- 캐시 공간이 부족하면, 잘 사용되지 않는 데이터를 삭제하여 공간을 확보합니다.
캐시의 계층 구조
캐시는 보통 L1, L2, L3 캐시로 나뉘며, 각 계층은 속도와 용량이 다릅니다.
- L1 캐시: 코어별로 존재하며, 가장 작고 빠름
- 명령어 저장(L1I)과 데이터 저장(L1D)으로 나뉘기도 함 - 분리형 캐시
- L2 캐시: L1보다 크고 느리고, 코어별로 존재.
- L3 캐시: 여러 코어가 공유, 가장 크고 느림.
참조 지역성(Locality of Reference)
시간 지역성(Time Locality) : 최근에 접근한 데이터에 다시 접근하는 경향.
for (int i = 0; i < 10; i++) {
arr[i] = i; // 변수 i를 여러 번 참조.
}공간 지역성(Spatial Locality) : 최근 접근한 데이터 주변 공간에 다시 접근하는 경향.
int[] arr = new int[10];
for (int i = 0; i < 10; i++) {
arr[i] = i; // 배열 요소에 연속적으로 접근.
}캐시의 필요성
-
병목 현상 완화:
CPU와 메인 메모리(RAM) 사이의 병목 현상을 줄이기 위해, 크기는 작지만 속도가 빠른 캐시를 사용합니다. CPU가 자주 사용하는 데이터를 캐시에 저장하여, 데이터를 더 빠르게 가져옵니다.- 병목 현상: 시스템 성능이 특정 구성 요소의 제한으로 인해 저하되는 현상.
-
데이터 접근 시간 감소:
캐싱은 데이터를 빠르게 액세스할 수 있는 위치에 저장함으로써, 디스크나 데이터베이스와 같은 느린 저장 장치에 대한 접근을 줄입니다. -
서버 부하 분산:
캐시에서 데이터를 제공함으로써 데이터베이스 서버나 파일 시스템에 가해지는 부하를 줄이고, 전체 시스템 성능을 향상시킵니다.
캐시 관련 용어
- 캐시 히트(Cache Hit): CPU가 요청한 데이터가 캐시에 있는 경우.
- 캐시 미스(Cache Miss): CPU가 요청한 데이터가 캐시에 없는 경우.
- 캐시 적중률(Cache Hit Ratio):
캐시 히트 / (캐시 히트 + 캐시 미스). - 캐시 일관성(Cache Coherence): 멀티 코어 환경에서 각 코어의 캐시에 저장된 데이터가 동일하게 유지되는 것을 보장.
캐시와 이차원 배열 성능
다음과 같이 간단하게 c++ 로 배열 원소의 주소를 출력하면 다음과 같습니다.
#include <iostream>
using namespace std;
int arr[20][101010];
int main() {
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
cout << "arr[" << i << "]" << "[" << j << "]" << " : " << &arr[i][j] << '\n';
}
}
return 0;
}arr[0][0] : 0x7ff6a3957040
arr[0][1] : 0x7ff6a3957044
arr[0][2] : 0x7ff6a3957048
arr[1][0] : 0x7ff6a39b9a88
arr[1][1] : 0x7ff6a39b9a8c
arr[1][2] : 0x7ff6a39b9a90
arr[2][0] : 0x7ff6a3a1c4d0
arr[2][1] : 0x7ff6a3a1c4d4
arr[2][2] : 0x7ff6a3a1c4d8arr[0][0], arr[0][1], arr[0][2] 와 같은 경우에는 int 가 4 byte 이므로 연속적입니다. 배열에 원소가 연속적으로 있으면 앞서 언급한 참조 지역성으로 캐시는 자주 사용되거나 인접한 데이터를 미리 가져와서 처리 속도를 높이고, 캐시 히트율이 높습니다. 즉 효율적입니다.
단, 2차원 배열에서 두번째 항목의 크기가 101010으로 크기에, arr[0] 에서 arr[1] 로 넘어가면 기존 캐시에 저장되어 있는 데이터가 존재하지 않아 캐시 미스가 일어나게 됩니다. 이렇게 불연속적이면 캐시 미스가 일어날 가능성이 높습니다.
행-열 순서
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
a[i][j] = 0; // 연속된 메모리 공간 접근.
}
}배열의 행은 메모리에 연속적으로 배치되기 때문에, CPU는 한 번 데이터를 가져올 때 여러 인접 요소를 캐시에 저장합니다. 결과적으로 캐시 히트율이 높아지고 성능이 향상됩니다.
열-행 순서
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
a[j][i] = 0; // 비연속적인 메모리 공간 접근.
}
}반대로, 열 단위로 접근할 경우 메모리의 비연속적으로 띄엄띄엄 참조하게 됩니다. 이는 캐시에 저장된 데이터 블록을 효과적으로 활용하지 못하므로, 캐시 미스가 발생할 확률이 높아집니다.
Sparse Table을 다시 보자!
아래 두 코드는 모두 제가 제출한 최소 공통 조상 문제의 해설코드입니다.
두 코드 변수명, 공백까지 다 같은데 딱 다른 점이 하나 있습니다.
- table을
[size + 1][N + 1]로 생성한 것이 1번, - table을
[N + 1][size + 1]로 생성한 것이 2번입니다.
Sparse Table 에서는 1번 방식으로 표기하였고, 실제 시간도 1번(680 ms)가 2번(724 ms)보다 더 빠른 것을 확인할 수 있었습니다. 단순한 우연일지 확인해보도록 해보겠습니다.
table 초기화
// 1번 코드
dfs(1, 1);
for(int i = 1; i <= size; i++) {
for(int j = 1; j <= N; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
} // 2번 코드
dfs(1, 1);
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= N; j++) {
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}벌써 눈치채신 분들도 있겠지만, 바로 i, j가 1, 2번 코드가 서로 바뀌어 있습니다. sparse table의 초기화 시에는 이동 횟수별로 각 노드가 이동했을 때 도착 노드가 초기화 된 뒤 다음 이동 횟수로 넘어가야 초기화가 되기에, for-loop 자체는 table 생성 순서와 관계 없이 동일해야 됩니다. 그러면 행과 열을 반대로 작성해야 되는데, 그러면 이차원 배열 예시와 동일한 이유로 1번 코드가 2번보다 빠르게 됩니다.
참고
