Structure Packing

original link

누가 이 글을 읽어야 할까

​ 이 페이지는 C와 비슷한 구조의 컴파일된 언어로 된 프로그램의 메모리 공간을 줄이는 기술에 관한 것이다(이러한 선언을 수동으로 다시 압축해 크기를 줄인다).

​ 메모리가 제한된 임베디드 시스템이나 운영 체제 커널을 위한 코드를 작성하려는 경우 이 기술을 알아야 한다. 프로그램이 일상적으로 메모리 한계에 도달할 정도로 큰 어플리케이션 데이터 세트로 작업하는 경우에 유용하다.메모리 대역폭 사용을 최적화하고 캐시 라인 누락을 최소화하는 데 꽤 관심이 있는 모든 어플리케이션에서 유용할 것이다.

​ 마지막으로, 이 기술을 아는 것은 다른 난해한 C 주제로 가는 관문이다. 이 규칙을 이해하기 전에는 고급 C 프로그래머가 아니다. 이 문서를 직접 작성하고 지능적으로 비판할 수 있을 때까지는 C의 마스터가 아니다.

​ 이 문서는 제목에 “C”로 시작했지만 거의 모든 내용이 C++에도 적용된다. 여기에서 논의된 많은 기술은 Go 언어에도 적용되며 C와 같은 구조를 가진 모든 컴파일된 언어에서 일반화된다. 끝에 C++, Go, Rust, Java, Swiftm, C#에 대한 설명이 있다.

​

이 글을 왜 썼을까

​ 이 웹 페이지가 존재하는 이유는 2013년 후반에, 내가 20년 이상 전에 배웠고 그 이후로는 많이 사용하지 않은 최적화 기술을 꽤나 많이 적용하고 있다는 사실을 깨달았기 때문이다.

​ 수천, 때로는 수십만의 C 구조체 인스턴스를 사용하는 프로그램의 메모리 공간을 줄여야 했다. 이 프로그램은 cvs-fast-export 였고 문제는 큰 저장소에서 메모리 부족 오류로 죽어가고 있다는 것이었다.

​ 이러한 사오항에서 구조체 멤버의 순서를 신중하게 재배열해 메모리 사용량을 크게 줄이는 방법이 있다. 이것은 극적인 이득으로 이어질 수 있다. 내 경우에는 작업 세트 크기를 약 40% 줄일 수 있었고, 프로그램이 죽지 않고 훨씬 더 큰 저장소를 처리할 수 있었다.

​ 그러나 일을 하고 내가 하고 있는 일에 대해 생각하면서, 내가 사용하고 있던 기술이 이 후기에 절반 이상 잊혀졌다는 것을 깨닫게 되었다. 약간의 웹 연구에 따르면 프로그래머는 적어도 검색 엔진에서 볼 수 있는 곳에서는 더 이상 이러한 주제에 대해 이야기하지 않는 것 같다. 몇 가지 Wikipedia 항목이 주제를 다루지만, 포괄적으로 다룬 사람은 찾지 못했다.

​ 여기에는 합당한 이유가 있다. CS 과정은 사람들을 미세 최적화에서 더 나은 알고리즘을 찾는 방향으로 유도한다. 머신 리소스의 가격 하락으로 메모리 사용량을 축소할 필요가 줄어들었다.

​ 그러나 이 기술을 중요한 상황에서 여전히 가치가 있으며, 메모리가 한정되어 있는 한 그럴 것이다. 이 문서는 프로그래머가 기술을 재발견하지 않아도 되도록 하여 더 중요한 일에 노력을 집중할 수 있도록 하기 위한 것이다.

​

정렬 요구 사항

​ 가장 먼저 이해해야 할 것은 최신 프로세서에서 컴파일러가 메모리에 기본 데이터 유형을 배치하는 방식이 메모리 액세스를 더 빠르게 만들기 위해 제한된다는 것이다. 예제는 C로 되어 있지만, 컴파일된 모든 언어는 동일한 제약 조건에서 코드를 생성한다.

​ x86 또는 ARM 프로세서의 기본 C 데이터 유형을 위한 저장소는 일반적으로 메모리의 임의 바이트 주소에서 시작하지 않는다. 오히려 char를 제외한 각 유형에는 정렬 요구 사항이 있다. chars는 모든 바이트 주소에서 시작할 수 있지만, 2바이트 short는 짝수 주소에서 시작해야 하고, 4바이트 int/float는 4로 나눌 수 있는 주소에서 시작해야 하며, 8바이트 long/double은 8로 나눌 수 있는 주소에서 시작해야 한다. signed/unsigned 도 동일하다.

​ 이에 대한 전문 용어는 x86 및 ARM의 기본 C 유형이 자체 정렬된다는 것이다. 32비트(4바이트)든 64비트(8바이트)던지 포인터도 자체 정렬된다.

