0

Khái lược nghệ thuật nhồi cấu trúc

gigajet đã đăng vào 19, Tháng 4, 2025, 21:05

Khái lược nghệ thuật nhồi cấu trúc

Khái lược bài viết "The Lost Art of Structure Packing" của Eric S. Raymond. Người viết không dịch toàn bộ mà tóm lại những phần bản thân cho là quan trọng.

Tiêu chuẩn về căn chỉnh

  • Trên các bộ xử lý hiện đại, trình biên dịch phải sắp đặt các kiểu dữ liệu căn bản trong bộ nhớ để đọc ghi được nhanh hơn.

  • Do tiêu chuẩn này mà lớp lớn các kiến trúc tập lệnh (ISA) từ Intel, tới ARM, tới RISC-V, đều sắp đặt cùng một cách.

  • Trong C, mỗi biến dữ liệu kiểu căn bản cần tuân theo yêu cầu căn chỉnh là: một short 2 byte phải bắt đầu ở địa chỉ chẵn, một int hay float 4 byte phải bắt đầu ở địa chỉ chia hết cho 4, và một long hay double 8 byte phải bắt đầu ở địa chỉ chia hết cho 8. signed hay unsigned đều vậy. Con trỏ, tùy theo cỡ của nó là 32-bit hay 64-bit, cũng được căn chỉnh tương ứng theo 4 byte hoặc 8 byte. Đây gọi là tính tự căn chỉnh.

  • Phần cứng có cách căn chỉnh khác với tính tự căn chỉnh rất là hiếm, gần như không tồn tại hoặc quá cũ và quá đặc thù trong nhóm nhỏ. Trừ khi cần quan tâm đặc biệt tới phần cứng đặc thù, có thể giả định đại đa số phần cứng đều có tính tự căn chỉnh để căn chỉnh kiểu dữ liệu.

Padding, tức căn lề

  • Tuy tài liệu tiêu chuẩn C không bắt buộc rằng các biến tĩnh được sắp đặt theo thứ tự được viết ra trong mã nguồn (tức mặc định là trình biên dịch được đổi chỗ các biến toàn cục), nhưng các trình biên dịch như gcc và clang thường làm như vậy, sắp theo mã nguồn, nên ít khi ta cần quan tâm, trừ khi làm việc với trình biên dịch đặc biệt nào đó.

  • Cho nên giả định khai báo sau ở biến toàn cục:

char *p;
char c;
int x;

thì để thỏa tính tự căn chỉnh cho x, bộ nhớ được sắp đặt như vầy trong máy 32-bit:

char *p;    /* 4 byte */
char c;     /* 1 byte */
char pad[3];
int x;      /* 4 byte */

Trong đây pad là biến tượng trưng cho phần lề được căn chỉnh để thỏa tính tự căn chỉnh của biến. Đây là bộ nhớ bị lãng phí. Còn nếu là 

char *p;
char c;
short x;

thì sự sắp đặt là như vầy:

char *p;    /* 4 byte */
char c;     /* 1 byte */
char pad[1];/* 1 byte */
short x;    /* 2 byte */

Nếu x là kiểu có 8 bytes (như long trên máy 64-bit) thì sẽ có 7 bytes pad.

  • Ở trường hợp khó đoán hơn như vầy thì sao:
char c;
char *p;
int x;

nếu gọi các lề là pad1 và pad2 và viết sự sắp đặt bộ nhớ thành:

char c;         /* 1 byte */
char pad1[M];
char *p;        /* 8 byte */
char pad2[N];
int x;          /* 4 byte */

thì M và N bằng bao nhiêu?

N bằng không. Bởi vì kiểu con trỏ (4 hoặc 8 byte) luôn có yêu cầu tự căn chỉnh nghiêm ngặt hơn kiểu int (4 byte). Nhưng M khó đoán hơn vì vốn c (1 byte) không cần tự căn chỉnh nên không biết trình biên dịch đặt c ở đâu. Nếu c được đặt ở byte cuối cùng của word (word là độ lớn của thanh ghi đa năng) thì M bằng không, nhưng xác suất cao hơn là c được đặt ở byte đầu tiên của word, lúc này M bằng 3 trên máy 32-bit và bằng 7 trên máy 64-bit, và các trường hợp M từ 1 tới 2 trên máy 32-bit và từ 1 tới 6 trên máy 64-bit cũng có thể xảy ra, có thể do các biến toàn cục khác được khai báo liền trước đó.

  • Đối với mảng của kiểu căn bản, vì các phần tử đều tự căn chỉnh, nên chúng không cần thêm điều kiện căn chỉnh nào khác. Các phần tử sắp xếp liền nhau không có thêm khoảng trống nào giữa các phần tử.

  • Vậy với struct thì khác biệt chỗ nào?

