데이터 구조 정렬

데이터 구조 정렬 또는 자료 구조 정렬(data structure alignment)은 컴퓨터 메모리에 데이터가 정렬되고 접근되는 방식이다. 이 방식은 세 가지의 별개이지만 연관된 문제인 데이터 정렬, 데이터 구조 패딩, 그리고 패킹으로 구성된다.

현대 컴퓨터 하드웨어의 CPU는 데이터가 자연스럽게 정렬될 때 메모리 읽기 및 쓰기를 가장 효율적으로 수행하며, 이는 일반적으로 데이터의 메모리 주소가 데이터 크기의 배수임을 의미한다. 예를 들어, 32비트 아키텍처에서 데이터가 4개의 연속된 바이트에 저장되고 첫 번째 바이트가 4바이트 경계에 있는 경우 데이터가 정렬될 수 있다.

데이터 정렬은 요소들을 그들의 자연 정렬에 따라 정렬하는 것이다. 자연 정렬을 보장하기 위해 구조 요소들 사이에 또는 구조의 마지막 요소 다음에 약간의 패딩을 삽입해야 할 수도 있다. 예를 들어, 32비트 머신에서 16비트 값 뒤에 32비트 값이 오는 데이터 구조는 32비트 값을 32비트 경계에 정렬하기 위해 16비트 값과 32비트 값 사이에 16비트의 패딩을 가질 수 있다. 또는 패딩을 생략하고 구조를 팩하여 접근 속도가 느려질 수 있지만 16비트의 메모리를 절약할 수 있다.

데이터 구조 정렬은 모든 현대 컴퓨터의 근본적인 문제이지만, 많은 컴퓨터 언어와 컴퓨터 언어 구현은 데이터 정렬을 자동으로 처리한다. 포트란, 에이다,^[1][2] PL/I,^[3] 파스칼,^[4] 특정 C 및 C++ 구현, D,^[5] 러스트,^[6] C#,^[7] 및 어셈블리어는 적어도 데이터 구조 패딩을 부분적으로 제어할 수 있도록 하며, 이는 특정 특수 상황에서 유용할 수 있다.

정의

메모리 주소 a는 n의 배수일 때 n-바이트 정렬되었다고 한다(여기서 n은 2의 거듭제곱). 이 맥락에서 바이트는 메모리 접근의 가장 작은 단위이며, 즉 각 메모리 주소는 다른 바이트를 지정한다. n-바이트 정렬된 주소는 이진수로 표현될 때 최소한 log₂(n)개의 최하위 0을 갖는다.

대체 표현인 b-비트 정렬은 b/8 바이트 정렬된 주소를 나타낸다(예: 64비트 정렬은 8 바이트 정렬이다).

메모리 접근은 접근되는 데이터의 길이가 n 바이트이고 데이터 주소가 n-바이트 정렬될 때 정렬되었다고 한다. 메모리 접근이 정렬되지 않았을 때는 잘못 정렬되었다고 한다. 바이트 메모리 접근은 정의상 항상 정렬된다는 점에 유의하라.

n 바이트 길이의 기본 데이터를 참조하는 메모리 포인터는 n-바이트 정렬된 주소만 포함하도록 허용될 때 정렬되었다고 하며, 그렇지 않으면 정렬되지 않았다고 한다. 데이터 집합(데이터 구조 또는 배열)을 참조하는 메모리 포인터는 집합 내의 각 기본 데이터가 정렬된 경우에만 정렬되었다고 한다.

위의 정의들은 각 기본 데이터가 2의 거듭제곱 바이트 길이임을 가정한다. 이 경우가 아닐 때(x86의 80비트 부동소수점과 같이) 컨텍스트가 데이터가 정렬되었는지 아닌지를 결정하는 조건에 영향을 미친다.

데이터 구조는 고정된 크기인 바운디드(bounded)로 스택에 저장되거나, 동적 크기인 언바운디드(unbounded)로 힙에 저장될 수 있다.

문제점

CPU는 한 번에 하나의 메모리 워드로 메모리에 접근한다. 메모리 워드 크기가 컴퓨터가 지원하는 가장 큰 원시 자료형보다 크거나 같은 한, 정렬된 접근은 항상 단일 메모리 워드에 접근할 것이다. 그러나 잘못 정렬된 데이터 접근의 경우 이는 사실이 아닐 수 있다.

