Wypełnienie i wypełnienie struktury

209

Rozważać:

struct mystruct_A
{
   char a;
   int b;
   char c;
} x;

struct mystruct_B
{
   int b;
   char a;
} y;

Rozmiary struktur wynoszą odpowiednio 12 i 8.

Czy te struktury są wyściełane czy zapakowane?

Kiedy ma miejsce wypełnianie lub pakowanie?

Manu
źródło
3
Przeczytaj stackoverflow.com/questions/119123/...
Prasoon Saurav
24
Pakowanie struktur Lost Art of C - catb.org/esr/structure-packing
Paolo
paddingczyni rzeczy większymi. packingzmniejsza rzeczy. Zupełnie inaczej.
smwikipedia,

Odpowiedzi:

264

Wypełnienie wyrównuje elementy struktury do „naturalnych” granic adresów - powiedzmy, intczłonkowie mieliby przesunięcia, które są mod(4) == 0na platformie 32-bitowej. Padding jest domyślnie włączony. Wstawia następujące „luki” do pierwszej struktury:

struct mystruct_A {
    char a;
    char gap_0[3]; /* inserted by compiler: for alignment of b */
    int b;
    char c;
    char gap_1[3]; /* -"-: for alignment of the whole struct in an array */
} x;

Z drugiej strony, pakowanie uniemożliwia kompilatorowi wypełnianie - należy tego wyraźnie zażądać - w GCC to __attribute__((__packed__)), więc:

struct __attribute__((__packed__)) mystruct_A {
    char a;
    int b;
    char c;
};

tworzy strukturę wielkości 6w architekturze 32-bitowej.

Uwaga: niezaangażowany dostęp do pamięci jest wolniejszy na architekturach, które na to pozwalają (jak x86 i amd64), i jest wyraźnie zabroniony na architekturach ścisłego wyrównania, takich jak SPARC.

Nikołaj Fetissow
źródło
2
Zastanawiam się: czy zakaz niezrównanej pamięci na iskrze oznacza, że ​​nie może poradzić sobie ze zwykłymi tablicami bajtów? Pakowanie struktur, o czym wiem, używane głównie w przesyłaniu (tj. Sieci) danych, gdy trzeba rzutować tablicę bajtów na strukturę i upewnić się, że tablica pasuje do pól struktury. Jeśli iskra nie może tego zrobić, to jak ci w ogóle pracują ?!
Cześć Anioł
14
Właśnie dlatego, jeśli spojrzysz na układy nagłówków IP, UDP i TCP, zobaczysz, że wszystkie pola liczb całkowitych są wyrównane.
Nikolai Fetissov
17
„Lost Art of C Structure Packing” wyjaśnia wypełnianie i pakowanie ptimizacji - catb.org/esr/structure-packing
Rob11311,
3
Czy pierwszy członek musi być pierwszy? Myślałem, że arragement jest całkowicie zależny od implementacji i nie można na nim polegać (nawet od wersji do wersji).
allyourcode
4
+ allyourcode Standard gwarantuje, że kolejność członków zostanie zachowana, a pierwszy członek rozpocznie od przesunięcia 0.
martinkunev
64

( Powyższe odpowiedzi wyjaśniły powód dość wyraźnie, ale nie wydają się całkowicie jasne co do wielkości wypełnienia, więc dodam odpowiedź zgodnie z tym, czego nauczyłem się z Zaginionej sztuki pakowania struktury , ewoluowała, aby nie ograniczać się do C, ale również zastosowanie Go, Rust. )


Wyrównanie pamięci (dla struct)

Zasady:

  • Przed każdym pojedynczym członkiem będzie padding, aby zaczął się od adresu, który można podzielić przez jego rozmiar.
    np. w systemie 64-bitowym, intpowinien zaczynać się pod adresem podzielnym przez 4, a longprzez 8 shortprzez 2.
  • chari char[]są wyjątkowe, mogą być dowolnym adresem pamięci, więc nie wymagają przed nimi wypełniania.
  • Ponieważ struct, poza potrzebą wyrównania dla każdego poszczególnego elementu, rozmiar całej struktury zostanie wyrównany do rozmiaru podzielnego przez rozmiar największego pojedynczego elementu, przez wypełnienie na końcu.
    np. jeśli największy członek struct jest longpodzielny przez 8, intnastępnie przez 4, shorta następnie przez 2.

