[Chia sẻ] Data structure alignment & padding

c
data-structures

(ddhuy137) #1

Mình có bài toán nhỏ như sau đố các bạn cho vui:

typedef struct
{
    char c;
    int i;
} mstruct;

Đố các bạn sizeof(mstruct) là bao nhiêu byte. Chú ý: các expert không được trả lời nhé! :slight_smile:

Mình dám cá là size của mstruct không phải là 5 bytes. Vì sao như vậy? Theo đúng lý thuyết ta học thì size của struct phải là tổng size của các thành phần bên trong nó mà. Vậy tại sao không phải là 5 bytes, có gì huyền bí ở đây?

Để hiểu rõ về việc này, chúng ta hãy cùng tìm hiểu sơ qua Data Structure Alignment & Padding.

Data structure alignment là gì? Nó hoạt động như thế nào? Lâu lâu chúng ta vẫn hay nghe software này không tương thích với hệ điều hành 64bit hay software này chỉ chạy trên HĐH 32bit gì đó, vậy liên quan gì tới data structure alignment không?

Bên cạnh đó chúng ta cần một số kiến thức nền về hệ thống để có thể hiểu sâu hơn. Mình sẽ cung cấp cho các bạn trong bài viết này (nhưng chỉ là tổng quan thôi, vì nó khá là chuyên sâu, nếu có thời gian mình sẽ viết thêm những bài về nó) và mình sẽ cung cấp keyword để các bạn có thể tra google thêm.

  1. Data Structure Alignment là gì?
    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:
  2. 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
  3. 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

  4. Sau đây mình sẽ giới thiệu thêm về hệ thống.

  5. Trên các hệ thống khác nhau, chúng ta sẽ có sự khác nhau giữa sizecủa các data type như sau:
    (chú ý “bool” không có trong C. Từ C99 trở đi ta có kiểu tương đương là _Bool)

  • Lúc nãy ở trên chúng ta có biết được rằng CPU chỉ thao tác trên memory theo từng khối ở địa chỉ chẵn. Hay nói chính xác hơn khối ở đây là 1 WORD size. Tùy thuộc vào kiến trúc của CPU, nhưng thông dụng nhất có các size như sau:
    • Trên system 16bit: 1 WORD = 16bit = 2 bytes
    • Trên system 32bit: 1 WORD = 32bit = 4 bytes
    • Trên system 64bit: 1 WORD = 64bit = 8 bytes
  • N-byte alignment:
    chúng ta có các loại n-byte alignment: 2-byte align, 4-byte align, 8-byte align.

Như vậy sizeof(mstruct) sẽ là bao nhiêu:
- Với system 16bit

sizeof(mstruct): 4 bytes
  • Với system 32bit

sizeof(mstruct): 8 bytes

Thêm một ví dụ nữa để hiểu hơn:

typedef struct
{
    char c; // 1 byte
    double d; // 8 bytes
} mstruct2;
  • Với system 32bit & 4-byte alignment

sizeof(mstruct2): 12 bytes
  • Với system 32bit & 8-byte alignment

sizeof(mstruct2): 16 bytes

Như hình trên ta sẽ thấy rõ sự khác biệt giữa các n-byte alignment. N-byte alignment phụ thuộc vào compiler, chúng ta có thể điều chỉnh được.

Thêm 1 ví dụ nữa:

typedef struct
{
    char c;
    int i;
    double d;
} mstruct3;
  • Với system 32bit hay 64bit chúng ta luôn có sizeof(mstruct3) là 16 bytes. Nhưng việc sắp xếp trên memory sẽ khác.
  • Với system 32bit

sizeof(mstruct3): 16 bytes

sizeof(mstruct3): 16 bytes

Thêm ví dụ nữa:

typedef struct
{
    char c;
    int i;
    short s;
    double d;
} mstruct4;
  • System 32 bit & 4 byte alignment

sizeof(mstruct4): 20 bytes

sizeof(mstruct4): 24 bytes

sizeof(mstruct4): 24 bytes

Ví dụ nữa:

typedef struct
{
    char c;
    short s;
} mstruct5;

Các bạn thử tính toán xem size của mstruct5 là bao nhiêu trên các hệ thống 32bit/64bit với các n-byte alignment khác nhau.

Kết luận: Hy vọng các bạn đã hiểu được đôi chút về data structure alignment. Có thắc mắc gì hay có đoạn code nào hay các bạn post lên chia sẻ với mọi người nhé.


Tại sao biến struct gồm 1 biến int và 1 biến char lại có sizeof là 8 bytes?
[Wiki] Bit fields trong C/C++
Các loại Sort nâng cao
Poll: Kiểm tra kiến thức C - 4.09
Thiết kết Meetup DNH
Thiết kế Meetup DNH lần 1 ở TP HCM - 7PM - 6/6/2015
Xin chỉ giáo về Struct size
Làm sao để khiến DNH trở thành diễn đàn uy tín cho lập trình viên
(Lê Trần Đạt) #2

