Поравнање структуре података

Поравнање структуре података је начин на који се подаци уређују и којима се приступа у меморији рачунара. Састоји се од два одвојена, али сродна питања: поравнање података и постављање структуре података. Када модеран рачунар чита из или пише на меморијску адресу, он ће то учинити у речи величине делова (нпр. 4 дела бајта на 32-битном систему) или веће. Усклађивање података значи стављање података на меморијску адресу што је једнако некој вишеструкој величини текста, што повећава перформансе система због начина на који процесор управља меморијом. Да би се поравнали подаци, можда ће бити потребно да се убаце неки бесмислени бајтови између краја претходне структуре података и почетка следеће, што је постављање структуре података.

На пример, када је величина речи рачунара 4 бајта (бајт значи 8 битова на већини машина, али може бити другачији на неким системима), подаци који треба да се читају би требало да буду на меморијској адреси која је нека вишеструка од 4. Када ово није случај, на пример, подаци почињу са адресе 14, уместо 16, а затим рачунар мора да прочита два или више 4 делова бајта и да учини неке обрачуне пре него што затражи прочитане податке, или може генерисати грешку поравнања. Иако је претходна структура података крај на адреси 13, следећа структура података требало би да почне са адресе 16. Два постављена бајта се стављају између две структуре података на адресе 14 и 15 како би поравнали следећу структуру података на адреси 16.

Иако је поравнање структуре података фундаментално питање за све модерне рачунаре, многи компјутерски језици и имплементације компјутерског језика рукују поравнањем података аутоматски. Ада ,^[1]^[2] PL/I, одређене C и C++ имплементације, D,^[3] и асемблер дозвољавају најмање делимичну контролу над постављањем структуре података, што може бити корисно у одређеним специјалним околностима.

Дефиниције

За меморијску адресу а, се каже да је поравнана n-бајт када је а дељиво са n бајтова (где је n степена 2). У том контексту бајт је најмања јединица приступа меморији, односно свака меморијска адреса утврђује други бајт. Једна n-бајт поравнана адреса би имала log₂(n) најмање значајане нула када би била изражена у бинарном систему.

Алтернативни текст b-бита поравнат означава b/8 бајт поравнату адресу (нпр. 64-битни усклађен је 8 бајтова поравнан).

За приступ меморији се каже да је поравната када је податак коме се приступа n бајтова дуг и податак адресе је n -бајт поравнат. Када приступ меморији није усклађен, онда се каже да је непоравната. Имајте на уму да су по дефиницији приступи бајт меморије увек поравнати.

Меморијски показивач који се односи на примитивне податке је n бајтова дуг и каже се за њега да је поравнат ако је само дозвољено да садржи адресе које су n-бајт поравнате, иначе се каже да је непоравнат. Меморијски показивач који се односи на збирне податке (структура података или низ) је усклађен ако (и само ако) је сваки примитивни податак у збиру поравнат.

Имајте на уму да горенаведене дефиниције претпостављају да је сваки примитивни податак јачине дужине два бајта. Када ово није случај (као са 80-бита померајућим зарезом на x86) контекст утиче на услове где се податак сматра поравнатим или не.

Структуре података се могу чувати у меморији на стеку са статичком величином познатом као ограниченом или на гомили са динамичком величином познатом као неограничена.

Проблеми

Рачунар приступа меморији једном меморијском речи у исто време. Докле год је величина речи меморије барем толико велика као највећи примитивни тип података подржан од стране рачунара, поравнати приступи ће увек приступити једној меморијској речи. То не мора бити тачно за непоравнате приступе података.

Ако највиши и најнижи бајтови у податку нису у истој меморијској речи рачунар мора поделити приступ податку у више приступа меморији. Ово захтева доста сложена струјна кола за генерисање приступа меморије и координира их. Да би управљали случајем где су меморијске речи у различитим меморијским страницама процесор мора или да потврди да су обе стране присутне пре извршавања инструкције или да буде у стању да рукује недостајућим TLB-ом или грешком странице на било ком приступу меморији током извршавања инструкције.

Када се једној меморијској речи приступа операција је атомска, односно цела меморијска реч се чита или пише једном и остали уређаји морају да чекају док се читање или писање операција заврши пре него што они могу да приступе. То не може бити тачно за непоравнате приступе ка више меморијских речи, на пример прва реч може бити прочитана од стране једног уређаја, обе речи написане од стране другог уређаја, а затим друга реч прочитана од стране првог уређаја тако да је вредност читања или оригинална вредност, или је ажурирана вредност. Иако су такви неуспеси ретки, они се могу веома тешко идентификовати.

Архитектуре

RISC