​ 자동 정렬은 입력된 데이터의 single-instruction fetchs 및 puts 생성을 용이하게 하기 때문에 액세스를 더 빠르게 만든다. 반면에 정렬 제약 조건이 없으면 코드는 결국 기계어 경계에 걸쳐 두 개 이상의 액세스를 수행해야 할 수 있다. Character는 특별한 경우이다. 그들은 하나의 기계어 안에 사는 곳 어디에서나 비용이 비싸다. 그렇기 때문에 선호하는 정렬이 없다.

​ “on modern processors”라고 말한 이유는 일부 오래된 프로세서에서 C 프로그램이 정렬 규칙을 위반하도록 하는 것이(ex: 홀수 주소를 int 포인터르 캐스팅하고 사용하려고 함) 코드 속도를 늦출 뿐만 아니라 불법적인 명령 오류를 일으키기 때문이다.예를 들어 Sun SPARC 칩의 동작이었다. 사실, 충분한 결정과 프로세서에 올바른(e18) 하드웨어 플래그가 설정되어 있으면 x86에서 여전히 이를 트리거할 수 있다.

​ 한 가지 흥미로운 예시가되는 예외는 Motorola 68020과 그 후속 제품이다. 이들은 word-oriented 32-bit 머신이다. 즉, 빠른 액세스의 기본 세분성은 16비트이다. 컴파일러는 첫 번째 멤버가 32비트 스칼라인 경우에도 속도 저하 없이 16비트 경계에서 구조체를 시작할 수 있다. 따라서 홀수 바이트 길이의 문자 필드만 패딩을 유발할 수 있다.

​ 2014년 초에 처음 작성되었을 때부터 2016년 말까지 이 섹션은 이상한 아키텍처에 대한 경고로 끝났다. 그 기간 동안 나는 NTP의 참조 구현을 위한 소스 코드로 작업하면서 오히려 안심할 수 있는 것을 배웠다. 최소 자체 정렬 패딩 또는 690x0과 같은 이상한 경우 제로 패딩의 가정에 따라 나머지 코드가 구조체로 보는 메모리로 직접 패킷을 읽어서 패킷 분석을 수행한다.

​ 흥미로운 소식은 NTP가 Unix뿐만 아니라 Window 변형도 포함해 매우 광범위한 하드웨어, 운영 체제 및 컴파일러에서 수십 년 동안 이 문제를 해결하고 있다는 것이다. 이것은 자체 정렬 이외의 패딩 규칙이 있는 플랫폼이 존재하지 않거나 NTP 서버나 클라이언트가 아닌 특수한 틈새에 국한되어 있음을 시사한다.

​

Padding

​ 이제 메모리에서 가변 레이아웃의 간단한 예를 살펴보자. C 모듈의 최상위 수준에서 다음과 같은 일련의 변수 선언을 고려해보자.

char *p;
char c;
int x;

​ 데이터 정렬에 대해 아무것도 모른다면 이 세 가지 변수가 메모리에서 연속적인 바이트 범위를 차지할 것이라고 가정할 수 있다. 즉, 32비트 시스템에서 4바이트의 포인터 바로 뒤에 1바이트의 char가 오고, 그 바로 뒤에 4바이트의 int가 온다. 그리고 64비트 시스템은 포인터가 8바이트라는 점에서만 다르다.

​ 사실, 정적 변수의 할당된 순서가 소스 순서라는 숨겨진 가정이 반드시 유효한 것은 아니다. C 표준에서는 이를 의무화하지 않는다. (a) 숨겨진 가정은 일반적으로 정확하고, (b) 외부 구조 패딩 및 패킹에 대해 이야기하는 실제 목적은 내부에서 일어나는 일에 대비하기 위한 것이기 때문에 이 세부 사항을 무시하자.

​ 다음은 실제로 일어나는 일이다(x86, ARM 또는 자체 정렬 유형이 있는 다른 모든 것). *p 에 대한 저장소는 기계어 크기에 따라 자체 정렬된 4바이트 또는 8바이트 경계에서 시작된다. 이것은 가능한 가장 엄격한 포인터 정렬이다.

​ c에 대한 저장이 즉시 이어진다. 그러나 x의 4바이트 정렬 요구 사항으로 인해 레이아웃에 간격이 생긴다. 다음과 같이 네 번째 중간 변수가 있는 것처럼 나타난다.

char *p;      /* 4 or 8 bytes */
char c;       /* 1 byte */
char pad[3];  /* 3 bytes */
int x;        /* 4 bytes */

​ pad[3] 문자 배열은 구조에 3바이트의 낭비 공간이 있다는 사실을 나타낸다. 이에 대한 구식 용어는 “slop”이었다. 패딩 비트의 값은 정의되지 않는다. 특히 0이 될 것이라는 보장은 없다.

​ x가 2바이트 short인 경우 어떤 일이 발생하는지 비교해보자:

char *p;
char c;
short x;

​ 이 경우에는, 다음과 같은 레이웃이 된다.

char *p;      /* 4 or 8 bytes */
char c;       /* 1 byte */
char pad[1];  /* 1 byte */
short x;      /* 2 bytes */

​ 다른 방식으로, 만약 x가 64비트 머신에서 long이라면

