데이터 구조 정렬

Data structure alignment

데이터 구조 정렬은 컴퓨터 메모리에서 데이터를 정렬하고 액세스하는 방법입니다.데이터 정렬, 데이터 구조 패딩 및 패킹의 세 가지 관련 문제로 구성됩니다.

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

데이터 정렬은 요소의 자연스러운 정렬에 따라 정렬하는 것입니다.자연스러운 정렬을 위해 구조물 요소 사이에 또는 구조물의 마지막 요소 뒤에 일부 패딩을 삽입해야 할 수 있습니다.예를 들어 32비트 머신에서는 16비트 값 뒤에 32비트 값을 포함하는 데이터 구조가 16비트 값과 32비트 값 사이에 16비트의 패딩을 가지며 32비트 경계에 32비트 값을 정렬할 수 있습니다.또는 패딩을 생략하고 구조를 패킹할 수 있습니다.접근 속도가 느려질 수 있지만 메모리 사용량은 4분의 3입니다.

데이터 구조 정렬은 모든 최신 컴퓨터에서 기본적인 문제이지만 많은 컴퓨터 언어 및 컴퓨터 언어 구현에서 데이터 정렬을 자동으로 처리합니다.Fortran, Ada,[1][2] PL/I,[3] [4]Pascal, 특정 C 및 C++ 구현, D,[5] Rust,[6] C#[7] 및 어셈블리 언어를 통해 데이터 구조 패딩을 적어도 부분적으로 제어할 수 있으며, 이는 특정 특수한 상황에서 유용할 수 있습니다.

정의들

메모리 주소 a는 a가 n의 배수(여기서 n은 2의 거듭제곱)일 때 n바이트 정렬이라고 한다.이 문맥에서 바이트는 메모리 액세스의 최소 단위입니다. 즉, 각 메모리 주소는 다른 바이트를 지정합니다.n바이트로 정렬된 주소는 이진수로 표현될 때 최소 log(n)의 최하위 0을 가집니다2.

대체 표현 b-bit aligned는 b/8 바이트 정렬 주소를 나타냅니다(예: 64비트 aligned는 8바이트 정렬).

메모리 액세스는 액세스되는 데이터의 길이가 n바이트이고 데이터 주소가 n바이트일 때 정렬된다고 한다.메모리 액세스가 정렬되어 있지 않은 경우, 메모리 액세스가 정렬되어 있지 않다고 합니다.정의상 바이트 메모리 액세스는 항상 정렬됩니다.

n바이트 길이의 원시 데이터를 참조하는 메모리 포인터는 n바이트로 정렬된 주소만 포함할 수 있는 경우 정렬된 것으로 간주되며, 그렇지 않은 경우 정렬되지 않은 것으로 간주됩니다.데이터 집약체(데이터 구조 또는 어레이)를 참조하는 메모리 포인터는 집약체 내의 각 프리미티브 데이텀이 정렬된 경우에만 정렬된다.

위의 정의에서는 각 원시 데이텀이 2바이트 길이의 거듭제곱이라고 가정합니다.그렇지 않은 경우(x86의 80비트 부동소수점처럼), 컨텍스트는 데이터가 정렬된 것으로 간주되는 조건에 영향을 미칩니다.

데이터 구조는 유계라고 하는 정적 크기 또는 비계라고 하는 동적 크기의 힙에 있는 메모리에 저장할 수 있습니다.

문제

CPU는 한 번에 하나의 메모리 워드로 메모리에 액세스합니다.메모리 워드 사이즈가 적어도 컴퓨터에서 지원되는 가장 큰 원시 데이터 타입과 같은 크기인 한 정렬된 액세스는 항상 단일 메모리 워드에 액세스합니다.이는 잘못 정렬된 데이터 액세스의 경우에는 해당되지 않을 수 있습니다.

데이텀의 최대 바이트와 최소 바이트가 같은 메모리 워드 내에 없는 경우 컴퓨터는 데이텀 액세스를 여러 메모리 액세스로 분할해야 합니다.메모리 액세스를 생성하고 조정하려면 복잡한 회로가 많이 필요합니다.메모리 워드가 다른 메모리 페이지에 있는 경우를 처리하려면 프로세서는 명령을 실행하기 전에 두 페이지가 모두 존재하는지 확인하거나 명령 실행 중 메모리 액세스의 TLB 오류 또는 페이지 장애를 처리할 수 있어야 합니다.