Већина RISC процесора ће генерисати грешку поравнања када учитавање или складиштење инструкција приступа неусклађеној адреси. Ово омогућава оперативном систему да опонаша непоравнати приступ коришћењем других инструкција. На пример, поравнање грешке руководиоца може да користи учитавање бајтова или складиште (који су увек поравнати) да имитира веће учитавање или инструкцију складишта.

Неке архитектуре као MIPS имају посебне инстуркције непоравнатог учитавања и складишта . Једно непоравнато упутство учитавања добија бајтова са меморијске речи са најнижом адресом бајта, а друго добија бајтове са меморијске речи са највећом адресом бајтова. Слично томе, инструкције виших и нижих складишта чувају одговарајуће бајтове у вишим и нижим меморијским речима.

Алфа архитектура има приступ два корака до непоравнатих учитавања и складишта. Први корак је да се учита горња и доња меморија речи у засебним регистрима. Други корак је да се екстрактују или преправљају меморијске речи помоћу посебних нижих / виших инструкција сличним на MIPS инструкцијама. Непоравнато складиште је завршено чувањем модификованих меморијских речи назад у меморију. Разлог за ову комплексност је та да оригинална Алфа архитектура може само да чита или пише 32-битне или 64-битне вредности. Ово се показало као озбиљно ограничење које често доводи до изазивања надувеног кода и лошег учинка. Да би се адресирало ово ограничење, проширење названо Byte Word Extensions (BWX) је додато у оригиналну архитектуру. Оно се састојало од инструкција за бајт и за речи учитавања и складишта.

Зато што су ове инструкције веће и спорије од нормалног оптерећења меморије и складишта инструкција, треба их користити само када је то неопходно. Неки C и C++ компајлери имају "непоравнати" атрибут који се може применити на показиваче којима су потребне непоравнате инструкције.

x86

Док x86 архитектура првобитно није захтевала усклађен приступ меморији, и још увек ради без ње, SSE2 инструкције на процесорима x86 не захтевају податке да буду 128-битни (16 бајтова) поравнати, а ту могу бити предности значајне перформансе од коришћења поравнатих података на овим архитектурама. Међутим, постоје и упутства за непоравнати приступ као што је MOVDQU. Осим тога, учитавање и складиште операција су углавном само атомски када су правилно поравнати.

Компатибилност

Предност за подршку непоравнатог приступа је да је лакше писати компајлере да не треба да ускладе меморију, на трошкове споријег приступа. Један од начина да се повећа учинак у RISC процесорима који су дизајнирани како би се повећале сирове перформансе је да захтева податке да се учитавају или сачувају на природној граници за податке. Дакле, иако се меморија обично адресира са 8-битним бајтовима, учитавање 32-битног целог броја ће бити у обавези да се почне на сваких 32 бита на 32-битним машинама, и учитавањем 64-битног целог броја или децималног броја ће бити у обавези да почне на сваких 64 бита на 64-битној машини. Процесор би могао да означи грешку ако је питан да стави број који није био на таквој граници, али то би довело до споријег позива на рутину која би требало да схвати која је реч или речи садржала податке и екстракт еквивалентне вредности.

Постава структуре података

Иако компилатор (или интерпретатор) обично додељују појединачне ставке података на поравнатим границама, структуре података често имају чланове са различитим захтевима поравнања. За одржавање одговарајућег поравнања преводилац нормално убацује додатне неименоване чланове података, тако да сваки члан буде исправно поравнат. Поред тога структура података као целина може да буде постављена са коначним неименованим чланом. Ово омогућава сваком члану низа структуре да буде правилно поравнат.

Постава је уметнута само када је члан структуре праћен чланом са већим условом поравнавања или на крају структуре. Променом редоследа чланова у структури, могуће је променити количину поставе потребне за одржавање поравнања. На пример, ако су чланови сортирани по захтевима опадајућег поравнања минимална количина поставе је потребна. Минималан износ поставе потребан је увек мањи од највећег поравнања у структури. Израчунавање максималног износа тражене поставе је компликованије, али је увек мање од збира када се захтева поравнање за све чланове минус два пута збира захтева поравнања за најмање усклађену половину чланова структуре.

Иако C и C++ не дозвољавају компајлеру да преуреди чланове структуре да би уштедео простор, други језици дозвољавају. Такође је могуће да се каже већини C и C++ компајлера да "пакују" чланове структуре на одређени ниво усклађености, на пример, "паковати (2)" значи да поравнава чланове података веће од бајта у границе са 2 бајта, тако да су било који чланови поставе највише дужине једног бајта.

