동일한 크기의 배열인데 탐색 속도가 다르다?
// 10000 * 10000 크기의 2차원 배열 생성
let n = 10000;
const matrix1 = Array.from({ length: n }, () => Array(n).fill(0));
const matrix2 = Array.from({ length: n }, () => Array(n).fill(0));
console.time("1");
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix1[j][i] = 1;
}
}
console.timeEnd("1");
console.time("2");
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix2[i][j] = 1;
}
}
console.timeEnd("2");
// 1: 867.832ms
// 2: 83.058msmatrix1 과 matrix2 는 둘 다 10000 * 10000 크기의 2차원 배열이고, 2중 for 문을 돌며 모든 원소에 1을 삽입하고 있다.
그러나 위 코드의 결과에서 보이다시피 2번 방식의 속도가 1번 방식보다 약 10배 정도 빠른 것을 확인할 수 있다.
1번 방식과 2번 방식은 차이는 딱 한 줄 차이다.
matrix1[j][i] = 1; // 1번 방식
...
matrix2[i][j] = 1; // 2번 방식i와 j의 위치만 달라진 것 뿐인데 어째서 이런 차이가 발생하는 걸까?
배열은 메모리에 어떻게 저장될까?
속도 차이가 발생하는 이유를 알기 전에 배열이 어떻게 메모리에 저장되는지부터 알아야 한다.
1차원 배열에서는 각각의 요소가 그림과 같이 메모리 상에서 인접한 위치에 연속적으로 저장된다. (number = 4byte)
그러나 2차원 배열의 경우 각 요소는 그림과 같이 배열의 참조를 가리킨다.
2차원 배열 안에 존재하는 1차원 배열들은 위 그림처럼 메모리 상에서 각각 떨어져 있을 수도 있다. (높은 확률로 떨어져 있을 것이다.)
이렇게 저장하면 좋은 점은 각각의 1차원 배열이 독립적인 위치에 저장되기 때문에 각각의 배열의 크기를 동적으로 키우고 줄이기 쉽다는 특징이 있다.
이제 배열이 메모리에 어떻게 저장되는지 알았으니 속도 차이가 왜 발생하는지 본격적으로 알아보자.
1. 물리적인 위치로 인한 속도 차이
속도 차이가 발생하는 가장 직관적인 이유는 각각의 배열의 물리적인 위치가 떨어져 있기 때문이다.
1번 방식은 그림으로 보면 다음과 같은 순서로 탐색을 진행하는 것이다.
이런 순서로 탐색을 진행하면 물리적으로 떨어져 있는 위치에 매번 점프(?) 해야 되기 때문에 속도가 느려진다.
2. 캐싱으로 인한 속도 차이
CPU는 가까운 미래에 사용될 것 같은 데이터를 예측하여 캐시에 저장해놓는데, 이때의 예측 정확도(캐시히트)를 높이기 위해 다음과 같은 원리들을 사용한다.
- 공간(spatial) 지역성: 최근에 참조된 메모리 공간에서 가까울수록 다시 참조할 확률이 높다.
- 시간(temporal) 지역성: 최근에 참조한 메모리일수록 다시 참조될 확률이 높다.
- 순차(sequential) 지역성: 순차적으로 구성되어 있는 데이터가 다시 참조될 확률이 높다.
위와 3가지 원리들을 지역성의 원리라고 한다.
최근에 참조한 데이터는 다시 참조할 가능성이 높고, 메모리 상에서 그 데이터와 인접한 위치에 있는 데이터도 연관이 있는 데이터일 확률이 높기 때문에 지역성의 원리를 이용해 캐시에 데이터를 저장하는 것이다.
1번 방식은 캐시미스가 자주 발생하여 2번 방식보다 속도가 더 느리다.
예를 들어 0x00 을 탐색하고 있는 중이라고 했을 때, CPU는 지역성의 원리에 기반하여 0x00 근처에 있는 데이터를 캐시에 저장해놓을 것이다. 따라서 0x00 ~ 0x08 까지를 캐시에 저장해놓는다고 생각해보자.
그러나 다음 탐색 때 0x20을 탐색하므로 이는 캐시에 없기 때문에 다시 메모리로부터 데이터를 꺼내온다 (캐시미스).
2번 방식은 캐시히트가 자주 발생하여 1번 방식보다 속도가 더 빠르다.
예를 들어 0x00 을 탐색하고 있는 중이라고 했을 때, CPU는 지역성의 원리에 기반하여 0x00 근처에 있는 데이터를 캐시에 저장해놓을 것이다. 따라서 0x00 ~ 0x08 까지를 캐시에 저장해놓는다고 생각해보자.
다음 탐색 때 0x04 를 탐색해야 되는데, 0x04의 데이터는 이미 캐시에 저장되어 있으므로 캐시에서 불러온다 (캐시히트).
이 차이로 인해 2번 방식이 1번 방식보다 빠르다.
번외
각각의 원소가 인접한 위치에 연속적으로 저장되는 2차원 배열도 있다.
C, C++ 처럼 메모리 정적 할당이 가능한 언어들은 메모리를 정적으로 할당할 경우, 처음부터 배열의 크기가 고정되어 있기 때문에 2차원 배열의 원소끼리도 서로 인접한 위치에 연속적으로 저장된다. (동적으로 할당할 경우에는 자바스크립트와 마찬가지로 떨어진 위치에 저장된다.)
int main() {
// 메모리 정적 할당
int arr[3][4] = {
{0, 1, 2, 3},
{4, 5, 6, 7},
{8, 9, 10, 11}
};
printf("arr[0]: %p %i\n", arr[0], *arr[0]); // arr[0]: 000000000061FDF0 0
printf("arr[1]: %p %i\n", arr[1], *arr[1]); // arr[1]: 000000000061FE00 4
printf("arr[2]: %p %i\n", arr[2], *arr[2]); // arr[2]: 000000000061FE10 8
return 0;
}
참고자료
