Cùng dữ liệu, chỉ xếp lại trong bộ nhớ, một vòng lặp nhanh gấp 4,7 lần

Một lớp học có 40 học sinh, mỗi em một tờ hồ sơ ghi đủ tên, điểm Toán, Văn, Anh, địa chỉ, số điện thoại. Cần xem hồ sơ trọn vẹn một em thì cách xếp "mỗi em một tờ" là tuyệt nhất — rút một tờ ra là có hết. Nhưng nếu bạn phải cộng điểm Toán của cả lớp, cách ấy bắt bạn lật từng tờ, đọc đúng một dòng rồi bỏ qua cả trang còn lại — 40 lần. Lúc đó, một tờ giấy chỉ liệt kê 40 điểm Toán thành một cột lại nhanh hơn hẳn. Đó chính xác là AoS (Array of Structs — mỗi object một khối) đọ với SoA (Struct of Arrays — mỗi trường 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.

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à chỗ tôi suýt hố, và nó có một mặt trái đáng đo tiếp.

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ộ. Điều rút ra: 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ề đến code hằng ngày

Điều đầ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.

Điều 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".

Và đây là chỗ cái tưởng-chỉ-là-mẹo-C hóa ra điều khiển cả những công nghệ bạn dùng hằng ngày. Cơ sở dữ liệu phân tích (ClickHouse, DuckDB, Parquet, Redshift) lưu theo cột — chính là SoA ở quy mô đĩa — nên SELECT AVG(luong) FROM nhan_vien chỉ đọc đúng cột lương, không lôi cả bản ghi; còn cơ sở dữ liệu giao dịch (Postgres, MySQL) lưu theo hàng (AoS) vì chúng thường đọc/ghi trọn một bản ghi. Trong Java, một int[] là SoA thứ thiệt còn List<Point> là AoS đầy con trỏ (mỗi object một lần nhảy heap) — đó là một lý do Java đưa ra record và đang làm Project Valhalla cho "value class" để gói dữ liệu phẳng hơn; Go với struct value trong slice ([]Point) đã cho bạn AoS liền mạch sẵn, và tách thành các slice riêng khi cần SoA. Mẫu số chung: bố cục bộ nhớ là một quyết định hiệu năng thật, không có đáp án chung — chỉ có đáp án đúng cho cách cụ thể bạn đọc dữ liệu.

Muốn tự thấy thì 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. Đế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".