[Chia sẻ] Data structure alignment & padding

c
data-structures

(Long Dragon) #22

Vậy cho em hỏi nếu hiểu theo cách khoa học thì như thế nào ạ ? :slight_smile:


(Trọng Dũng) #23

Thanks a đã share bài, em có 1 thắc mắc sau mong mọi người giải thích dùm ạ :

CPU hiện đại của chúng ta luôn thao tác trên memory theo từng khối ở địa chỉ là một số chẵn, không thể thao tác trên địa chỉ là số lẻ được.

Như vậy với mstruct của chúng ta, ví dụ biến “char c” nằm trên memory có địa chỉ chẵn, nếu biến “int i” nằm kế tiếp thì sẽ có địa chỉ lẻ rất phức tạp để CPU thao tác với biến “int i” này.

image

Question:

Giả sử em có 1 struct như sau:

typedef struct {
     char a1;
     char a2;
     char a3;
     char a4;
     int     b;
} A ;

Vậy với alignlemt = 4 thì struct đó được sắp xếp là lưu trữ theo hình nào dưới đây ạ?

Hình 1:
image

Hình 2:
image

Khi echo ra sizeof của struct trên, e thấy kqua trả về là 8byte , tức nó lưu trữ struct này như hình 1. Mà nếu lưu như hình 1, địa chỉ của a1 là địa chỉ chẵn rồi, thì a2 sẽ là địa chỉ lẻ thì sao CPU thao tác được với địa chỉ lẻ ạ?


(rogp10) #24

a2 không lẻ đâu, vì char chỉ cần align 1 byte thôi.


(Trọng Dũng) #25

là sao thế bác?

  1. Theo Wikipedia: Data Structure is the way data is arranged and accessed in computer memory. Có nghĩa là khi data load lên memory sẽ được CPU sắp xếp lại để tiện cho việc truy xuất tối ưu nhất có thể.
    Chúng ta đều biết rằng các CPU hiện đại của chúng ta luôn thao tác trên memory theo từng khối ở địa chỉ là một số chẵn, không thể thao tác trên địa chỉ là số lẻ được. Như vậy với mstruct của chúng ta, ví dụ biến “char c” nằm trên memory có địa chỉ chẵn, nếu biến “int i” nằm kế tiếp thì sẽ có địa chỉ lẻ rất phức tạp để CPU thao tác với biến “int i” này. Vì vậy chúng ta có thêm 2 khái niệm sau:
  • Data alignment: sắp xếp data sao cho địa chỉ của các biến luôn là số chẵn và phù hợp với hệ thống
  • Data padding: để làm được việc alignment như ở trên chúng ta cần phải “padding” thêm một số byte vào sau biến “char c” để khi đó biến “int i” có thể ở địa chỉ chẵn

Như cách chủ bài nói, thì khi áp dụng vào struct của mình:

typedef struct {
 char a1;
 char a2;
 char a3;
 char a4;
 int     b;

} A ;

thì biến char a1 sẽ có địa chỉ chẵn, ô bên cạnh sẽ là địa chỉ lẻ , vậy sao a2 vẫn được cấp vào ô bên cạnh, trong khi CPU hiện đại của chúng ta luôn thao tác trên memory theo từng khối ở địa chỉ là một số chẵn, không thể thao tác trên địa chỉ là số lẻ được ?


(‏) #26

ví dụ thanh ghi của CPU là 32-bit hay 4 byte, a2 là 1 char thì kiểu nào cũng phải đọc vào 4 byte a1-a4 vào thanh ghi rồi mới tính toán chung, vậy nên địa chỉ a2 a4 có lẻ cũng chả quan trọng, chỉ cần đọc 1 lần 4 byte vào

còn struct { char a; int n; }; nếu n ko nằm trên địa chỉ là bội của 4 thì phải đọc vào 2 lần 4 byte: 4 byte ở offset 0 và 4 byte ở offset 4, rồi sau đó lấy 3/2/1 byte của 4 byte đầu tiên nối với 1/2/3 byte của 4 byte thứ 2 mới ghép được thành int n, đã đọc 2 lần lại còn phải cắt nối 2 giá trị lại nên phải pad 3 byte vào phía sau a. Khi có padding 3 byte vào thì int n chỉ cần đọc 1 lần 4 byte thứ 2 và ko cần phải cắt nối gì nữa.


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?