Zamówienie członka:

  • Kolejność członków może wpływać na rzeczywisty rozmiar struktury, więc weź to pod uwagę. np. stu_ci stu_dz poniższego przykładu mają te same elementy, ale w innej kolejności i dają różne rozmiary dla 2 struktur.

Adres w pamięci (dla struct)

Zasady:

  • 64-bitowy system
    Adres strukturalny zaczyna się od (n * 16)bajtów. ( W poniższym przykładzie widać, że wszystkie wydrukowane adresy szesnastkowe struktur kończą się na 0. )
    Powód : możliwy największy pojedynczy element struktury ma 16 bajtów ( long double).
  • (Aktualizacja) Jeśli struktura zawiera tylkocharczłonka, jej adres może zaczynać się pod dowolnym adresem.

Puste miejsce :

  • Pusta przestrzeń między 2 strukturami może zostać wykorzystana przez zmienne niestrukturalne, które mogłyby się zmieścić.
    Np . test_struct_address()Poniżej, zmienna xznajduje się pomiędzy sąsiednimi strukturami gi h.
    Bez względu na xto, czy zostanie zadeklarowany, hadres się nie zmieni, xwystarczy ponownie wykorzystać puste miejsce, które gzmarnowało się.
    Podobna sprawa dla y.

Przykład

( dla systemu 64-bitowego )

memory_align.c :

/**
 * Memory align & padding - for struct.
 * compile: gcc memory_align.c
 * execute: ./a.out
 */ 
#include <stdio.h>

// size is 8, 4 + 1, then round to multiple of 4 (int's size),
struct stu_a {
    int i;
    char c;
};

// size is 16, 8 + 1, then round to multiple of 8 (long's size),
struct stu_b {
    long l;
    char c;
};

// size is 24, l need padding by 4 before it, then round to multiple of 8 (long's size),
struct stu_c {
    int i;
    long l;
    char c;
};

// size is 16, 8 + 4 + 1, then round to multiple of 8 (long's size),
struct stu_d {
    long l;
    int i;
    char c;
};

// size is 16, 8 + 4 + 1, then round to multiple of 8 (double's size),
struct stu_e {
    double d;
    int i;
    char c;
};

// size is 24, d need align to 8, then round to multiple of 8 (double's size),
struct stu_f {
    int i;
    double d;
    char c;
};

// size is 4,
struct stu_g {
    int i;
};

// size is 8,
struct stu_h {
    long l;
};

// test - padding within a single struct,
int test_struct_padding() {
    printf("%s: %ld\n", "stu_a", sizeof(struct stu_a));
    printf("%s: %ld\n", "stu_b", sizeof(struct stu_b));
    printf("%s: %ld\n", "stu_c", sizeof(struct stu_c));
    printf("%s: %ld\n", "stu_d", sizeof(struct stu_d));
    printf("%s: %ld\n", "stu_e", sizeof(struct stu_e));
    printf("%s: %ld\n", "stu_f", sizeof(struct stu_f));

    printf("%s: %ld\n", "stu_g", sizeof(struct stu_g));
    printf("%s: %ld\n", "stu_h", sizeof(struct stu_h));

    return 0;
}

// test - address of struct,
int test_struct_address() {
    printf("%s: %ld\n", "stu_g", sizeof(struct stu_g));
    printf("%s: %ld\n", "stu_h", sizeof(struct stu_h));
    printf("%s: %ld\n", "stu_f", sizeof(struct stu_f));

    struct stu_g g;
    struct stu_h h;
    struct stu_f f1;
    struct stu_f f2;
    int x = 1;
    long y = 1;

    printf("address of %s: %p\n", "g", &g);
    printf("address of %s: %p\n", "h", &h);
    printf("address of %s: %p\n", "f1", &f1);
    printf("address of %s: %p\n", "f2", &f2);
    printf("address of %s: %p\n", "x", &x);
    printf("address of %s: %p\n", "y", &y);

    // g is only 4 bytes itself, but distance to next struct is 16 bytes(on 64 bit system) or 8 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "g", "h", (long)(&h) - (long)(&g));

    // h is only 8 bytes itself, but distance to next struct is 16 bytes(on 64 bit system) or 8 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "h", "f1", (long)(&f1) - (long)(&h));

    // f1 is only 24 bytes itself, but distance to next struct is 32 bytes(on 64 bit system) or 24 bytes(on 32 bit system),
    printf("space between %s and %s: %ld\n", "f1", "f2", (long)(&f2) - (long)(&f1));

    // x is not a struct, and it reuse those empty space between struts, which exists due to padding, e.g between g & h,
    printf("space between %s and %s: %ld\n", "x", "f2", (long)(&x) - (long)(&f2));
    printf("space between %s and %s: %ld\n", "g", "x", (long)(&x) - (long)(&g));

    // y is not a struct, and it reuse those empty space between struts, which exists due to padding, e.g between h & f1,
    printf("space between %s and %s: %ld\n", "x", "y", (long)(&y) - (long)(&x));
    printf("space between %s and %s: %ld\n", "h", "y", (long)(&y) - (long)(&h));

    return 0;
}

