跳至內容

數據結構對齊

維基百科,自由的百科全書

數據結構對齊是程式編譯後資料在記憶體內的佈局與使用方式。包括三方面內容:數據對齊數據結構填充(padding)與包入(packing)。

現代計算機CPU一般是以32位元64位元大小作地址對齊,以32位元架構的計算機舉例,每次以連續的4位元組為一個區間,第一個位元組的位址位在每次CPU抓取資料大小的邊界上,除此之外,如果要訪問的變量沒有對齊,可能會觸發總線錯誤

當資料小於計算機的字(word)尺寸,可能把幾個資料放在一個字中,稱為包入(packing)。

許多編程語言自動處理數據結構對齊。Ada語言[1][2] PL/I,[3] Pascal,[4] 某些C語言C++實現, D語言,[5] Rust,[6]匯編語言允許特別控制對齊的方式。

定義

[編輯]

內存地址a被稱為n字節對齊an的倍數(n應是2的),也可以理解為當被訪問的數據長度為n 字節時,數據地址為n字節對齊。如果內存未對齊,稱作misaligned

內存指針是對齊的,如果它所指的數據是對齊的。指向聚合數據(aggregate data,如struct或數組)是對齊的,當且僅當它的每個組成數據是對齊的。

體系結構

[編輯]

RISC

[編輯]

大多數RISC處理器在加載或存儲指令訪問錯位的地址時,會產生一個對齊錯誤。這允許操作系統使用其他指令來模擬錯位的訪問。例如,對齊錯誤處理程序可以使用字節加載或存儲(其總是對齊的)來模擬更大的加載或存儲指令。

一些架構,如MIPS架構有特殊的無對齊加載和存儲指令。一條無對齊的加載指令從具有最低字節地址的內存字中獲取字節,另一條指令從具有最高字節地址的內存字中獲取字節。同樣的,store-high和store-low指令分別在較高和較低的內存字中存儲相應的字節。

DEC Alpha架構對不對齊的加載和存儲採用了兩步法。第一步是將上層和下層的內存字加載到獨立的寄存器中。第二步是使用類似於MIPS指令的特殊低/高指令來提取或修改內存字。通過將修改後的內存字存儲到內存中,就完成了一個無對齊存儲。造成這種複雜性的原因是,最初的Alpha架構只能讀取或寫入32位或64位的值。這被證明是一個嚴重的限制,經常導致代碼臃腫和性能不佳。為了解決這個限制,在最初的架構中加入了一個名為 "字節字擴展"(BXW)的擴展。它包括字節和字的加載和存儲指令。

因為這些指令比正常的內存加載和存儲指令更大、更慢,所以只有在必要時才可以使用它們。一些C和C++編譯器有一個 "無對齊 "屬性,可以應用於需要無對齊指令的指針。

x86

[編輯]

x86體系架構最初是不要求內存對齊。一些SSE2指令要求數據是128比特(16字節)對齊。有些CPU指令用於未對齊訪問如MOVDQU。讀寫內存操作僅在對齊時才是原子的。

C語言struct在x86上的對齊

[編輯]

C語言數據結構內的成員按照先後順序在內存中存儲。

默認對齊

[編輯]

結構體中每個成員的類型通常有一個默認的對齊方式,也就是說,除非程序員另有要求,否則它將在一個預先確定的邊界上對齊。以下典型的對齊方式對微軟Visual C++)、Borland/CodeGear英語CodeGearC++Builder)、Digital Mars英語Digital Mars(DMC)和GNUGCC)的編譯器在為32位x86編譯時有效。

一個char(一個字節)變量將被1字節對齊。

一個short(兩個字節)變量將是2字節對齊的。

一個int(四個字節)變量將是4字節對齊的。

一個long(四個字節)變量將被4字節對齊。

一個float(四個字節)變量將是4字節對齊的。

一個double(8個字節)變量在Windows上是8字節對齊的,在Linux上是4字節對齊的(用-malign-double編譯時選項是8字節)。

一個long long(8個字節)變量將被4字節對齊。

一個long double(C++Builder和DMC為10個字節,Visual C++為8個字節,GCC為12個字節)變量在C++Builder上將是8字節對齊,DMC為2字節對齊,Visual C++為8字節對齊,GCC為4字節對齊。

任何指針(四個字節)都將是4字節對齊的。(例如:char*, int*)

與32位系統相比,LP64 64位系統在對齊方面唯一值得注意的區別是。

一個long(八個字節)變量將是8字節對齊的。

一個double(8個字節)變量將是8字節對齊的。

一個long long(8個字節)變量將是8字節對齊的。

一個long double(在Visual C++中是8個字節,在GCC中是16個字節)變量在Visual C++中是8字節對齊的,在GCC中是16字節對齊的。

任何指針(八個字節)變量都將是8字節對齊的。

有些數據類型取決於實現方式。

指定對齊

[編輯]

一些編譯器(Microsoft,[7] Borland, GNU,[8]等等)使用#pragma directive指定對齊的包入(packing)。例如:

#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 */

這個結構在32位系統的大小為6字節。

缺省packing與#pragma pack

[編輯]

Microsoft編譯器的項目缺省packing(編譯選項/Zp)與#pragma pack指令。#pragma pack指令僅能減少packing尺寸。[9]

參見

[編輯]

參考文獻

[編輯]
  1. ^ Ada Representation Clauses and Pragmas. GNAT Reference Manual 7.4.0w documentation. [2015-08-30]. (原始內容存檔於2015-10-13). 
  2. ^ F.8 Representation Clauses. SPARCompiler Ada Programmer's Guide (PDF). [2015-08-30]. (原始內容存檔 (PDF)於2021-12-16). 
  3. ^ IBM System/360 Operating System PL/I Language Specifications (PDF). IBM. July 1966: 55–56 [2017-11-21]. C28-6571-3. (原始內容存檔 (PDF)於2019-05-29). 
  4. ^ Niklaus Wirth. The Programming Language Pascal (Revised Report) (PDF): 12. July 1973 [2017-11-21]. (原始內容 (PDF)存檔於2015-03-15). 
  5. ^ Attributes - D Programming Language: Align Attribute. [2012-04-13]. (原始內容存檔於2012-04-09). 
  6. ^ The Rustonomicon - Alternative Representations. [2016-06-19]. (原始內容存檔於2016-05-09). 
  7. ^ pack. [2017-11-21]. (原始內容存檔於2017-03-28). 
  8. ^ 6.58.8 Structure-Packing Pragmas. [2017-11-21]. (原始內容存檔於2017-01-08). 
  9. ^ Working with Packing Structures. MSDN Library. Microsoft. 2007-07-09 [2011-01-11]. (原始內容存檔於2012-10-18). 

外部連結

[編輯]