Căn chỉnh cấu trúc dữ liệu – Wikipedia

Posted on by lordneo

Căn chỉnh cấu trúc dữ liệu đề cập đến cách sắp xếp và truy cập dữ liệu trong bộ nhớ máy tính. Nó bao gồm ba vấn đề riêng biệt nhưng có liên quan: sắp xếp dữ liệu đệm cấu trúc dữ liệu và đóng gói .

CPU trong phần cứng máy tính hiện đại thực hiện đọc và ghi vào bộ nhớ một cách hiệu quả nhất khi dữ liệu được căn chỉnh tự nhiên điều đó có nghĩa là địa chỉ dữ liệu là bội số của kích thước dữ liệu. Căn chỉnh dữ liệu đề cập đến việc sắp xếp các yếu tố theo sự liên kết tự nhiên của chúng. Để đảm bảo căn chỉnh tự nhiên, có thể cần phải chèn một số phần đệm giữa các phần tử cấu trúc hoặc sau phần tử cuối cùng của cấu trúc.

Mặc dù căn chỉnh cấu trúc dữ liệu là vấn đề cơ bản cho tất cả các máy tính hiện đại, nhiều ngôn ngữ máy tính và triển khai ngôn ngữ máy tính tự động xử lý căn chỉnh dữ liệu. Ada, [1][2] PL / I, [3] Pascal, [4] một số triển khai C và C ++ nhất định, D, [5] Rust, [6] và ngôn ngữ lắp ráp cho phép kiểm soát ít nhất một phần đệm cấu trúc dữ liệu, có thể hữu ích trong một số trường hợp đặc biệt

Định nghĩa [ chỉnh sửa ]

Một địa chỉ bộ nhớ a được gọi là n-byte được căn chỉnh khi ] là bội số của n byte (trong đó n là lũy thừa của 2). Trong ngữ cảnh này, một byte là đơn vị truy cập bộ nhớ nhỏ nhất, tức là mỗi địa chỉ bộ nhớ chỉ định một byte khác nhau. Một địa chỉ được căn chỉnh n sẽ có tối thiểu log 2 (n) các số 0 có ý nghĩa nhỏ nhất khi được biểu thị ở dạng nhị phân.

Từ ngữ thay thế b-bit được căn chỉnh chỉ định một địa chỉ b / 8 byte được căn chỉnh (ví dụ: căn chỉnh 64 bit là 8 byte được căn chỉnh).

Một truy cập bộ nhớ được gọi là được căn chỉnh khi dữ liệu được truy cập là n byte dài và địa chỉ dữ liệu là n -byte được căn chỉnh. Khi quyền truy cập bộ nhớ không được căn chỉnh, nó được gọi là bị điều chỉnh sai . Lưu ý rằng theo định nghĩa truy cập bộ nhớ byte luôn được căn chỉnh.

Một con trỏ bộ nhớ đề cập đến dữ liệu nguyên thủy là n byte dài được cho là được căn chỉnh nếu nó chỉ được phép chứa các địa chỉ là n -bạn liên kết, nếu không, nó được gọi là không được phân bổ . Một con trỏ bộ nhớ tham chiếu tổng hợp dữ liệu (cấu trúc dữ liệu hoặc mảng) là được căn chỉnh nếu (và chỉ khi) mỗi mốc dữ liệu nguyên thủy trong tổng hợp được căn chỉnh.

Lưu ý rằng các định nghĩa ở trên giả định rằng mỗi mốc thời gian nguyên thủy là một sức mạnh dài hai byte. Khi đây không phải là trường hợp (như với dấu phẩy động 80 bit trên x86), bối cảnh ảnh hưởng đến các điều kiện trong đó mốc được coi là căn chỉnh hay không.

Các cấu trúc dữ liệu có thể được lưu trữ trong bộ nhớ trên ngăn xếp với kích thước tĩnh được gọi là giới hạn hoặc trên heap với kích thước động được gọi là không giới hạn .

