Size of struct

struct , computer-architecture , struct-memory , memory

서론

이 글은 구조체를 사용할 때 구조체가 차지하는 메모리가 어떻게 계산되는지를 다룬다. Problem Solving을 할 때 조금이나마 도움이 되기를 바란다.

구조체의 메모리 계산

예시

PS가 아닌 개발을 목적으로 한 프로그래밍을 할 때에는 보통 가독성을 중요하게 생각한다. 다음과 같은 c++ 코드를 생각해 보자.

const int SIZE = 1000000;
struct User{
    char sex;
    short age;
    long long id;
} db[SIZE];

유저의 성별, 나이, 고유한 id를 설정해야 하는 상황이다. 우선 위와 같이 설정한 이유를 간략히 설명하겠다.

성별은 ‘M’ / ‘F’를 담을 수 있도록 char로 설정하였다.
사람의 나이는 short로도 충분히 담을 수 있다. 메모리를 조금이라도 아끼기 위해 굳이 int가 아닌 short로 설정하였다.
지금은 db크기가 1,000,000뿐이지만 세계 인구 수는 80억이 넘으므로 long long으로 id를 지정하였다.

위 이유들은 충분히 합리적으로 보이고, 메모리 관점에서 구조체를 설계하는데 특별히 더 손볼 곳이 없어 보인다. (나이를 저장하기 위해서는 char로도 충분하지만, 언젠가 255세를 넘게 사는 사람도 있지 않겠는가..? 그리고 너무 비직관적이기도 하니 넘어가자)

그럼 User 구조체는 크기가 얼마일까? 맨 처음 드는 생각은 char이 1바이트, short가 2바이트, long long int가 8바이트니 1 + 2 + 8 = 11바이트가 차지되지 않을까 하는 생각이 든다. 저 구조체가 실제로 차지하는 용량은 아래의 코드를 통해 쉽게 확인할 수 있다.

printf("Size of User struct = %d bytes\n", sizeof(db[0]));

실행 결과 User구조체는 16 bytes를 차지하고 있었다. 예상보다 5바이트나 더 차지하고 있었다.

또한 설계자의 작은 고민을 통해 int age를 short age로 바꾸었다는 점을 떠올려 보자. 여기서 우리는 저 short를 int로 바꾸어도 구조체가 차지하는 크기는 여전히 16 bytes임을 확인할 수 있다.

const int SIZE = 1000000;
struct User{
    char sex;
    int age; //short -> int
    long long id;
} db[SIZE];

위 코드의 실행 결과는 attribute하나를 short에서 int로 바꿨음에도 차지하는 용량에는 변화가 없음을 보여준다.

더 놀라운 사실은 모든 변수명의 타입을 유지하면서 단순히 변수 순서만을 바꿨을 뿐인데도 구조체의 크기가 바뀐다는 점이다. 예컨데, 아래 코드에서 구조체가 차지하는 용량은 24 bytes이다.

const int SIZE = 1000000;
struct User{
    char sex;
    long long id; //id와 age의 순서를 교환
    short age;
} db[SIZE];

정리하자면

변수명의 타입을 바꾸었는데도 차지하는 용량이 그대로일 수 있다.
타입을 유지하면서 정의 순서를 바꾸면 차지하는 용량이 바뀔 수 있다.

이제부터 그 이유를 살펴보도록 하자. 이 차이를 이해한다면 앞으로 2D segment tree나 persistent segment tree, splay tree, Trie, Aho–Corasick 등등 맞춤화된 구조체를 설계해서 해결해야하는 문제 (특히 이런 문제들의 특징은 메모리 제한이 빡빡하단 점이다)에 적용하여 메모리 용량 초과를 회피하는데 조금이나마 도움이 될 수 있을 것이다.

변수의 메모리 할당 방식

컴퓨터에서 여러 값들이 메모리에 저장될 때 특정 주소에 저장되고 있다는 사실은 다들 알고 있을 것이다. 또한 메모리들은 byte단위로 묶여서 저장되며 접근도 byte단위로만 가능하다. 주소에서 0x0010번이 8bit를 저장하고, 그 다음 주소인 0x0011이 그다음 8bit를 저장하고.. 이런 방식이다. 따라서 32bit 크기를 가지는 int 타입 변수는 메모리에 4개의 연속한 바이트를 차지하면서 저장된다.

int저장

하지만 모든 위치에 변수가 저장될 수 있는것은 아니다. 이를 Data alignment라고 부르며, 크기가 s인 변수는 시작주소가 s의 배수여야 한다. 이 조건을 하드웨어적으로 강제하는 마이크로프로세서도 있으며, 권고사항이기만 한 경우도 있다. 자세한 조건은 조금씩 다르다. 하지만 C/C++언어는 자체적으로 Data alignment를 지키도록 컴파일하는 것으로 보인다[1]

위 사진은 값 1108을 가지는 int타입 변수이므로 시작주소가 4의 배수여야 한다. 실제로 시작 주소가 0x0010 (=16) 이므로 조건을 만족함을 확인할 수 있다.

구조체의 메모리 할당 방식

이제 구조체를 살펴보자. 구조체가 변수를 메모리에 저장하는 방식의 핵심은 코드에서 정의된 순서대로 메모리에 저장한다는 것이다. 이 원칙에 더해 각각의 데이터가 메모리에 저장될 때 자신의 크기의 배수가 되는 위치에 저장되어야 한다.