데이터의 최상위 바이트와 최하위 바이트가 동일한 메모리 워드 내에 있지 않으면, 컴퓨터는 데이터 접근을 여러 메모리 접근으로 분할해야 한다. 이는 메모리 접근을 생성하고 조정하기 위한 많은 복잡한 회로를 필요로 한다. 메모리 워드가 다른 메모리 페이지에 있는 경우를 처리하기 위해 프로세서는 명령을 실행하기 전에 두 페이지가 모두 존재하는지 확인하거나, 명령 실행 중 발생하는 TLB 미스 또는 페이지 부재를 처리할 수 있어야 한다.

일부 프로세서 설계는 의도적으로 이러한 복잡성을 도입하지 않고, 대신 잘못 정렬된 메모리 접근이 발생할 경우 다른 동작을 수행한다. 예를 들어, ARMv6 ISA 이전의 ARM 아키텍처 구현에서는 모든 멀티바이트 로드 및 스토어 명령어에 대해 강제적인 정렬된 메모리 접근이 필요하다.^[8] 특정 명령어가 발행되었는지에 따라, 잘못 정렬된 접근 시도의 결과는 문제가 되는 주소의 최하위 비트를 반올림하여 정렬된 접근으로 만들거나(때로는 추가 주의 사항과 함께), MMU 예외를 발생시키거나(MMU 하드웨어가 존재하는 경우), 또는 다른 잠재적으로 예측할 수 없는 결과를 조용히 반환할 수 있다. ARMv6 및 이후 아키텍처는 많은 상황에서 정렬되지 않은 접근을 지원하지만, 반드시 모든 상황에서 지원하는 것은 아니다.

하나의 메모리 워드가 접근될 때 해당 연산은 원자적이다. 즉, 전체 메모리 워드가 한 번에 읽히거나 쓰이며, 다른 장치들은 읽기 또는 쓰기 연산이 완료될 때까지 기다려야 접근할 수 있다. 그러나 여러 메모리 워드에 대한 정렬되지 않은 접근의 경우, 예를 들어 첫 번째 워드가 한 장치에 의해 읽히고, 두 워드가 다른 장치에 의해 쓰여진 다음, 첫 번째 장치에 의해 두 번째 워드가 읽히는 경우처럼, 읽힌 값이 원래 값도 아니고 업데이트된 값도 아닌 상황이 발생할 수 있다. 이러한 실패는 드물지만, 식별하기가 매우 어려울 수 있다.

데이터 구조 패딩

컴파일러 (또는 인터프리터)는 일반적으로 개별 데이터 항목을 정렬된 경계에 할당하지만, 데이터 구조는 종종 다른 정렬 요구 사항을 가진 멤버를 갖는다. 적절한 정렬을 유지하기 위해 번역기는 일반적으로 각 멤버가 적절하게 정렬되도록 추가적인 이름 없는 데이터 멤버를 삽입한다. 또한, 데이터 구조 전체는 마지막 이름 없는 멤버로 패딩될 수 있다. 이를 통해 구조체 배열의 각 멤버가 적절하게 정렬될 수 있다.

패딩은 구조체 멤버 뒤에 더 큰 정렬 요구 사항을 가진 멤버가 오거나 구조체 끝에 올 때만 삽입된다. 구조체 멤버의 순서를 변경함으로써 정렬을 유지하는 데 필요한 패딩의 양을 변경할 수 있다. 예를 들어, 멤버가 정렬 요구 사항이 내림차순으로 정렬되면 최소한의 패딩이 필요하다. 필요한 최소 패딩 양은 항상 구조체에서 가장 큰 정렬보다 작다. 필요한 최대 패딩 양을 계산하는 것은 더 복잡하지만, 항상 모든 멤버의 정렬 요구 사항의 합계에서 구조체 멤버 중 가장 적게 정렬된 절반의 정렬 요구 사항의 합계의 두 배를 뺀 값보다 작다.

C 및 C++는 공간 절약을 위해 컴파일러가 구조체 멤버의 순서를 변경하는 것을 허용하지 않지만, 다른 언어는 허용할 수 있다. 또한 대부분의 C 및 C++ 컴파일러에게 구조체 멤버를 특정 정렬 수준으로 "팩"(pack)하도록 지시할 수 있다. 예를 들어, "pack(2)"는 바이트보다 큰 데이터 멤버를 2바이트 경계에 정렬하여 모든 패딩 멤버가 최대 1바이트 길이가 되도록 한다. 마찬가지로, PL/I에서는 비트 문자열 주위를 제외한 모든 패딩을 제거하기 위해 구조체를 `UNALIGNED`로 선언할 수 있다.