Các sự cố [ chỉnh sửa ]

Một máy tính truy cập bộ nhớ bằng một từ bộ nhớ duy nhất tại một thời điểm. Miễn là kích thước từ bộ nhớ ít nhất bằng loại dữ liệu nguyên thủy lớn nhất được máy tính hỗ trợ, các truy cập được căn chỉnh sẽ luôn truy cập vào một từ bộ nhớ. Điều này có thể không đúng đối với truy cập dữ liệu sai.

Nếu các byte cao nhất và thấp nhất trong một mốc thời gian không nằm trong cùng một từ bộ nhớ, máy tính phải phân chia quyền truy cập dữ liệu thành nhiều truy cập bộ nhớ. Điều này đòi hỏi rất nhiều mạch phức tạp để tạo ra các truy cập bộ nhớ và phối hợp chúng. Để xử lý trường hợp các từ bộ nhớ nằm trong các trang bộ nhớ khác nhau, bộ xử lý phải xác minh rằng cả hai trang đều có mặt trước khi thực hiện lệnh hoặc có thể xử lý lỗi TLB hoặc lỗi trang trên mọi truy cập bộ nhớ trong khi thực hiện lệnh.

Khi một từ bộ nhớ duy nhất được truy cập hoạt động là nguyên tử, tức là toàn bộ từ bộ nhớ được đọc hoặc ghi cùng một lúc và các thiết bị khác phải đợi cho đến khi hoạt động đọc hoặc ghi hoàn thành trước khi chúng có thể truy cập. Điều này có thể không đúng đối với các truy cập không được phân bổ vào nhiều từ bộ nhớ, ví dụ: từ đầu tiên có thể được đọc bởi một thiết bị, cả hai từ được viết bởi thiết bị khác và sau đó từ thứ hai được đọc bởi thiết bị đầu tiên để giá trị đọc không phải là giá trị gốc cũng không phải là giá trị cập nhật. Mặc dù những thất bại như vậy là rất hiếm, nhưng chúng có thể rất khó xác định.

Phần đệm cấu trúc dữ liệu [ chỉnh sửa ]

Mặc dù trình biên dịch (hoặc trình thông dịch) thường phân bổ các mục dữ liệu riêng lẻ trên các ranh giới được căn chỉnh, cấu trúc dữ liệu thường có các thành viên với các yêu cầu căn chỉnh khác nhau. Để duy trì căn chỉnh phù hợp, người dịch thường chèn thêm các thành viên dữ liệu chưa được đặt tên để mỗi thành viên được căn chỉnh chính xác. Ngoài ra, cấu trúc dữ liệu nói chung có thể được đệm với một thành viên chưa được đặt tên cuối cùng. Điều này cho phép mỗi thành viên của một mảng các cấu trúc được căn chỉnh chính xác.

Đệm chỉ được chèn khi thành viên cấu trúc được theo sau bởi thành viên có yêu cầu căn chỉnh lớn hơn hoặc ở cuối cấu trúc. Bằng cách thay đổi thứ tự của các thành viên trong một cấu trúc, có thể thay đổi số lượng phần đệm cần thiết để duy trì sự liên kết. Ví dụ: nếu các thành viên được sắp xếp theo yêu cầu căn chỉnh giảm dần thì sẽ cần một lượng đệm tối thiểu. Số lượng tối thiểu của phần đệm cần thiết luôn nhỏ hơn mức căn chỉnh lớn nhất trong cấu trúc. Việc tính toán số lượng đệm tối đa cần thiết phức tạp hơn, nhưng luôn nhỏ hơn tổng yêu cầu căn chỉnh cho tất cả các thành viên trừ hai lần tổng yêu cầu căn chỉnh cho một nửa số thành viên cấu trúc được căn chỉnh ít nhất.