이 두 원칙이 동시에 작용한다면, 구조체가 포함하는 모든 원소들 중에서 크기가 제일 큰 원소에 맞추어 구조체 전체가 정렬되어야 한다는 점을 확인할 수 있다. 구조체가 2바이트, 4바이트, 8바이트 원소를 포함한다면 8바이트가 최소공배수이므로 이 모든 것을 포함한 구조체 자체도 시작 위치가 8의 배수여야만 한다.

만일 구조체의 시작 위치가 8의 배수가 아니라면, 그 안에서 크기 8인 원소는 주소가 8의 배수가 되는 위치에 담겨야 하므로 구조체 내부의 변수 배치가 일관되지 않을 것이다.

따라서 전체 구조체는 구조체가 포함한 가장 큰 원소의 배수로 시작 위치가 제한되며, 내부적으로는 코드에 등장한 원소의 순서대로 각자의 위치에 배치한 구조가 될 것이다.

예시를 들기 위해 아래의 새로운 Struct를 정의하자.

struct Temp1{
    char a;
    int b;
    char c;
    short d;
    short e;
} temp1;

위 구조체가 메모리에 담기는 형태는 아래와 같다.

Temp1

변수 a는 크기가 1이므로 시작 위치에 그대로 담길 수 있다. 변수 b는 크기가 4이므로 a 뒤에 잇따라 담길 수 없다. 이렇게 e까지 자연스럽게 배치할 수 있다. 이 과정에서 중간 중간에 빈 공간을 padding이라 한다.

이때 변수 e뒤에도 구조체의 영역이 2 bytes추가로 있음을 확인할 수 있다. 이눈 구조체가 배열에 담겼을때 바로 뒤의 또한 시작 위치가 Data alignment를 만족하기 위해서이다. 즉, 구조체가 포함한 원소의 최대 크기가 D라면 구조체의 시작 위치는 D의 배수여야 하며, 마지막 원소의 뒤에 다음 시작 위치를 D의 배수로 맞춰주기 위해 padding을 넣는다.

실제로 printf("Size of temp struct = %d\n", sizeof(temp)); 를 실행하면 16 bytes가 나오는 걸 확인할 수 있다.

구조체의 메모리를 줄이는 법

이제 구조체가 차지하는 용량을 줄이는 법을 다뤄 보자. 아주 단순한 두 스텝만 거치면 된다.

구조체의 각 속성이 가지는 타입이 불필요하게 크다면 줄인다.
1. 을 적용한 후, 타입의 크기가 내림차순이 되도록 코드에서 나열한다. 크기가 제일 큰 원소를 제일 처음 선언하고, 크기가 제일 작은 원소를 맨 아래에 선언한다.

스텝 2가 핵심이다. 구조체의 모든 속성의 크기가 배수관계라면 (보통 1, 2, 4, 8, 16 중 하나이므로 성립) 해당 전략이 항상 최적의 배치를 찾아냄을 쉽게 확인할 수 있다. 이 전략대로라면 바로 위의 Temp1구조체는 아래와 같이 재정의할 수 있다.

struct Temp2{ //크기 내림차순으로 정의
    int b;
    short d;
    short e;
    char a;
    char c;
} temp2;

이렇게 정의한 Temp2의 크기는 16 bytes이다. 아까 전보다 8 bytes줄어들은 결과이다. 이 경우에 Temp2구조체는 메모리에서 아래와 같이 배치된다. 사진을 보며 왜 16 bytes영역을 차지하는지 확인해 보자.

Temp2

실제 사례

가장 흔하게 사용되는 알고리즘 문제풀이 사이트인 백준에서 실제로 구조체가 차지하는 용량이 달라지는지 검증해 보자. 메모리가 차이가 나는지 검증하는게 목표이므로 #1000번: A+B 를 해결하는 코드에다가 구조체 코드만 넣어서 제출하였다.

const int SIZE = 1000000;
struct Temp1{
    int b;
    short d;
    short e;
    char a;
    char c;
} temp[SIZE];

int main(){
    int a, b;
    cin>>a>>b;
    cout<<a+b;
}

이렇게 제출한 뒤, Temp1을 위에서 최적화한 Temp2로 바꾸어서 다시 제출하였다. 그 결과 메모리가 약 23%감소한 것을 확인할 수 있다.

마치는 말

위의 다양한 예시들로부터 배웠듯이, 구조체를 사용하는 경우라면 코드를 완성한 다음에 크기순으로 정렬해서 내는 것을 추천한다

구조체를 사용하며, 메모리 제한에 간당간당한 경우는 글에 처음에 언급하였던 persistent segment tree, Aho–Corasick 등이 있다. 이들 모두 포인터를 사용하는 구조체인데, 포인터가 차지하는 크기는 컴퓨터 아키텍처마다 다르다. 채점 서버가 32bit라면 포인터는 4bytes, 채점 서버가 64bit라면 포인터는 8bytes를 차지한다. 이에 유의하여 최적화를 하길 바란다.

사실 문제의 메모리 제한을 넘길 듯 말듯 하는 코드를 최적화를 해서 넘기는 것을 좋은 풀이라고 볼 수 있을지는 모르겠지만, 이것도 하나의 재밌는 경험이 될 거라 믿어 의심치 않는다. 문제도 맞고 컴퓨터 구조에서 다루는 내용까지 조금 예습할 수 있으니 일석 이조이다.

참고문헌

[1] https://en.wikipedia.org/wiki/Data_structure_alignment