Căn chỉnh và căn lề trong cấu trúc struct

  • Một biến kiểu struct được căn chỉnh theo trường có kiểu căn bản rộng nhất. Tức là nếu trong struct kiểu căn bản rộng nhất là 4 byte, thì struct phải bắt đầu ở địa chỉ chia hết cho 4, còn nếu có trường căn bản lớn nhất là 8 byte, thì phải bắt đầu ở địa chỉ chia hết cho 8. Trong C, địa chỉ của struct cũng là địa chỉ của trường đầu tiên, trong C++ thì không chắc vì còn tùy theo có kế thừa và có hàm ảo hay không.

  • Vì ta biết struct được căn chỉnh theo trường căn bản rộng nhất, cho nên với khai báo biến tĩnh rời nhau như vầy ở máy 64-bit như cuối phần trước

char c;     /* 1 byte */
char *p;    /* 8 byte */
int x;      /* 4 byte */

thì ta không biết phần lề giữa c và p là bao nhiêu byte, nhưng nếu khai báo cùng một struct nhưng vầy

struct foo {
    char c; /* 1 byte */
    char pad[7]; /* 7 byte */
    char *p; /* 8 byte */
    int x; /* 4 byte */
};

thì ta biết chắc pad gồm 7 byte, bởi vì địa chỉ của một biến struct foo phải được căn theo trường căn bản rộng nhất là p gồm 8 byte, nên phải có địa chỉ chia hết cho 8. c là trường đầu tiên của struct foo nên có cùng địa chỉ với biến struct foo, nên cũng có địa chỉ chia hết cho 8, tức nằm ở byte đầu tiên của word, mà như vậy thì cần có 7 byte phần lề trước khi sắp đặt p.

  • struct có thể có thêm phần lề ở cuối, dựa trên địa chỉ sải chân, còn gọi là stride address, của struct đó. Địa chỉ sải chân là địa chỉ đầu tiên đằng sau một struct có cùng độ căn chỉnh với struct đó. Trình biên dịch sẽ làm theo luật là đệm thêm phần lề vào sau một struct cho tới ngay trước địa chỉ sải chân của struct đó. Luật này quyết định sizeof() trả về cái gì.

  • Cho nên, xét ví dụ sau trên máy 64-bit

struct foo3 {
    char *p;     /* 8 byte */
    char c;      /* 1 byte */
};

struct foo3 singleton;
struct foo3 quad[4];

thì foo3 được căn chỉnh theo 8 byte (vì trường căn bản rộng nhất là p gồm 8 byte). Tuy nhiên thay vì 9 bytes thì sizeof(struct foo3) bằng 16 byte, bởi vì địa chỉ sải chân của struct foo3 là 16, vì 16 là số nhỏ nhất sau 9 mà chia hết cho 8. Cho nên 7 byte từ offset 9 tới offset 15 trở thành lề của struct foo3. Vậy biến singleton cũng như các phần tử của mảng quad đều bằng 16 bytes. Nói cách khác, có thể viết lại struct foo3 thêm các phần lề pad như sau:

struct foo3 {
    char *p;     /* 8 byte */
    char c;      /* 1 byte */
    char pad[7];
};

Còn đối với ví dụ này 

struct foo4 {
    short s;     /* 2 byte */
    char c;      /* 1 byte */
};

thì struct foo4 không có phần lề giữa các phần tử, và có phần lề cuối là 1 byte, sizeof(struct foo4) cũng như địa chỉ sải chân là 4 (bạn đọc hãy xem tại sao).

  • Nếu struct được khai báo lồng nhau thì mỗi struct bên trong được tự căn chỉnh theo chính nó, và các trường của struct bên trong cũng ảnh hưởng tới độ căn chỉnh của struct bên ngoài, chứ không chỉ các trường trực tiếp của struct bên ngoài. Chẳng hạn trong máy 64 bit có khai báo này