Mặc dù C và C ++ không cho phép trình biên dịch sắp xếp lại các thành viên cấu trúc để tiết kiệm không gian, các ngôn ngữ khác có thể. Cũng có thể yêu cầu hầu hết các trình biên dịch C và C ++ "đóng gói" các thành viên của cấu trúc theo một mức độ căn chỉnh nhất định, ví dụ: "Pack (2)" có nghĩa là sắp xếp các thành viên dữ liệu lớn hơn một byte thành ranh giới hai byte để bất kỳ thành viên đệm nào dài tối đa một byte.

Một cách sử dụng cho các cấu trúc "đóng gói" như vậy là để bảo tồn bộ nhớ. Ví dụ, một cấu trúc chứa một byte đơn và một số nguyên bốn byte sẽ yêu cầu thêm ba byte đệm. Một mảng lớn các cấu trúc như vậy sẽ sử dụng bộ nhớ ít hơn 37,5% nếu chúng được đóng gói, mặc dù việc truy cập từng cấu trúc có thể mất nhiều thời gian hơn. Sự thỏa hiệp này có thể được coi là một hình thức đánh đổi thời gian của Space.

Mặc dù việc sử dụng các cấu trúc "đóng gói" được sử dụng thường xuyên nhất để tiết kiệm dung lượng bộ nhớ, nó cũng có thể được sử dụng để định dạng cấu trúc dữ liệu để truyền bằng giao thức chuẩn. Tuy nhiên, trong cách sử dụng này, cũng cần chú ý để đảm bảo rằng các giá trị của các thành viên cấu trúc được lưu trữ với độ bền theo yêu cầu của giao thức (thường là thứ tự byte mạng), có thể khác với độ bền được sử dụng bởi máy chủ.

Đệm máy tính [ chỉnh sửa ]

Các công thức sau đây cung cấp số lượng byte đệm cần thiết để căn chỉnh bắt đầu cấu trúc dữ liệu (trong đó mod là modulo nhà điều hành): 

 padding = (align - (offset mod align)) mod align căn chỉnh = offset + đệm         = offset + ((align - (offset mod align)) mod align)

Ví dụ: phần đệm để thêm vào bù 0x59d cho cấu trúc căn chỉnh 4 byte là 3. Cấu trúc sau đó sẽ bắt đầu ở 0x5a0, là bội số của 4. Tuy nhiên, khi căn chỉnh của bù ] đã bằng với align modulo thứ hai trong (align – (offset mod align)) mod align sẽ trả về 0, do đó giá trị ban đầu được giữ nguyên.

Vì định nghĩa theo định nghĩa là lũy thừa của hai, nên phép toán modulo có thể được giảm xuống thành phép toán Boolean bit bit.

Các công thức sau đây tạo ra phần bù được căn chỉnh (trong đó & là một bit VÀ VÀ ~ một chút KHÔNG): 

 padding = (align - (offset & (align - 1))) & (align - 1)         = (-offset & (căn chỉnh - 1)) căn chỉnh = (offset + (căn chỉnh - 1)) & ~ (căn chỉnh - 1)         = (offset + (căn chỉnh - 1)) & -ign

Căn chỉnh điển hình của các cấu trúc C trên x86 [ chỉnh sửa ]

Các thành viên cấu trúc dữ liệu được lưu trữ tuần tự trong bộ nhớ để trong cấu trúc bên dưới, thành viên Data1 sẽ luôn đi trước Data2; và Data2 sẽ luôn đi trước Data3: 

 struct   MyData   {      ngắn   Dữ liệu1 ;       ngắn   Data2 ;       ngắn   ]};

Nếu loại "ngắn" được lưu trữ trong hai byte bộ nhớ thì mỗi thành viên của cấu trúc dữ liệu được mô tả ở trên sẽ được căn chỉnh 2 byte. Data1 sẽ ở offset 0, Data2 ở offset 2 và Data3 ở offset 4. Kích thước của cấu trúc này sẽ là 6 byte.