이러한 "팩된" 구조체를 사용하는 한 가지 용도는 메모리를 절약하는 것이다. 예를 들어, 단일 바이트(예: char)와 4바이트 정수(예: uint32_t)를 포함하는 구조체는 3바이트의 추가 패딩이 필요하다. 이러한 구조체의 큰 배열은 팩될 경우 37.5% 더 적은 메모리를 사용하지만, 각 구조체에 접근하는 데 더 오래 걸릴 수 있다. 이러한 절충은 공간-시간 트레이드오프의 한 형태로 간주될 수 있다.

"팩된" 구조체는 주로 메모리 공간을 절약하기 위해 사용되지만, 표준 프로토콜을 사용하여 데이터 구조를 전송하기 위해 형식을 지정하는 데도 사용될 수 있다. 그러나 이 용도에서는 구조체 멤버의 값이 프로토콜이 요구하는 엔디언스(종종 네트워크 바이트 순서)로 저장되도록 주의해야 하며, 이는 호스트 머신에서 기본적으로 사용되는 엔디언스와 다를 수 있다.

패딩 계산

다음 공식들은 데이터 구조의 시작을 정렬하는 데 필요한 패딩 바이트 수를 제공한다(여기서 mod는 모듈러 연산자이다):

padding = (align - (offset mod align)) mod align
aligned = offset + padding
        = offset + ((align - (offset mod align)) mod align)

예를 들어, 4바이트 정렬된 구조체에 대해 오프셋 0x59d에 추가할 패딩은 3이다. 그러면 구조체는 0x5a0에서 시작하며, 이는 4의 배수이다. 그러나 오프셋의 정렬이 이미 정렬과 같을 때, `(align - (offset mod align)) mod align`의 두 번째 모듈로는 0을 반환하므로 원래 값은 변경되지 않고 남는다.

정렬은 정의에 따라 2의 거듭제곱이므로,^[a] 모듈러 연산은 비트 AND 연산으로 줄일 수 있다.

다음 공식들은 올바른 값을 생성한다(여기서 &는 비트 AND이고 ~는 비트 NOT이다) – 오프셋이 부호 없는 정수이거나 시스템이 2의 보수 연산을 사용하는 경우:

padding = (align - (offset & (align - 1))) & (align - 1)
        = -offset & (align - 1)
aligned = (offset + (align - 1)) & ~(align - 1)
        = (offset + (align - 1)) & -align

x86에서 C 구조체의 일반적인 정렬

자료 구조 멤버는 메모리에 순차적으로 저장되므로, 아래 구조체에서 Data1 멤버는 항상 Data2보다 먼저 오고, Data2는 항상 Data3보다 먼저 온다:

struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

"short" 타입이 2바이트 메모리에 저장된다면, 위 데이터 구조의 각 멤버는 2바이트 정렬될 것이다. Data1은 오프셋 0에, Data2는 오프셋 2에, Data3은 오프셋 4에 위치할 것이다. 이 구조체의 크기는 6바이트가 될 것이다.

구조체의 각 멤버 유형은 일반적으로 기본 정렬을 가지며, 이는 프로그래머가 별도로 요청하지 않는 한 미리 결정된 경계에 정렬될 것임을 의미한다. 다음 일반적인 정렬은 32비트 x86용으로 컴파일할 때 마이크로소프트(비주얼 C++), 볼랜드/코드기어(C++빌더), 디지털 마스(DMC), 그리고 GNU(GCC)의 컴파일러에서 유효하다:

• char (1바이트)는 1바이트 정렬된다.
• short (2바이트)는 2바이트 정렬된다.
• int (4바이트)는 4바이트 정렬된다.
• long (4바이트)은 4바이트 정렬된다.
• float (4바이트)은 4바이트 정렬된다.
• double (8바이트)은 윈도우에서 8바이트 정렬되고 리눅스에서 4바이트 정렬된다(-malign-double 컴파일 타임 옵션 사용 시 8바이트).
• long long (8바이트)은 윈도우에서 8바이트 정렬되고 리눅스에서 4바이트 정렬된다(-malign-double 컴파일 타임 옵션 사용 시 8바이트).
• long double (C++빌더 및 DMC는 10바이트, 비주얼 C++는 8바이트, GCC는 12바이트)은 C++빌더에서 8바이트 정렬되고, DMC에서 2바이트 정렬되며, 비주얼 C++에서 8바이트 정렬되고, GCC에서 4바이트 정렬된다.
• 모든 포인터 (4바이트)는 4바이트 정렬된다. (예: char*, int*)

