[Chia sẻ] Data structure alignment & padding

#22

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

#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ẻ ạ?

#24

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

1 Like
#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.

2 Likes
#27

Thanks anh , sách hay ghê !

#28

E xin file sách được không ạ

#29

image
Các bạn cho em hỏi em xác định size struct như bác ở trên nói mà sao bài em nó ra 12 vậy ạ,mong mọi người giải thích em với.

#30

do data alignment nha :V https://en.cppreference.com/w/cpp/language/object#Alignment

2 Likes
#31

bác xem cái đề em hỏi phía trên với ạ,em dùng máy tính 64 bit thì size của struct là 8 bytes đúng ko bác

#32

12 chứ :V

hiểu sơ sơ là biến int cần được nằm ở ô địa chỉ có giá trị là bội của ví dụ 4 chẳng hạn, để tối ưu tốc độ đọc/viết.

vậy tes::b phải nằm ở ô nhớ có địa chỉ bội là 4, nên trình biên dịch nó dịch struct tes cũng phải nằm ở ô nhớ có địa chỉ là bội của 4 luôn :V nó dịch tes thành

char a;           // ở địa chỉ 4x
char padding1[3]; // địa chỉ 4x+1 tới 4x+3
int b;            // ở địa chỉ 4x+4 tới 4x+7
char c;           // ở địa chỉ 4x+8
char padding2[3]; // ở địa chỉ 4x+9 tới 4x+11

nếu a ko nằm ở địa chỉ 4x luôn thì làm sao biết pad bao nhiêu bytes để bảo đảm b nằm ở địa chỉ 4y :V nên nó pad vậy thành ra 12 bytes :V

muốn nó pad còn 8 bytes thì khai báo lại thành char a; char c; int b; hoặc int b; char a; char c; :V

int b; char a; char c; thì hơi khó hiểu chút vì 6 bytes là bảo đảm b ở đúng 4x rồi :V nhưng nếu khai báo mảng tes arr[10]; thì sẽ thấy nhiều tes nằm cạnh nhau, nếu 6 bytes thì chỉ bảo đảm tes[0] nằm ở 4x, tes[1] sẽ nằm ở 4x+6 ko phải là bội của 4 :V nên nó pad luôn thành ra 8 bytes :V

4 Likes
#33

Như vậy thì nếu có 1 struct mình nên sắp xếp các biến bên trong nó với size giảm dần thì sẽ tối ưu bộ nhớ nhất.

1 Like
#34

ờm logic như thế cũng đúng :V

đọc thêm: https://stackoverflow.com/questions/56761591/how-do-i-organize-members-in-a-struct-to-waste-the-least-space-on-alignment

câu trả lời trong SO có nêu ra trường hợp đặc biệt http://www.catb.org/esr/structure-packing/#_readability_and_cache_locality nếu mục đích là tốc độ thì có khi cần để các member truy cập nhiều nhất trong struct gần nhau để nó fit 1 cache line (ví dụ 1 cache line có kích thước là 64 bytes). Máy tính nó fetch 1 ô địa chỉ nào đó thì nó ko chỉ fetch 1 byte của địa chỉ đó mà fetch 1 cache line ~~64 bytes. Nếu ví dụ 2 biến trong 1 struct truy cập nhiều lần thì để 2 biến này gần nhau nó fit trên 1 cache line, khi truy cập 2 biến này chỉ cần fetch 1 lần. Nếu để xa theo thứ tự alignment giảm dần thì tuy giảm dung lượng struct, giảm dung lượng bộ nhớ nhưng có khi phải fetch 2 cache line để truy cập 2 biến đó thì tốc độ thực thi chậm hơn :V

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