char *p;
char c;
long x;

​ 다음과 같이 나타내진다:

char *p;     /* 8 bytes */
char c;      /* 1 byte
char pad[7]; /* 7 bytes */
long x;      /* 8 bytes */

​ 주의 깊게 따라왔다면, 이제 더 짧은 변수 선언이 먼저 오는 경우에 대해 궁금해질 것이다.

char c;
char *p;
int x;

​ 실제 메모리 레이아웃을 이렇게 작성했다면

char c;
char pad1[M];
char *p;
char pad2[N];
int x;

​ M과 N에 대해 무엇을 말할 수 있나?

​ 첫째, 위의 경우에 N은 0이다. *p 바로 다음에 오는 x의 주소는 포인터 정렬이 보장되며, 이는 int 정렬보다 덜 엄격하다.

​ M값은 예측 가능성이 낮다. 컴파일러가 c를 기계어의 마지막 바이트에 매핑한 경우, 다음 바이트(*p의 첫 번째 바이트)는 다음 바이트의 첫 번째 바이트가 되며 적절하게 포인터 정렬된다. 이때 M은 0이 될 것이다.

​ c가 기계어의 첫 번째 바이트에 매핑될 가능성이 더 높다. 이 경우 M은 *p가 포인터 정렬을 갖도록 하기 위해 필요한 패딩이 될 것이다. 32비트 시스템에서는 3, 64비트 시스템에서는 7의 패딩이 생긴다.

​ 중간 경우가 가능하다. char는 기계어의 모든 바이트 경계에서 시작할 수 있기 때문에 M은 0에서 7(32비트 경우 0에서 3) 사이의 값일 수 있다.

​ 이러한 변수가 공간을 덜 차지하도록 하려면 원래 시퀀스에서 x를 c로 교체해 그 효과를 얻을 수 있다.

char *p;     /* 8 bytes */
long x;      /* 8 bytes */
char c;      /* 1 byte

​ 일반적으로 C 프로그램의 적은 수의 스칼라 변수에 대해 선언 순서를 변경해 얻을 수 있는 몇 바이트를 없애는 것은 중요할 만큼 충분히 절약하지 못한다. 이 기술을 비 스칼라 변수, 특히 구조체에 적용될 때 더욱 흥미로워진다.

​ 그것들을 다루기 전에 스칼라 배열을 처리하자. 자체 정렬 유형이 있는 플랫폼에서 char/short/int/long/pointer 배열에는 내부 패딩이 없다. 각 멤버는 다음 멤버가 끝날 때 자동으로 정렬된다.

​ 이 모든 규칙과 예는 Go 구조체와 “repr(C)” 속성이 있는 Rust 구조체에 매핑되며 구문만 변경된다.

​ 다음 섹션에서 우리는 구조체 배열의 경우에도 반드시 그렇지는 않다는 것을 알게 된다.

​

구조체 정렬 및 패딩

​ 일반적으로 구조체 인스턴스는 가장 넓은 스칼라 멤버의 정렬을 갖는다. 컴파일러는 모든 멤버가 빠른 액세스를 위해 자체 정렬되도록 하는 가장 쉬운 방법으로 이 작업을 수행한다.

​ 또한 C(그리고 Go, Rust)에서 구조체의 주소는 첫 번째 멤버의 주소와 동일하다 - 선행 패딩이 없다. C++에서는 이것이 사실이 아닐 수 있다. - 섹션 14, “Other languages”를 참조해라.

​ (이런 종류의 것이 의심스러울 때, ANSI C는 구조체 멤버 오프셋을 읽는 데 사용할 수 있는 offsetof() 매크로를 제공한다)

​ 다음 구조체를 고려하자:

struct foo1 {
    char *p;
    char c;
    long x;
};

​ 64비트 시스템을 가정하면 struct foo1의 모든 인스턴스는 8바이트 정렬을 갖는다. 이들 중 하나의 메모리 레이아웃은 다음과 같다:

struct foo1 {
    char *p;     /* 8 bytes */
    char c;      /* 1 byte
    char pad[7]; /* 7 bytes */
    long x;      /* 8 bytes */
};

​ 이러한 유형의 변수가 별도로 선언된 것처럼 정확하게 배치된다. 그러나 c를 먼저 넣으면 다르다.

struct foo2 {
    char c;      /* 1 byte */
    char pad[7]; /* 7 bytes */
    char *p;     /* 8 bytes */
    long x;      /* 8 bytes */
};

​ 멤버가 별도의 변수인 경우 c는 모든 바이트 경계에서 싲가할 수 있고, pad의 크기는 다를 수 있다. struct foo2에는 가장 넓은 멤버의 포인터 정렬이 있기 때문에 더 이상 불가능하다. 이제 c는 포인터로 정렬되어야 하며 다음 7바이트 패딩이 잠겨 있다.

​ 이제 구조체의 trailing padding(후행 패딩)에 대해 이야기해보자. 이것을 설명하려면 구조체의 stride address라고 하는 기본 개념을 소개해야 한다. Stride Address는 구조체와 동일한 정렬을 갖는 구조체 데이터 다음의 첫 번째 주소이다.