int main(int argc, char * argv[]) {
    test_struct_padding();
    // test_struct_address();

    return 0;
}

Wynik wykonania - test_struct_padding():

stu_a: 8
stu_b: 16
stu_c: 24
stu_d: 16
stu_e: 16
stu_f: 24
stu_g: 4
stu_h: 8

Wynik wykonania - test_struct_address():

stu_g: 4
stu_h: 8
stu_f: 24
address of g: 0x7fffd63a95d0  // struct variable - address dividable by 16,
address of h: 0x7fffd63a95e0  // struct variable - address dividable by 16,
address of f1: 0x7fffd63a95f0 // struct variable - address dividable by 16,
address of f2: 0x7fffd63a9610 // struct variable - address dividable by 16,
address of x: 0x7fffd63a95dc  // non-struct variable - resides within the empty space between struct variable g & h.
address of y: 0x7fffd63a95e8  // non-struct variable - resides within the empty space between struct variable h & f1.
space between g and h: 16
space between h and f1: 16
space between f1 and f2: 32
space between x and f2: -52
space between g and x: 12
space between x and y: 12
space between h and y: 8

Zatem początek adresu dla każdej zmiennej to g: d0 x: dc h: e0 y: e8

wprowadź opis zdjęcia tutaj

Eric Wang
źródło
4
„Reguły” faktycznie były bardzo jasne, nigdzie nie mogłem znaleźć prostej reguły. Dzięki.
Pervez Alam
2
@PervezAlam Książka <The Lost Art of C Structure Packing>dość dobrze wyjaśnia zasady, nawet że jest trochę dłuższa niż ta odpowiedź. Książka jest dostępna bezpłatnie online: catb.org/esr/structure-packing
Eric Wang
Spróbuję, btw, czy ogranicza się to do pakowania struktur? Po prostu ciekawostki, bo podobało mi się wyjaśnienie w książce.
Pervez Alam
1
@PervezAlam Jest to bardzo krótka książka, skupiająca się głównie na technologii, która zmniejszyłaby ślad pamięci programu c, a czytanie zajmuje tylko kilka dni.
Eric Wang
1
@ValidusOculus Tak, oznacza 16 bajtów wyrównanych.
Eric Wang
44

Wiem, że to pytanie jest stare i większość odpowiedzi tutaj wyjaśnia padding naprawdę dobrze, ale starając się to zrozumieć, doszedłem do wniosku, że posiadam „wizualny” obraz tego, co się dzieje.

Procesor odczytuje pamięć w „kawałkach” o określonym rozmiarze (słowie). Powiedz, że słowo procesora ma 8 bajtów. Będzie patrzył na pamięć jako duży rząd 8 bajtów bloków konstrukcyjnych. Za każdym razem, gdy musi pobrać jakieś informacje z pamięci, dotrze do jednego z tych bloków i je zdobędzie.

Wyrównanie zmiennych

Jak wydaje się na powyższym obrazku, nie ma znaczenia, gdzie jest Char (1 bajt), ponieważ będzie on w jednym z tych bloków, wymagając od CPU przetworzenia tylko 1 słowa.

Kiedy mamy do czynienia z danymi większymi niż jeden bajt, takimi jak 4-bajtowy int lub 8-bajtowy podwójny, sposób, w jaki są one wyrównane w pamięci, wpływa na to, ile słów będzie musiało przetworzyć procesor. Jeśli 4-bajtowe fragmenty są wyrównane w taki sposób, że zawsze pasują do wnętrza bloku (adres pamięci jest wielokrotnością 4), tylko jedno słowo będzie musiało zostać przetworzone. W przeciwnym razie fragment 4 bajtów może mieć część siebie w jednym bloku, a część w innym, wymagając od procesora przetworzenia 2 słów w celu odczytania tych danych.

