Veri yapısı hizalaması - Data structure alignment

Veri yapısı hizalaması , verilerin bilgisayar belleğinde düzenlenme ve erişilme şeklidir . Üç ayrı fakat birbiriyle ilişkili konudan oluşur: veri hizalama , veri yapısı doldurma ve paketleme .

İşlemci , modern bilgisayar donanım gerçekleştirir okur ve veri zaman en verimli belleğe yazar doğal hizalanmış , verilerin bellek adres veri boyutunun katı olduğunu olan, genel olarak bir araç. Örneğin, 32 bitlik bir mimaride, veriler ardışık dört baytta saklanıyorsa ve ilk bayt 4 baytlık bir sınırda bulunuyorsa, veriler hizalanabilir.

Veri hizalama , öğelerin doğal hizalamalarına göre hizalanmasıdır. Doğal hizalamayı sağlamak için yapı elemanları arasına veya bir yapının son elemanından sonra bir miktar dolgu eklemek gerekebilir . Örneğin, 32 bitlik bir makinede, 32 bitlik bir değerin ardından 16 bitlik bir değer içeren bir veri yapısı , 32 bitlik değeri hizalamak için 16 bitlik değer ile 32 bitlik değer arasında 16 bitlik dolguya sahip olabilir. 32 bitlik bir sınırdaki değer. Alternatif olarak, daha yavaş erişime yol açabilecek, ancak dörtte üçü daha fazla bellek kullanan dolgu atlanarak yapı paketlenebilir .

Veri yapısı hizalaması tüm modern bilgisayarlar için temel bir sorun olmasına rağmen, birçok bilgisayar dili ve bilgisayar dili uygulaması veri hizalamasını otomatik olarak gerçekleştirir. Fortran , Ada , PL/I , Pascal , belirli C ve C++ uygulamaları, D , Rust , C# ve montaj dili , bazı özel durumlarda faydalı olabilecek veri yapısı dolgusunun en azından kısmi kontrolüne izin verir.

Tanımlar