Једна употреба за такве "паковане" структуре је да сачува меморију. На пример, структура која садржи један бајт и четири бајтова целог броја би захтевала три додатна бајта поставе. Велики низ таквих структура би користио 37,5% мање меморије ако су паковане, иако приступ свакој структури може потрајати дуже. Овај компромис може се сматрати обликом просторно-временског компромиса.

Иако се коришћење "пакованих" структура најчешће користило како би се сачувао меморијски простор, такође се може користити за форматирање структуре података за пренос коришћењем стандардног протокола. Међутим, у овој употреби, мора се водити рачуна да су вредности чланова структуре складиштени са Big endian захтевани од стране протокола (често ред мреже бајта), који може бити различит од Big endian коришћења природно од стране машине домаћина.

Постава у рачунарству

Следеће формуле дају број постава бајтова потребних да се усклади почетак структуре података (где је mod оператор модула):

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

На пример, потребна постава која треба да се дода offset 0x59d за структуру усклађену на сваких 4 бајта је 3. Структура ће почети у 0x5a0, који је дељив са 4. Имајте на уму да када је offset већ дељив са align , други по модулу у (align - (offset mod align)) је mod align потребан да се добија постава од 0.

Пошто је поравнање по дефиницији јачине два, операција модула може да се сведе на битове буловске AND операције. Следеће формуле обезбеђују нови offset (где је & бит AND и ~ бит NOT):

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

Типично поравнање С структуре на x86

Чланови структуре података се чувају у меморији редом, тако да, у структури испод, Data1 ће увек претходити Data2 ; и Data2 ће увек претходити Дата3:

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

Ако се тип "short" чува у два бајта меморије онда сваки члан структуре података приказан изнад ће бити 2 бајта поравнат. Data1 биће на offset 0, Data2 на offset 2, а Data3 на offset 4. Величина ове структуре ће бити 6 бајтова.

Тип сваког члана структуре обично има подразумевано поравнање, што значи да ће, осим ако није другачије захтевано од стране програмера, бити усклађен на претходно утврђене границе. Следећа типична поравнања важе за компилатор из Мајкрософт (Visual C++), Borland/CodeGear (C++Builder), Digital Mars (DMC), и GNU (GCC) приликом састављања за 32-бита x86:

char (један бајт) ће бити 1-бајт поравнат.
short (два бајта) ће бити 2-бајта поравнат.
int (четири бајта) ће бити 4-бајта поравнат.
long (четири бајта) ће бити 4-бајта поравнат.
float (четири бајта) ће бити 4-бајта поравнат.
double (осам бајтова) ће бити 8-бајтова поравнат на Windows-у и 4-бајта поравнат на Linux-у (8-бајтова са дуплом малигном опцијом састављања времена).
long long (осам бајтова) ће бити 8-бајтова поравнат.
long double (десет бајтова са C++Builder и DMC, осам бајтова са Visual C++, дванаест бајтова са GCC) ће бити 8-бајтова поравнат са C++Builder, 2-бајта поравнат са DMC, 8-бајтова поравнат са Visual C++, и 4-бајта поравнат са GCC.
pointer (четири бајта) ће бити 4-бајта поравнат. (нпр.: char*, int*)

Једине значајне разлике у усклађивању једног LP64 64-битног система у поређењу са 32-битним системом су:

long (осам бајтова) ће бити 8-бајтова поравнати.
double (осам бајтова) ће бити 8-бајтова поравнати.
long double (осам бајтова са Visual C++, шеснаест бајтова са GCC) ће бити 8-бајтова поравнати са Visual C++ и 16-бајтова поравнати са GCC.
pointer (осам бајтова) ће бити 8-бајтова поравнати.

Неке врсте података зависе од имплементације.

Овде је структура са члановима различитих типова, у укупном износу од 8 бајтова пре компилације:

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

Након компилације структура података ће бити допуњена поставом бајтова да би се обезбедило одговарајуће усклађивање за сваки од његових чланова:

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 бајтова */
};

Преведена величина објекта је сада 12 бајтова. Важно је напоменути да је последњи члан испуњен са бројем бајтова потребних тако да укупна величина објекта треба да буде вишеструко највеће усклађивање било ког члана структуре (поравнање (int), у овом случају, који = 4 на linux-32bit/gcc).

У овом случају 3 бајта се додају до последњег члана да поставе структуру величине 12 бајтова (поравнање (int) × 3).

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

У овом примеру укупна величина структуре sizeof(FinalPad) = 8, а не 5 (тако да је величина дељива са 4 (усклађивање са float)).

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

У овом примеру укупна величина структуре sizeof(FinalPadShort) = 6, а не 5 (није ни 8) (тако да је величина дељива са 2 (усклађеност (short) = 2 на linux-32bit/gcc)).