To samo odnosi się do 8-bajtowego podwójnego, z tym wyjątkiem, że musi on znajdować się w wielokrotności adresu pamięci 8, aby zagwarantować, że zawsze będzie znajdować się w bloku.

Dotyczy to 8-bajtowego edytora tekstu, ale ta koncepcja ma zastosowanie do innych rozmiarów słów.

Wypełnianie polega na wypełnianiu luk między tymi danymi, aby upewnić się, że są one wyrównane z tymi blokami, co poprawia wydajność podczas odczytu pamięci.

Jednak, jak stwierdzono w innych odpowiedziach, czasami przestrzeń ma większe znaczenie niż sama wydajność. Być może przetwarzasz dużo danych na komputerze, który nie ma dużo pamięci RAM (można by użyć przestrzeni wymiany, ale jest DUŻO wolniejszy). Możesz ustawiać zmienne w programie, dopóki nie zostanie wykonane najmniejsze wypełnienie (co zostało to bardzo dobrze zilustrowane w niektórych innych odpowiedziach), ale jeśli to nie wystarczy, możesz jawnie wyłączyć wypełnianie, co jest pakowaniem .

IanC
źródło
3
To nie wyjaśnia pakowania struktury, ale całkiem ładnie ilustruje wyrównanie słów CPU.
David Foerster,
Czy narysowałeś to farbą? :-)
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
1
@ CiroSantilli709 大 抓捕 六四 事件 法轮功, było na gimpie, ale myślę, że zaoszczędziłbym trochę czasu, robiąc to na farbie, chociaż haha
IanC
1
Jeszcze lepiej, odkąd open source (Y)
Ciro Santilli 法轮功 冠状 病 六四 事件 法轮功
21

Wypełnienie struktury eliminuje wyściółkę struktury, wypełnienie stosowane, gdy najważniejsze jest wyrównanie, pakowanie stosowane, gdy liczy się przestrzeń.

Niektóre kompilatory zapewniają #pragmatłumienie wypełniania lub spakowanie go do liczby bajtów. Niektóre zawierają w tym celu słowa kluczowe. Zasadniczo pragma, która służy do modyfikowania wypełnienia struktury, będzie miała następujący format (zależy od kompilatora):

#pragma pack(n)

Na przykład ARM zapewnia __packedsłowo kluczowe w celu powstrzymania wypełnienia struktury. Przejrzyj instrukcję kompilatora, aby dowiedzieć się więcej na ten temat.

Tak więc upakowana struktura jest strukturą bez wypełnienia.

Zostaną wykorzystane ogólnie upakowane struktury

  • aby zaoszczędzić miejsce

  • sformatować strukturę danych do transmisji przez sieć przy użyciu jakiegoś protokołu (oczywiście nie jest to dobra praktyka, ponieważ musisz
    poradzić sobie z endianowością)

użytkownik2083050
źródło
5

Wypełnienie i pakowanie to tylko dwa aspekty tego samego:

  • pakowanie lub wyrównanie to rozmiar, do którego zaokrąglany jest każdy element
  • dopełnienie to dodatkowe miejsce dodane w celu dopasowania do wyrównania

Przy mystruct_Azałożeniu domyślnego wyrównania 4, każdy element jest wyrównany do wielokrotności 4 bajtów. Ponieważ rozmiar charwynosi 1, dopełnienie dla ai cwynosi 4-1 = 3 bajty, podczas gdy wypełnienie nie jest wymagane, dla int bktórego jest już 4 bajty. Działa w ten sam sposób mystruct_B.

Casablanka
źródło
1

Pakowanie struktury odbywa się tylko wtedy, gdy wyraźnie powiesz swojemu kompilatorowi, aby spakował strukturę. Padding to, co widzisz. Twój 32-bitowy system dopełnia wyrównanie każdego pola do słowa. Gdybyś powiedział kompilatorowi, aby spakował struktury, miałyby one odpowiednio 6 i 5 bajtów. Nie rób tego jednak. Nie jest przenośny i powoduje, że kompilatory generują znacznie wolniejszy (a czasem nawet błędny) kod.

