정렬시 최소한의 공간을 낭비하기 위해 구조체에서 멤버를 구성하려면 어떻게해야합니까?
[ 구조 패딩 및 패킹 의 중복이 아닙니다 . 그 질문은 패딩이 언제 어떻게 발생하는지에 관한 것입니다. 이건 어떻게 다룰 지에 대한 것입니다.]
방금 C ++의 정렬 결과로 얼마나 많은 메모리가 낭비되는지 깨달았습니다. 다음과 같은 간단한 예를 고려하십시오.
struct X
{
int a;
double b;
int c;
};
int main()
{
cout << "sizeof(int) = " << sizeof(int) << '\n';
cout << "sizeof(double) = " << sizeof(double) << '\n';
cout << "2 * sizeof(int) + sizeof(double) = " << 2 * sizeof(int) + sizeof(double) << '\n';
cout << "but sizeof(X) = " << sizeof(X) << '\n';
}
g ++를 사용할 때 프로그램은 다음과 같은 출력을 제공합니다.
sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 24
그것은 50 %의 메모리 오버 헤드입니다! 134'217'728 Xs 의 3 기가 바이트 배열에서 1 기가 바이트는 순수한 패딩입니다.
다행스럽게도 문제에 대한 해결책은 매우 간단합니다. 우리는 간단히 다음 double b과 같이 교체하면 int c됩니다.
struct X
{
int a;
int c;
double b;
};
이제 결과는 훨씬 더 만족 스럽습니다.
sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 16
그러나 문제가 있습니다. 이것은 상호 호환되지 않습니다. 예, g ++에서 a int는 4 바이트이고 a double는 8 바이트이지만 항상 사실은 아닙니다 (정렬도 동일 할 필요는 없음). 따라서 다른 환경에서이 "수정"은 쓸모가 없을뿐만 아니라 또한 필요한 패딩의 양을 늘림으로써 상황을 악화시킬 수도 있습니다.
이 문제를 해결할 수있는 신뢰할 수있는 크로스 플랫폼 방법이 있습니까 ( 오정렬로 인한 성능 저하없이 필요한 패딩의 양을 최소화 )? 컴파일러가 이러한 최적화를 수행하지 않는 이유는 무엇입니까 (패딩을 줄이기 위해 구조체 / 클래스 멤버를 교체)?
설명
오해와 혼란으로 인해 .NET Core 를 "포장"하고 싶지 않다는struct 점을 강조하고 싶습니다 . 즉, 구성원이 정렬되지 않아 액세스 속도가 느려지는 것을 원하지 않습니다. 대신, 나는 여전히 모든 멤버가 자체 정렬되기를 원하지만 패딩에 최소한의 메모리를 사용합니다. 예를 들어 여기와 Eric Raymond 의 The Lost Art of Packing 에 설명 된대로 수동 재 배열을 사용하여이 문제를 해결할 수 있습니다 . 저는 다가오는 C ++ 20 표준에 대한 제안 P1112 에 설명 된 것과 유사한 자동화 된 가능한 한 많은 크로스 플랫폼 방법을 찾고 있습니다.
(생각없이 이러한 규칙을 적용하지 마십시오. 함께 사용하는 구성원의 캐시 지역성에 대한 ESR의 요점을 참조하십시오. 다중 스레드 프로그램에서는 다른 스레드에서 작성된 구성원의 잘못된 공유를주의하십시오. 일반적으로 스레드 당 데이터를 원하지 않습니다. 큰으로 분리를 제어하지 않는 한 이러한 이유로 단일 구조체 alignas(128). 이것은 atomic비 원자 변수에 적용됩니다. 중요한 것은 스레드가 캐시 라인에 쓰는 방법에 관계없이 쓰레드입니다.)
경험 법칙 : 가장 큰 것에서 가장 작은 것alignof() . 어디에서나 완벽하게 할 수있는 일은 없지만 요즘 가장 일반적인 경우는 일반 32 비트 또는 64 비트 CPU에 대한 정상적인 "일반"C ++ 구현입니다. 모든 기본 유형에는 2의 제곱 크기가 있습니다.
대부분의 유형은 구현의 레지스터 너비를 갖 alignof(T) = sizeof(T)거나 alignof(T)제한합니다. 따라서 큰 유형은 일반적으로 작은 유형보다 더 정렬됩니다.
대부분의 ABI의 구조체 패킹 규칙은 구조체 멤버에게 구조체 alignof(T)시작에 대한 절대적인 정렬을 제공 하며 구조체 자체는 alignof()해당 멤버 중 가장 큰 멤버를 상속합니다 .
- 항상 64 비트 멤버를 먼저 배치합니다 (예
double:long long, 및int64_t). 물론 ISO C ++는 이러한 유형을 64 비트 / 8 바이트로 수정하지 않지만 실제로는 관심있는 모든 CPU에서 이러한 유형을 수정합니다. 코드를 이국적인 CPU로 이식하는 사람들은 필요한 경우 최적화하기 위해 구조 레이아웃을 조정할 수 있습니다. 다음 포인터 및 포인터 폭 정수 :
size_t,intptr_t및ptrdiff_t(일 수있는 32 또는 64 비트). 이는 플랫 메모리 모델을 사용하는 CPU에 대한 일반적인 최신 C ++ 구현에서 모두 동일한 너비입니다.x86 및 Intel CPU에 관심이 있다면 연결 목록 및 트리 왼쪽 / 오른쪽 포인터를 먼저 배치하는 것이 좋습니다. 트리 또는 연결 목록의 노드를 통한 포인터 추적 은 구조체 시작 주소가 액세스중인 멤버와 다른 4k 페이지에있는 경우 패널티를 갖습니다 . 그것들을 우선시하는 것은 사실 일 수없는 것을 보장합니다.
그런 다음
long(Windows x64와 같은 LLP64 ABI에서 포인터가 64 비트 인 경우에도 32 비트가됩니다.) 그러나 최소한int.다음 32 비트
int32_t,int,float,enum. (선택적으로 해당 유형을 32 비트로 패딩하는 가능한 8/16 비트 시스템에 대해 관심 이있는 경우 미리 분리int32_t하고 , 또는 자연스럽게 정렬 된 상태에서 더 잘 수행합니다. 대부분의 이러한 시스템에는 더 넓은 부하 (FPU 또는 SIMD)가 없습니다. 더 넓은 유형은 어쨌든 여러 개의 개별 청크로 처리되어야합니다.)floatintISO C ++는
int16 비트만큼 좁거나 임의로 너비를 허용하지만 실제로는 64 비트 CPU에서도 32 비트 유형입니다. ABI 설계자는 32 비트에서 작동하도록 설계된 프로그램 이 더 넓int으면 메모리 (및 캐시 공간) 만 낭비 한다는 사실을 발견했습니다int. 정확성 문제를 야기 할 것이라고 가정하지 마십시오. 그러나 "휴대용 성능"을 위해서는 정상적인 경우에 옳 아야합니다.이국적인 플랫폼에 맞게 코드를 조정하는 사람들은 필요한 경우 조정할 수 있습니다. 특정 구조체 레이아웃이 성능이 중요하다면 헤더에 가정과 추론에 대해 설명 할 수 있습니다.
- 다음
short/int16_t - 다음
char/int8_t/bool - (여러
bool플래그의 경우, 특히 대부분을 읽거나 모두 함께 수정 된 경우 1 비트 비트 필드로 패킹하는 것을 고려하십시오.)
(부호없는 정수 유형의 경우 내 목록에서 해당 서명 유형을 찾으십시오.)
원하는 경우 더 좁은 유형의 8 바이트 배열 을 더 빨리 갈 수 있습니다. 그러나 유형의 정확한 크기를 모르는 경우 int i+ char buf[4]가 두 doubles 사이에 8 바이트로 정렬 된 슬롯을 채울 것이라고 보장 할 수 없습니다 . 그러나 그것은 나쁜 가정이 아니므로 마지막 대신에 그들을 모으는 이유 (함께 액세스하는 구성원의 공간적 위치와 같은)가 있다면 어쨌든 그렇게 할 것입니다.
이국적인 유형 : x86-64 System V에는 alignof(long double) = 16, i386 System V에는 alignof(long double) = 4, sizeof(long double) = 12. 실제로는 10 바이트이지만 12 또는 16으로 패딩 된 x87 80 비트 유형이므로 alignof의 배수이므로 정렬 보장을 위반하지 않고 배열이 가능합니다.
그리고 일반적으로 구조체 멤버 자체가 sizeof(x) != alignof(x).
또 다른 트위스트 (I 올바르게 기억 경우 예를 들어, 32 비트 Windows) 일부 ABI를에 구조체 멤버 (8 바이트까지) 크기로 정렬되어 있다는 것입니다 구조체의 시작 부분을 기준으로 하더라도, alignof(T)단지 4 아직 double하고 int64_t.
이는 정렬 보장 을 제공하지 않고 단일 구조체에 대해 8 바이트 정렬 메모리를 별도로 할당하는 일반적인 경우를 최적화하기위한 것 입니다. i386 System V는 또한 alignof(T) = 4대부분의 기본 유형에 대해 동일 합니다 (그러나 malloc여전히 8 바이트 정렬 메모리를 제공합니다 alignof(maxalign_t) = 8). 그러나 어쨌든 i386 System V에는 구조 패킹 규칙이 없으므로 (구조체를 가장 큰 것에서 가장 작은 것으로 배열하지 않으면) 8 바이트 멤버가 구조의 시작에 상대적으로 과소 정렬 될 수 있습니다. .
대부분의 CPU에는 레지스터의 포인터가 주어지면 모든 바이트 오프셋에 대한 액세스를 허용하는 주소 지정 모드가 있습니다. 최대 오프셋은 일반적으로 매우 크지 만 x86에서는 바이트 오프셋이 부호있는 바이트 ( [-128 .. +127])에 맞으면 코드 크기를 절약합니다 . 따라서 어떤 종류의 큰 배열이있는 경우 자주 사용하는 멤버 뒤에 나중에 구조체에 넣는 것이 좋습니다. 이것이 약간의 패딩 비용이 들더라도.
컴파일러는 거의 항상 레지스터에 구조체 주소가있는 코드를 만들고, 짧은 음의 변위를 이용하기 위해 구조체 중간에있는 주소가 아닙니다.
Eric S. Raymond는 The Lost Art of Structure Packing을 썼습니다 . 특히 구조 재정렬 에 대한 섹션 은 기본적으로이 질문에 대한 답변입니다.
그는 또 다른 중요한 점을 지적합니다.
크기별로 재정렬하는 것이 슬롭을 제거하는 가장 간단한 방법 이지만 반드시 올바른 것은 아닙니다 . 가독성과 캐시 지역성이라는 두 가지 문제가 더 있습니다.
캐시 라인 경계에서 쉽게 분할 할 수 있는 대형 구조체 에서는 항상 함께 사용되는 경우 두 가지를 근처에 두는 것이 좋습니다. 또는로드 / 스토어 병합을 허용하기 위해 인접 해 있습니다. 예를 들어 더 작은 멤버를 개별적으로로드하는 대신 하나의 (무의미한) 정수 또는 SIMD로드 / 스토어로 8 바이트 또는 16 바이트를 복사합니다.
캐시 라인은 일반적으로 최신 CPU에서 32 또는 64 바이트입니다. (최신 x86에서는 항상 64 바이트입니다. Sandybridge 제품군은 L2 캐시에 기본 L2 스 트리머 HW 프리 페치 패턴 감지기 및 L1d 프리 페치와는 별도로 128 바이트 쌍의 라인을 완료하려고 시도하는 인접 라인 공간 프리 페 처가 있습니다.)
재미있는 사실 : Rust는 컴파일러가 더 나은 패킹이나 다른 이유로 구조체를 재정렬 할 수 있도록합니다. 하지만 컴파일러가 실제로 그렇게하는 경우 IDK. 아마도 구조체가 실제로 사용되는 방식을 기반으로 선택하려는 경우 링크 타임 전체 프로그램 최적화를 통해서만 가능할 것입니다. 그렇지 않으면 프로그램의 별도로 컴파일 된 부분이 레이아웃에 동의 할 수 없습니다.
(@alexis는 ESR의 기사에 대한 링크 전용 답변을 게시 했으므로 시작 지점에 감사드립니다.)
gcc에는 -Wpadded구조에 패딩이 추가 될 때 경고하는 경고가 있습니다.
https://godbolt.org/z/iwO5Q3 :
<source>:4:12: warning: padding struct to align 'X::b' [-Wpadded]
4 | double b;
| ^
<source>:1:8: warning: padding struct size to alignment boundary [-Wpadded]
1 | struct X
| ^
패딩이 적거나 없도록 멤버를 수동으로 재정렬 할 수 있습니다. 그러나 이것은 다른 유형이 다른 시스템에서 다른 크기 / 정렬을 가질 수 있기 때문에 크로스 플랫폼 솔루션이 아닙니다 (특히 포인터는 다른 아키텍처에서 4 또는 8 바이트 임). 일반적인 경험 법칙은 멤버를 선언 할 때 가장 큰 정렬에서 가장 작은 정렬로 이동하는 것이며, 여전히 걱정이되는 경우 코드를 -Wpadded한 번 컴파일하십시오 (하지만 패딩이 때때로 필요하기 때문에 일반적으로 유지하지는 않습니다).
컴파일러가 자동으로 수행 할 수없는 이유는 표준 ( [class.mem] / 19 ) 때문입니다. 이것은 public 멤버 &x.a < &x.c(일부 X x;) 만있는 간단한 구조체이기 때문에 재 배열 할 수 없음을 보장합니다 .
일반적인 경우에는 실제로 휴대용 솔루션이 없습니다. 표준이 부과하는 최소 요구 사항을 제외하고 유형은 구현에서 원하는 크기가 될 수 있습니다.
이를 위해 컴파일러는 클래스 멤버를 더 효율적으로 재정렬 할 수 없습니다. 표준은 객체가 선언 된 순서 (접근 수정 자에 의해)로 배치되어야한다고 규정하고 있습니다.
다음과 같은 고정 너비 유형을 사용할 수 있습니다.
struct foo
{
int64_t a;
int16_t b;
int8_t c;
int8_t d;
};
이러한 유형을 제공하는 경우 모든 플랫폼에서 동일하지만 정수 유형에서만 작동합니다. 고정 너비 부동 소수점 유형이 없으며 많은 표준 객체 / 컨테이너는 플랫폼마다 크기가 다를 수 있습니다.
Mate, 데이터가 3GB 인 경우 다른 방법으로 문제에 접근 한 다음 데이터 멤버를 교체해야합니다.
'구조체 배열'을 사용하는 대신 '배열 구조'를 사용할 수 있습니다. 그래서 말하십시오
struct X
{
int a;
double b;
int c;
};
constexpr size_t ArraySize = 1'000'000;
X my_data[ArraySize];
될 것입니다
constexpr size_t ArraySize = 1'000'000;
struct X
{
int a[ArraySize];
double b[ArraySize];
int c[ArraySize];
};
X my_data;
각 요소는 여전히 쉽게 액세스 할 수 있습니다 mydata.a[i] = 5; mydata.b[i] = 1.5f;....
패딩이 없습니다 (배열 사이의 몇 바이트 제외). 메모리 레이아웃은 캐시 친화적입니다. 프리 페처는 몇 가지 개별 메모리 영역에서 순차적 메모리 블록 읽기를 처리합니다.
그것은 언뜻보기에 비 정통적이지 않습니다. 이 접근 방식은 SIMD 및 GPU 프로그래밍에 널리 사용됩니다.
AoS (Array of Structures), 배열 구조
이것은 교과서의 메모리 대 속도 문제입니다. 패딩은 속도를 위해 메모리를 교환하는 것입니다. 다음과 같이 말할 수 없습니다.
내 구조체를 "포장"하고 싶지 않습니다.
pragma 팩은이 거래를 다른 방식으로 만들기 위해 정확히 고안된 도구이기 때문입니다. 즉, 메모리 속도입니다.
신뢰할 수있는 크로스 플랫폼 방식이 있습니까?
아니요,있을 수 없습니다. 정렬은 엄격하게 플랫폼에 따라 다릅니다. 다양한 유형의 크기는 플랫폼에 따라 다릅니다. 재구성하여 패딩을 피하는 것은 플랫폼에 따라 다릅니다.
속도, 메모리 및 크로스 플랫폼-두 개만 가질 수 있습니다.
컴파일러가 이러한 최적화를 수행하지 않는 이유는 무엇입니까 (패딩을 줄이기 위해 구조체 / 클래스 멤버를 교체)?
C ++ 사양은 컴파일러가 꼼꼼하게 구성된 구조체를 엉망으로 만들지 않도록 특별히 보장하기 때문입니다. 네 개의 수레가 연속으로 있다고 상상해보십시오. 때로는 이름으로 사용하고 때로는 float [3] 매개 변수를 사용하는 메소드에 전달합니다.
당신은 컴파일러가 그것들을 섞어서 1970 년대 이후로 잠재적으로 모든 코드를 깨뜨려야한다고 제안하고 있습니다. 그리고 어떤 이유로? 모든 프로그래머가 실제로 구조체 당 8 바이트를 저장하기를 원할 것이라고 보장 할 수 있습니까? 하나는 3GB 어레이가 있으면 1GB보다 더 큰 문제가 있음을 확신합니다.
표준은 구현에 구조 멤버 사이에 임의의 공간을 삽입 할 수있는 광범위한 재량권을 부여하지만, 이는 작성자가 패딩이 유용 할 수있는 모든 상황을 추측하려고하지 않았기 때문이며 원칙은 "이유없이 공간을 낭비하지 마십시오." "는 자명 한 것으로 간주되었습니다.
실제로, 커먼 플레이스 하드웨어에 대한 거의 모든 커먼 플레이스 구현은 크기가 2의 제곱이고 필요한 정렬이 크기보다 크지 않은 2의 제곱 인 기본 객체를 사용합니다. 또한, 거의 모든 구현은 구조체의 각 멤버를 이전 멤버를 완전히 따르는 첫 번째 사용 가능한 배열의 배열에 배치합니다.
일부 pedants는 그 행동을 악용하는 코드가 "이동 불가능"하다고 경고합니다. 그들에게 나는 대답 할 것이다
C 코드는 이식 불가능할 수 있습니다. 비록 프로그래머들에게 진정으로 이식 가능한 프로그램을 작성할 수있는 기회를주기 위해 노력했지만 C89위원회는 프로그래머가 이식성있게 작성하도록 강요하지 않고 "고수준 어셈블러"로서 C를 사용하지 못하게하고 싶지 않았습니다. 기계 별 코드를 작성할 수있는 능력은 다음과 같습니다. C의 강점 중 하나입니다.
이 원칙에 대한 약간의 확장으로, 90 %의 컴퓨터에서 실행해야하는 코드의 기능은 90 %의 컴퓨터에 공통적 인 기능을 악용 할 수 있다는 것입니다. C 프로그래머가 수십 년 동안 박물관에서만 사용 되어온 아키텍처의 한계를 수용하기 위해 뒤로 구부러져서는 안된다는 개념은 자명해야하지만 그렇지 않은 것 같습니다.
당신은 할 수 있습니다 사용 #pragma pack(1)하지만,이의 아주 이유는 컴파일러가 최적화 있다는 것입니다. 전체 레지스터를 통해 변수에 액세스하는 것이 최소 비트에 액세스하는 것보다 빠릅니다.
특정 패킹은 직렬화 및 인터 컴파일러 호환성 등에 유용합니다.
'IT이야기' 카테고리의 다른 글
| Rails 5에서 터보 링크를 비활성화하는 방법 (0) | 2021.04.19 |
|---|---|
| Docker-이 플랫폼에서는 이미지 운영 체제 "창"을 사용할 수 없습니다. (0) | 2021.04.19 |
| 다른 메서드를 호출하는 메서드 단위 테스트 (0) | 2021.04.19 |
| PreparedStatements 및 성능 (0) | 2021.04.18 |
| GetView VS 사용자 지정 CursorAdapter의 BindView (0) | 2021.04.18 |