struct foo5 {
    char c;
    struct foo5_inner {
        char *p;
        short x;
    } inner;
};

thì ta thấy sizeof(struct foo5_inner) bằng 16. Và struct foo5 được căn chỉnh theo 8 byte (trường căn bản dài nhất là p của inner), cho nên giữa c và inner có phần lề 7 byte, và không cần phần lề sau vì địa chỉ sải chân vừa bằng 24, viết lại thêm các phần lề pad1, pad2 như sau:

struct foo5 {
    char c;           /* 1 byte */
    char pad1[7];     /* 7 byte */
    struct foo5_inner {
        char *p;      /* 8 byte */
        short x;      /* 2 byte */
        char pad2[6]; /* 6 byte */
    } inner;
};

Vì sizeof(struct foo5) bằng 24, và có 13 bit trong đó là phần lề, ta thấy hơn 50% bộ nhớ bị lãng phí!

  • Xét thêm một ví dụ khác, với khai báo sau trên máy 64-bit:
struct foo5x {
    char c;
    struct foo5x_inner {
        char *p;
        short x;
    } inner;
    char d;
};

thì sizeof(struct foo5x)=32 viết lại thêm các phần lề (bắt đầu bằng) pad được 

struct foo5x {
    char c;
    char pad1[7];
    struct foo5x_inner {
        char *p;
        short x;
        char pad2[6];
    } inner;
    char d;
    char pad3[7];
};

Tỉ lệ bộ nhớ lãng phí là 20/32, tức 62,5%.

Về trường bit (bitfield)

  • Trường bit cho phép giới hạn độ lớn các trường theo bit (thấp nhất là 1 bit), được cài đặt bằng các phép mặt nạ và xoay bit trên byte và word. Đây là một ví dụ khai báo trường bit.
struct foo6 {
    short s;
    char c;
    int flip:1;
    int nybble:4;
    int septet:7;
};

  • C99 đảm bảo trường bit được nén chặt nhất có thể, miễn là không vượt quá biên của đơn vị lưu trữ (word). Nhưng C11 và C++14 lỏng lẻo hơn, và trường bit có thể vượt qua biên lưu trữ để trải dài trên nhiều word thay vì bắt đầu word mới, và C11/C++14 cho phép trình biên dịch quyết định chuyện này. Với GCC thì để ABI quyết định, và x64 ABI thì làm giống như C99.

  • Không có quy định về thứ tự các trường bit là phải từ bit nhỏ nhất tới lớn nhất hay ngược lại, cho nên struct foo6 ở trên máy 32-bit có thể hiểu là

struct foo6 {
    short s;       /* 2 byte */
    char c;        /* 1 byte */
    int flip:1;    /* tổng 1 bit */
    int nybble:4;  /* tổng 5 bit */
    int pad1:3;    /*  phần lề cho đủ 8-bit, bởi vì không đủ chỗ để nhét thêm 7 bit phía sau, do tính từ đầu struct thì word lúc này đã là 3 byte + 5 bit = 29 bit, nên phải cho `septet` qua word mới */
    int septet:7;  /* 7 bit */
    int pad2:25;   /* phần lề cho đủ 32 bit */
};

hoặc phần lề có thể nằm trước các trường bit như sau

struct foo6 {
    short s;       /* 2 byte */
    char c;        /* 1 byte */
    int pad1:3;    /* phần lề cho đủ 8 bit */
    int flip:1;    /* tổng 1 bit */
    int nybble:4;  /* tổng 5 bit, kết thúc word 1 từ đầu struct */
    int pad2:25;   /* phần lề cho `septet` đủ 32 bit */
    int septet:7;  /* 7 bit, kết thúc word 2 */
};

  • Tiêu chuẩn từ C99 trở đi thì phần lề không chắc sẽ được phủ bằng các byte 00. Còn về kiểu thì khi tính toán, trình biên dịch sẽ hiểu tính có dấu (sign/unsigned) của kiểu nhưng không chắc liệu trình biên dịch quyết định độ lớn như thế nào, liệu đơn vị lưu trữ có bị giữa hai khai báo short flip:1 và long flip:1 hay không, cái này tùy vào trình biên dịch.

  • Do giới hạn không được lấn qua word khác của C99, struct foo9 dưới đây tốn ba word 32-bit trong C99, mà word cuối cùng chỉ dùng có 1 bit. C11 và C++14 có thể nén struct foo9 chặt hơn, nhưng đừng trông đợi trình biên dịch sẽ làm vậy. Ngoài ra, struct foo8 có thể nằm gọn trong một word 64-bit nếu máy hỗ trợ độ lớn này.

