Poravnanje strukture podataka

Poravnanje strukture podataka je način na koji se podaci uređuju i kojima se pristupa u memoriji računara. Sastoji se od dva odvojena, ali srodna pitanja: poravnanje podataka i postavljanje strukture podataka. Kada moderan računar čita iz ili piše na memorijsku adresu, on će to učiniti u reči veličine delova (npr. 4 dela bajta na 32-bitnom sistemu) ili veće. Usklađivanje podataka znači stavljanje podataka na memorijsku adresu što je jednako nekoj višestrukoj veličini teksta, što povećava performanse sistema zbog načina na koji procesor upravlja memorijom. Da bi se poravnali podaci, možda će biti potrebno da se ubace neki besmisleni bajtovi između kraja prethodne strukture podataka i početka sledeće, što je postavljanje strukture podataka.

Na primer, kada je veličina reči računara 4 bajta (bajt znači 8 bitova na većini mašina, ali može biti drugačiji na nekim sistemima), podaci koji treba da se čitaju bi trebalo da budu na memorijskoj adresi koja je neka višestruka od 4. Kada ovo nije slučaj, na primer, podaci počinju sa adrese 14, umesto 16, a zatim računar mora da pročita dva ili više 4 delova bajta i da učini neke obračune pre nego što zatraži pročitane podatke, ili može generisati grešku poravnanja. Iako je prethodna struktura podataka kraj na adresi 13, sledeća struktura podataka trebalo bi da počne sa adrese 16. Dva postavljena bajta se stavljaju između dve strukture podataka na adrese 14 i 15 kako bi poravnali sledeću strukturu podataka na adresi 16.

Iako je poravnanje strukture podataka fundamentalno pitanje za sve moderne računare, mnogi kompjuterski jezici i implementacije kompjuterskog jezika rukuju poravnanjem podataka automatski. Ada ,^[1]^[2] PL/I, određene C i C++ implementacije, D,^[3] i asembler dozvoljavaju najmanje delimičnu kontrolu nad postavljanjem strukture podataka, što može biti korisno u određenim specijalnim okolnostima.

Definicije

Za memorijsku adresu a, se kaže da je poravnana n-bajt kada je a deljivo sa n bajtova (gde je n stepena 2). U tom kontekstu bajt je najmanja jedinica pristupa memoriji, odnosno svaka memorijska adresa utvrđuje drugi bajt. Jedna n-bajt poravnana adresa bi imala log₂(n) najmanje značajane nula kada bi bila izražena u binarnom sistemu.

Alternativni tekst b-bita poravnat označava b/8 bajt poravnatu adresu (npr. 64-bitni usklađen je 8 bajtova poravnan).

Za pristup memoriji se kaže da je poravnata kada je podatak kome se pristupa n bajtova dug i podatak adrese je n -bajt poravnat. Kada pristup memoriji nije usklađen, onda se kaže da je neporavnata. Imajte na umu da su po definiciji pristupi bajt memorije uvek poravnati.

Memorijski pokazivač koji se odnosi na primitivne podatke je n bajtova dug i kaže se za njega da je poravnat ako je samo dozvoljeno da sadrži adrese koje su n-bajt poravnate, inače se kaže da je neporavnat. Memorijski pokazivač koji se odnosi na zbirne podatke (struktura podataka ili niz) je usklađen ako (i samo ako) je svaki primitivni podatak u zbiru poravnat.

Imajte na umu da gorenavedene definicije pretpostavljaju da je svaki primitivni podatak jačine dužine dva bajta. Kada ovo nije slučaj (kao sa 80-bita pomerajućim zarezom na x86) kontekst utiče na uslove gde se podatak smatra poravnatim ili ne.

Strukture podataka se mogu čuvati u memoriji na steku sa statičkom veličinom poznatom kao ograničenom ili na gomili sa dinamičkom veličinom poznatom kao neograničena.

Problemi