​ 후행 구조체 패딩의 일반적인 규칙은 다음과 같다. 컴파일러는 구조체에 stride address까지 후행 패딩이 있는 것처럼 동작한다. 이 규칙은 반환할 sizeof()를 제어한다.

​ 64비트 x86 또는 ARM 머신에서 다음 예제를 고려해라:

struct foo3 {
    char *p;     /* 8 bytes */
    char c;      /* 1 byte */
};

struct foo3 singleton;
struct foo3 quad[4];

​ sizeof(struct foo3)가 9여야 한다고 생각할 수도 있지만, 실제로는 16이다. stride address는 (&p)[2]의 주소이다. 따라서 quad 배열에서 각 멤버에는 7바이트의 후행 패딩이 있다. 그 이유는 다음 각 구조체의 첫 번째 멤버가 8바이트 경계에서 자체 정렬되기를 원하기 때문이다. 메모리 레이아웃은 구조체가 다음과 같이 선언된 것과 같다.

struct foo3 {
    char *p;     /* 8 bytes */
    char c;      /* 1 byte */
    char pad[7];
};

​ 대조적으로 다음 예를 고려하자.

struct foo4 {
    short s;     /* 2 bytes */
    char c;      /* 1 byte */
};

​ s는 2바이트 정렬만 하면 되기 때문에 stride address는 c 다음의 1바이트이고, struct foo4는 전체적으로 1바이트의 후행 패딩만 필요하다. 다음과 같이 배치된다.

struct foo4 {
    short s;     /* 2 bytes */
    char c;      /* 1 byte */
    char pad[1];
};

​ sizeof(struct foo4)는 4를 반환한다.

​ 마지막으로 중요한 세부 사항이 있다. 구조체에 구조체 멤버가 있는 경우 내부 구조체도 가장 긴 스칼라 정렬을 갖기를 원한다. 다음과 같이 작성한다고 가정한다.

struct foo5 {
    char c;
    struct foo5_inner {
        char *p;
        short x;
    } inner;
};

​ 내부 구조체의 char *p 멤버는 외부 구조체와 내부 구조체를 강제로 포인터 정렬한다. 실제 레이아웃은 64비트 시스템에서 다음과 같다.

struct foo5 {
    char c;           /* 1 byte*/
    char pad1[7];     /* 7 bytes */
    struct foo5_inner {
        char *p;      /* 8 bytes */
        short x;      /* 2 bytes */
        char pad2[6]; /* 6 bytes */
    } inner;
};

​ 이 구조체는 구조체를 재포장해 얻을 수 있는 절감 효과에 대한 힌트를 제공한다. 24바이트 중 13바이트가 패딩이다. 50% 이상의 공간 낭비이다.

​

비트 필드

​ 이제 C 비트 필드를 살펴보자. 그들이 할 수 있는 일은 다음과 같이 1비트까지 문자 너비보다 작은 구조체 필드를 선언하는 것이다.

struct foo6 {
    short s;
    char c;
    int flip:1;
    int nybble:4;
    int septet:7;
};

​ 비트필드에 대해 알아야 할 사항은 비트필드가 워드 및 바이트 레벨 마스크로 구현되고 기계어에서 작동하는 rotate 명령어로 구현되며, 워드 경계를 넘을 수 없다는 것이다. C99는 비트 피륻가 저장 장치 경계를 넘지 않는 한 가능한 한 꽉 채워질 것임을 보장한다.

​ 이 제한은 C11 및 C++14에서 완화되었다. 이 개정판에서는 실제로 struct foo9가 32비트 대신 64비트가 되도록 요구하지 않는다. 비트 필드는 새 할당 단위를 시작하는 대신 여러 할당 단위에 걸쳐 있을 수 있다. 결정하는 것은 구현에 달려 있습니다. GCC는 x64의 경우 할당 단위를 공유하는 것을 방지하는 ABI에 맡기고 있다.

​ 우리가 32비트 시스템에 있다고 가정하면 C99 규칙은 레이아웃이 다음과 같을 수 있음을 의미한다.

struct foo6 {
    short s;       /* 2 bytes */
    char c;        /* 1 byte */
    int flip:1;    /* total 1 bit */
    int nybble:4;  /* total 5 bits */
    int pad1:3;    /* pad to an 8-bit boundary */
    int septet:7;  /* 7 bits */
    int pad2:25;   /* pad to 32 bits */
};

​ 그러나 이것이 유일한 가능성은 아니다. C 표준은 비트가 낮은 순서로 할당되도록 지정하지 않기 때문이다. 따라서 레이아웃은 다음과 같을 수 있다.

struct foo6 {
    short s;       /* 2 bytes */
    char c;        /* 1 byte */
    int pad1:3;    /* pad to an 8-bit boundary */
    int flip:1;    /* total 1 bit */
    int nybble:4;  /* total 5 bits */
    int pad2:25;   /* pad to 32 bits */
    int septet:7;  /* 7 bits */
};