LP64 64비트 시스템에서 32비트 시스템과 비교했을 때 정렬의 유일한 주목할 만한 차이점은 다음과 같다:

• long (8바이트)은 8바이트 정렬된다.
• double (8바이트)은 8바이트 정렬된다.
• long long (8바이트)은 8바이트 정렬된다.
• long double (비주얼 C++은 8바이트, GCC는 16바이트)은 비주얼 C++에서 8바이트 정렬되고 GCC에서 16바이트 정렬된다.
• 모든 포인터 (8바이트)는 8바이트 정렬된다.

일부 데이터 유형은 구현에 따라 다르다.

다음은 다양한 유형의 멤버를 가진 구조체로, 컴파일 전 총 8바이트이다:

struct MixedData
{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
};

컴파일 후 데이터 구조는 각 멤버의 적절한 정렬을 보장하기 위해 패딩 바이트로 보충될 것이다:

struct MixedData  /* 32비트 x86 머신에서 컴파일 후 */
{
    char Data1; /* 1바이트 */
    char Padding1[1]; /* 다음 'short'가 2바이트 경계에 정렬되도록 하기 위한 1바이트
구조체가 시작하는 주소가 짝수라고 가정 */
    short Data2; /* 2바이트 */
    int Data3;  /* 4바이트 - 가장 큰 구조체 멤버 */
    char Data4; /* 1바이트 */
    char Padding2[3]; /* 구조체의 총 크기를 12바이트로 만들기 위한 3바이트 */
};

컴파일된 구조체의 크기는 이제 12바이트이다.

마지막 멤버는 구조체 전체 크기가 모든 구조체 멤버 중 가장 큰 정렬(이 경우 리눅스-32비트/gcc에서 alignof(int) = 4)의 배수가 되도록 필요한 바이트 수로 패딩된다.

이 경우 구조체를 12바이트 크기(alignof(int) * 3)로 패딩하기 위해 마지막 멤버에 3바이트가 추가된다.

struct FinalPad {
  float x;
  char n[1];
};

이 예시에서 구조체 sizeof(FinalPad) == 8의 총 크기는 5가 아니라 8이다(따라서 크기는 4(alignof(float))의 배수이다).

struct FinalPadShort {
  short s;
  char n[3];
};

이 예시에서 구조체 sizeof(FinalPadShort) == 6의 총 크기는 5가 아니라 6이다(8도 아니다) (따라서 크기는 2(alignof(short) == 2 on linux-32bit/gcc)의 배수이다).

구조체 멤버의 순서를 변경하거나 컴파일러의 구조체 멤버 정렬(또는 "패킹")을 변경함으로써 구조체의 정렬을 변경하여 필요한 메모리를 줄이거나 기존 형식에 맞출 수 있다.

struct MixedData  /* 재정렬 후 */
{
    char Data1;
    char Data4;   /* 재정렬됨 */
    short Data2;
    int Data3;
};

구조체의 컴파일된 크기는 이제 컴파일 전 크기인 8바이트와 일치한다. Padding1[1]이 Data4로 대체(따라서 제거)되었고, 구조체가 이미 롱 워드 크기로 정렬되어 있으므로 Padding2[3]는 더 이상 필요하지 않다는 점에 유의한다.

MixedData 구조체를 1바이트 경계에 정렬하도록 강제하는 다른 방법은 전처리기가 구조체 멤버의 미리 결정된 정렬을 무시하도록 하여 패딩 바이트가 삽입되지 않게 할 것이다.

구조체 멤버의 정렬을 정의하는 표준적인 방법은 없지만(C 및 C++는 이를 위해 alignas 지정자를 사용할 수 있지만 더 엄격한 정렬을 지정하는 데만 사용될 수 있다), 일부 컴파일러는 소스 파일 내에서 패킹을 지정하기 위해 #pragma 지시어를 사용한다. 다음은 예시이다:

#pragma pack(push)  /* 현재 정렬을 스택에 푸시 */
#pragma pack(1)     /* 정렬을 1바이트 경계로 설정 */

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
};

#pragma pack(pop)   /* 스택에서 원래 정렬 복원 */

이 구조체는 32비트 시스템에서 컴파일된 크기가 6바이트일 것이다. 위 지시어는 마이크로소프트,^[9] 볼랜드, GNU,^[10] 및 다른 많은 컴파일러에서 사용할 수 있다.

또 다른 예시:

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
} __attribute__((packed));

기본 패킹 및 #pragma pack