Računar pristupa memoriji jednom memorijskom reči u isto vreme. Dokle god je veličina reči memorije barem toliko velika kao najveći primitivni tip podataka podržan od strane računara, poravnati pristupi će uvek pristupiti jednoj memorijskoj reči. To ne mora biti tačno za neporavnate pristupe podataka.

Ako najviši i najniži bajtovi u podatku nisu u istoj memorijskoj reči računar mora podeliti pristup podatku u više pristupa memoriji. Ovo zahteva dosta složena strujna kola za generisanje pristupa memorije i koordinira ih. Da bi upravljali slučajem gde su memorijske reči u različitim memorijskim stranicama procesor mora ili da potvrdi da su obe strane prisutne pre izvršavanja instrukcije ili da bude u stanju da rukuje nedostajućim TLB-om ili greškom stranice na bilo kom pristupu memoriji tokom izvršavanja instrukcije.

Kada se jednoj memorijskoj reči pristupa operacija je atomska, odnosno cela memorijska reč se čita ili piše jednom i ostali uređaji moraju da čekaju dok se čitanje ili pisanje operacija završi pre nego što oni mogu da pristupe. To ne može biti tačno za neporavnate pristupe ka više memorijskih reči, na primer prva reč može biti pročitana od strane jednog uređaja, obe reči napisane od strane drugog uređaja, a zatim druga reč pročitana od strane prvog uređaja tako da je vrednost čitanja ili originalna vrednost, ili je ažurirana vrednost. Iako su takvi neuspesi retki, oni se mogu veoma teško identifikovati.

Arhitekture

RISC

Većina RISC procesora će generisati grešku poravnanja kada učitavanje ili skladištenje instrukcija pristupa neusklađenoj adresi. Ovo omogućava operativnom sistemu da oponaša neporavnati pristup korišćenjem drugih instrukcija. Na primer, poravnanje greške rukovodioca može da koristi učitavanje bajtova ili skladište (koji su uvek poravnati) da imitira veće učitavanje ili instrukciju skladišta.

Neke arhitekture kao MIPS imaju posebne insturkcije neporavnatog učitavanja i skladišta . Jedno neporavnato uputstvo učitavanja dobija bajtova sa memorijske reči sa najnižom adresom bajta, a drugo dobija bajtove sa memorijske reči sa najvećom adresom bajtova. Slično tome, instrukcije viših i nižih skladišta čuvaju odgovarajuće bajtove u višim i nižim memorijskim rečima.

Alfa arhitektura ima pristup dva koraka do neporavnatih učitavanja i skladišta. Prvi korak je da se učita gornja i donja memorija reči u zasebnim registrima. Drugi korak je da se ekstraktuju ili prepravljaju memorijske reči pomoću posebnih nižih / viših instrukcija sličnim na MIPS instrukcijama. Neporavnato skladište je završeno čuvanjem modifikovanih memorijskih reči nazad u memoriju. Razlog za ovu kompleksnost je ta da originalna Alfa arhitektura može samo da čita ili piše 32-bitne ili 64-bitne vrednosti. Ovo se pokazalo kao ozbiljno ograničenje koje često dovodi do izazivanja naduvenog koda i lošeg učinka. Da bi se adresiralo ovo ograničenje, proširenje nazvano Byte Word Extensions (BWX) je dodato u originalnu arhitekturu. Ono se sastojalo od instrukcija za bajt i za reči učitavanja i skladišta.

Zato što su ove instrukcije veće i sporije od normalnog opterećenja memorije i skladišta instrukcija, treba ih koristiti samo kada je to neophodno. Neki C i C++ kompajleri imaju "neporavnati" atribut koji se može primeniti na pokazivače kojima su potrebne neporavnate instrukcije.

x86

