Bạn có 15 triệu "hạt", mỗi hạt có vị trí, vận tốc, khối lượng, thẻ — tám trường. Cách hiển nhiên là một mảng các struct (AoS): struct Particle { x, y, z, ... } rồi Particle[15tr]. Nhưng có một cách khác: một struct chứa các mảng (SoA) — mỗi trường một mảng riêng: x[15tr], y[15tr], z[15tr]... Cùng dữ liệu, chỉ khác cách xếp trong bộ nhớ. Nhiều người nghĩ đây thuần túy là chuyện tổ chức code, không ảnh hưởng tốc độ. Tôi đo cả hai bố cục trong container gcc:13, và con số cho thấy chỉ đổi cách xếp có thể làm chương trình nhanh hoặc chậm vài lần — theo cả hai chiều.
Cache line quyết định, và bố cục quyết định cache line
Nhớ lại từ phần 1: CPU không đọc từng byte, nó luôn kéo cả một cache line 64 byte mỗi lần chạm bộ nhớ. Câu hỏi sống còn là: 64 byte đó chứa dữ liệu bạn cần, hay phần lớn là thứ bạn không dùng?
Struct Particle của tôi có 8 trường int64 = đúng 64 byte = một cache line.
- AoS (
Particle[N]): các trường của một hạt nằm liền nhau. Nếu bạn chỉ cần trường.xcủa mọi hạt (ví dụ cộng tất cả toạ độ x), thì mỗi lần đọcaos[i].x, CPU kéo về cả 64 byte của hạt đó — nhưng bạn chỉ dùng 8 byte (.x), phí 56 byte (87,5%). Cache và băng thông bộ nhớ bị lãng phí gần hết. - SoA (
x[N], y[N], ...): các giá trị.xcủa mọi hạt nằm liền nhau trong mảngx[]. Đọcx[i]kéo về 64 byte chứa 8 giá trị x — dùng hết. Không phí byte nào.
Vậy khi chỉ đụng một trường, SoA rõ ràng thắng. Nhưng khi bạn đụng mọi trường thì sao? Tôi đo cả ba tình huống.
Đo: SoA thắng 3,6×, rồi AoS thắng 2×
15 triệu phần tử, struct 64 byte (8 trường), g++ -O2:
A. Duyệt CHỈ 1 trường (.x), tuần tự:
SoA : 0,25 ns/phần tử (cache line chứa 8 giá trị x, dùng hết)
AoS : 0,90 ns/phần tử (cache line chứa 1 struct, dùng 8B, phí 87,5%)
-> SoA nhanh hơn 3,6 lần
C1. Duyệt MỌI trường, tuần tự:
AoS : 0,95 ns/phần tử
SoA : 0,89 ns/phần tử
-> ~ngang nhau (cả hai đọc hết dữ liệu, không phí)
C2. Truy cập NGẪU NHIÊN, dùng MỌI trường của mỗi phần tử:
AoS : 14,8 ns/truy cập (1 cache line = cả phần tử = 1 cache miss)
SoA : 28,5 ns/truy cập (8 mảng xa nhau = tới 8 cache miss)
-> AoS nhanh hơn 2 lần
Nhìn A: chỉ đổi bố cục, SoA nhanh hơn AoS 3,6 lần khi duyệt một trường. Đo khớp lý thuyết: AoS phí 87,5% mỗi cache line (dùng 8/64 byte), nên nó phải kéo về gấp ~8 lần lượng dữ liệu để làm cùng việc — và bộ nhớ là nút cổ chai, nên nó chậm ~3,6 lần. Đây là lý do các engine game, hệ thống số học lớn, cơ sở dữ liệu cột (columnar) dùng SoA: khi bạn xử lý một thuộc tính trên rất nhiều phần tử, SoA không phí băng thông.
Nhưng đừng vội kết luận "SoA luôn tốt". Nhìn C1: khi duyệt mọi trường tuần tự, cả hai ngang nhau (0,95 so với 0,89 ns) — vì lúc này cả hai đều phải đọc toàn bộ dữ liệu, không bên nào phí cache line. Và C2 lật ngược hẳn: khi truy cập ngẫu nhiên và dùng mọi trường của mỗi phần tử, AoS nhanh hơn 2 lần (14,8 so với 28,5 ns). Vì với AoS, cả phần tử nằm trong một cache line — một lần chạm ngẫu nhiên = một cache miss mang về đủ 8 trường. Với SoA, 8 trường nằm ở 8 mảng cách xa nhau, nên một phần tử cần tới 8 cache miss riêng biệt. "Locality theo phần tử" của AoS thắng khi bạn dùng cả phần tử một lúc.
Một lần tôi đo hớ: "bố cục không đổi tốc độ" rồi "vậy luôn dùng SoA"
Tôi vào đo với niềm tin đầu: "AoS hay SoA chỉ là cách tổ chức code, dữ liệu như nhau nên tốc độ như nhau". Đo phá tan: chỉ duyệt một trường, SoA nhanh hơn 3,6 lần — vì cache line của AoS phí 87,5%. Bố cục rất ảnh hưởng tốc độ. Nhưng rồi tôi suýt rơi vào đo hớ ngược: "vậy SoA luôn tốt hơn, cứ dùng SoA". Cũng sai — khi truy cập ngẫu nhiên và dùng mọi trường, AoS nhanh gấp đôi, vì một phần tử gọn trong một cache line (1 miss) thay vì rải ra 8 mảng (8 miss). Không có bố cục nào "luôn thắng"; nó phụ thuộc mẫu truy cập.
Bài học đo lường: bố cục dữ liệu (SoA vs AoS) đổi tốc độ NHIỀU LẦN qua cache line, và bên thắng phụ thuộc MẪU TRUY CẬP — duyệt một trường trên nhiều phần tử thì SoA thắng (0,25 vs 0,90 ns = 3,6x, vì AoS phí 87,5% cache line); truy cập ngẫu nhiên mọi trường của một phần tử thì AoS thắng (14,8 vs 28,5 ns = 2x, vì AoS 1 cache line/phần tử = 1 miss còn SoA tới 8 miss); duyệt mọi trường tuần tự thì ngang nhau. Nếu tôi tin "bố cục không quan trọng", tôi bỏ lỡ một tối ưu 3,6 lần miễn phí; nếu tôi tin "luôn dùng SoA", tôi làm chậm gấp đôi những chỗ truy cập theo phần tử.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn bố cục theo cách bạn truy cập dữ liệu nhiều nhất, không theo cách tự nhiên khi khai báo. Nếu vòng nóng của bạn xử lý một thuộc tính trên rất nhiều phần tử (cộng, lọc, biến đổi một trường) — dùng SoA. Nếu nó xử lý từng phần tử với mọi thuộc tính (nhất là truy cập ngẫu nhiên) — dùng AoS. Đây là quyết định hiệu năng thật, không phải phong cách. Data-oriented design trong game engine và cơ sở dữ liệu cột (Parquet, ClickHouse) chính là SoA áp dụng ở quy mô lớn — vì phân tích thường quét một cột trên nhiều dòng.
Hệ quả thứ hai: struct càng lớn (nhiều trường không dùng trong vòng nóng), lợi ích của SoA càng lớn. Đo cho thấy phí 87,5% với struct 64 byte khi chỉ dùng 8 byte; struct lớn hơn thì tỷ lệ phí cao hơn nữa. Nếu bạn thấy một cấu trúc to mà vòng nóng chỉ chạm một hai trường, tách các trường nóng ra mảng riêng (SoA một phần) là một tối ưu cache mạnh. Ngược lại, nếu vòng nóng dùng mọi trường cùng lúc, giữ chúng liền nhau (AoS).
Hệ quả thứ ba là tinh thần đo lường: "cùng dữ liệu" không có nghĩa "cùng tốc độ" — cách xếp trong bộ nhớ đổi hiệu năng qua cache. Con số mang theo: bố cục SoA (mỗi trường 1 mảng) vs AoS (mảng struct) đổi tốc độ nhiều lần: duyệt 1 trường trên 15tr phần tử SoA 0,25 ns vs AoS 0,90 ns = SoA 3,6x (AoS phí 87,5% cache line 64B, dùng 8/64 byte); truy cập NGẪU NHIÊN mọi trường AoS 14,8 ns vs SoA 28,5 ns = AoS 2x (1 cache line/phần tử = 1 miss vs 8 mảng = 8 miss); duyệt mọi trường tuần tự ~ngang. Chọn bố cục theo MẪU truy cập, không có 'luôn tốt hơn'. Cache line 64 byte là đơn vị thật, và bố cục quyết định 64 byte đó chứa gì.
Thử ba mươi giây
Định nghĩa một struct vài trường (ví dụ 8 số), tạo một mảng vài triệu struct (AoS) và tách riêng thành các mảng từng trường (SoA). Rồi đo hai việc: cộng một trường trên tất cả phần tử, và làm gì đó với mọi trường của từng phần tử. Bạn sẽ thấy SoA thắng đậm ở việc thứ nhất (cache line không phí), còn khi dùng mọi trường thì khoảng cách biến mất — và nếu bạn thêm truy cập ngẫu nhiên, AoS vượt lên (một cache miss mang về cả phần tử thay vì tám). Ba mươi giây đó cho bạn thấy điều mà "chỉ là cách tổ chức" giấu đi: bố cục bộ nhớ không phải thẩm mỹ code — nó quyết định mỗi cache line 64 byte chứa dữ liệu bạn cần hay rác, và đó là khác biệt vài lần về tốc độ. Cùng dữ liệu, khác cách xếp, khác tốc độ.
