아 한 것이


캐시의 지역성임


캐시는 프로세서에 있는 메모리 종류 중 하나임


니들이 컴퓨터 개론이던 정처기던에서 저장 장치 관련해서


한 번쯤은 봤던 레지스터 - 캐시 - 메인 메모리 - 보조기억장치


레지스터와 메인 메모리 사이의 입출력 병목 현상을 해소하기 위해 만들어진


그 캐시를 말하는 거심


프로세서가 캐시한테 어떤 데이터를 요청하면,


1. 캐시에 그 데이터가 있을 경우, 캐시 히트라고 하고,


캐시에 있는 그 데이터를 프로세서에게 그냥 그대로 전달함


이 경우는, 프로세서가 메인 메모리에서 직접 가져오는 것보다 빠르기 때문에,


성능상 이득이 생김


2. 캐시에 그 데이터가 없을 경우, 캐시 미스라고 하고,


메인 메모리에서 그 데이터를 찾고,


그 데이터 주변에 있는 데이터 덩어리를 캐시에 저장한 후에


프로세서한테 데이터를 줌


참고로 그 데이터만 찾더라도 캐시는 블록 단위로 저장하는 특성을 가지기 때문에 덩어리로 가져감


이런 경우는 생각해보면, 메인 메모리에서 직접 가져오는 것보다 많은 과정을 거쳤기 때문에


성능상 손해가 생김


근데 캐시에 저장할 수 있는 양은 별로 안 되기 때문에(L1 캐시만 봐도 ...)


캐시에 없을 확률이 더 클 것 같아서, 성능상 손해가 더 많을 것 같음.


하지만 그러면 캐시를 사용할 일이 있을까?


사실 "지역성"이라는 특성 때문에 이득을 본다 할 수 있음


지역성은 크게 1) 공간적 지역성이랑 2) 시간적 지역성으로 나눌 수 있음


여기서는 1만 서술할 거심


나머지도 궁금하면 찾아보센


별 건 아님


공간적 지역성은 한 마디로 보통 참조한 주소와 인접한 주소를 참조를 자주한다는 특성을 가진다는 거심


예로 들어, 우리가 많이 사용하는 것 중 하나가 일차원 배열을 반복문을 통해서 접근하는 거심


이 로직을 생각해보면


주소 + 0 * 자료형크기 -> 주소 + 1 * 자료형크기 ... 이런 형태로 인접한 주소의 데이터에 접근하는 것을 공간적 지역성이라 함


자, 서론이 길었음


그러면 문제를 주겠음


```

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

x = arr[i][j] vs x = arr[j][i] 뭐가 더 성능상 유리할까? (arr = new arr[n][n]라 가정했을 때)

}

}

```


정답은 a[i][j]임


왜냐면, 캐시가 메인메모리에서 데이터 한 개씩이 아니라


아까 말했듯이, 블록(라인)으로 가져오기 때문임


블록 크기를 16개라고 가정하면,


1. arr[j][i]의 경우를 보면,


arr[0][0], 즉, 맨 처음에는 데이터가 없을 것이니 캐시 미스가 발생해서


캐시로 arr[0][0] ~ arr[0][15] 까지 가져올 것임


(블록 크기 16 단위로 가져온다 했었다)


그럼 다음은?


arr[1][0], 두 번째도 근데 캐시에 없어서 캐시 미스가 발생할 거심


캐시로 arr[1][0] ~ arr[1][15] 까지 가져올 것임


뭐 이런 식으로 캐시 미스가 쭉 발생하고,


바깥 for문을 한 바퀴 돌아서


arr[0][1]이 되었을 때, 캐시에 arr[0][0] ~ arr[0][15]가 남아 있으면 괜찮을 건데


문제는 캐시가 생각보다 작고, 다른 프로그램도 돌아가기 때문에,


데이터가 커서 최악의 경우는 전부 캐시 미스되서 할 때마다 다시 메인 메모리에서 캐시를 가져올 수 있음


2) arr[i][j] 의 경우를 보면,


arr[0][0], 즉, 맨 처음에는 데이터가 없을 것이니 캐시 미스가 발생해서


캐시로 arr[0][0] ~ arr[0][15] 까지 가져올 것임


그 다음


arr[0][1]은 arr[0][0] ~ arr[0][15]에 있음


arr[0][2] ~ arr[0][15]는 다른 프로그램이랑 같이 실행되더라도 앵간하면 캐시 히트임


그래서 성능상 이점이 매우 커짐


쉽게 배치 처리로 오버헤드 줄여서 성능상 이점나는 그런 느낌임 ㅇㅇ


이 이상은 확실히 캐시 히트 많이 뜰 거시고 이게 10 ~ 100배까지 난다고도 한다고 그 분이 그러시더라


3줄 요약


1. arr[j][i] 쓰는 짓 하지마라

2. 운영체제 공부해라

3. 잠결에 정리하면서 쓴 거라 틀릴 시 니말이 맞다