Dok x86 arhitektura prvobitno nije zahtevala usklađen pristup memoriji, i još uvek radi bez nje, SSE2 instrukcije na procesorima x86 ne zahtevaju podatke da budu 128-bitni (16 bajtova) poravnati, a tu mogu biti prednosti značajne performanse od korišćenja poravnatih podataka na ovim arhitekturama. Međutim, postoje i uputstva za neporavnati pristup kao što je MOVDQU. Osim toga, učitavanje i skladište operacija su uglavnom samo atomski kada su pravilno poravnati.

Kompatibilnost

Prednost za podršku neporavnatog pristupa je da je lakše pisati kompajlere da ne treba da usklade memoriju, na troškove sporijeg pristupa. Jedan od načina da se poveća učinak u RISC procesorima koji su dizajnirani kako bi se povećale sirove performanse je da zahteva podatke da se učitavaju ili sačuvaju na prirodnoj granici za podatke. Dakle, iako se memorija obično adresira sa 8-bitnim bajtovima, učitavanje 32-bitnog celog broja će biti u obavezi da se počne na svakih 32 bita na 32-bitnim mašinama, i učitavanjem 64-bitnog celog broja ili decimalnog broja će biti u obavezi da počne na svakih 64 bita na 64-bitnoj mašini. Procesor bi mogao da označi grešku ako je pitan da stavi broj koji nije bio na takvoj granici, ali to bi dovelo do sporijeg poziva na rutinu koja bi trebalo da shvati koja je reč ili reči sadržala podatke i ekstrakt ekvivalentne vrednosti.

Postava strukture podataka

Iako kompilator (ili interpretator) obično dodeljuju pojedinačne stavke podataka na poravnatim granicama, strukture podataka često imaju članove sa različitim zahtevima poravnanja. Za održavanje odgovarajućeg poravnanja prevodilac normalno ubacuje dodatne neimenovane članove podataka, tako da svaki član bude ispravno poravnat. Pored toga struktura podataka kao celina može da bude postavljena sa konačnim neimenovanim članom. Ovo omogućava svakom članu niza strukture da bude pravilno poravnat.

Postava je umetnuta samo kada je član strukture praćen članom sa većim uslovom poravnavanja ili na kraju strukture. Promenom redosleda članova u strukturi, moguće je promeniti količinu postave potrebne za održavanje poravnanja. Na primer, ako su članovi sortirani po zahtevima opadajućeg poravnanja minimalna količina postave je potrebna. Minimalan iznos postave potreban je uvek manji od najvećeg poravnanja u strukturi. Izračunavanje maksimalnog iznosa tražene postave je komplikovanije, ali je uvek manje od zbira kada se zahteva poravnanje za sve članove minus dva puta zbira zahteva poravnanja za najmanje usklađenu polovinu članova strukture.

Iako C i C++ ne dozvoljavaju kompajleru da preuredi članove strukture da bi uštedeo prostor, drugi jezici dozvoljavaju. Takođe je moguće da se kaže većini C i C++ kompajlera da "pakuju" članove strukture na određeni nivo usklađenosti, na primer, "pakovati (2)" znači da poravnava članove podataka veće od bajta u granice sa 2 bajta, tako da su bilo koji članovi postave najviše dužine jednog bajta.

Jedna upotreba za takve "pakovane" strukture je da sačuva memoriju. Na primer, struktura koja sadrži jedan bajt i četiri bajtova celog broja bi zahtevala tri dodatna bajta postave. Veliki niz takvih struktura bi koristio 37,5% manje memorije ako su pakovane, iako pristup svakoj strukturi može potrajati duže. Ovaj kompromis može se smatrati oblikom prostorno-vremenskog kompromisa.

Iako se korišćenje "pakovanih" struktura najčešće koristilo kako bi se sačuvao memorijski prostor, takođe se može koristiti za formatiranje strukture podataka za prenos korišćenjem standardnog protokola. Međutim, u ovoj upotrebi, mora se voditi računa da su vrednosti članova strukture skladišteni sa Big endian zahtevani od strane protokola (često red mreže bajta), koji može biti različit od Big endian korišćenja prirodno od strane mašine domaćina.

