Khi bạn có một triệu "hạt" (particle), mỗi hạt gồm vị trí, vận tốc, khối lượng, màu sắc..., cách tự nhiên nhất để lưu là một mảng các struct: Particle arr[N], mỗi phần tử gói đủ các trường. Đó gọi là AoS (Array of Structs), và nó khớp với cách ta nghĩ về dữ liệu — một object là một khối. Nhưng có một cách khác, lộn ngược: SoA (Struct of Arrays), tách mỗi trường thành một mảng riêng. Chúng chứa cùng dữ liệu, chỉ khác cách xếp trong bộ nhớ. Bài này đo xem cái khác biệt "chỉ là bố cục" ấy đáng giá bao nhiêu — và câu trả lời phụ thuộc hoàn toàn vào một điều ta hay quên hỏi.
Dòng cache không quan tâm bạn dùng bao nhiêu
Nhắc lại một sự thật phần cứng từ bài về cache: CPU không nạp từng byte, mà nạp từng dòng cache — một khối 64 byte. Khi bạn đọc một byte, cả 64 byte quanh nó được kéo về cache. Điều này quyết định toàn bộ câu chuyện AoS/SoA.
Giả sử mỗi hạt là một struct rộng — nói 256 byte (nhiều trường) — và bạn cần cộng một trường của mọi hạt (ví dụ tổng khối lượng). Với AoS, các hạt nằm liền nhau, nên trường khối lượng của các hạt cách nhau 256 byte. Mỗi lần đọc một khối lượng, CPU kéo về một dòng cache 64 byte, nhưng bạn chỉ dùng 8 byte trong đó — phần còn lại (vị trí, vận tốc, màu...) bị kéo về vô ích rồi vứt đi. Với SoA, mọi khối lượng nằm liền trong một mảng riêng, nên mỗi dòng cache 64 byte chứa 8 khối lượng đều dùng được. SoA đọc ít dòng cache hơn hẳn cho cùng công việc. Tôi đo xem khác biệt đó lớn tới đâu, và nó thay đổi thế nào theo bề rộng struct.
Đo: SoA phẳng, AoS phình theo bề rộng
Tôi cộng một trường của hai triệu phần tử, với struct rộng dần từ 16 tới 256 byte:
bề rộng struct AoS SoA AoS/SoA
16 byte 1,1 ms 1,1 ms 1,0×
64 byte 1,8 ms 1,1 ms 1,6×
128 byte 4,9 ms 1,1 ms 4,3×
256 byte 5,3 ms 1,1 ms 4,7×
Đường cong nói rất rõ. Thời gian của SoA phẳng lì ở 1,1 ms bất kể struct rộng bao nhiêu — vì nó luôn đọc đúng một mảng trường liền mạch, không phụ thuộc các trường khác. Thời gian của AoS phình lên theo bề rộng (1,1 → 5,3 ms) — vì struct càng rộng, mỗi dòng cache càng lãng phí nhiều: ở struct 256 byte, cộng một trường 8 byte kéo AoS chậm gấp 4,7 lần SoA. Ở struct nhỏ (16 byte, vừa trong một dòng cache) hai cách bằng nhau vì không có gì để lãng phí. Đây là cú hớ của tôi, và nó có một mặt trái đáng đo tiếp.
Một lần tôi đo hớ: không có bố cục "đúng", chỉ có bố cục hợp cách đọc
Tôi vào bài với thiên kiến rằng AoS là cách "đúng" — nó tự nhiên, gói một object lại thành một khối gọn gàng, khớp với cách con người nghĩ. Đo ra, AoS chậm tới gần năm lần khi ta chỉ dùng một phần nhỏ của mỗi struct. Nhưng trước khi kết luận "vậy SoA luôn tốt hơn", tôi đo trường hợp ngược lại: cộng tất cả các trường của mỗi phần tử (dùng trọn struct):
cộng tất cả 16 trường: AoS 17,2 ms SoA 18,2 ms (AoS nhỉnh hơn)
Ở đây AoS ngang, thậm chí nhỉnh hơn SoA. Vì khi bạn dùng mọi trường, mỗi dòng cache AoS được đọc trọn vẹn — không một byte lãng phí — và các trường của một phần tử nằm sát nhau, đúng lúc bạn cần chúng cùng lúc. SoA lúc này phải nhảy qua 16 mảng riêng, mất một chút lợi thế cục bộ. Bài học đo lường: không có bố cục bộ nhớ "đúng" tuyệt đối — AoS và SoA mỗi cái thắng ở một kiểu truy cập, và mẫu truy cập (bạn đọc dữ liệu thế nào) mới là thứ quyết định, không phải bố cục nào nghe tự nhiên hơn. Dùng vài trường của struct rộng thì SoA; dùng cả object thì AoS. Chọn theo cách bạn đọc, không theo cách bạn nghĩ về dữ liệu.
Có cả đường ở giữa
Đừng nghĩ chỉ có hai lựa chọn cực đoan. Khi một số vòng lặp quét theo trường còn số khác dùng cả object, có bố cục lai AoSoA (Array of Struct of Arrays): chia dữ liệu thành các lô nhỏ (ví dụ 8 phần tử), trong mỗi lô lưu theo SoA, và xếp các lô cạnh nhau. Cách này giữ được tính liền mạch theo trường bên trong một lô (thân thiện cache và vector hóa) mà vẫn gom một cụm phần tử gần nhau. Nhiều engine game và thư viện tính toán hiệu năng cao dùng đúng kiểu này. Điểm mấu chốt không đổi: bố cục là một trục tự do bạn chỉnh được, và chỉnh đúng bắt đầu từ việc đo xem vòng lặp nóng thật sự chạm dữ liệu ra sao — chứ không phải chọn AoS hay SoA vì thói quen.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất cụ thể: khi một vòng lặp nóng chỉ chạm vài trường của một struct rộng, hãy nghĩ tới SoA. Đây là mẫu hình cực phổ biến trong xử lý dữ liệu lớn: một vòng lặp cộng/lọc/biến đổi một cột của hàng triệu bản ghi. Nếu dữ liệu để dạng AoS (mỗi bản ghi một struct nhiều trường), bạn đang kéo tất cả các cột không dùng qua cache. Chuyển cột cần xử lý thành một mảng liền (SoA) có thể nhanh vài lần mà không đổi một dòng logic — chỉ đổi bố cục. Đây là lý do các hệ cơ sở dữ liệu phân tích và thư viện tính toán số học thường lưu dữ liệu theo cột (một dạng SoA).
Hệ quả thứ hai: đừng chọn bố cục dữ liệu theo thẩm mỹ, hãy chọn theo mẫu truy cập nóng nhất. AoS đọc dễ hơn, khớp trực giác hơn, và hoàn toàn đúng khi bạn thường xử lý cả object một lúc (như một trò chơi cập nhật đủ trường của mỗi thực thể mỗi khung hình). SoA khó đọc hơn nhưng thắng khi bạn quét theo trường. Câu hỏi quyết định không phải "cái nào đẹp hơn" mà "vòng lặp tốn nhiều thời gian nhất của tôi chạm những trường nào".
Hệ quả thứ ba là con số mang theo: không có bố cục đúng tuyệt đối — cộng một trường của struct 256 byte, SoA nhanh hơn AoS 4,7 lần (AoS kéo cả struct qua cache mà chỉ dùng một trường), và SoA phẳng theo bề rộng còn AoS phình; nhưng cộng hết mọi trường thì AoS ngang, nhỉnh hơn SoA (dùng trọn dòng cache); mẫu truy cập quyết định bố cục. Bố cục bộ nhớ là một quyết định hiệu năng thật, và nó không có đáp án chung — chỉ có đáp án đúng cho cách cụ thể bạn đọc dữ liệu.
Thử ba mươi giây
Nhìn vòng lặp xử lý dữ liệu nóng nhất của bạn và hỏi: mỗi lần lặp, tôi đọc bao nhiêu phần của mỗi phần tử? Nếu struct của bạn rộng (nhiều trường) mà vòng lặp chỉ đụng một hai trường, bạn đang lãng phí phần lớn mỗi dòng cache — và một bố cục SoA (tách trường đó thành mảng riêng) có thể nhanh vài lần. Cách thử nhanh: đếm kích thước struct của bạn (bằng byte) và số trường vòng lặp thực sự dùng; nếu bạn dùng, chẳng hạn, 8 byte trên một struct 128 byte, bạn đang phí khoảng 15/16 băng thông bộ nhớ ở đúng chỗ nóng nhất. Ngược lại, nếu vòng lặp dùng gần hết mỗi struct, cứ để AoS — nó đã tối ưu. Bố cục đúng không phải cái nghe hợp lý, mà là cái khớp với con số "dùng bao nhiêu trên mỗi dòng cache".
