동적 2차원 배열을 1차원 배열로 구현하면 빠를까?
1 이론
2차원 자료를 저장하기 위해서 1차원 배열의 배열을 만드는 것과 인덱싱 계산을 통해서 1차원 배열로 구현하는 것 중 어느 것이 더 빠를까? 아무래도 1차원 배열로 구현하는 것이 빠를 것 같다. 인덱싱 계산은 거의 무시해도 될 것 같다. 그리고 메모리는 1차원이 덜 차지하니까 자료의 크기가 클 수록 1차원 배열로 구현하는 것이 좋다.
2 2차원 배열의 메모리를 연속적으로 할당하기
그나저나 이런 C 문법은 오늘 2020 년 8 월 24 일 처음 보네.
int (*p)[num_columns] = malloc(num_rows * sizeof *p);
p[row_index][col_index]*p가 num_columns개의 int를 가지고 있으니까 이것만큼의 num_rows를 할당하면 num_rows*num_columns개의 int를 저장할 수 있다? 이 답변에 의하면 컴파일할 때 차원이 정해진 경우에만 C99나 C2011 표준없이 사용할 수 있는 문법인 것 같지만 gcc -ansi -Wall로 다음의 코드를 컴파일할 수 있다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num_rows = atoi(argv[1]);
int num_columns = atoi(argv[2]);
int (*p)[num_columns] = malloc(sizeof *p * num_rows);
p[0][0] = 100;
p[1][0] = 210;
printf("%d %d\n", p[0][0], p[1][0]);
free(p);
exit(0);
}이 글을 잘 읽어 보면 이 문법이 어떻게 작동하는지 쉽게 이해할 수 있다.
이렇게 사용하는 경우가 있구만.
int *sieve = malloc(sizeof *sieve * length);어쨌든, 다음의 코드에서 p[0] 배열을 오버플로우해서 p[0][1]에 999를 저장하니까 p[1][0]이 999가 된 걸 보면 1차원 배열을 2차원 인덱싱으로 접근할 수 있는 문법이다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int num_rows = 2;
int num_columns = 1;
int (*p)[num_columns] = malloc(sizeof *p * num_rows);
int i;
p[0][0] = 100;
p[1][0] = 210;
p[0][1] = 999;
printf("%d %d\n", p[0][0], p[1][0]);
printf("%p == %p == %p == %p == %p\n", p, *p, &(p[0]), p[0], &p[0][0]);
for(i = 0; i < 2; i++)
printf("%d == %d\n", **(p+i), *(*p+i));
free(p);
exit(0);
}p(&p[0])의 주소에 *p(p[0])가 있고, 바로 거기에 p[0][0] 값이 저장되어 있다. 즉, 1차원 배열이면서 2차원 인덱싱이 가능한 문법이다.
그런데 이 문법은 배열을 정의할 당시에 열의 개수가 정해져 있어야 한다. 그렇지 않으면 열의 크기가 정해지지 않았기 때문에 컴파일 오류가 난다.
int num_rows;
int num_columns;
int (*p)[];
num_rows = 2;
num_columns = 1;
p[num_columns] = malloc(sizeof *p * num_rows);
*p[num_columns] = malloc(sizeof *p * num_rows);
(*p)[num_columns] = malloc(sizeof *p * num_rows);그렇다면 이런 배열의 크기가 정해지지 않은 시점에서 C 구조체를 정의한 다음 나중에 메모리를 할당하는 방법이 있을까? 방법을 찾기는 했지만 자료형과 행의 개수를 계속 달고 다녀야 해서 매크로나 함수를 사용하지 않으면 불편하다.
#include <stdio.h>
#include <stdlib.h>
#define INT_ELEMENT(mat, row, col) ((int (*)[(mat)->ncols])(mat)->data)[row][col]
struct int_matrix
{
void *data;
int nrows;
int ncols;
};
static void update_matrix(struct int_matrix *, int, int, int);
int main()
{
struct int_matrix mat;
mat.nrows = 2;
mat.ncols = 5;
mat.data = malloc(sizeof(int) * mat.nrows * mat.ncols); /* 여기까진 특별한 게 없다. */
((int (*)[mat.ncols])mat.data)[0][1] = 999; /* 캐스팅을 이렇게 하면 된다. */
printf("%d\n", ((int (*)[mat.ncols])mat.data)[0][1]);
update_matrix(&mat, 0, 1, 123);
printf("%d\n", INT_ELEMENT(&mat, 0, 1));
INT_ELEMENT(&mat, 0, 1) = 345;
printf("%d\n", INT_ELEMENT(&mat, 0, 1));
}
void update_matrix(struct int_matrix *mat, int row, int col, int val)
{
int (*data)[mat->ncols] = mat->data; /* 이렇게도 된다. */
data[row][col] = val;
}3 테스트 결과
이론은 그런데 실제로 Reflow에 적용해 보니까 2차원 배열이 약 350 밀리초(GA)에서 1,368 밀리초(TX) 더 빨랐다. 아마도 인덱싱 계산이 너무 많아서 그랬던 것이 아닐까 짐작해 본다. 그리고 메모리도 1.8 GB(GA)에서 7.5 GB(TX)를 사용해서 무작위로 셀에 접근하니 CPU의 캐시가 크게 도움이 되지는 않았나 보다.