Postava u računarstvu

Sledeće formule daju broj postava bajtova potrebnih da se uskladi početak strukture podataka (gde je mod operator modula):

# псеудо-код, види стварни код испод
padding = (align - (offset mod align)) mod align
new offset = offset + padding = offset + (align - (offset mod align)) mod align

Na primer, potrebna postava koja treba da se doda offset 0x59d za strukturu usklađenu na svakih 4 bajta je 3. Struktura će početi u 0x5a0, koji je deljiv sa 4. Imajte na umu da kada je offset već deljiv sa align , drugi po modulu u (align - (offset mod align)) je mod align potreban da se dobija postava od 0.

Pošto je poravnanje po definiciji jačine dva, operacija modula može da se svede na bitove bulovske AND operacije. Sledeće formule obezbeđuju novi offset (gde je & bit AND i ~ bit NOT):

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

Tipično poravnanje S strukture na x86

Članovi strukture podataka se čuvaju u memoriji redom, tako da, u strukturi ispod, Data1 će uvek prethoditi Data2 ; i Data2 će uvek prethoditi Data3:

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

Ako se tip "short" čuva u dva bajta memorije onda svaki član strukture podataka prikazan iznad će biti 2 bajta poravnat. Data1 biće na offset 0, Data2 na offset 2, a Data3 na offset 4. Veličina ove strukture će biti 6 bajtova.

Tip svakog člana strukture obično ima podrazumevano poravnanje, što znači da će, osim ako nije drugačije zahtevano od strane programera, biti usklađen na prethodno utvrđene granice. Sledeća tipična poravnanja važe za kompilator iz Majkrosoft (Visual C++), Borland/CodeGear (C++Builder), Digital Mars (DMC), i GNU (GCC) prilikom sastavljanja za 32-bita x86:

char (jedan bajt) će biti 1-bajt poravnat.
short (dva bajta) će biti 2-bajta poravnat.
int (četiri bajta) će biti 4-bajta poravnat.
long (četiri bajta) će biti 4-bajta poravnat.
float (četiri bajta) će biti 4-bajta poravnat.
double (osam bajtova) će biti 8-bajtova poravnat na Windows-u i 4-bajta poravnat na Linux-u (8-bajtova sa duplom malignom opcijom sastavljanja vremena).
long long (osam bajtova) će biti 8-bajtova poravnat.
long double (deset bajtova sa C++Builder i DMC, osam bajtova sa Visual C++, dvanaest bajtova sa GCC) će biti 8-bajtova poravnat sa C++Builder, 2-bajta poravnat sa DMC, 8-bajtova poravnat sa Visual C++, i 4-bajta poravnat sa GCC.
pointer (četiri bajta) će biti 4-bajta poravnat. (npr.: char*, int*)

Jedine značajne razlike u usklađivanju jednog LP64 64-bitnog sistema u poređenju sa 32-bitnim sistemom su:

long (osam bajtova) će biti 8-bajtova poravnati.
double (osam bajtova) će biti 8-bajtova poravnati.
long double (osam bajtova sa Visual C++, šesnaest bajtova sa GCC) će biti 8-bajtova poravnati sa Visual C++ i 16-bajtova poravnati sa GCC.
pointer (osam bajtova) će biti 8-bajtova poravnati.

Neke vrste podataka zavise od implementacije.

Ovde je struktura sa članovima različitih tipova, u ukupnom iznosu od 8 bajtova pre kompilacije:

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

Nakon kompilacije struktura podataka će biti dopunjena postavom bajtova da bi se obezbedilo odgovarajuće usklađivanje za svaki od njegovih članova:

struct MixedData /* После компилације на 32-битној x86 машини */
{
    char Data1; /* 1 бајт */
    char Padding1[1]; /* 1 бајт за предстојећи 'short' да би био поравнат на границу од 2 бајта претпостављајући да је адреса где структура почиње паран број */
    short Data2; /* 2 бајта */
    int Data3;  /* 4 бајта - највећи члан структуре */
    char Data4; /* 1 бајт */ 
    char Padding2[3]; /* 3 бајта која треба да направе укупну величину структуре 12 бајтова */
};

Prevedena veličina objekta je sada 12 bajtova. Važno je napomenuti da je poslednji član ispunjen sa brojem bajtova potrebnih tako da ukupna veličina objekta treba da bude višestruko najveće usklađivanje bilo kog člana strukture (poravnanje (int), u ovom slučaju, koji = 4 na linux-32bit/gcc).

U ovom slučaju 3 bajta se dodaju do poslednjeg člana da postave strukturu veličine 12 bajtova (poravnanje (int) × 3).

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

U ovom primeru ukupna veličina strukture sizeof(FinalPad) = 8, a ne 5 (tako da je veličina deljiva sa 4 (usklađivanje sa float)).

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

U ovom primeru ukupna veličina strukture sizeof(FinalPadShort) = 6, a ne 5 (nije ni 8) (tako da je veličina deljiva sa 2 (usklađenost (short) = 2 na linux-32bit/gcc)).

Moguće je da promenite poravnanje struktura da se smanji memorija koja im je potrebna (ili da se povinuju postojećem formatu) od preraspodela članova strukture ili menjanja poravnanja kompajlera (ili "pakovanje") članova struktura.

struct MixedData /* након поновне наредбе */
{
    char Data1;
    char Data4;   /* поновна наредба*/
    short Data2;
    int Data3;
};

Prevedena veličina objekta sada odgovara prethodno prevedenoj veličini 8 bajtova. Imajte na umu da je Padding1[1] zamenjen (i na taj način eliminisan) od Data4 i Padding2[3] više nije potrebno jer je struktura već usklađena sa veličinom duge reči.

Alternativni način sprovođenja strukture MixedData da bude usklađena sa granicom od jednog bajta će izazvati pre procesora da odbaci predodređeno usklađivanje članova strukture i dakle nema postave bajtova koja će biti ubačena.

Iako ne postoji standardni način definisanja poravnanja članova strukture, neki kompajleri koriste #pragma direktive da preciziraju pakovanje u izvorne fajlove. Evo primera:

#pragma pack(push) /* пребацује тренутно поравнање на стек */
#pragma pack(1) /* поставља поравнање на границу 1 бајт */

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

#pragma pack(pop) /* враћа оригинално поравнање са стека */

Ova struktura će imati prevedenu veličinu 6 bajtova na 32-bitnom sistemu. Navedene direktive su dostupne u kompajlerima iz Majkrosofta[1], Borland-a, GNU-a [2] Arhivirano na sajtu Wayback Machine (11. novembar 2013), i mnogih drugih. Drugi primer:

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

Uobičajeno pakovanje i #pragma pakovanje

Na nekim Majkrosoft kompajlerima, posebno za RISC procesor, tu je neočekivan odnos između projekta podrazumevanog pakovanja (/Zp direktive) i direktive #pragma paketa. Direktiva #pragma pakovanje može da se koristi za smanjenje veličine pakovanja strukture iz projekta podrazumevanog pakovanja.^[4] To dovodi do problema interooperabilnosti sa zaglavlja biblioteke koje koriste, na primer, #pragma pack(8), ako je pakovanje projekta manje od ovoga. Iz tog razloga, postavljanje projekta pakovanja na bilo koju vrednost osim podrazumevane od 8 bajtova bi kršilo direktive #pragma pakovanja koja se koristi u zaglavlju biblioteke i doveli bi do binarnih nekompatibilnosti struktura. Ovo ograničenje nije prisutno prilikom sastavljanja za x86.

Dodela poravnanja memorije na keš linije

