(row-major)

(col-major)

사실 코딩을 하다보면 이중 for문을 하고, 나서 왜 행(row,가로) 먼저 하고, 열(col,세로)을 하는지 의문을 가지지 않고 배우는 경우가 많다.

하지만 실제로 프로그래밍쪽이 아닌 순수 과학이나 데이터 사이언스의 할 경우

Col-major을 쓰는 언어가 있다.

그럼 왜 메이저 언어들은 row-major가 메인이 됐을까?

그 답은 컴퓨터 시스템의 책의 명저중의 명저 Computer Systems: A Programmer's Perspective에 자세히 나와있다.

우선 들어가기 앞서 우리는 컴퓨터의 캐시에 대해서 알아야한다.

캐시란?

캐시는 메모리 데이터를 블록 단위로 저장하는데

각 블록은 일반적으로 32바이트에서 128 바이트 사이의 크기를 가지고

이 블록은 태그,인덱스, 오프셋으로 구성된다 

태그: 메모리 주소 상위 비트로, 캐시 블록이 어떤 메모리 주소를 저장하고 있는지 식별

인덱스:캐시 내에서 블록의 위치를 지정

오프셋:블록 내에서 특정 바이트를 선택

캐시 블록은 메모리 접근 요청이 들어오면 해당 주소의 데이터가 캐시에 있는지 확인하는데, 데이터가 있을 경우 히트했다고 하고, 없을 경우 미스했다고 한다.

일반적으로 캐시 미스(데이터가 캐시에 없으면) 해당 데이터를 포함한 캐시 블록 전체를 메모리에서 캐시로 로드한다.

캐시 블록의 크기가 커질수록 공간 지역성(spatial locality)을 더 잘 활용할 수 있으나, 캐시 용량과 더불어 캐시 미스의 패널티가 커진다.

우선 책의 3장에서 보듯 C 배열이 연속적으로 저장되는데

배열의 요소가 연속된 메모리 블록에 저장되있고, 

C에서 배열은 모든 요소가 메모리에 연속적으로 할당되고, 각 요소의 주소가 기본 주소에서 일정 간격(L,즉 데이터의 타입 크기 만큼)떨어져 있다는 사실인데

이게 바로 C 배열이 행(row) 연속적이라는 뜻이다.

자, 그럼 이 2가지 사실을 합치면 다음과 같은 결론이 나온다.

배열이 row-major order로 저장되므로 한 행의 데이터가 메모리상에서 연속되어 있게 되고,

캐시 블록이 연속된 메모리 주소를 가져오기 때문에,

하나의 캐시 블록은 보통 한 행의 연속된 일부분(또는 전체)을 포함하게 된다라는 것.

그래서 캐시 친화적인 코드를 작성하면 다음과 같다.

이후, 캐시 친화적인 코드를 설명할때 Row-major로 캐시친화적이게 하는데

여기서 Row-major order가 다차원 배열을 메모리에 저장할때 행단위로 연속적으로 저장하는 방식을 이야기하는데

이는 '공간적 지역성(Spatial locality)를 극대화한다. 즉 연속된 메모리 주소를 접근할때 캐시 효율성이 높아진다.

a[i][j]의 캐시 동작은 행단위로 접근되므로, 한번의 캐시 미스로 연속된 여러 요소를 캐시에 로드 할 수 있다.

예시로 들자면

a[0][0]에 접근할때 a[0][0]부터 a[0][[3]까지의 블록이 캐시에 로드 되는데, 이후 a[0][1],a[0][2],a[0][3]은 캐시 히트가 발생한다

따라서 캐시미스율이 낮아진다.

반대로 열단위로 접근해서

a[j][i]의 캐시 동작은 열단위 접근으로 서로 다른 캐시 블록을 필요로 하고, a[0][0]에 접근한 후 a[1][0]은 다른 캐시 블록에 있고, 결과적으로 캐시 미스율이 높아지는데

이러한 접근은 행에서 접근할때 캐시미스율에 비해서 열에서 접근할때 캐시미스율이 매우 높아짐을 알 수 있다.

즉, 행 우선순서로 배열을 스캔하면, 인접한 데이터가 동일한 캐시블록에 로드되어 효율적 처리가 가능하다는 것이다.

자, 그럼 이제 C계열의 언어에서 배열의 저장방법이 row-major라서 이중 for문을 작성할때, a[i][j]로 작성한다면

포트란,매틀랩 과학에서는 왜 a[j][i]로 작성하는가?

그것은 포트란과 매틀랩이 열(column)-major 로 배열을 저장하기때문이다.

캐시 메모리 자체는 단순히 연속된 메모리 블록(캐시 라인)으로 읽히기때문에, 그저 메모리상의 연속성, 즉 배열이 어떻게 저장됐는지가 중요한 것이다.

그래서 각 배열의 저장방식에 따라서

이중 포문의 바깥을 행으로 할지, 이중 포문의 바깥을 열로 할지 선택해서 더 효율적인 방식을 고려하는 것이고.

참고로 C의 배열방식이 저렇게 되는 이유는 row major order를 채택한 것은 포인터 산술 주소가 row - major-order를 선택하는게 표기하는 게 훨씬 쉬워서였고

포트란- 매틀랩과 같이 과학에서 쓰이는 언어가 col major order를 채택한 것은 선형 대수에서 수학적 표기할때 벡터를 열벡터로 표기하는 경우가 많아서였다.

즉 공학에 가까운 계열이면 row-major를 과학에 가까운 계열이면 col-major를 쓰는 경우가 많다! 라고 이해하면 편하다

따라서 프붕이들도 이중 포문을 쓰기전에 배열의 저장방식때문에 이렇게 쓰는구나 생각하면서 써보는 것은 어떨까?