​ 즉, 패딩이 payload 비트를 따르지 않고, 선행할 수 있다.

​ 또한 일반 구조체 패딩과 마찬가지로 패딩 비트가 0으로 보장되지는 않는다. C99는 이것을 언급한다.

​ 비트 필드의 기본 유형은 부호에 대해 해석되지만 반드시 크기에 대해서는 해석되지 않는다. “short flip:1”, 또는 “long flip:1”이 지원되는지 여부와 이러한 기본 유형이 필드가 채워지는 저장 장치의 크기를 변경하는지 여부는 구현자에게 달려 있다.

​ 주의해서 진행하고 사용 가능한 경우 -Wpadded로 확인해라. 이국적인 하드웨어의 컴파일러는 C99 규칙을 놀라운 방식으로 해석할 수 있다. 이전 컴파일러는 제대로 따르지 않을 수 있다.

​ 비트 필드가 기계 단어 경계를 넘을 수 없다는 제한은 다음 구조체 중 처음 두 개는 예상대로 1개와 2개의 32비트 word로 압축되지만, 세 번째(구조체 foo9)는 C99에서 3개의 32비트 word를 차지함을 의미하낟.

struct foo7 {
    int bigfield:31;      /* 32-bit word 1 begins */
    int littlefield:1;
};

struct foo8 {
    int bigfield1:31;     /* 32-bit word 1 begins /*
    int littlefield1:1;
    int bigfield2:31;     /* 32-bit word 2 begins */
    int littlefield2:1;
};

struct foo9 {
    int bigfield1:31;     /* 32-bit word 1 begins */
    int bigfield2:31;     /* 32-bit word 2 begins */
    int littlefield1:1;
    int littlefield2:1;   /* 32-bit word 3 begins */
};

​ 다시 말하지만, C11과 C++14는 foo9를 더 타이트하게 압축할 수 있지만, 이것에 의존하는 것은 현명하지 못할 것이다.

​ 반면에 struct foo8는 머신에 64비트 단어가 있는 경우 단일 64비트 단어에 맞는다.

​

구조체 재정렬

​ 이제 컴파일러가 구조체 안과 뒤에 패딩을 삽입하는 방법과 이유를 알았으므로, slop을 짜내기 위해 무엇을 할 수 있는지 조사할 것이다. 이것이 structure packing의 기술이다.

​ 가장 먼저 주목해야 할 것은 slop이 두 곳에서만 발생한다는 것이다. 하나는 더 큰 데이터 유형에 바인딩된 스토리지가 더 작은 데이터 유형에 바인딩된 스토리지를 따르는 곳이다. 다른 하나는 구조체가 보폭 주소 이전에 자연스럽게 끝나는 곳이므로 패딩이 필요해 다음 구조체가 올바르게 정렬된다.

​ slop을 제거하는 가장 간단한 방법은 정렬을 줄여 구조체 부재를 재정렬하는 것이다. 즉, 64비트 시스템에서는 8바이트가 되기 때문에 모든 포인터 정렬 하위 필드가 오도록 한다. 그런 다음 4바이트 정수이다. 그런 다음 2바이트 shor, 그 다음은 char 필드.

​ 예를 들어, 다음과 같은 간단한 연결 목록 구조를 고려해보자:

struct foo10 {
    char c;
    struct foo10 *p;
    short x;
};

​ 묵시적 slop을 명시적으로 나타내면 다음과 같다:

struct foo10 {
	char c;          /* 1 byte */
    char pad1[7];    /* 7 bytes */
    struct foo10 *p; /* 8 bytes */
    short x;         /* 2 bytes */
    char pad2[6];    /* 6 bytes */
};

​ slop은 24바이트이다. 크기별로 재정렬하면 다음을 얻을 수 있다.

struct foo11 {
    struct foo11 *p;
    short x;
    char c;
};

​ 자체 정렬을 고려할 때 패딩이 필요한 데이터 필드는 없다. 더 엄격한 정렬이 있는 (긴) 필드의 stride address가 덜 엄격한 요구 사항을 가진 (더 짧은) 필드에 대해 항상 유효하게 정렬된 시작 주소이기 때문이다. 재포장된 구조체가 실제로 필요로 하는 모든 것은 후행 패딩이다:

struct foo11 {
    struct foo11 *p; /* 8 bytes */
    short x;         /* 2 bytes */
    char c;          /* 1 byte */
    char pad[5];     /* 5 bytes */
};

​ repack 변환은 크기를 24바이트에서 16바이트로 줄인다. 많지 않은 것 같지만 200,000개의 연결 목록이 있다고 가정해보자. 특히 메모리가 제한된 임베디드 시스템이나 상주해야 하는 OS 커널의 핵심 부분에서 절감 효과가 빠르게 추가된다.

​ 재정렬은 비용 절감을 보장하지 않는다. 이 기술을 이전 예제인 struct foo5에 적용하면 다음을 얻는다.

struct foo12 {
    struct foo5 {
        char *p;      /* 8 bytes */
        short x;      /* 2 bytes */
    } inner;
    char c;           /* 1 byte*/
};