Bilo bi korisno da se dodeli poravnanje memorije na keš linije. Ako je niz podeljen na više od jedne niti da rade na njemu, imajući u podnizu granice neporavatog na keš linije što može dovesti do degradacije performansi. Evo primera gde se poravnava memorija (dvostruki niz veličine 10) usklađena sa kešom od 64 bajtova.

#include <stdlib.h>
double *foo(void) {
   double *var;//креира низ величине 10
   int     ok;

   ok = posix_memalign((void**)&var, 64, 10*sizeof(double));

   if(ok != 0)
     return NULL;

   return var;
}

Značaj hardvera za zahtev poravnanja

Zabrinutost poravnanja može da utiče na oblasti mnogo veće nego C strukture kada je svrha efikasno mapiranje tog područja kroz mehanizam hardverske translacije adrese (PCI prekrajanje, operacija MMU).

Na primer, na 32-bitnim operativnim sistemima, 4 KB strana nije samo proizvoljni 4 MB komad podataka. Umesto toga, to je obično region memorije koja je usklađena na 4 KB granici. To je zato što usklađivanje stranicu na granici stranice veličine omogućava hardveru kartu virtualne adrese na fizičku adresu zamenom viših bitova u adresi, pre nego da se uradi složena aritmetika.

Primer: Pretpostavimo da imamo TLB mapiranje virtuelne adrese 0x2cfc7000 na fizičku adresu 0x12345000. (Imajte na umu da su obe adrese poravnate na 4 KB granicama.) Pristup podacima koji se nalaze na virtuelnoj adresi va=0x2cfc7abc izaziva TLB rezoluciju 0x2cfc7 na 0x12345 da izda fizički pristup pa=0x12345abc. Ovde, 20/12-bitni split srećom odgovara heksadecimalnom prikazu splita u 5/3 cifara. Hardver može implementirati ovaj prevod jednostavnim kombinovanjem prvih 20 bita fizičke adrese (0x12345) i poslednjih 12 bita virtuelne adrese (0xabc). Ovo se takođe naziva gotovim indeksiranjem (abc) fizički označeno (12345).

Blok podataka veličine 2^(n+1)-1 uvek ima jedan pod-blok veličine 2^n poravnati na 2^n bajtova.

Ovo je kako dinamičan alokator koji nema znanje o poravnanju, može biti iskorišćen kako bi obezbedio poravnate ublaživače, na cenu faktora 2 u gubitku podataka.

Example: get a 12-bit aligned 4 KBytes buffer with malloc()

// непоравнати показивач на великом простору
void *up=malloc((1<<13)-1);
// добро поравнати показивач од 4 KB
void *ap=aligntonext(up,12);

where aligntonext() is meant as:
move p to the right until next well-aligned address if
not correct already. A possible implementation is

// ПСЕУДОКОД претпоставља uint32_t p, битова; за читљивост
// --- није безбедан тип, није сигурни споредни ефекат
#define alignto(p,bits) (p>>bits<<bits)
#define aligntonext(p,bits) alignto((p+(1<<bits)-1),bits)

Vidi još

Reference

^ "Ada Representation Clauses and Pragmas". Nedostaje ili je prazan parametar |title= (pomoć)
^ "F.8 Representation Clauses". Nedostaje ili je prazan parametar |title= (pomoć)
^ "Attributes - D Programming Language: Align Attribute".
^ "Working with Packing Structures".

Literatura

Bryant, Randal E.; David, O'Hallaron . Computer Systems: A Programmer's Perspective (2003 ed.). Upper Saddle River, NJ: Pearson Education. (2003) ISBN 978-0-13-034074-0

Spoljašnje veze

[1] "Ada Representation Clauses and Pragmas". Nedostaje ili je prazan parametar |title= (pomoć)

[2] "F.8 Representation Clauses". Nedostaje ili je prazan parametar |title= (pomoć)

[3] "Attributes - D Programming Language: Align Attribute".

[4] "Working with Packing Structures".

[1]

[2]

[3]

[4]