Đổi thứ tự 6 trường trong struct: 40 byte xuống 24, và mảng duyệt nhanh 1,6 lần

Hình dung xếp đồ vào vali. Nếu bạn nhét một cuốn sách dày giữa hai chiếc áo phông rồi lại một cuốn sách nữa, giữa chúng luôn có những khe hở lồi lõm không dùng được. Nhưng nếu xếp mọi thứ cồng kềnh xuống trước, rồi nhét áo phông, tất, đồ nhỏ lấp vào các khe — vali khít lại, chứa được nhiều hơn hẳn dù vẫn từng ấy món. Trường trong một struct C xếp vào bộ nhớ đúng theo logic cái vali đó, và cái "thứ tự xếp" — thứ bạn quyết định khi gõ khai báo — lại đổi kích thước struct nhiều hơn tôi từng nghĩ.

Một struct C có kích thước bao nhiêu? Nhiều người cộng kích thước các trường: một char (1) + một double (8) + một int (4) là 13 byte. Sai — vì trình biên dịch chèn padding (byte đệm) giữa các trường để mỗi trường rơi đúng vào địa chỉ căn lề của nó. Và điều bất ngờ: thứ tự bạn khai báo các trường quyết định có bao nhiêu padding, tức quyết định kích thước struct. Tôi đo xem thứ tự trường ảnh hưởng thế nào trong container gcc:13 (ARM), tin rằng "compiler lo hết" — và thấy đây là một tối ưu miễn phí mà chỉ người viết làm được.

Padding và vì sao thứ tự đổi kích thước

Mỗi kiểu có một yêu cầu căn lề (như bài căn lề dữ liệu đã bàn): int 4 byte muốn địa chỉ chia hết 4, double 8 byte muốn chia hết 8. Để bảo đảm điều đó cho từng trường trong struct, compiler chèn byte đệm trước một trường nếu vị trí hiện tại chưa căn lề. Nên nếu bạn xen một char (1 byte) ngay trước một double, compiler phải chèn 7 byte đệm để double rơi đúng lề — 7 byte hoàn toàn lãng phí. Đúng cái khe hở giữa cuốn sách và chiếc áo.

Tôi đo một struct sáu trường (char, double, char, long, char, int), sắp theo hai thứ tự:

thứ tự XẤU  (char; double; char; long; char; int) : sizeof = 40 byte
thứ tự TỐT  (double; long; int; char; char; char) : sizeof = 24 byte
packed      (bỏ hết padding)                       : sizeof = 23 byte

Cùng sáu trường, cùng dữ liệu, chỉ khác thứ tự khai báo — mà kích thước chênh từ 40 xuống 24 byte, tức thứ tự xấu phình 40%, mang theo 16 byte padding rác. Thứ tự tốt (xếp trường lớn trước, nhỏ sau) dồn các char về cuối nên chúng nằm liền nhau không cần đệm — y như xếp đồ cồng kềnh trước rồi lấp khe bằng đồ nhỏ. Bản packed bỏ hết padding còn 23 byte. Kích thước khác nhau, nhưng nó có làm chương trình chạy khác nhau không?

Đo: struct gọn duyệt nhanh 1,6 lần

Tôi tạo một mảng 20 triệu phần tử của mỗi loại struct, rồi duyệt tuần tự cộng một trường:

struct        kích thước   mảng      thời gian
xấu (40B)     40 byte      800 MB    0,564 ns/phần tử
tốt (24B)     24 byte      480 MB    0,349 ns/phần tử   -> nhanh 1,6 lần
packed (23B)  23 byte      460 MB    0,335 ns/phần tử

Struct thứ tự tốt duyệt nhanh 1,6 lần struct thứ tự xấu — chỉ vì nó nhỏ hơn. Vòng lặp này nghẽn ở băng thông bộ nhớ: mỗi phần tử phải kéo qua cache, và struct 40 byte kéo theo 16 byte padding rác cho mỗi phần tử, nhân 20 triệu là 320MB byte vô dụng phải nạp. Struct 24 byte không mang gánh đó, nên nhanh hơn 1,6 lần dù logic y hệt. Đây chính là bố cục dữ liệu và cache hiện ra qua một quyết định tưởng chừng vô hại: thứ tự khai báo trường.

Đây là chỗ tôi nhầm. Tôi tin "sắp trường thế nào cũng vậy, compiler tự lo". Đo ra sai: thứ tự trường người viết đặt quyết định kích thước, và compiler KHÔNG được đổi thứ tự đó. Chuẩn C bảo đảm các trường nằm trong bộ nhớ đúng thứ tự khai báo (để mã tương thích với bố cục nhị phân, memcpy, ghi ra file), nên compiler chỉ được chèn padding, không được sắp lại trường. Cái mà compiler làm hộ bạn (căn lề) khác hẳn cái nó không được làm (đổi thứ tự) — và cái thứ hai để lại cho bạn.