Bir bellek adresi bir olduğu söylenir , n bayt hizalanmış olduğunda , bir katı olan , n bayt (burada n, 2 'lik bir gücü). Bu bağlamda bayt, bellek erişiminin en küçük birimidir, yani her bellek adresi farklı bir baytı belirtir. Bir n- -byte hizalanmış adres minimum olurdu günlük 2 (n) olarak ifade edildiğinde en önemsiz sıfır ikili .

Alternatif b-bit hizalı ifade , b/8 bayt hizalı bir adresi belirtir (örn. 64-bit hizalı 8 bayt hizalıdır).

Bir bellek erişimi olduğu söylenen hizalanmış accedere edilmekte olan N  kadar bayt ve referans noktası adresi olan N -byte hizalanır. Bir bellek erişimi hizalanmadığında, yanlış hizalanmış olduğu söylenir . Tanım olarak bayt bellek erişimlerinin her zaman hizalı olduğunu unutmayın.

İlkelin veriler belirtmektedir bir bellek işaretçisi , n  uzun olduğu söylenen bayt hizalanmış sadece adreslerine içermesine izin verildiği takdirde , n -byte hizalanır, aksi takdirde olduğu söylenir hizalanmamış . Bir veri kümesine (bir veri yapısı veya dizi) başvuran bir bellek işaretçisi, kümedeki her ilkel veri hizalanırsa (ve yalnızca) hizalanır.

Yukarıdaki tanımların, her ilkel verinin iki bayt uzunluğunda bir güç olduğunu varsaydığına dikkat edin. Bu (80 bitlik kayan nokta ile durumda değil ise x 86 ) içerik veri hizalanmış ya da kabul edilir koşulları etkilemektedir.

Veri yapıları, sınırlı olarak bilinen statik bir boyuta sahip yığında veya sınırsız olarak bilinen dinamik bir boyuta sahip yığın üzerinde bellekte saklanabilir .

sorunlar

CPU, belleğe bir seferde tek bir bellek sözcüğü ile erişir . Bellek sözcük boyutu en az bilgisayar tarafından desteklenen en büyük ilkel veri türü kadar büyük olduğu sürece , hizalanmış erişimler her zaman tek bir bellek sözcüğüne erişecektir. Bu, yanlış hizalanmış veri erişimleri için doğru olmayabilir.

Bir verideki en yüksek ve en düşük bayt aynı bellek sözcüğü içinde değilse, bilgisayar veri erişimini birden çok bellek erişimine bölmelidir. Bu, bellek erişimlerini oluşturmak ve bunları koordine etmek için çok sayıda karmaşık devre gerektirir. Bellek sözcüklerinin farklı bellek sayfalarında olduğu durumu ele almak için işlemci, talimatı yürütmeden önce her iki sayfanın da mevcut olduğunu doğrulamalı veya talimatın yürütülmesi sırasında herhangi bir bellek erişiminde bir TLB eksikliğini veya bir sayfa hatasını işleyebilmelidir .

Bazı işlemci tasarımları kasıtlı olarak bu tür karmaşıklığı ortaya çıkarmaktan kaçınır ve bunun yerine yanlış hizalanmış bellek erişimi durumunda alternatif davranış sağlar. Örneğin, ARMv6 ISA'dan önceki ARM mimarisi uygulamaları, tüm çok baytlı yükleme ve depolama talimatları için zorunlu hizalanmış bellek erişimi gerektirir. Hangi özel talimatın verildiğine bağlı olarak, yanlış hizalanmış erişim girişiminin sonucu, kusurlu adresin en önemsiz bitlerini aşağı yuvarlayarak hizalı bir erişime dönüştürmek (bazen ek uyarılarla) veya bir MMU istisnası atmak (MMU donanımı ise) olabilir. mevcut) veya sessizce potansiyel olarak öngörülemeyen diğer sonuçları vermek için. ARMv6 ve sonraki mimariler, her durumda olmasa da birçok durumda hizalanmamış erişimi destekler.

Tek bir bellek sözcüğüne erişildiğinde işlem atomiktir, yani tüm bellek sözcüğü bir kerede okunur veya yazılır ve diğer aygıtlar buna erişmeden önce okuma veya yazma işleminin tamamlanmasını beklemelidir. Bu, birden fazla bellek kelimesine hizalanmamış erişimler için doğru olmayabilir, örneğin ilk kelime bir cihaz tarafından okunabilir, her iki kelime başka bir cihaz tarafından yazılabilir ve ardından ikinci kelime ilk cihaz tarafından okunabilir, böylece okunan değer ne orijinal değer olur ne de güncellenmiş değer. Bu tür arızalar nadir olmakla birlikte, tespit edilmesi çok zor olabilir.

Veri yapısı dolgusu

Derleyici (veya yorumlayıcı ) normalde tek tek veri öğelerini hizalanmış sınırlara tahsis etse de , veri yapıları genellikle farklı hizalama gereksinimlerine sahip üyelere sahiptir. Düzgün hizalamayı sağlamak için çevirmen normalde ek adsız veri üyeleri ekler, böylece her üye uygun şekilde hizalanır. Ek olarak, bir bütün olarak veri yapısı, son bir isimsiz üye ile doldurulabilir. Bu, bir dizi yapının her bir üyesinin uygun şekilde hizalanmasını sağlar.

Dolgu, yalnızca bir yapı elemanını daha büyük hizalama gereksinimi olan bir eleman tarafından takip edildiğinde veya yapının sonunda eklenir . Bir yapıdaki elemanların sırasını değiştirerek, hizalamayı sürdürmek için gereken dolgu miktarını değiştirmek mümkündür. Örneğin, üyeler azalan hizalama gereksinimlerine göre sıralanırsa, minimum miktarda dolgu gereklidir. Gereken minimum dolgu miktarı her zaman yapıdaki en büyük hizalamadan daha azdır. Gerekli maksimum dolgu miktarının hesaplanması daha karmaşıktır, ancak her zaman tüm elemanlar için hizalama gereksinimlerinin toplamından yapı elemanlarının en az hizalanmış yarısı için hizalama gereksinimlerinin toplamının iki katından daha azdır.

C ve C++, derleyicinin alan kazanmak için yapı üyelerini yeniden düzenlemesine izin vermese de, diğer diller olabilir. Çoğu C ve C++ derleyicisine, bir yapının üyelerini belirli bir hizalama düzeyine "paketlemesini" söylemek de mümkündür, örneğin "pack(2)", bir bayttan büyük veri üyelerini iki baytlık bir sınıra hizalamak anlamına gelir. herhangi bir dolgu elemanı en fazla bir bayt uzunluğundadır. Benzer şekilde, PL/I'de , UNALIGNEDbit dizileri dışında tüm dolguyu ortadan kaldırmak için bir yapı bildirilebilir .

Bu tür "paketlenmiş" yapılar için bir kullanım, belleği korumaktır. Örneğin, tek bir bayt ve dört baytlık bir tamsayı içeren bir yapı, üç ek bayt dolgu gerektirir. Bu tür yapıların büyük bir dizisi, paketlenirlerse %37,5 daha az bellek kullanır, ancak her bir yapıya erişim daha uzun sürebilir. Bu uzlaşma, bir tür uzay-zaman değiş tokuşu olarak düşünülebilir .

"Paketlenmiş" yapıların kullanımı en sık bellek alanını korumak için kullanılsa da, standart bir protokol kullanılarak iletim için bir veri yapısını biçimlendirmek için de kullanılabilir. Bununla birlikte, bu kullanımda, yapı üyelerinin değerlerinin , ana makine tarafından yerel olarak kullanılan endianlıktan farklı olabilen protokolün gerektirdiği endianness (genellikle ağ bayt sırası ) ile saklanmasına da özen gösterilmelidir .

bilgi işlem dolgusu

Aşağıdaki formüller, bir veri yapısının başlangıcını hizalamak için gereken doldurma baytlarının sayısını sağlar (burada mod , modulo operatörüdür): 

padding = (align - (offset mod align)) mod align
aligned = offset + padding
        = offset + ((align - (offset mod align)) mod align)

Örneğin, 4 baytlık hizalanmış bir yapı için ofset 0x59d'ye eklenecek dolgu 3'tür. Bu durumda yapı, 4'ün katı olan 0x5a0'dan başlar. Ancak, öteleme hizalaması zaten hizalama hizalamasına eşit olduğunda , (align - (ofset mod align)) mod align içindeki ikinci modulo sıfıra dönecek, bu nedenle orijinal değer değişmeden bırakılacaktır.

Hizalama tanımı gereği ikinin gücü olduğundan, modulo işlemi bitsel bir boole AND işlemine indirgenebilir.

Aşağıdaki formüller (burada ofset hizalı üretmek ve a, lojik AND ve ~ bir bit-bazında değil ): 

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

x86'da C yapılarının tipik hizalaması

Veri yapısı üyeleri, aşağıdaki yapıda, Veri1 üyesi her zaman Veri2'den önce gelecek şekilde bellekte sıralı olarak depolanır; ve Data2 her zaman Data3'ten önce gelir: 

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

"Kısa" tipi iki baytlık bellekte saklanırsa, yukarıda gösterilen veri yapısının her bir üyesi 2 bayt hizalı olacaktır. Veri1 ofset 0'da, Data2 ofset 2'de ve Data3 ofset 4'te olacaktır. Bu yapının boyutu 6 bayt olacaktır.

Yapının her bir üyesinin türü genellikle varsayılan bir hizalamaya sahiptir, yani programcı tarafından aksi talep edilmediği sürece önceden belirlenmiş bir sınırda hizalanacaktır. Aşağıdaki tipik hizalamalar, 32 bit x86 için derlerken Microsoft ( Visual C++ ), Borland / CodeGear ( C++Builder ), Digital Mars (DMC) ve GNU ( GCC ) derleyicileri için geçerlidir:

  • Bir karakter (bir bayt) 1 bayt hizalı olacaktır.
  • Bir kısa (iki bayt) 2 bayt hizalı olacaktır.
  • Bir int (dört bayt) 4 bayt hizalı olacaktır.
  • Bir uzun (dört bayt) 4 baytlık hizalı olacaktır.
  • Bir kayan nokta (dört bayt) 4 bayt hizalı olacaktır.
  • Bir çift (sekiz bayt), Windows'ta 8 bayt ve Linux'ta 4 bayt ( -malign-double derleme zamanı seçeneğiyle 8 bayt) hizalanır .
  • Bir çok uzun (sekiz bayt) 4 baytlık hizalı olacaktır.
  • Bir uzun çift (C ++ Builder ve DMC, Visual C ++, GCC ile on iki bayt ile sekiz bayt on bayt) C ++ Builder, DMC ile hizalanmış 2 bayt ile hizalanmış 8 baytlık olacaktır, 8 bayt Görsel ile hizalanmış C++ ve GCC ile uyumlu 4 bayt.
  • Herhangi bir işaretçi (dört bayt) 4 bayt hizalı olacaktır. (örneğin: karakter*, int*)

32 bit sistemle karşılaştırıldığında LP64 64 bit sistem için hizalamadaki tek dikkate değer farklar şunlardır:

  • Bir uzun (sekiz bayt) 8 bayt hizalı olacaktır.
  • Bir çift (sekiz bayt) 8 bayt hizalı olacaktır.
  • Bir çok uzun (sekiz bayt) 8 bayt hizalı olacaktır.
  • Bir uzun çift (Visual C ++ ile sekiz bayt, GCC ile on altı bayt) Visual C ++ ve GCC ile hizalanmış 16-bayt ile hizalanmış 8 bayt olur.
  • Herhangi bir işaretçi (sekiz bayt) 8 bayt hizalı olacaktır.

Bazı veri türleri uygulamaya bağlıdır.

Derlemeden önce toplam 8 bayt olan çeşitli türlerde üyelere sahip bir yapı : 

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

Derlemeden sonra, veri yapısı, üyelerinin her biri için uygun bir hizalama sağlamak için dolgu baytlarıyla desteklenecektir: 

struct MixedData  /* After compilation in 32-bit x86 machine */
{
    char Data1; /* 1 byte */
    char Padding1[1]; /* 1 byte for the following 'short' to be aligned on a 2 byte boundary
assuming that the address where structure begins is an even number */
    short Data2; /* 2 bytes */
    int Data3;  /* 4 bytes - largest structure member */
    char Data4; /* 1 byte */
    char Padding2[3]; /* 3 bytes to make total size of the structure 12 bytes */
};

Yapının derlenmiş boyutu artık 12 bayttır. Yapının toplam boyutunun herhangi bir yapı üyesinin en büyük hizalamasının bir katı olması için son üyenin gerekli bayt sayısıyla doldurulduğunu not etmek önemlidir (bu durumda hizalama(int), bu durumda = 4'tür). linux-32bit/gcc).

Bu durumda, yapıyı 12 bayt boyutunda doldurmak için son üyeye 3 bayt eklenir (alignment(int) × 3). 

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

Bu örnekte sizeof yapısının toplam boyutu (FinalPad) == 8 , 5 değil (böylece boyut 4'ün katıdır (şamandıra hizalaması)). 

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

Bu örnekte sizeof yapısının toplam boyutu (FinalPadShort) == 6 , 5 değil (8 de değil) (böylece boyut 2'nin katıdır (linux-32bit/gcc'de hizalama(kısa) = 2)).

Yapı elemanlarını yeniden sıralayarak veya derleyicinin yapı elemanlarının hizalamasını (veya "paketleme") değiştirerek, ihtiyaç duydukları belleği azaltmak (veya mevcut bir formata uymak) için yapıların hizalamasını değiştirmek mümkündür. 

struct MixedData  /* after reordering */
{
    char Data1;
    char Data4;   /* reordered */
    short Data2;
    int Data3;
};

Yapının derlenmiş boyutu şimdi önceden derlenmiş 8 bayt boyutuyla eşleşiyor . Bu Not Padding1 [1] ile ikame (ve bu şekilde yok) olan Data4 ve Padding2 [3] bir yapı zaten uzun kelime büyüklüğü hizalanmış olarak artık gerekli değildir.

MixedData yapısının bir bayt sınırına hizalanmasını zorlamanın alternatif yöntemi , ön işlemcinin yapı elemanlarının önceden belirlenmiş hizalamasını atmasına neden olacak ve böylece hiçbir dolgu baytı eklenmeyecektir.

Yapı üyelerinin hizalamasını tanımlamanın standart bir yolu olmasa da, bazı derleyiciler kaynak dosyaların içindeki paketlemeyi belirtmek için #pragma yönergelerini kullanır. İşte bir örnek: 

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

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

#pragma pack(pop)   /* restore original alignment from stack */

Bu yapı, 32 bitlik bir sistemde derlenmiş 6 baytlık bir boyuta sahip olacaktır . Yukarıdaki yönergeler Microsoft , Borland , GNU ve diğer birçok derleyicide mevcuttur .

Başka bir örnek: 

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

Varsayılan paketleme ve #pragma paketi

Bazı Microsoft derleyicilerinde, özellikle RISC işlemcileri için, proje varsayılan paketlemesi (/Zp yönergesi) ile #pragma paketi yönergesi arasında beklenmeyen bir ilişki vardır . # Pragma paketi yönergesi sadece kullanılabilir azaltmak proje varsayılan ambalajı bir yapının ambalaj boyutu. Bu , proje paketi bundan daha küçükse, örneğin #pragma pack(8) kullanan kitaplık başlıklarıyla birlikte çalışabilirlik sorunlarına yol açar . Bu nedenle, proje paketlemesinin varsayılan 8 bayt dışında herhangi bir değere ayarlanması, kitaplık başlıklarında kullanılan #pragma paketi yönergelerini bozar ve yapılar arasında ikili uyumsuzluklara neden olur. Bu sınırlama, x86 için derlenirken mevcut değildir.

Önbellek satırlarına hizalanmış bellek ayırma

Önbellek satırlarına hizalanmış bellek ayırmak faydalı olacaktır . Bir dizi üzerinde çalışması için birden fazla iş parçacığı için bölümlenmişse, alt dizi sınırlarının önbellek satırlarına hizalanmamış olması performansın düşmesine neden olabilir. 64 baytlık önbelleğe hizalanmış bellek (10 boyutlu çift dizi) tahsis etmek için bir örnek. 

#include <stdlib.h>
double *foo(void) {
   double *var;//create array of size 10
   int     ok;

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

   if (ok != 0)
     return NULL;

   return var;
}

Hizalama gereksinimlerinin donanımsal önemi

Amaç, bir donanım adresi çeviri mekanizması (PCI yeniden eşleme, bir MMU'nun çalışması ) aracılığıyla bu alanın verimli bir şekilde eşlenmesi olduğunda, hizalama endişeleri bir C yapısından çok daha büyük alanları etkileyebilir .

Örneğin, 32 bitlik bir işletim sisteminde 4  KiB (4096 Bayt) bir sayfa yalnızca rastgele 4 KiB'lik bir veri yığını değildir. Bunun yerine, genellikle 4 KiB sınırında hizalanmış bir bellek bölgesidir. Bunun nedeni, bir sayfayı sayfa boyutunda bir sınırda hizalamanın, donanımın karmaşık aritmetik yapmak yerine adresteki daha yüksek bitleri değiştirerek sanal bir adresi fiziksel bir adresle eşleştirmesine izin vermesidir.

Örnek: 0x2CFC7000 sanal adresinin 0x12345000 fiziksel adresine bir TLB eşlememiz olduğunu varsayalım. (Bu iki adresin de 4 KiB sınırında hizalanmış olduğuna dikkat edin.) va=0x2CFC7ABC sanal adresinde bulunan verilere erişim, pa=0x12345ABC'ye fiziksel bir erişim sağlamak için 0x2CFC7 ila 0x12345 TLB çözünürlüğüne neden olur. Burada, 20/12 bitlik bölme, neyse ki 5/3 basamaklı onaltılık gösterimle eşleşir. Donanım, fiziksel adresin (0x12345) ilk 20 bitini ve sanal adresin son 12 bitini (0xABC) birleştirerek bu çeviriyi uygulayabilir. Bu aynı zamanda sanal olarak indekslenmiş (ABC) fiziksel olarak etiketlenmiş (12345) olarak da adlandırılır.

2 (n+1) - 1 boyutundaki bir veri bloğunun her zaman  2 n  bayt üzerinde hizalanmış 2 n boyutunda bir alt bloğu vardır .

Bu, hizalama bilgisi olmayan dinamik bir ayırıcının, alan kaybında iki faktör fiyatına hizalanmış arabellekler sağlamak için nasıl kullanılabileceğidir. 

// Example: get 4096 bytes aligned on a 4096 byte buffer with malloc()

// unaligned pointer to large area
void *up = malloc((1 << 13) - 1);
// well-aligned pointer to 4 KiB
void *ap = aligntonext(up, 12);

aligntonext (burada p , r ) Daha sonra temizleme, hizalanmış artış eklenerek çalışır r en önemsiz bit p . Olası bir uygulama 

// Assume `uint32_t p, bits;` for readability
#define alignto(p, bits)      (((p) >> bits) << bits)
#define aligntonext(p, bits)  alignto(((p) + (1 << bits) - 1), bits)

Notlar

Referanslar

daha fazla okuma

  • Bryant, Randal E. ; David, O'Hallaron (2003). Bilgisayar Sistemleri: Bir Programcının Perspektifi (2003 ed.). Upper Saddle River, New Jersey, ABD: Pearson Education . ISBN'si 0-13-034074-X.
  • "1. Giriş: Segment Hizalama". 8086 Family Utilities - 8080/8085-Based Development Systems için Kullanıcı Kılavuzu (PDF) . Revizyon E (A620/5821 6K DD ed.). Santa Clara, California, ABD: Intel Corporation . Mayıs 1982 [1980, 1978]. s. 1-6, 3-5. Sipariş Numarası: 9800639-04. 2020-02-29 tarihinde orijinalinden arşivlendi (PDF) . 2020-02-29 alındı . […] Bir segment, beş hizalama özelliğinden birine (ve sayfa içi özniteliği durumunda iki) sahip olabilir: […] Bayt, bir segmentin herhangi bir adreste bulunabileceği anlamına gelir. […] Bir segment anlamına gelen Word, 0H adresinden başlayarak yalnızca ikinin katı olan bir adreste bulunabilir. [...] Paragraf, bir segmentin yalnızca 16'nın katı olan bir adreste bulunabileceği anlamına gelir, adres 0'dan başlar. [...] Sayfa, yani bir segmentin yalnızca 256'nın katı olan bir adreste bulunabileceği anlamına gelir. , adres 0'dan başlayarak […] […] Inpage, yani bir segment önceki niteliklerden hangisine uygulanıyorsa orada bulunabilir, artı bir sayfa sınırını geçmeyecek şekilde yerleştirilmelidir […] Hizalama kodları şunlardır: […] B - bayt […] W - kelime […] G - paragraf […] xR - sayfa içi […] P - sayfa […] A - mutlak […] sayfa içi hizalama kodundaki x herhangi bir başka hizalama kodu olabilir. […] bir segment, sayfa içi özniteliğine sahip olabilir, yani 256 baytlık bir sayfada yer almalıdır ve kelime özniteliğine sahip olabilir, yani çift numaralı bir baytta yer almalıdır. […]

Dış bağlantılar