Loại của mỗi thành viên trong cấu trúc thường có căn chỉnh mặc định, nghĩa là nó sẽ, trừ khi được lập trình viên yêu cầu, được căn chỉnh trên một ranh giới được xác định trước. Các sắp xếp điển hình sau đây hợp lệ cho các trình biên dịch từ Microsoft (Visual C ++), Borland / CodeGear (C ++ Builder), Digital Mars (DMC) và GNU (GCC) khi biên dịch cho 32-bit x86:

  • Một char (một byte) sẽ được căn chỉnh 1 byte.
  • Một ngắn (hai byte) sẽ được căn chỉnh 2 byte.
  • Một ] int (bốn byte) sẽ được căn chỉnh 4 byte.
  • Một dài (bốn byte) sẽ được căn chỉnh 4 byte.
  • A float ( bốn byte) sẽ được căn chỉnh 4 byte.
  • Một nhân đôi (tám byte) sẽ được căn chỉnh 8 byte trên Windows và căn chỉnh 4 byte trên Linux (8 byte với -double tùy chọn biên dịch thời gian).
  • Một dài (tám byte) sẽ được căn chỉnh 4 byte.
  • Một dài gấp đôi (mười byte với C ++ Builder và DMC, tám byte với Visual C ++, mười hai byte với GCC) sẽ được liên kết 8 byte với C ++ Builder, 2 byte được liên kết với DMC, 8 byte được liên kết với Visual C ++ và 4 byte được căn chỉnh với GCC.
  • Bất kỳ con trỏ (bốn byte) sẽ được căn chỉnh 4 byte. (ví dụ: char *, int *)

Sự khác biệt đáng chú ý duy nhất trong việc căn chỉnh cho hệ thống LP64 64 bit khi so sánh với hệ thống 32 bit là:

  • Một dài (tám byte) sẽ được căn chỉnh 8 byte.
  • Một gấp đôi (tám byte) sẽ được căn chỉnh 8 byte.
  • A dài (tám byte) sẽ được căn chỉnh 8 byte.
  • Một dài gấp đôi (tám byte với Visual C ++, mười sáu byte với GCC) sẽ được liên kết 8 byte với Visual C ++ và 16 byte được căn chỉnh với GCC.
  • Bất kỳ con trỏ (tám byte) sẽ được căn chỉnh 8 byte.

Một số loại dữ liệu phụ thuộc vào việc triển khai.

Đây là một cấu trúc với các thành viên thuộc nhiều loại khác nhau, tổng cộng 8 byte trước khi biên dịch: 

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

Sau khi biên dịch, cấu trúc dữ liệu sẽ được bổ sung các byte đệm để đảm bảo căn chỉnh phù hợp cho từng thành viên của nó: 

 struct   MixedData    / * Sau khi biên dịch trong máy x86 32 bit * /   {      char   Data1 ;   / * 1 byte * / [196590] char   Padding1  [ 1 ];   / * 1 byte cho 'ngắn' sau để được căn chỉnh trên ranh giới 2 byte   giả sử rằng địa chỉ nơi cấu trúc bắt đầu là một số chẵn * /       ngắn   Data2 ;   / * 2 byte * /       int   Data3 ;    / * 4 byte - thành viên cấu trúc lớn nhất * /       char   Data4 ;   / * 1 byte * /       char   Padding2  [ 3 ];   byte để tạo tổng kích thước của cấu trúc 12 byte * /  };

Kích thước được biên dịch của cấu trúc hiện là 12 byte. Điều quan trọng cần lưu ý là thành viên cuối cùng được đệm với số lượng byte cần thiết để tổng kích thước của cấu trúc phải là bội số của căn chỉnh lớn nhất của bất kỳ thành viên cấu trúc nào (căn chỉnh (int) trong trường hợp này, trong đó = 4 trên linux-32bit / gcc) [ cần trích dẫn ] .