struct foo7 {
    int bigfield:31;      /* bắt đầu 32 bit của word 1 */
    int littlefield:1;
};

struct foo8 {
    int bigfield1:31;     /* bắt đầu 32 bit của word 1 */
    int littlefield1:1;
    int bigfield2:31;     /* bắt đầu 32 bit của word 2 */
    int littlefield2:1;
};

struct foo9 {
    int bigfield1:31;     /* bắt đầu 32 bit của word 1 */
    int bigfield2:31;     /* bắt đầu 32 bit của word 2 */
    int littlefield1:1;
    int littlefield2:1;   /* bắt đầu 32 bit của word 3 */
};

Sắp đặt lại cấu trúc

  • Từ các hiểu biết trên, ta thấy có thể sắp đặt lại thứ tự các trường để giảm thiểu phần lề bị bỏ phí. Đây là nghệ thuật nhồi cấu trúc. Phần lề chỉ xảy ra ở hai chỗ: một là để lưu trữ kiểu lớn hơn (nên cần tự căn chỉnh với độ lớn lớn hơn), hai là khi một struct kết thúc trước địa chỉ sải chân của nó, dẫn tới phần lề được thêm.

  • Cách đơn giản nhất là sắp đặt lại các trường giảm dần theo cỡ. Như vậy giảm thiểu nguyên nhân thứ nhất sinh ra phần lề, vì sự thay đổi từ kiểu cỡ nhỏ qua cỡ lớn là ít nhất. Nhưng với kiểu có struct lồng nhau thì chưa chắc sẽ giảm được, do bộ nhớ tiết kiệm được bị chuyển thành phần lề trước địa chỉ sải chân, chẳng hạn như khi áp dụng với struct foo5 ở trên

struct foo12 {
    struct foo5 {
        char *p;      /* 8 byte */
        short x;      /* 2 byte */
    } inner;
    char c;           /* 1 byte*/
};

thì ta thấy sizeof(struct foo12) vẫn là 24 byte:

struct foo12 {
    struct foo5 {
        char *p;      /* 8 byte */
        short x;      /* 2 byte */
        char pad1[6]; /* 6 byte */
    } inner;
    char c;           /* 1 byte*/
    char pad2[7];     /* 7 byte */
};

cho nên cần thiết kế lại cấu trúc nếu muốn giảm cỡ.

  • Cũng có thể sắp đặt các trường theo thứ tự tăng dần của cỡ sao cho phần lề dồn lên phía trước thay vì phía sau như cách trên. Có thể giảm thiểu phần lề bằng mọi thứ tự được sắp mà, một là, mọi trường cùng cỡ nằm liền nhau (nên không có phần lề nằm giữa chúng), và hai là, các lỗ hổng nằm giữa các dải liền nhau này được sắp sao cho từ cỡ của dải có cỡ nhỏ hơn (cỡ của cả dải, không phải cỡ của độ căn chỉnh), cần ít bước nhân đôi nhất để đến được cỡ của dải liền kề có cỡ lớn hơn. Chẳng hạn như struct foo13 bên dưới không có phần lề nào:
struct foo13 {
    int32_t i;
    int32_t i2;
    char octet[8];
    int32_t i3;
    int32_t i4;
    int64_t l;
    int32_t i5;
    int32_t i6;
};
  • Ngoài lề, không ảnh hưởng nội dung: vì sao struct foo13 không có phần lề nào được xem như bài tập cho người đọc. Và người viết bài bằng tiếng Việt cũng khuyến khích người đọc hiểu tại sao bằng 2 cách, một là từ định nghĩa luật tự căn chỉnh, hai là từ điều nhận thấy liền trước. Để thấy được bằng cách thứ hai, ta thấy struct foo13 gồm có năm dải (các phần tử liền nhau cùng cỡ) được viết cách ra sau đây cùng với cỡ của mỗi dải trong phần bình luận:
struct foo13 {
    int32_t i;      /* Dải 1: 8 byte */
    int32_t i2;

    char octet[8];  /* Dải 2: 8 byte */

    int32_t i3;     /* Dải 3: 8 byte */
    int32_t i4;

    int64_t l;      /* Dải 4: 8 byte */

    int32_t i5;     /* Dải 5: 8 byte */
    int32_t i6;
};

Như vậy không cần bước nhân đôi nào để đi từ dải này qua dải liền kề kia, nên không có phần lề.

  • C không tự ý thay đổi thứ tự các trường trong cấu trúc, bởi vì C vốn được dùng để viết hệ điều hành và mã nguồn gắn với phần cứng, cho nên người lập trình hệ thống cần phải sắp đặt cấu trúc để phản ánh chính xác trên bộ nhớ cách sắp đặt byte và bit của thiết bị hòng điều khiển thiết bị ngoại vi một cách trừu tượng bằng sự đọc ghi bộ nhớ thông thường, nên sự không tự sắp thứ tự cũng là một tính năng. Go làm giống C; nhưng Rust thì ngược lại, mặc định thì trình biên dịch được sắp đặt lại thứ tự các trường.

Một số ngoại lệ

  • Với kiểu enum thì trình biên dịch được tùy ý xem đó là short, long, hay char ở mặc định, cho nên tùy trình biên dịch mới biết được bộ nhớ được sắp đặt ra sao.

  • long double thì tùy nền tảng, có thể là 80 bit, có thể là 128 bit, có thể là 80 bit nhưng được căn chỉnh phần lề theo 96 hay 128 bit.

  • double trong x86 Linux có thể tự căn chỉnh theo 4 byte trong khi cỡ của nó là 8 byte nếu biến này nằm trong một struct, nhưng vẫn căn chỉnh theo 8 byte nếu khai bao bên ngoài, tùy trình biên dịch và tùy chọn.

  • Tóm lại, gặp các trường hợp này nên dùng sizeof() và offsetof() để kiểm tra cỡ lưu trữ.

Tính dễ đọc và tính cục bộ bộ nhớ đêm

  • Nếu sắp thứ tự một cách máy móc và vụng về có thể làm giảm tính dễ đọc và tính cục bộ bộ nhớ đệm của mã nguồn.

  • Về tính dễ đọc, nên nhớ rằng mã nguồn còn để cho con người đọc như một bản thiết kế cấu trúc dữ liệu, chứ không chỉ để máy móc biên dịch. Để dễ đọc thì cần gom nhóm các trường dữ liệu liên quan với nhau về ngữ nghĩa, đặt chúng nằm gần nhau. Lý tưởng mà nói, thiết kế của cấu trúc cần phải truyền đạt thiết kế của chương trình.

  • Về tính cục bộ bộ nhớ đệm, cái mà ta làm để bảo quản tính dễ đọc, tức là gom nhóm những trường liên quan với nhau đặt chúng nằm gần nhau, cũng cải thiên tính cục bộ bộ nhớ đệm, nếu như các trường này thường được đọc ghi cùng nhau. Nên nếu sắp thứ tự một cách máy móc và để chúng xa nhau có thể làm chậm thuật toán do cache miss.

  • Nếu mã nguồn chạy bằng nhiều tiến trình hay thread, còn có vấn đề thứ ba là cache line bouncing. Để giảm thiểu thời gian đọc ghi bTính dễ đọcus đắt đỏ, cần giảm thiểu chuyện đọc từ cache line này và ghi ra cache line khác trong một vòng lặp.

  • Tóm lại, cần xem xét một số rủi ro ở trên khi đưa ra quyết định sắp lại thứ tự của trường.

Cẩn thận khi dùng trường bit và union để tiết kiệm bộ nhớ.

Một số công cụ có thể tham khảo thêm, nghe đồn

  • pahole

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.