일부 프로세서 설계에서는 이러한 복잡성을 의도적으로 회피하고 메모리 액세스가 잘못되었을 때 대체 동작을 발생시킵니다.예를 들어 ARMv6 ISA보다 이전 ARM 아키텍처를 구현하려면 모든 멀티바이트 로드 [8]및 저장 명령에 대해 정렬된 메모리 액세스가 필요합니다.어떤 특정 명령이 발행되었는지에 따라 잘못 정렬된 액세스를 시도하면 문제가 되는 주소의 최하위 비트가 정렬된 액세스로 반올림되거나(때로는 추가 경고 포함), MMU 예외를 발생시키거나(MU 하드웨어가 존재하는 경우), 기타 예측 불가능한 다른 비트를 사일런트하게 발생시킬 수 있습니다.결과.ARMv6 이후의 아키텍처는 많은 상황에서 비정렬 액세스를 지원하지만 반드시 모든 것을 지원하는 것은 아닙니다.

하나의 메모리 워드에 액세스 하는 경우, 조작은 원자성이 됩니다.즉, 메모리 워드 전체가 동시에 읽히거나 쓰입니다.다른 디바이스는 읽기 또는 쓰기 조작이 완료될 때까지 기다려야 액세스 할 수 있습니다.이것은 복수의 메모리 워드에 대한 비정렬 액세스에 대해서는 해당되지 않을 수 있습니다.예를 들어, 첫 번째 워드는 다른 디바이스에 의해 쓰여지고 두 번째 워드는 첫 번째 디바이스에 의해 읽혀져 원래 값도 갱신된 값도 아닙니다.이러한 장애는 드물지만 식별이 매우 어려울 수 있습니다.

데이터 구조 패딩

컴파일러(또는 인터프리터)는 일반적으로 정렬된 경계에 개별 데이터 항목을 할당하지만 데이터 구조에는 정렬 요구사항이 다른 멤버가 있는 경우가 많습니다.올바른 정렬을 유지하기 위해 번역자는 일반적으로 이름 없는 데이터 멤버를 추가로 삽입하여 각 멤버가 올바르게 정렬되도록 합니다.또, 데이터 구조 전체를 최종 이름 없는 부재로 패딩해도 좋다.이를 통해 구조 배열의 각 구성원을 올바르게 정렬할 수 있습니다.

패딩은 구조물 부재 뒤에 더 큰 정렬 요건이 있는 부재 또는 구조물 끝에 있을 때만 삽입됩니다.구조물 내 부재의 순서를 변경함으로써 정렬을 유지하기 위해 필요한 패딩의 양을 변경할 수 있다.예를 들어, 구성원을 내림차순 정렬 요구 사항에 따라 정렬하는 경우 최소량의 패딩이 필요합니다.필요한 최소 패딩 양은 항상 구조물에서 가장 큰 선형보다 작습니다.필요한 패딩의 최대량을 계산하는 것은 더 복잡하지만, 항상 모든 부재의 정렬 요건 합계에서 구조물 부재의 최소 정렬 절반에 대한 정렬 요건 합계의 2배보다 작습니다.

C와 C++에서는 컴파일러가 공간을 절약하기 위해 구조 멤버의 순서를 변경할 수 없지만 다른 언어도 가능합니다.또한 대부분의 C 컴파일러와 C++ 컴파일러가 구조의 멤버를 특정 레벨의 정렬로 "패킹"하도록 지시할 수 있습니다.예를 들어 "pack (2)"는 패딩 멤버의 길이가 최대 1바이트가 되도록 바이트보다 큰 데이터 멤버를 2바이트 경계에 정렬하는 것을 의미합니다.마찬가지로 PL/I에서는 구조물이 다음과 같이 선언될 수 있다.UNALIGNED비트 문자열 주변을 제외한 모든 패딩을 제거합니다.