Trong trường hợp này, 3 byte được thêm vào thành viên cuối cùng để đệm cấu trúc với kích thước của 12 byte (căn chỉnh (int) × 3). 

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

Trong ví dụ này, tổng kích thước của cấu trúc sizeof (FinalPad) == 8 không phải 5 (sao cho kích thước là bội số của 4 (căn lề của float)). 

 struct   FinalPadShort   {    ngắn   s ;     char   n  [ 3 ];

Trong ví dụ này, tổng kích thước của cấu trúc sizeof (FinalPadShort) == 6 không phải 5 (không phải 8) (do đó kích thước là bội số của 2 (căn chỉnh (ngắn) = 2 trên linux-32bit / gcc)).

Có thể thay đổi căn chỉnh các cấu trúc để giảm bộ nhớ mà chúng yêu cầu (hoặc phù hợp với định dạng hiện có) bằng cách sắp xếp lại các thành viên cấu trúc hoặc thay đổi căn chỉnh của trình biên dịch (hoặc gói đóng gói) của các thành viên cấu trúc. 

 struct   MixedData    / * sau khi sắp xếp lại * /   {      char   Data1 ;       char   Data4 ; được sắp xếp lại * /       ngắn   Data2 ;       int   Data3 ;  };

Kích thước được biên dịch của cấu trúc hiện khớp với kích thước được biên dịch trước của 8 byte . Lưu ý rằng Padding1 [1] đã được thay thế (và do đó bị loại bỏ) bởi Data4 và Padding2 [3] không còn cần thiết vì cấu trúc đã được căn chỉnh theo kích thước của một từ dài .

Phương pháp thay thế bắt buộc cấu trúc MixedData được căn chỉnh theo ranh giới một byte sẽ khiến bộ xử lý trước loại bỏ căn chỉnh được xác định trước của các thành viên cấu trúc và do đó không có byte đệm nào được chèn .

Mặc dù không có cách tiêu chuẩn nào để xác định sự liên kết của các thành viên cấu trúc, một số trình biên dịch sử dụng các lệnh #pragma để chỉ định đóng gói bên trong các tệp nguồn. Đây là một ví dụ: 

 #pragma pack (đẩy)  / * đẩy căn chỉnh hiện tại lên stack * /   #pragma pack (1)  / * đặt căn chỉnh thành ranh giới 1 byte * /    struct   MyPackedData   {      char   Data1 ;       dài   Data2 ;       char   Data3 ; gói pragma (pop)  / * khôi phục căn chỉnh ban đầu từ ngăn xếp * /

Cấu trúc này sẽ có kích thước được biên dịch là 6 byte trên hệ thống 32 bit. Các chỉ thị trên có sẵn trong các trình biên dịch từ Microsoft, [7] Borland, GNU, [8] và nhiều lệnh khác.

Một ví dụ khác: 

 struct   MyPackedData   {      char   Data1 ;       dài   Data2   __ thuộc tính __  ;       char   Data3 ;  };

Đóng gói mặc định và #pragma pack [ chỉnh sửa ] Các trình biên dịch của Microsoft, đặc biệt là bộ xử lý RISC, có một mối quan hệ bất ngờ giữa việc đóng gói mặc định của dự án (chỉ thị / Zp) và chỉ thị #pragma . Chỉ thị #pragma chỉ có thể được sử dụng để giảm kích thước đóng gói của một cấu trúc từ bao bì mặc định của dự án. [9] Điều này dẫn đến các vấn đề về khả năng tương tác với các tiêu đề thư viện sử dụng, cho ví dụ: #pragma pack (8) nếu bao bì dự án nhỏ hơn mức này. Vì lý do này, việc đặt gói dự án thành bất kỳ giá trị nào ngoài 8 byte mặc định sẽ phá vỡ các lệnh #pragma được sử dụng trong các tiêu đề thư viện và dẫn đến sự không tương thích nhị phân giữa các cấu trúc. Giới hạn này không có khi biên dịch cho x86.

Phân bổ bộ nhớ được căn chỉnh theo các dòng bộ đệm [ chỉnh sửa ]

Sẽ có ích khi phân bổ bộ nhớ được căn chỉnh theo các dòng bộ đệm. Nếu một mảng được phân vùng cho nhiều hơn một luồng hoạt động, việc các ranh giới của mảng con không được gán cho các dòng bộ đệm có thể dẫn đến suy giảm hiệu năng. Dưới đây là một ví dụ để phân bổ bộ nhớ (mảng kép kích thước 10) được căn chỉnh theo bộ đệm 64 byte. 

 #include    double   *  foo  ( void )   {     double   *  19659246] // tạo mảng có kích thước 10      int       ok ;       ok   =   posix_memalign  (( void  ** )  &  var   64   10  *  sizeof  ( gấp đôi ); if  ( ok  ! =   0 )        return   NULL ;       return   var ;

Tầm quan trọng phần cứng của các yêu cầu căn chỉnh [ chỉnh sửa ]

Mối quan tâm liên kết có thể ảnh hưởng đến các khu vực lớn hơn nhiều so với cấu trúc C khi mục đích là ánh xạ hiệu quả của khu vực đó thông qua cơ chế dịch địa chỉ phần cứng (Ánh xạ lại PCI, hoạt động của MMU).

Chẳng hạn, trên hệ điều hành 32 bit, trang 4 KB không chỉ là một đoạn dữ liệu 4 KB tùy ý. Thay vào đó, nó thường là một vùng bộ nhớ được căn trên ranh giới 4 KB. Điều này là do việc căn chỉnh một trang trên một ranh giới có kích thước trang cho phép phần cứng ánh xạ địa chỉ ảo thành địa chỉ vật lý bằng cách thay thế các bit cao hơn trong địa chỉ, thay vì thực hiện số học phức tạp.

Ví dụ: Giả sử rằng chúng ta có ánh xạ TLB của địa chỉ ảo 0x2cfc7000 đến địa chỉ vật lý 0x12345000. . Ở đây, sự phân chia 20/12 bit may mắn phù hợp với sự phân chia đại diện thập lục phân ở 5/3 chữ số. Phần cứng có thể thực hiện bản dịch này bằng cách kết hợp 20 bit đầu tiên của địa chỉ vật lý (0x12345) và 12 bit cuối của địa chỉ ảo (0xabc). Điều này cũng được gọi là hầu như được lập chỉ mục (abc) được gắn thẻ vật lý (12345).

Một khối dữ liệu có kích thước 2 ^ (n + 1) -1 luôn có một khối phụ có kích thước 2 ^ n được căn trên 2 ^ n byte.

Đây là cách phân bổ động không có kiến ​​thức về căn chỉnh, có thể được sử dụng để cung cấp bộ đệm căn chỉnh, với giá của một yếu tố hai trong mất không gian. 

 // Ví dụ: lấy bộ đệm 4 KBytes được căn chỉnh 12 bit với malloc ()    // con trỏ không được gán cho khu vực rộng lớn   void   *  lên   =   malloc  (( 1   <<   13 )   -   1 );   // con trỏ được căn chỉnh tốt đến 4 KBytes   void   *  ap   =   aligntonext  ( up   12 );

trong đó aligntonext ] r ) hoạt động bằng cách thêm một gia số được căn chỉnh, sau đó xóa r các bit có ý nghĩa nhỏ nhất của p . Một triển khai có thể là 

 // Giả sử `uint32_t p, bits;` cho khả năng đọc   #define alignto (p, bits) (((p) >> bits) << bits)   #define aligntonext (p, bits) alignto (((p) + (1 << bit) - 1), bit)

Tài liệu tham khảo [ chỉnh sửa ]

Đọc thêm [ chỉnh sửa ]

Liên kết ngoài [ chỉnh sửa ]