일부 마이크로소프트 컴파일러, 특히 RISC 프로세서용 컴파일러에서는 프로젝트 기본 패킹(/Zp 지시어)과 #pragma pack 지시어 사이에 예상치 못한 관계가 있다. #pragma pack 지시어는 프로젝트 기본 패킹보다 구조체의 패킹 크기를 줄이는 데만 사용할 수 있다.^[11] 이는 프로젝트 패킹이 이보다 작은 경우, 예를 들어 #pragma pack(8)을 사용하는 라이브러리 헤더와의 상호 운용성 문제를 야기한다. 이러한 이유로, 프로젝트 패킹을 기본값인 8바이트 이외의 값으로 설정하면 라이브러리 헤더에서 사용되는 #pragma pack 지시어를 깨뜨리고 구조체 간의 바이너리 비호환성을 초래할 수 있다. 이 제한은 x86용으로 컴파일할 때는 존재하지 않는다.

캐시 라인에 정렬된 메모리 할당

캐시 라인에 정렬된 메모리를 할당하는 것이 유용할 것이다. 배열이 여러 스레드에서 작동하도록 분할될 때, 캐시 라인에 정렬되지 않은 서브 배열 경계는 성능 저하로 이어질 수 있다. 다음은 64바이트 캐시에 정렬된 메모리(크기 10의 double 배열)를 할당하는 예시이다.

#include <stdlib.h>
double *foo(void) { //크기 10의 배열 생성
   double *array;
   if (0 == posix_memalign((void**)&array, 64, 10*sizeof(double)))
     return array;

   return NULL;
}

정렬 요구사항의 하드웨어적 중요성

정렬 문제는 하드웨어 주소 변환 메커니즘(PCI 재매핑, MMU의 동작)을 통해 해당 영역을 효율적으로 매핑하는 것이 목적인 경우 C 구조체보다 훨씬 더 큰 영역에 영향을 미칠 수 있다.

예를 들어, 32비트 운영 체제에서 4 KiB (4096 바이트) 페이지는 임의의 4 KiB 데이터 청크가 아니다. 대신, 일반적으로 4 KiB 경계에 정렬된 메모리 영역이다. 이는 페이지를 페이지 크기 경계에 정렬하면 하드웨어가 복잡한 산술 연산 없이 주소의 상위 비트를 대체하여 가상 주소를 물리 주소에 매핑할 수 있기 때문이다.

예시: 가상 주소 0x2CFC7000이 물리 주소 0x12345000에 매핑되는 TLB가 있다고 가정한다. (이 두 주소는 모두 4 KiB 경계에 정렬되어 있다.) 가상 주소 va=0x2CFC7ABC에 위치한 데이터에 접근하면 0x2CFC7을 0x12345로 TLB 확인하여 pa=0x12345ABC로 물리적 접근을 발행한다. 여기서 20/12비트 분할은 다행히도 5/3자리에서 16진수 표현 분할과 일치한다. 하드웨어는 물리 주소의 처음 20비트(0x12345)와 가상 주소의 마지막 12비트(0xABC)를 단순히 결합하여 이 변환을 구현할 수 있다. 이는 가상으로 인덱싱된(ABC) 물리적으로 태그된(12345) 것으로도 언급된다.

크기가 2⁽ⁿ⁺¹⁾ − 1인 데이터 블록은 항상 2ⁿ바이트에 정렬된 크기가 2ⁿ인 서브 블록을 하나 갖는다.

이것이 정렬에 대한 지식이 없는 동적 할당자가 공간 손실 요인을 두 배로 감수하고 정렬된 버퍼를 제공하는 데 사용될 수 있는 방법이다.

// 예: malloc()으로 4096바이트 버퍼에 4096바이트 정렬된 메모리를 얻는다.

// 큰 영역에 대한 정렬되지 않은 포인터
void *up = malloc((1 << 13) - 1);
// 4 KiB에 잘 정렬된 포인터
void *ap = aligntonext(up, 12);

여기서 aligntonext(p, r)는 정렬된 증분값을 더한 다음 p의 최하위 r비트를 지워서 작동한다. 가능한 구현은 다음과 같다.

// 가독성을 위해 `uint32_t p, bits;`로 가정
#define alignto(p, bits)      (((p) >> bits) << bits)
#define aligntonext(p, bits)  alignto(((p) + (1 << bits) - 1), bits)

내용주

1. 대상 정렬이 2의 거듭제곱인 현대 컴퓨터에서. 예를 들어, 9비트 바이트 또는 60비트 워드를 사용하는 시스템에서는 그렇지 않을 수 있다.