이러한 "충전된" 구조의 한 가지 용도는 메모리를 절약하는 것입니다.예를 들어, 1바이트와 4바이트 정수를 포함하는 구조에는 추가로 3바이트의 패딩이 필요합니다.이러한 구조를 대규모로 배열할 경우 각 구조에 액세스하는 데 시간이 더 오래 걸리지만 패킹된 경우 메모리 사용량이 37.5% 줄어듭니다.이러한 타협은 시공간의 트레이드오프의 한 형태로 간주될 수 있다.

메모리 공간을 절약하기 위해 "충전된" 구조의 사용이 가장 자주 사용되지만 표준 프로토콜을 사용하여 전송을 위한 데이터 구조를 포맷하는 데에도 사용될 수 있습니다.그러나 이 사용법에서는 구조 멤버의 값이 프로토콜에 필요한 엔디안(종종 네트워크 바이트 순서)으로 저장되도록 주의할 필요가 있습니다.이것은 호스트 머신에서 기본적으로 사용되는 엔디안과는 다를 수 있습니다.

컴퓨터 패딩

다음 공식은 데이터 구조의 시작을 정렬하는 데 필요한 패딩 바이트 수를 제공합니다(mod는 모듈로 연산자). 

패딩 = (align - (표준 mod align)) mod align align = 오프셋 + 패딩 = 오프셋 + (표준 mod align) mod align