Cảm ơn Huy, bài viết rất hay. Anh đã đọc qua bài này và hiểu được thêm nhiều điều về padding. Ngày trước đi học chỉ có khái niệm về nó nhưng không hiểu sâu như bài em viết được.

Như em viết ở trên thì padding sẽ khiến cho các biến có kích thước nhỏ, phình to ra cho tương xứng với các biến có giá trị lớn hơn. Điều này giúp cho việc truy xuất (đọc ghi) các biến này với tốc độ nhanh hơn.

Dựa vào kiến thức mà em cung cấp, anh phát hiện ra một điều thú vị như sau.

  • Struct padding này sẽ có sizeof = 12. Tuy nhiên nếu anh thay đổi một chút

struct padding {
    char c1;
    int i1;
    char c2;
    short s1;
};
  • Di chuyển char c1; xuống dưới để tránh nó bị padding. Thì ta sẽ có struct no_padding với sizeof = 8.

struct no_padding {
    int i1;
    char c1;
    char c2;
    short s1;
};

Như vậy ta có thể vừa tiết kiệm vùng nhớ, vừa đảm bảo tốc độ truy vấn của chương trình đối với struct này. Bài hay lắm Huy.


(Lê Trần Đạt) #3

(Nguyen Huu Nghia) #4

Chào a Huy anh có thể nói rõ hơn cho em biết nguyên tắc sắp xếp các biến trong 1 khối được không ạ, ví dụ như trường hợp của struct4 trong trường hợp 32bit -8alignment tại sao lại không sắp xếp " sort " cùng khối với " char " và" int " ạ. Em cảm ơn anh


(ddhuy137) #5

Do thứ tự trong mstruct4 là char, int rồi tới short. Nên khi đó compile phải cấp phát theo thứ tự này. Đầu tiên compiler cấp phát vùng nhớ cho biến char, rồi sau đó tới biến int. Khi đó sau biến char cần phải được padding để alignment với biến int. Sau 2 bước này xong thì tới biến short. Nên vì thế biến short không thể nằm chung block với 2 biến kia được.
smile


(Phố Pháo Hoa) #7
  1. Ở vd mstruct:
    Với system 16bit thì size(int) = 2byte?

  2. Ở vd mstruct 3, mstruct 4:
    Với system 64bit (1 WORD là 8byte ) thì tại sao vùng nhớ của int lại bắt đầu từ số 4, nếu vậy thì địa chỉ của biến int đó đâu có chẵn.

  3. Hình như sáng nay do mất tập trng hay sao mà đọc 1 hồi em cứ bị luẩn quẩn miết: - N-byte alignment phụ thuộc vào compiler như thế nào vậy a? Có phải như là phần mềm bản 64bit thì n-byte alignment là 8-byte , bản 32 bit thì n-byte alignment là 4-byte? Nếu vậy thì khi nào n-byte alignment là 2-byte?


(ddhuy137) #8
  1. Ở system 16bit thì sizeof(int) = 2 bytes.

  2. À, em đọc địa chỉ từ phải sang đó. Ở đây mình ko ghi rõ địa chỉ ra, chỉ ghi chung chung để mọi người dễ hình dung

  3. Thông thường sẽ là như vậy em. Chỉ có ở 1 số hệ thống hoặc compiler cũ thì alignment có 2 bytes hoặc thậm chí là 1 byte. Nhưng cái này giờ không thông dụng nữa rồi
    smile


(Nguyen Huu Nghia) #9

Chính vì vậy e muốn hỏi nguyên tắc chèn padding ạ smile tại sao int không bắt đầu nằm ở vị trí thứ 6 (đảm bảo khối địa chỉ chẵn ) và short nằm ở vị trí thứ 2 trong cùng block với 2 biến trên. em chưa rõ chỗ này mong a giải thích giúp e ạ smile


(Lãnh Huyết) #10

Bài viết hay lắm bạn smile


(Lê Trần Đạt) #11

(Huy) #12
  • Theo mình nghĩ thì byte alignment nó tùy thuộc vào cái kiểu dữ liệu có số byte cao nhất mà mình khai báo thôi sao ? . Thí dụ thì double là 8 byte thì sẽ quyết định những kiểu kia sẽ padding vào.
  • Tiếp với lý do câu hỏi trên là int là 4 byte thì với system 32 bit & 8 byte alignment thì int sẽ chiếm 8 byte trong 1 ô nhớ ???

(Tâm Ninja) #13

Há há! Anh Huy cho em xin phép ăn cắp bài viết này về blog nhá... =)) Mà em ăn cắp lun roài xin phép sau...

Em mới update lại thư viện sách vừa đọc xong quyển này nó giải thích vô cùng kĩ càng:
https://drive.google.com/file/d/0B9jVt0SX-XdeQUxTRll5aHpWWFE/view?usp=sharing
Cuốn này là cuốn nghệ thuật tận dụng lỗi phần mềm của anh Nguyễn Thành Nam. Giờ tìm trên mạng hình như không có nữa mà cũng không có còn sách giấy. Phí thật. Quyển hay thế này mà ít người đọc.