​ 패딩을 작성하면 다음과 같다.

struct foo12 {
    struct foo5 {
        char *p;      /* 8 bytes */
        short x;      /* 2 bytes */
        char pad[6];  /* 6 bytes */
    } inner;
    char c;           /* 1 byte*/
    char pad[7];      /* 7 bytes */
};

​ c가 내부 구조체의 후행 패딩으로 돌아갈 수 없기 때문에 여전히 24바이트이다. 그 이득을 수집하려면 데이터 구조를 다시 설계해야 한다.

​ 흥미롭게도 크기를 늘려 구조 필드를 엄격하게 정렬하면 패딩을 최소화할 수도 있다. (a) 한 크기의 모든 필드가 연속 범위에 있고(그 사이의 패딩을 완전히 제거) (b) 이러한 span 사이의 간격은 양쪽의 크기가 가능한 서로 2배의 차이보다 적게 갖도록 하는 것이다. 일반적으로 이것은 한쪽에 패딩이 전혀 없음을 의미한다.

​ 보다 일반적인 최소 패딩 정렬이 가능하다. 예시:

struct foo13 {
    int32_t i;
    int32_t i2;
    char octet[8];
    int32_t i3;
    int32_t i4;
    int64_t l;
    int32_t i5;
    int32_t i6;
};

​ 이 구조체는 자체 정렬 규칙에 따라 패딩이 없다. 이유를 알아내는 것은 이해력을 키우는 데 유용한 연습이다.

​ 이 가이드의 첫 번째 버전을 제공한 이후로 왜 최소 슬롭을 위한 재정렬이 그렇게 간단한데, C 컴파일러가 자동으로 재정렬하지 않는지에 대한 질문을 받았다. 그에 대한 답은, C는 원래 하드웨어에 가까운 운영 체제 및 기타 코드를 작성하도록 설계된 언어이다. 자동 재정렬을 메모리 매핑된 장치 제어 블록의 바이트 및 비트 수준 레이아웃과 정확히 일치하는 구조를 레이아웃하는 시스템 프로그래머의 기능을 방해한다.

​ C 철학을 따르고, 필드를 재정렬하지 않는다. Rust는 반대의 선택을 한다. 기본적으로 컴파일러는 구조 필드를 재정렬할 수 있다.

​

어색한 스칼라 케이스

​ symbolic debugger가 symbol을 사용할 수 있고, raw integer 대신 사용할 수도 있기 때문에 #define 보다는 enum을 사용하는 것이 좋다. 그러나 열거형은 정수 형식과 호환되도록 보장되지만, C 표준은 어떤 기본 정수 형식을 사용할 것인지 지정하지 않는다.

​ 열거형 변수가 일반적으로 int이지만 이는 컴파일러에 따라 다르다는 것을 구조체를 재포장할 때 주의해라. 기본적으로 short, long, char 일 수 있다. 컴파일러에는 크기를 강제로 적용하는 pragma 또는 command-line 옵션이 있을 수 있다.

​ long double 타입도 비슷헌 trouble spot이다. 일부 C 플랫폼은 이를 80비트로 구현하고, 일부는 128비트로 구현하며 일부 80비트 플랫폼에서는 이를 96 또는 128비트로 채운다.

​ 두 경우 sizeof()를 사용해 저장소 크기를 확인하는 것이 가장 좋다.

​ 마지막으로 x86에서 Linux double은 때때로 자체 정렬 규칙의 예외이다. 8바이트 double은 독립형 double 변수에 8바이트 자체 정렬이 있더라도 구조체 내에서 4바이트 정렬만 필요할 수 있다. 이것은 컴파일러와 옵션에 따라 다르다.

​

가독성 및 캐시 위치

​ 크기로 재정렬하는 것이 슬롭을 제거하는 가장 간단한 방법이지만, 반드시 옳은 것은 아니다. 가독성과 캐시 위치라는 두 가지 문제가 더 있다.

​ 프로그램은 단순히 컴퓨터와의 통신이 아니라 다른 사람과의 통신이다. 코드 가독성은 커뮤니케이션의 대상이 미래의 나일 때도 중요하다.

​ 구조를 서투르고 기계적으로 재정렬하면 가독성이 떨어질 수 있다. 가능하면 필드를 재정렬해 의미적으로 관련된 데이터 조각이 서로 가깝게 유지되는 일관된 그룹으로 유지되도록 하는 것이 좋다. 이상적으로는 구조 설계가 프로그램 설계를 전달해야 한다.

​ 프로그램이 구조체 또는 구조체의 일부에 자주 액세스할 때 액세스가 캐시라인(블록 내에서 단일 주소를 가져오라는 지시를 받았을 때 프로세서가 가져온 메모리 블록) 내에 들어가는 경향이 있는 경우 성능에 도움이 된다. 64비트 x86에서 캐시 라인은 자체 정렬된 주소에서 시작하는 64바이트이다. 다른 플랫폼에서는 종종 32바이트이다.