Могуће је да промените поравнање структура да се смањи меморија која им је потребна (или да се повинују постојећем формату) од прерасподела чланова структуре или мењања поравнања компајлера (или "паковање") чланова структура.

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

Преведена величина објекта сада одговара претходно преведеној величини 8 бајтова. Имајте на уму да је Padding1[1] замењен (и на тај начин елиминисан) од Data4 и Padding2[3] више није потребно јер је структура већ усклађена са величином дуге речи.

Алтернативни начин спровођења структуре MixedData да буде усклађена са границом од једног бајта ће изазвати пре процесора да одбаци предодређено усклађивање чланова структуре и дакле нема поставе бајтова која ће бити убачена.

Иако не постоји стандардни начин дефинисања поравнања чланова структуре, неки компајлери користе #pragma директиве да прецизирају паковање у изворне фајлове. Ево примера:

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

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

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

Ова структура ће имати преведену величину 6 бајтова на 32-битном систему. Наведене директиве су доступне у компајлерима из Мајкрософта[1], Borland-a, GNU-a [2] Архивирано на сајту Wayback Machine (11. новембар 2013), и многих других. Други пример:

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

Уобичајено паковање и #pragma паковање

На неким Мајкрософт компајлерима, посебно за RISC процесор, ту је неочекиван однос између пројекта подразумеваног паковања (/Zp директиве) и директиве #прагма пакета. Директива #pragma паковање може да се користи за смањење величине паковања структуре из пројекта подразумеваног паковања.^[4] То доводи до проблема интерооперабилности са заглавља библиотеке које користе, на пример, #pragma pack(8), ако је паковање пројекта мање од овога. Из тог разлога, постављање пројекта паковања на било коју вредност осим подразумеване од 8 бајтова би кршило директиве #pragma паковања која се користи у заглављу библиотеке и довели би до бинарних некомпатибилности структура. Ово ограничење није присутно приликом састављања за x86.

Додела поравнања меморије на кеш линије

Било би корисно да се додели поравнање меморије на кеш линије. Ако је низ подељен на више од једне нити да раде на њему, имајући у поднизу границе непораватог на кеш линије што може довести до деградације перформанси. Ево примера где се поравнава меморија (двоструки низ величине 10) усклађена са кешом од 64 бајтова.

#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;
}

Значај хардвера за захтев поравнања

Забринутост поравнања може да утиче на области много веће него C структуре када је сврха ефикасно мапирање тог подручја кроз механизам хардверске транслације адресе (PCI прекрајање, операција MMU).

На пример, на 32-битним оперативним системима, 4 KB страна није само произвољни 4 MB комад података. Уместо тога, то је обично регион меморије која је усклађена на 4 КБ граници. То је зато што усклађивање страницу на граници странице величине омогућава хардверу карту виртуалне адресе на физичку адресу заменом виших битова у адреси, пре него да се уради сложена аритметика.

Пример: Претпоставимо да имамо TLB мапирање виртуелне адресе 0x2cfc7000 на физичку адресу 0x12345000. (Имајте на уму да су обе адресе поравнате на 4 КБ границама.) Приступ подацима који се налазе на виртуелној адреси va=0x2cfc7abc изазива TLB резолуцију 0x2cfc7 на 0x12345 да изда физички приступ pa=0x12345abc. Овде, 20/12-битни сплит срећом одговара хексадецималном приказу сплита у 5/3 цифара. Хардвер може имплементирати овај превод једноставним комбиновањем првих 20 бита физичке адресе (0x12345) и последњих 12 бита виртуелне адресе (0xabc). Ово се такође назива готовим индексирањем (abc) физички означено (12345).

Блок података величине 2^(n+1)-1 увек има један под-блок величине 2^n поравнати на 2^n бајтова.

Ово је како динамичан алокатор који нема знање о поравнању, може бити искоришћен како би обезбедио поравнате ублаживаче, на цену фактора 2 у губитку података.

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)

Види још

Референце

^ "Ada Representation Clauses and Pragmas". Недостаје или је празан параметар |title= (помоћ)
^ "F.8 Representation Clauses". Недостаје или је празан параметар |title= (помоћ)
^ "Attributes - D Programming Language: Align Attribute".
^ "Working with Packing Structures".

Литература

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

Спољашње везе

[1] "Ada Representation Clauses and Pragmas". Недостаје или је празан параметар |title= (помоћ)

[2] "F.8 Representation Clauses". Недостаје или је празан параметар |title= (помоћ)

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

[4] "Working with Packing Structures".

[1]

[2]

[3]

[4]