nmichaels
źródło
1

Nie ma w tym nic złego! Kto chce zrozumieć temat, musi wykonać następujące czynności,

  • Peruse The Lost Art of Structure Packing napisany przez Erica S. Raymonda
  • Rzuć okiem na przykład Erica
  • Na koniec, nie zapomnij o poniższej regule dotyczącej wypełniania, że struktura jest dopasowana do wymagań wyrównania największego typu.
snr
źródło
1

Zasady wypełniania:

  1. Każdy członek struktury powinien znajdować się pod adresem podzielnym według jego wielkości. Wypełnienie jest wstawiane między elementy lub na końcu struktury, aby upewnić się, że reguła jest spełniona. Odbywa się to w celu łatwiejszego i bardziej wydajnego dostępu do magistrali przez sprzęt.
  2. Uzupełnienie na końcu struktury jest ustalane na podstawie wielkości największego elementu struktury.

Dlaczego reguła 2: Zastanów się nad następującą strukturą,

Struktura 1

Jeśli mielibyśmy stworzyć tablicę (2 struktur) tej struktury, na końcu nie będzie wymagane wypełnianie:

Tablica Struct1

Dlatego rozmiar struct = 8 bajtów

Załóżmy, że mieliśmy stworzyć inną strukturę, jak poniżej:

Struktura 2

Gdybyśmy utworzyli tablicę tej struktury, istnieją 2 możliwości liczby bajtów wypełnienia wymaganych na końcu.

A. Jeśli dodamy 3 bajty na końcu i wyrównamy je dla int, a nie Long:

Tablica Struct2 wyrównana do int

B. Jeśli dodamy 7 bajtów na końcu i wyrównajmy do Długiej:

Tablica Struct2 wyrównana do Long

Adres początkowy drugiej tablicy jest wielokrotnością liczby 8 (tj. 24). Rozmiar struktury = 24 bajty

Dlatego poprzez wyrównanie adresu początkowego następnej tablicy struktury do wielokrotności największego elementu (tj. Jeśli mielibyśmy utworzyć tablicę tej struktury, pierwszy adres drugiej tablicy musi zaczynać się od adresu, który jest wielokrotnością największego członka struktury. Oto 24 (3 * 8)), możemy obliczyć liczbę bajtów dopełniania wymaganych na końcu.

AlphaGoku
źródło
-1

Wyrównanie struktury danych to sposób, w jaki dane są rozmieszczane i dostępne w pamięci komputera. Składa się z dwóch oddzielnych, ale powiązanych zagadnień: wyrównania danych i wypełnienia struktury danych . Gdy współczesny komputer odczytuje lub zapisuje adres pamięci, zrobi to w kawałkach wielkości słowa (np. 4 bajty w systemie 32-bitowym) lub większych. Wyrównanie danych oznacza umieszczenie danych pod adresem pamięci równym pewnej wielokrotności wielkości słowa, co zwiększa wydajność systemu ze względu na sposób, w jaki procesor obsługuje pamięć. Aby wyrównać dane, może być konieczne wstawienie niektórych bezsensownych bajtów między końcem ostatniej struktury danych a początkiem następnej, czyli wypełnianiem struktury danych.

  1. Aby wyrównać dane w pamięci, jeden lub więcej pustych bajtów (adresów) wstawia się (lub pozostawia pustych) między adresami pamięci, które są przydzielane innym członkom struktury podczas przydzielania pamięci. Ta koncepcja nazywa się wypełnieniem struktury.
  2. Architektura procesora komputerowego pozwala na odczyt 1 słowa (4 bajty w procesorze 32-bitowym) na raz.
  3. Aby wykorzystać tę zaletę procesora, dane są zawsze wyrównywane jako pakiet 4 bajtów, co prowadzi do wstawiania pustych adresów między adresami innych członków.
  4. Z powodu tej koncepcji wypełniania struktury w C, rozmiar struktury nie zawsze jest taki sam, jak myślimy.
manoj yadav
źródło
1
Dlaczego w swojej odpowiedzi potrzebujesz 5 razy link do tego samego artykułu ? Zachowaj tylko jeden link do przykładu. Ponieważ linkujesz do swojego artykułu, musisz ujawnić ten fakt.
Artjom B.,