​ 가독성을 유지하기 위해 수행해야 하는 작업(인접 필드에서 관련 데이터 및 공동 액세스 데이터 그룹화)도 캐시 라인 지역성을 개선한다. 이는 코드의 데이터 액세스 패턴을 인식해 지능적으로 재정렬해야하는 두 가지 이유이다.

​ 코드가 여러 스레드에서 구조에 동시 액세스를 수행해야 하는 경우 세 번째 문제인 캐시 라인 바운싱이 있다. 값비싼 버스 트래픽을 최소화하려면 읽기가 한 캐시 라인에서 나오고 쓰기가 더 촘촘한 루프에서 다른 캐시 라인으로 이동하도록 데이터를 정렬해야 한다.

​ 이것은 때때로 동일한 캐시 라인 크기 블록에서 관련 데이터를 그룹화하는 것에 대한 이전 지침과 모순된다. 멀티스레딩은 어렵다. 캐시 라인 바운싱 및 기타 멀티스레드 최적화 문제는 자체 튜토리얼이 필요한 매우 고급 주제이다. 여기서 내가 할 수 있는 최선은 이러한 문제가 존재한다는 것을 알려주는 것이다.

​

기타 팩킹 테크닉

​ 재정렬은 구조체를 얇게 하기 위한 다른 기술과 결합할 때 가장 잘 작동한다. 예를 들어, 구조체에 여러 개의 bool flag가 있는 경우 이를 1비트 비트필드로 줄이고, 구조체 내에서 그렇지 않으면 슬롭이 될 위치에 패킹하는 것을 고려하자.

​ 이에 대해 약간의 액세스 시간 패널티를 받게 되지만 작업 세트를 충분히 더 작게 압축하면 그 패널티는 회피된 캐시 미스로 인한 이득에 의해 압도될 것이다.

​ 보다 일반적으로 데이터 필드 크기를 줄이는 방법을 찾자. 예를 들어, cvs-fast-export에서 내가 적용한 한 가지 압박은 RCS 및 CVS 저장소가 1982년 이전에는 존재하지 않았다는 지식을 사용하는 것이었다. 1982-01-01T00:00:00의 32비트 시간 오프셋; 이것은 2118년까지의 날짜를 다룰 것이다. (참고: 이와 같은 트릭을 가져오는 경우, 불쾌한 버그를 방지하기 위해 필드를 설정할 때마다 경계 검사를 수행해라)

​ 이러한 각 필드 단축은 구조체의 명시적 크기를 감소시킬 뿐만 아니라 슬롭을 제거하거나 필드 재정렬을 통해 추가 기회를 생성할 수 있다. 그러한 효과의 고결한 종속은 트리거하기가 그리 어렵지 않다.

​ 팩킹의 가장 위험한 형태는 union(공용체)을 사용하는 것이다. 구조의 특정 필드가 다른 특정 필드와 함께 사용되지 않는다는 것을 알고 있다면, union을 사용해 스토리지를 공유하도록 하는 것이 좋다. 그러나 lifetime 분석이 약간만 잘못되어도 충돌에서 (훨씬 더 나쁜) 미묘한 데이터 손상에 이르는 버그가 발생할 수 있기 때문에 각별히 주의하고 회귀 테스트로 작업을 확인해라.

​

정렬 규칙 재정의

​ 때로는 pragma를 사용해 프로세서의 일반 정렬 규칙을 사용하지 않도록 컴파일러를 강제할 수 있다. GCC 및 clang에는 개별 구조 선언에 연결할 수 있는 “packed” 속성이 있다. GCC에는 전체 컴파일을 위한 -fpack-struct 옵션이 있다.

​ 이것은 더 비싸고 느린 코드를 생성하게 하므로 아무렇게나 하면 안 된다. 일반적으로 여기에서 설명하는 기술을 사용해 메모리를 최대한 절약할 수 있다.

​ #pragma pack이 필요한 유일한 이유는 C 데이터 레이아웃을 메모리 맵핑 하드웨어 포트와 같은 일종의 비트 수준 하드웨어 또는 프로토콜 요구 사항과 정확히 일치시켜야 하고, normal alignment를 위반해야 작동하는 경우이다.

​

도구

​ clang 컴파일러에는 alignment hole 및 padding에 대한 메시지를 생성하도록 하는 -Wpadded 옵션이 있다. 일부 버전에는 추가 정보를 제공하는 문서화되지 않은 -fdump-record-layouts 옵션도 있다.

​ C11을 사용하는 경우 static_assert를 배포해 유형 및 구조 크기에 대한 가정을 확인할 수 있다. 예시:

#include <assert.h>
struct foo4 {
    short s;     /* 2 bytes */
    char c;      /* 1 byte */
};
static_assert(sizeof(struct foo4) == 4, “Check your assumptions");

​ 내가 직접 사용해보지는 않았지만 몇몇 응답자들은 pahole이라는 프로그램에 대해 좋은 평가를 내렸다. 이 도구는 컴파일러와 협력해 패딩, 정렬, 캐시 랑니 경계를 설명하는 구조에 대한 보고서를 생성한다. 이것은 한때 독립 실행형 C 프로그램이었지만 지금은 유지 관리되지 않는다. 이름이 pahole인 스크립트가 이제 gdb와 함께 제공되며 이것을 사용해야 한다.

​ “PVS Studio”라는 독점 코드 감사 도구가 구조 패킹 기회를 감지할 수 있다는 보고를 받았다.

​

증거 및 예외 사례

​ 위에서 만든 스칼라 및 구조 크기에 대한 주장을 보여주는 작은 프로그램의 소스 코드를 다운로드할 수 있다. packtest.c

​ 컴파일러, 옵션 및 특이한 하드웨어의 이상한 조합을 충분히 살펴보면 내가 설명한 일부 규칙에 대한 예외를 찾을 수 있다. 이전 프로세서 디자인으로 시간을 거슬러 올라갈수록 더 일반적이다.

​ 이러한 규칙을 아는 것 이상의 다음 단계는 규칙이 위반될 것으로 예상하는 방법과 시기를 아는 것이다. 내가 그것들을 배웠을때 우리는 이것을 이해하지 못한 사람들이 “all-the-world’s-a-VAS” 증후군의 희생자라고 말했다. 전 세계가 인텔이나 ARM이 아니라는 것을 기억해라.

​

다른 언어

​ 이 섹션에서는 구조체 및 배열 멤버가 자체 정렬되고 컴파일러에 의해 재정렬되지 않고 구조체의 주소가 첫 번째 멤버의 주소이고, 구조체의 후행 padding이 있는 경우 “C 유사” 언어라고 부를 것이다.

• 14.1 C++
  • C++는 구조체처럼 보이는 클래스가 있다. 클래스는 구조체의 주소가 첫 번째 멤버의 주소라는 규칙을 무시할 수 있다는 점을 제외하고는 C와 유사하다. 실행 여부는 기본 클래스와 가상 멤버 함수가 구현되는 방식에 따라 다르며, 컴파일러에 따라 다르다. 그렇지 않으면 C에 대해 관찰한 모든 것이 적용된다.
• 14.2 GO
  • Go 언어는 여러 면에서 C와 유사하다. 비트필드나 공용체는 아니지만 구조와 배열이 있다. Go 컴파일러에는 C 컴파일러와 동일한 최적화 및 정렬 문제가 있다. 한 가지 중요한 차이점은 Go 사양에서는 구조 필드가 자체 정렬되어야 한다는 것이다. C #pack pragma에 해당하는 것은 없다. C에서와 같이 배열 요소는 다음 padding 주소까지 채워진다.
  • Go에는 이상한 점이 하나 있다. Go 1.5부터 구조체(즉, 길이가 0인 배열 또는 빈 구조체) 끝에 있는 길이가 0인 필드는 마치 1바이트인 것처럼 크기가 조정되고 정렬된다. 그 이유는 Go 개발자 중 한 명이 쓴 에세이 Padding is Hard에서 농늬된다.
• 14.3 Rust
  • Rust는 구조체에 “repr(C)” 주석이 달린 경우 C와 유사한 패킹 규칙을 따른다. 그렇지 않으면 기본적으로 모든 bet이 해제된다. 패딩 규칙은 의도적으로 지정되지 않고, 컴파일러는 구조 멤버를 재정렬할 수도 있다. Rust 컴파일러가 공간 최적화를 강제하는 것보다 하도록 하는 것이 가장 좋다.
• 14.4 Java
  • Java의 JNI(Java Native Interface)는 JNI Java 구조가 C equivalent(등가물)에 정확히 매핑될 수 있도록 구조 멤버에 대해 C와 유사한 패킹 규칙을 지원한다. pack pragma가 있다.
  • 그러나 JVM 자체의 패킹은 잘 정의되어 있지 않다. JVM 사양은 단순히 “Java Virtual Machine은 객체에 대한 특정 내부 구조를 요구하지 않는다.”라고 말하며, 이 구현에 대한 선택은 종속적이다.
  • 그렇긴 하지만 많은 JVM 구현은 모토로라 프로세서보다 훨씬 더 엄격한 방식으로 word 중심이다. 구조체 및 배열 구성원은 모든 32비트 경계에서 시작할 수 있지만, 16비트 또는 8비트 경계에서는 시작할 수 없다. 이것은 C와 같은 규칙에서 예상되지 않는 char 및 16비트 short 멤버 뒤에 내부 패딩을 생성한다.
• 14.5 Swift
  • Swift는 정확히 C와 유사하다. pack pragma에 해당하는 것은 없다.
• 14.6 C#
  • C#은 기본 구조 레이아웃 속성인 LayoutKind.Sequential을 사용하는 C와 유사하다. LayoutKind.Auto를 사용하면 컴파일러가 재정렬할 수 있고, LayoutKind.Explicit을 사용하면 프로그래머가 필드 크기를 명시적으로 지정할 수 있다. C pack pragma에 해당하는 pack 수정자가 있다.