Hôm trước đọc xong cuốn trên em ngồi vọc tiếp cái link này:
http://www.ibm.com/developerworks/vn/library/java/201301/j-codetoheap/


(abcxyz) #14

bạn có thể sửa lại bài viết k, có 1 số ảnh k xem được, mình vẫn chưa hiểu lắm về chỗ hệ thống 16,32,64 bít sẽ padding số byte bao nhiêu, và như thế nào


(Long Dragon) #15

E có đọc 1 bài viết bên web CongDongCViet thì họ nói là: Trong 1 struct sẽ lấy kích thước của biến thành viên có kích thước lớn nhất làm size chung cho block, sau đó sẽ lần lượt lưu trữ từng biến thành viên vô block, nếu còn đủ chỗ thì "nhét" vô, ko đủ thì create 1 segment mới => Có đúng & liên quan đến ý trên ko nhỉ ? :slight_smile:

Em chưa hiểu chỗ này lắm :frowning: Theo như ý kiến của em ở phía trên thì phải là 16 bytes chứ nhỉ ? :thinking:

Có cách nào điều chỉnh trên CB ko ạ ? Chứ e ko dùng VS :cry:

Trên system 32bit thì size của mstruct5 là 8 bytes đúng ko nhỉ ? :thinking:

Nói chung e cũng còn khá mơ hồ, một phần cũng do những images của bài viết bị mất, bác nào tốt bụng zô update giúp đi ạ ^_^

P/S: Mà cũng chưa thấy nói gì về #pragma pack(n) hết nhỉ :grinning:


(Long Dragon) #16

Em trả lời thử, các pro đánh giá xem đúng hay sai nhé :wink:

Đối với system 16bit (2-byte alignment) thì sizeof(mstruct5) sẽ cho kết quả là 4 bytes, lý do: Vì system 16bit là 1 WORD chỉ có 2 bytes nên block đầu tiên sẽ chứa biến c (tức là padding thêm 1 byte để cho đủ 2 bytes / block). Còn biến s có kích thước 2 bytes nên sẽ vừa vặn với block thứ 2 luôn => size = 4 bytes.

Đối với system 32 bit (4-byte alignment) thì sizeof(mstruct5) sẽ cho kết quả là 4 bytes, lý do: Vì system 32bit là 1 WORD có 4 bytes nên block đầu tiên sẽ chứa cả biến c và biến s (tức sau biến c sẽ padding thêm 1 byte để đảm bảo biến s có 2 bytes sẽ nằm ở địa chỉ chẵn), vậy là sẽ vừa block đầu tiên luôn => size = 4 bytes.

Đối với system 32 bit (8-byte alignment) thì sizeof(mstruct5) sẽ cho kết quả là … 8 bytes ??? Lý do: Cũng như system 32bit (4-byte alignment) nhưng do 1 WORD là 8 bytes nên block đầu tiên (chứa biến cs) sẽ là 8 bytes => size = 8 ???

Còn với system 64 bit thì y chang như system 32 bit (8-byte alignment) vì 1 WORD của nó là 8 bytes.

Em cũng còn hơi hoang mang với do dự, các pro xem coi đúng ko ạ :blush:


(rogp10) #17

Nếu trình biên dịch không dựa vào max size của primitive để pad thì sẽ dẫn đến một số thành phần primitive trong struct bị misalign (vị trí không chẵn byte). Với 1 struct gồm char, int32_t, double, int32_t và pack(4) thì size sẽ là 4+4+8+4 = 20. Khi dùng mảng struct này (tạm gọi là arr) thì arr[1].double sẽ nằm ở byte thứ 28 (!) mà 28 chia 8 dư 4.

Còn tại sao lại có 64 với 32 là do sizeof(int) đó.

Tất nhiên đó là khi chưa chỉnh #pragma.


(Long Dragon) #18

“primitive” và “pad” là gì ạ ? :sweat:

#pragma pack (n) có thể hiểu đơn giải là set WORD (size của 1 block) thành n bytes đúng ko anh ?
Đó cũng là lý do vì sao khi để #pragma pack (1) thì size của mỗi block (WORD) là 1 byte nên ko thể có chuyện “dư” byte ?


(rogp10) #19

Primitive trong C là (signed/unsigned) char, int, short, long, long long, double, float và những typedef dựa trên chúng. Struct không phải primitive nữa nên ko có alignment.

Hiểu như vậy cũng được.


(Long Dragon) #20

là sao ạ ? Em chưa hiểu chỗ này lắm :slight_smile:

Ý anh là nội dung của cái topic đó ạ ?


(rogp10) #21

typedef int int32_t; đại loại vậy.

Ý anh là nội dung của cái topic đó ạ ?

Tức là bản thân struct không có alignment mà do chính những thành phần primitive trong nó đòi hỏi alignment.


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