row-major (행 우선), column-major(열 우선)가 왜 중요한가?

아마도 소프트웨어 혹은 컴과 전공생이라면 아직 찌들지 않은 푸릇한 1~2학년 시절 자료구조나 이산수학을 배우면서 행렬(배열)의 row-major, col-major를 눈 깜짝할 새 배우고 지나갔을 것이다.

 

그것이 어언 몇 년이 지나 지금이 되면.. 그게 뭔지는 대충 아는데 왜 배웠는지 기억이 나는 새럼 손 드세요. 손 드신 분들은 그대로 가슴에 손을 얹고 양심에게 여쭈어보시면 됩니다. 정녕 잘 기억이 나는가!

 

암튼 이번 포스트에서는 행렬(배열)의 row-major, col-major의 차이점과 중요성에 대해서 알아보도록 하자.

---

row-major, column-major가 뭔데?

얘네들은 2차원 이상의 배열을 저장할 때 적용이 되는 것들이다.

 

어떤 배열을 2차원으로 한정하여 생각해 보자.

아무리 배열이 2차원 3차원 4차원 n차원이라 하더라도, 저장 장치에 저장될 때에는 1차원으로 저장된다.

 

고로, 2차원 이상의 것들을 한 줄로 쫙 펴야 한다는 소리이다.

이때, 내 바로 옆에 어떤 놈이 저장될 것인가? 를 결정하는 것이 row-major, col-major 이다.

 

앞으로 이어질 예제에서 다음과 같은 2차원 배열(행렬)을 저장 장치에 저장한다고 해 보자.

 

$$
A = \begin{bmatrix}
a_{11} &a_{12} &a_{13} \
a_{21} &a_{22} &a_{23} \
a_{31} &a_{32} &a_{33}
\end{bmatrix}
$$

row-major (행 우선)

 

row-major는 말 그대로 row 단위로 저장하겠다는 것이다.
다시 말해, 하나의 row를 완전히 저장하고 다음 row를 저장할 것이라는 뜻.

 

고로, 위의 그림에서와 같이 $a_{11}$이 저장된 메모리 다음 칸에는 $a_{12}$가 저장될 것이다. $a_{13}$이 저장된 메모리 다음 칸에는 다음 row의 첫 번째 값인 $a_{21}$이 저장될 것이다.

 

따라서, 메모리에는 다음과 같이 1차원으로 펴져서 저장된다.

 

$$
\begin{bmatrix}
a_{11} &a_{12} &a_{13} &a_{21} &a_{22} &a_{23} &a_{31} &a_{32} &a_{33}
\end{bmatrix}
$$

 

만약, a[3][4] 크기인 int형 2차원 배열의 base address(a[0][0]의 addr)가 1000이며, row-major로 저장된 경우 a[x][y]의 메모리 주소는 어떻게 될까?

 

생각을 해 보면, row-major 이므로 a[x][y]가 저장된 곳 앞에는 x개의 꽉 채운 row가 저장되어 있을 것이다. 꽉 찬 하나의 row에는 4개의 원소가 있으므로, 일단 얘 앞에 $(x-0)*4$개의 원소가 있다. 0을 뺀 것은 base address가 row 0부터 시작하기 때문이다.

 

그러다가 x+1번째 row에서는 꽉 채우지 못하고 y개만 저장되어 있는 것이므로, a[x][y]의 메모리 주소는 다음과 같다.

 

$$
a[x][y]addr = 1000+((x-0)*4)+y)*4
$$

 

마지막에 4를 곱한 것은 지금 a 배열이 int형이므로, 하나의 원소가 4byte를 차지할 것이기 때문이다.

column-major (열 우선)

col-major는 row-major와 같은 맥락으로 col 단위로 저장하겠다는 의미이다.
다시 말해, 하나의 온전한 col을 저장한 뒤 다음 col을 저장하겠다는 것.

 

고로, $a_{11}$을 저장한 메모리 다음 칸에는 $a_{21}$이 올 것이다. 이와 마찬가지로, $a_{32}$를 저장한 메모리 다음 칸에는 다음 column의 첫 번째 원소인 $a_{13}$이 저장될 것이다.

 

따라서, 메모리에는 다음과 같이 1차원으로 퍼져서 저장된다.

$$
\begin{bmatrix}
a_{11} &a_{21} &a_{31} &a_{12} &a_{22} &a_{32} &a_{13} &a_{23} &a_{33}
\end{bmatrix}
$$

 

만약, a[3][4] 크기인 int형 2차원 배열의 base address(a[0][0]의 addr)가 1000이며, col-major로 저장된 경우 a[x][y]의 메모리 주소는 어떻게 될까?

 

생각을 해 보면, col-major 이므로 a[x][y]가 저장된 곳 앞에는 y개의 꽉 채운 col이 저장되어 있을 것이다. 꽉 찬 하나의 col에는 3개의 원소가 있으므로, 일단 얘 앞에 $(y-0)*3$개의 원소가 있다. 0을 뺀 것은 base address가 col 0부터 시작하기 때문이다.

 