예를 들어 4바이트 정렬 구조의 오프셋 0x59d에 추가하는 패딩은 3입니다.이 구조체는 4의 배수인 0x5a0에서 시작됩니다.그러나 오프셋의 정렬이 이미 정렬의 정렬과 동일한 경우 두 번째 모듈로 in(align - (오프셋 mod align) mod align은 0을 반환하므로 원래 값은 변경되지 않습니다.

얼라인먼트는 정의상 [a]2의 거듭제곱이므로 모듈로 연산은 비트 부울 AND 연산으로 줄일 수 있습니다.

다음 공식은 오프셋이 부호화되지 않았거나 시스템이 2의 보완 산술을 사용하는 경우 올바른 값(&는 비트 단위 AND 및 ~ 비트 단위 NOT)을 생성합니다.

패딩 =(align - (align - 1) & (align - 1) = -flash & (align - 1) align = (align + (align - 1) = (align + (align - 1) & - align

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

데이터 구조 멤버는 메모리에 순차적으로 저장되므로 아래 구조에서는 멤버 Data1이 항상 Data2 앞에 있고 Data2가 항상 Data3 앞에 있습니다.

구조 마이 데이터 {     짧다 데이터 1;     짧다 데이터2;     짧다 데이터 3; };

"short" 타입이 2바이트의 메모리에 저장되어 있는 경우, 위에서 설명한 데이터 구조의 각 멤버는 2바이트 정렬됩니다.Data1은 오프셋 0, Data2는 오프셋 2, Data3은 오프셋 4에 있습니다.이 구조의 크기는 6바이트입니다.

구조체의 각 부재의 유형은 일반적으로 기본 정렬을 가지며, 이는 프로그래머에 의해 특별히 요청되지 않는 한 미리 결정된 경계에 정렬됨을 의미합니다.Microsoft(Visual C++), Borland/CodeGear(C++Builder), Digital Mars(DMC) 및 GNU(GCC)의 컴파일러에 대해 32비트 x86용으로 컴파일할 때 다음과 같은 일반적인 정렬이 유효합니다.

  • 문자(1바이트)는 1바이트 정렬됩니다.
  • 쇼트(2바이트)는 2바이트 정렬됩니다.
  • int(4바이트)는 4바이트 정렬됩니다.
  • 긴 길이(4바이트)는 4바이트 정렬됩니다.
  • 플로트(4바이트)는 4바이트 정렬됩니다.
  • 더블(8바이트)은 Windows에서는 8바이트, Linux에서는 4바이트로 정렬됩니다(8바이트는 -malign-double 컴파일 시간 옵션).
  • 긴 길이(8바이트)는 4바이트 정렬됩니다.
  • 긴 더블(C++빌더와 DMC의 경우 10바이트, Visual C++의 경우 8바이트, GCC의 경우 12바이트)은 C++빌더의 경우 8바이트, DMC의 경우 2바이트, Visual C++의 경우 8바이트, GCC의 경우 4바이트가 됩니다.
  • 포인터(4바이트)는 모두 4바이트 정렬됩니다.(예: char*, int*)

LP64 64비트 시스템과 32비트 시스템의 얼라인먼트의 유일한 차이점은 다음과 같습니다.

  • 긴(8바이트)은 8바이트 정렬됩니다.
  • 더블(8바이트)은 8바이트 정렬됩니다.
  • 긴 길이(8바이트)는 8바이트 정렬됩니다.
  • 긴 더블(Visual C++의 경우 8바이트, GCC의 경우 16바이트)은 Visual C++의 경우 8바이트, GCC의 경우 16바이트가 됩니다.
  • 포인터(8바이트)는 모두 8바이트 정렬됩니다.

일부 데이터 유형은 구현에 따라 달라집니다.

컴파일 전 총 8바이트의 다양한 유형의 멤버를 가진 구조를 다음에 나타냅니다.

구조 혼합 데이터 {     차 데이터 1;     짧다 데이터2;     인트 데이터 3;     차 데이터 4; };

컴파일 후 데이터 구조는 패딩 바이트로 보완되어 각 멤버의 적절한 정렬이 보증됩니다.

구조 혼합 데이터  /* 32비트 x86 머신 컴파일 후 */ {     차 데이터 1; /* 1바이트 */     차 패딩 1[1]; /* 다음 '짧음'에 대한 1바이트는 2바이트 경계에 정렬됩니다. 구조가 시작되는 주소가 짝수 */라고 가정합니다.     짧다 데이터2; /* 2바이트 */     인트 데이터 3;  /* 4바이트 - 가장 큰 구조체 멤버 */     차 데이터 4; /* 1바이트 */     차 패딩 2[3]; /* 3바이트 구조체의 전체 크기를 12바이트로 합니다*/ };

이 구조체의 컴파일된 크기는 12바이트입니다.마지막 멤버는 필요한 바이트 수로 패딩되어 구조의 총 크기가 구조 멤버의 가장 큰 정렬의 배수(이 경우 정렬(int), Linux-32비트/[citation needed]gcc의 경우 = 4)가 되어야 합니다.

이 경우 마지막 멤버에 3바이트가 추가되어 구조를 12바이트 크기(얼라인먼트(int) × 3)로 패딩합니다. 

구조 파이널 패드 {   흘러가다 x;   차 n[1]; };

이 예에서는 구조물의 총 크기가size of(FinalPad) == 5가 아니라 8입니다(따라서 크기가 4의 배수(플로트 정렬)입니다). 

구조 파이널 패드 쇼트 {   짧다 s;   차 n[3]; };

이 예에서는 (FinalPadShort) == 6의 전체 크기이며, 5도 아닙니다(8도 아님). 따라서 크기는 2의 배수입니다(linux-32bit/gcc의 경우 alignment(short) = 2).

구조 멤버를 재정렬하거나 컴파일러의 구조 멤버의 정렬(또는 "패킹")을 변경함으로써 필요한 메모리를 줄이기 위해 구조의 정렬을 변경할 수 있습니다. 

구조 혼합 데이터  /* 재주문 후 */ {     차 데이터 1;     차 데이터 4;   /* 재주문*/     짧다 데이터2;     인트 데이터 3; };

이제 컴파일된 구조의 크기가 사전 컴파일된 크기인 8바이트와 일치합니다.Padding1[1]은 Data4로 대체되었으며(따라서 삭제됨) Padding2[3]는 구조가 이미 긴 단어의 크기에 맞춰져 있기 때문에 더 이상 필요하지 않습니다.

MixedData 구조를 1바이트 경계로 정렬하는 대체 방법을 사용하면 프리프로세서가 구조 멤버의 미리 결정된 정렬을 폐기하므로 패딩 바이트가 삽입되지 않습니다.

구조 멤버의 정렬을 정의하는 표준 방법은 없지만 일부 컴파일러는 #pragma 지시어를 사용하여 소스 파일 내의 패킹을 지정합니다.다음은 예를 제시하겠습니다.

#봉투팩(포장)/* 전류 정렬을 스택에 푸시 */ #봉투팩(1)/* 정렬을 1바이트 경계로 설정합니다 */  구조 MyPacked {     차 데이터 1;     긴 데이터2;     차 데이터 3; };  #봉투팩(팝)/* 스택에서 원래 얼라인먼트를 복원합니다*/

이 구조는 32비트 시스템에서 컴파일된 크기가 6바이트입니다.위의 명령어는 Microsoft,[9] Borland, [10]GNU 및 기타 많은 컴파일러에서 사용할 수 있습니다.

또 다른 예는 다음과 같습니다.

구조 MyPacked {     차 데이터 1;     긴 데이터2;     차 데이터 3; } __param__((포장된));

기본 포장 및 #pragma 팩

일부 Microsoft 컴파일러, 특히 RISC 프로세서의 경우 프로젝트 디폴트패킹(/Zp 디렉티브)과 #pragma pack 디렉티브 사이에 예기치 않은 관계가 있습니다.#pragma pack 지시문은 프로젝트의 기본 [11]패킹에서 구조물의 패킹 크기를 줄이는 데만 사용할 수 있습니다.이로 인해 프로젝트 패킹이 이보다 작은 경우 #pragma pack(8)을 사용하는 라이브러리 헤더와의 상호 운용성 문제가 발생합니다.따라서 프로젝트 패킹을 기본값인 8바이트 이외의 값으로 설정하면 라이브러리 헤더에서 사용되는 #pragma pack 지시어가 깨지고 구조 간에 이진 비호환성이 발생합니다.이 제한은 x86용 컴파일에는 적용되지 않습니다.

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

캐시 라인에 정렬된 메모리를 할당하는 것이 좋습니다.어레이가 여러 스레드에 대해 파티션으로 분할되어 있는 경우 하위 어레이의 경계가 캐시 라인에 맞춰져 있지 않으면 성능이 저하될 수 있습니다.다음으로 64바이트의 캐시로 정렬된 메모리(사이즈 10의 더블 어레이)를 할당하는 예를 나타냅니다. 

#실패하다 <stdlib.h> 이중으로 하다 *후우(무효) {    이중으로 하다 *변화하다;//사이즈가 10인 배열 만들기    인트     네 알겠습니다;     네 알겠습니다 = posix_memalign((무효**)&변화하다, 64, 10*크기(이중으로 하다));     한다면 (네 알겠습니다 != 0)      돌아가다 특수한 순서;     돌아가다 변화하다; }

얼라인먼트 요건의 하드웨어 중요성

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

예를 들어 32비트 운영체제에서는 4KiB(4096바이트) 페이지는 단순히 임의의 4KiB 청크가 아닙니다.대신 보통 4KiB 경계에 정렬된 메모리 영역입니다.이는 페이지 크기 경계에 페이지를 정렬하면 하드웨어가 복잡한 계산을 수행하는 대신 주소의 상위 비트를 대체하여 가상 주소를 물리적 주소에 매핑할 수 있기 때문입니다.

예:가상 주소 0x2CFC7000과 물리 주소 0x12345000의 TLB 매핑이 있다고 가정합니다(양쪽 주소는 4KiB 경계로 정렬되어 있습니다).가상 주소 va=0x2CFC7에 있는 데이터 액세스ABC는 0x2CFC7에서 0x12345의 TLB 해상도를 통해 pa=0x12345에 대한 물리적 액세스를 발행합니다.ABC. 여기서 20/12비트 분할은 다행히 5/3자리의 16진수 표현 분할과 일치합니다.하드웨어는 물리 주소의 처음 20비트(0x12345)와 가상 주소의 마지막 12비트(0xABC)를 조합하는 것만으로 이 변환을 실장할 수 있습니다.이것은 Virtual Indexed(ABC; 가상 인덱스) 물리 태그 부착(12345)이라고도 불립니다.

크기가(n+1) 2 - 1인 데이터 블록은 항상 크기가n 2인 하위 블록이 2바이트에n 정렬되어 있습니다.

이렇게 하면 얼라인먼트에 대한 지식이 없는 동적 할당기를 사용하여 공간 손실의 2배라는 가격으로 얼라인먼트된 버퍼를 제공할 수 있습니다. 

// 예: malloc()를 사용하여 4096 바이트 버퍼로 정렬된4096 바이트를 가져옵니다.  // 넓은 영역에 대한 정렬되지 않은 포인터 무효 *업. = 마로크((1 << > 13) - 1); // 4KiB에 대한 잘 정렬된 포인터 무효 *ap = 얼라인먼트 톤 익스트(업., 12);

여기서 aligntonext(p, r)는 정렬된 증분을 추가한 다음 p의 최하위 비트 r개를 지우는 방식으로 작동합니다.가능한 구현은 다음과 같습니다.

// 가독성을 위해 "uint32_t p, bits;"로 가정합니다. #param alignto(p, bits)((p) >> 비트) << 비트) #sign aligntonext(p, bits) alignto((p) + (1 < 비트) - 1), 비트)

메모들

  1. ^ 타겟 얼라인먼트가 2의 거듭제곱인 최신 컴퓨터.예를 들어 9비트바이트 또는 60비트 워드를 사용하는 시스템에서는 그렇지 않을 수 있습니다.

레퍼런스

  1. ^ "Ada Representation Clauses and Pragmas". GNAT Reference Manual 7.4.0w documentation. Retrieved 2015-08-30.
  2. ^ "F.8 Representation Clauses". SPARCompiler Ada Programmer's Guide (PDF). Retrieved 2015-08-30.
  3. ^ IBM System/360 Operating System PL/I Language Specifications (PDF). IBM. July 1966. pp. 55–56. C28-6571-3.
  4. ^ Niklaus Wirth (July 1973). "The Programming Language Pascal (Revised Report)" (PDF). p. 12.
  5. ^ "Attributes - D Programming Language: Align Attribute". Retrieved 2012-04-13.
  6. ^ "The Rustonomicon - Alternative Representations". Retrieved 2016-06-19.
  7. ^ "LayoutKind Enum (System.Runtime.InteropServices)". docs.microsoft.com. Retrieved 2019-04-01.
  8. ^ Kurusa, Levente (2016-12-27). "The curious case of unaligned access on ARM". Medium. Retrieved 2019-08-07.
  9. ^ 포장하다
  10. ^ 6.58.8 구조 패키징의 프래그마
  11. ^ "Working with Packing Structures". MSDN Library. Microsoft. 2007-07-09. Retrieved 2011-01-11.

추가 정보

  • Bryant, Randal E.; David, O'Hallaron (2003). Computer Systems: A Programmer's Perspective (2003 ed.). Upper Saddle River, New Jersey, USA: Pearson Education. ISBN 0-13-034074-X.
  • "1. Introduction: Segment Alignment". 8086 Family Utilities - User's Guide for 8080/8085-Based Development Systems (PDF). Revision E (A620/5821 6K DD ed.). Santa Clara, California, USA: Intel Corporation. May 1982 [1980, 1978]. pp. 1-6, 3-5. Order Number: 9800639-04. Archived (PDF) from the original on 2020-02-29. Retrieved 2020-02-29. […] A segment can have one (and in the case of the inpage attribute, two) of five alignment attributes: […] Byte, which means a segment can be located at any address. […] Word, which means a segment can only be located at an address that is a multiple of two, starting from address 0H. […] Paragraph, which means a segment can only be located at an address that is a multiple of 16, starting from address 0. […] Page, which means a segment can only be located at an address that is a multiple of 256, starting from address 0. […] Inpage, which means a segment can be located at whichever of the preceding attributes apply plus must be located so that it does not cross a page boundary […] The alignment codes are: […] B - byte […] W - word […] G - paragraph […] xR - inpage […] P - page […] A - absolute […] the x in the inpage alignment code can be any other alignment code. […] a segment can have the inpage attribute, meaning it must reside within a 256 byte page and can have the word attribute, meaning it must reside on an even numbered byte. […]

외부 링크