Nhìn thấy padding trước khi nó cắn

Padding vô hình trong mã nguồn nhưng lộ ra ngay khi bạn hỏi. sizeof(struct) cho tổng, còn offsetof(struct, truong) cho biết mỗi trường bắt đầu ở byte thứ mấy — chênh lệch giữa hai offsetof kề nhau lớn hơn kích thước trường trước chính là padding. Cộng sizeof các trường rồi so với sizeof struct: hiệu số là tổng byte đệm. Ở struct xấu của tôi, các trường cộng lại chỉ 24 byte thật (8+8+4+1+1+1+1) nhưng struct 40 byte — 16 byte kia là padding, gồm cả padding cuối để sizeof chia hết cho căn lề lớn nhất (8) hầu cho một mảng struct giữ mọi phần tử căn lề.

Điều này quan trọng vì trong dự án thật, struct thường ra đời và lớn dần theo thời gian: ai đó thêm một bool cờ ở giữa, một char mã trạng thái ở chỗ tiện tay, và mỗi lần như vậy có thể mở ra một lỗ padding mới mà không ai để ý — cho tới khi một mảng hàng triệu struct đó thành điểm nóng. Kiểm sizeof sau khi sửa struct là một thói quen rẻ để bắt chuyện đó sớm.

Về đến code hằng ngày

Điều đầu tiên là một quy tắc thực dụng: sắp trường struct từ lớn tới nhỏ. Đặt double/long/con trỏ (8 byte) trước, rồi int (4), rồi short (2), rồi char (1) cuối cùng. Cách này gần như luôn cho padding tối thiểu mà không cần suy nghĩ nhiều. Với struct dùng một hai lần thì không đáng bận tâm; nhưng với struct nằm trong mảng lớn được duyệt nóng, đây là 1,6 lần tốc độ miễn phí — không đổi một dòng logic, chỉ đổi thứ tự khai báo.

Điều thứ hai: nhỏ hơn thắng khi nghẽn bộ nhớ, và đó là chủ đề lặp lại. Ở bài căn lề dữ liệu tôi đo được padding thêm để căn lề cache-line làm struct phình và chậm đi; ở đây padding thừa do sắp trường xấu cũng vậy. Hai mặt của một nguyên tắc: với dữ liệu duyệt nhiều, mỗi byte thừa trong một phần tử là một byte phải kéo qua cache nhân với số phần tử.

Và đây là chỗ đáng nhớ, vì bố cục dữ liệu là một trong số ít tối ưu vượt hẳn ra ngoài C, thành quyết định kiến trúc. Điều thú vị: các ngôn ngữ cho phép compiler đổi thứ tự thì tự lo chuyện này giúp bạn — Rust mặc định sắp lại trường để tối thiểu padding (bạn phải #[repr(C)] mới ép giữ thứ tự khai báo), và trình biên dịch Go cũng như nhiều thảo luận cộng đồng khuyến khích xếp trường lớn-tới-nhỏ y hệt. Ở tầng dữ liệu lớn, đây chính là lý do các kho phân tích chuyển sang lưu theo cột (columnar — Parquet, ClickHouse): duyệt một triệu bản ghi để cộng một trường thì lưu-theo-cột chỉ kéo đúng cột đó qua bộ nhớ, không lôi theo mọi trường khác — cùng nguyên lý "đừng nạp byte bạn không dùng", phóng đại lên quy mô terabyte. Ngay cả cache dòng CPU và cache của Redis cũng thưởng cho bản ghi gọn. Mẫu số chung: với dữ liệu duyệt nhiều, kích thước mỗi phần tử là đòn bẩy hiệu năng lớn nhất — và cách rẻ nhất để thu nhỏ nó thường chỉ là sắp lại thứ tự các trường.

Muốn tự thấy thì khai một struct với các trường xen kẽ kích thước: struct { char a; long b; char c; int d; char e; };. In sizeof của nó, rồi in offsetof(struct, b), offsetof(struct, d) để thấy các lỗ padding. Giờ sắp lại struct { long b; int d; char a, c, e; }; và in sizeof lần nữa — bạn sẽ thấy nó nhỏ hơn hẳn, thường 30-40%. Nếu muốn thấy tác động tốc độ, tạo một mảng 10 triệu phần tử của mỗi loại và cộng một trường trong vòng, đo bằng clock_gettime: bản gọn nhanh hơn, vì nó nhỏ hơn nên vào cache tốt hơn. Ba mươi giây đó cho bạn một thói quen đáng giữ: khai trường struct từ lớn tới nhỏ.