그러다가 y+1번째 col에서는 꽉 채우지 못하고 x개만 저장되어 있는 것이므로, a[x][y]의 메모리 주소는 다음과 같다.

$$
a[x][y]addr = 1000+ ((y-0)4) + x)4
$$

 

마지막에 4를 곱한 것은 앞에서와 같이 지금 a 배열이 int형이므로, 하나의 원소가 4byte를 차지할 것이기 때문이다.

row-major, col-major 가 중요한 이유는?

언어마다 기본적으로 row-major, col-major 중 어떤 것을 native하게 쓸 것인지가 정해져 있다.

 

구분	언어
row-major	C/C++/Objective-C (for C-style arrays), PL/I, Pascal, Speakeasy, SAS, Rasdaman
col-major	Fortran, MATLAB, GNU Octave, S-Plus, R, Julia, Scilab

그래 그렇다 치는데, 그래서 왜 row-major, col-major 가 중요한 거냐고?

 

그건 바로 연속적인 배열 참조 시 cache memory 운용 때문이다.

 

엥 왜 갑자기 cache memory냐고? cache memory는 어디에나 숨 쉬고 어디에나 존재하는 문제이다.

 

cache memory 하면 떠올라야 하는 것이 바로 locality(지역성)다.
locality는 크게 보았을 때, spatial locality와 temporal locality로 나눌 수 있다.

 

locality에 대해 설명을 하고자 하는 포스팅이 아니므로, 두 locality의 차이점을 간단히 설명하겠다.

 

구분	특징
spatial locality	그 메모리 주변에 있는 것들이 앞으로 참조가 될 가능성이 높음
temporal locality	그 메모리를 참조하였을 때 (시간) 같이 참조했던 것들이 앞으로 참조가 될 가능성이 높음

이름에서 알 수 있듯이, 위치(?)냐 시간이냐의 차이이다.

 

row-major와 col-major가 중요한 것은 spatial locality 때문이다.

 

C를 많이 쓰니까 C를 떠올려 보자. C는 row-major native이다.

 

고로, 배열 A는 다음과 같이 메모리에 저장될 것이다.

 

$$
\begin{bmatrix}
a_{11} &a_{12} &a_{13} &a_{21} &a_{22} &a_{23} &a_{31} &a_{32} &a_{33}
\end{bmatrix}
$$

 

cache memory에 최대 3개의 원소들이 올라간다고 가정하며 실제로는 그럴 리가 없지만, 처음에는 cache memory가 비어 있다고 가정하자. 또한, cache miss가 일어난 경우, 해당 원소를 포함하여 다음 원소 2개를 포함한 총 3개의 원소들을 cache에 올린다고 가정해 보자.

 

다시 말해 그냥 miss가 일어나면 cache 갈아치우는 셈이다.

 

이제 배열 A를 탐색하는 row-major와 col-major로 각각 탐색할 경우를 살펴보자.

 

1. row-major 탐색
   
   

   현재 cache	읽어야 하는 것	cache hit?
   -	$a_{11}$	X
   $a_{11},a_{12},a_{13}$	$a_{12}$	O
   $a_{11},a_{12},a_{13}$	$a_{13}$	O
   $a_{11},a_{12},a_{13}$	$a_{21}$	X
   $a_{21},a_{22},a_{23}$	$a_{22}$	O
   ...	...	...

   끝까지 안해봐도 알겠지?
2. 총 9번 원소를 읽는 동안 3번의 cache miss, 6번의 cache hit이 일어난다.
3. col-major 탐색
   
   

   현재 cache	읽어야 하는 것	cache hit?
   -	$a_{11}$	X
   $a_{11},a_{12},a_{13}$	$a_{21}$	X
   $a_{21},a_{22},a_{23}$	$a_{31}$	X
   $a_{31},a_{32},a_{33}$	$a_{12}$	X
   ...	...	...

   음.. 그렇다. 총 9번의 원소를 읽는 동안 cache miss가 9번 일어나서 cache memory를 쓰는 덕이 없었다.

근데 뭐 실제 cache가 저렇게 쫌쫌따리일 리는 없지만.. 그냥 방법 차이에 따라 cache가 잘 쓰이지 않아 비효율적일 수 있겠구나를 생각하면 된다.

 

이렇게 하나씩 쫌쫌따리로 탐색을 할 때도 문제이지만, CPU에서 병렬 처리로 SIMD(Single Instruction Multiple Data)를 이용할 때도 문제가 생길 수 있다.

 

SIMD는 대표적으로 행렬 곱셈에 이용될 수 있는데, 하나의 operation에 vector data를 가지고 뭉텅 곱셈을 해야 하는데 데이터를 vector data로 뭉텅 가져올 수 없으면 SIMD를 이용할 수 없다. 효율성에 문제가 생기겠지!

 

따라서, row-major와 col-major native 언어 사이에 array를 주고받을 일이 있다면, 각별히 유의해야 한다. 또한, 하나의 언어 안에서 사용하더라도, 내가 사용하는 언어가 어떤 것을 native로 쓰느냐에 따라 코드르 조금 더 효율적으로 짜도록 머리를 3초라도 더 굴려봐서 이득을 볼 수도 있겠다.