Đừng truyền struct lớn hơn 16 byte trên AMD64

• Việc Neat tăng hạng trong benchmark related_post_gen không đến từ tối ưu hóa cấp cao mới, mà từ một thay đổi ABI nhỏ: truyền mảng dưới dạng 3 đối số con trỏ thay vì struct 24 byte
• Do dùng đếm tham chiếu, mảng của Neat ngoài con trỏ đầu/cuối còn cần một con trỏ dựa trên đối tượng mảng; vì vậy khác với mảng 16 byte của D, nó đi vào nhánh truyền qua bộ nhớ của SystemV AMD64 ABI
• Một số aggregate lớn hơn 16 byte khi gọi hàm sẽ bị sao chép giá trị lên stack rồi truyền bằng con trỏ, làm mất lợi thế truyền bằng thanh ghi và tăng chi phí xáo trộn stack
• Trong benchmark ví dụ, truyền struct Vector { double x, y, z; } dưới dạng struct khiến 1 tỷ lần chạy mất 12,3 giây, còn truyền từng trường như các đối số riêng thì giảm xuống 5,3 giây
• C API phải tuân theo C ABI, nhưng với các kiểu như mảng, tuple, sumtype bên trong runtime ngôn ngữ, nếu vượt quá 16 byte thì đáng để benchmark cách tách trường khi truyền

---

Nút thắt cổ chai lộ ra trong Neat

• Neat đã tăng vài bậc trong benchmark related_post_gen
• Mức tăng hiệu năng không đến từ một pass tối ưu hóa cấp cao mới, mà là kết quả của việc thay đổi cách truyền mảng
  • Trước đây: đối số struct chứa 3 con trỏ
  • Sau thay đổi: truyền 3 con trỏ như các đối số riêng biệt
• So với D, Neat chậm hơn dự kiến, và profiler cho thấy việc di chuyển một vùng lớn trên stack để gọi hàm
• Nút thắt gần với chi phí sắp xếp lại stack tại thời điểm gọi hơn là bản thân phép tính

Vì sao mảng của Neat thành 24 byte

• Khác với mảng của D, Neat dùng đếm tham chiếu
• Mảng của Neat gồm 3 con trỏ sau
  • Con trỏ bắt đầu
  • Con trỏ kết thúc
  • Con trỏ dựa trên đối tượng mảng nơi lưu bộ đếm tham chiếu
• 3 con trỏ là 24 byte, nên khác với mảng 16 byte gồm 2 con trỏ, nó đi theo con đường khác trong quy tắc truyền đối số của AMD64
• Lý do mảng D nhanh còn mảng Neat chậm là vì ở 24 byte, nó đã vượt qua ranh giới 16 byte

Ranh giới 16 byte trong SystemV AMD64 ABI

• Đặc tả SystemV AMD64 ABI quy định rằng nếu kích thước của một aggregate nhất định vượt quá hai eightbyte thì toàn bộ đối số sẽ được truyền qua bộ nhớ
• Để truyền một struct qua bộ nhớ, phía gọi phải làm các việc sau
  • Cấp phát trên stack một vùng có kích thước bằng struct
  • Điền giá trị cần truyền vào vùng đó
  • Truyền cho hàm một con trỏ tới vị trí của struct đó
• Trong trường hợp này, giá trị bắt buộc phải nằm trên stack, nên LLVM có rất ít chỗ để tối ưu
• Giá trị phải được sao chép từ thanh ghi xuống stack, đồng thời còn phải theo dõi phần nào của stack đang được dùng và phần nào có thể tái sử dụng
• Chính ở việc theo dõi tái sử dụng stack này mà LLVM thể hiện không tốt

Benchmark vector 3 double

• Benchmark dùng vector 3 trường có dạng struct Vector { TYPE x, y, z; };
• TYPE được định nghĩa là double
• Hai hàm thực hiện cùng một phép cộng nhưng khác cách truyền đối số
  • vector_add_struct(struct Vector left, struct Vector right) nhận struct lớn làm đối số
  • vector_add_fields(...) nhận left_x, left_y, left_z, right_x, right_y, right_z như các đối số riêng
• mode và thời lượng chạy được nhận từ đối số dòng lệnh để trình tối ưu hóa không thể constant-fold toàn bộ phép tính
• impl.c được biên dịch riêng để tránh inline

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Kết quả là bản truyền struct mất 12,3 giây, còn bản truyền từng trường riêng chỉ mất 5,3 giây

Khác biệt thấy được trong assembly

• Bản truyền struct dùng rất nhiều lệnh cho việc xáo trộn stack
• Bản truyền theo trường có lợi thế vì các tham số đã nằm sẵn trong thanh ghi SSE khi vào hàm
• Bản truyền struct phải nạp giá trị từ stack ở mỗi lần gọi
• SystemV ABI được thiết kế để cố gắng truyền giá trị bằng thanh ghi tối đa có thể, nhưng trong trường hợp này lợi thế đó biến mất vì struct vượt quá 16 byte
• Xét đến số lượng thanh ghi có thể dùng trên AMD64, tác giả cho rằng việc truyền theo giá trị vẫn sẽ hữu ích ngay cả với các kiểu lớn hơn 16 byte

Tình huống trở nên giống cdecl

• Cách ghi các trường xuống stack rồi truyền con trỏ về bản chất khiến mọi thứ trở nên giống ABI cdecl cũ của x86, nơi mọi thứ đều được truyền qua stack
• cdecl vốn nổi tiếng là chậm, và nhiều calling convention đã ra đời để làm nó nhanh hơn
• Vấn đề ở đây là System V ABI trên AMD64, vì kích thước struct, lại hành xử giống kiểu truyền qua stack cũ trong trường hợp này

Ngoại lệ của inline và LTO

• Trong mã thực tế, những hàm như vậy có thể đều được inline
• Khi bật LTO trong gcc, chênh lệch hiệu năng giữa hai phiên bản biến mất
• Với clang thì không cho ra cùng kết quả
• Không phải mọi hàm đều có thể hoặc nên được inline

Lời khuyên cho người triển khai ngôn ngữ và tối ưu hóa API

• Khi gọi C API thì phải tuân theo C ABI
• Tuy nhiên, với các kiểu cấp cao bên trong ngôn ngữ không phải C, dù backend nhìn chúng như struct thì cũng không nhất thiết phải biểu diễn chúng thành một struct duy nhất
• Người triển khai ngôn ngữ có thể tự quyết định cách truyền mảng, tuple, sumtype...
• Trong Neat, tác giả chọn truyền những kiểu như vậy vượt quá 16 byte dưới dạng các trường riêng, và benchmark cho thấy có lợi
• Nếu bạn đang triển khai ngôn ngữ trên AMD64 hoặc tinh chỉnh vi mô API, hãy benchmark xem việc tự tay tách các struct lớn hơn 16 byte có giúp ích không
• Đặc biệt trong vòng lặp nội bộ, chênh lệch hiệu năng có thể lớn hơn dự đoán

Bổ sung: struct double và SSE

• Câu hỏi được đặt ra là double theo đặc tả thuộc lớp SSE, vậy vì sao struct lại không được truyền qua thanh ghi SSE
• Câu trả lời là tác giả cũng không rõ nguyên nhân, nhưng trên thực tế nó không được truyền như vậy

[GN⁺]

Các ý kiến trên Hacker News

• Vấn đề ở đây là SysV amd64 ABI. Không nhất thiết phải dùng SysV làm ABI nội bộ của ngôn ngữ. Nếu không phơi bày cho bên gọi SysV C thì có thể dùng quy ước gọi tùy ý
  https://llvm.org/docs/LangRef.html#calling-conventions
  Với ai tò mò, thay đổi liên quan của neatlang ở đây: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Có vẻ phức tạp hơn nhiều so với việc chỉ đổi đầu ra quy ước gọi của LLVM. Có lẽ tác giả muốn phơi bày các kiểu này cho chương trình C với một quy ước gọi xác định

  • Thực ra có thể nói ABI nói chung đều như vậy. Nếu là lập trình viên assembly thì sẽ biết đây là một trong những “quả ngọt treo thấp”, nơi bạn có thể dễ dàng đánh bại trình biên dịch
    Đừng mù quáng làm theo thông lệ; hãy chọn cách hợp lý nhất trong tình huống cụ thể
  • Câu hỏi đầu tiên nảy ra trong đầu đã có câu trả lời. Thật thú vị khi nhiều thứ vẫn tuân theo các ABI được tạo ra từ rất lâu trước đây
    Đặc biệt, ABI thường nghiêng về khả năng tương thích với CPU cũ hơn, trong khi CPU mới hơn có thể còn dư địa cải thiện bằng các tính năng như thanh ghi mở rộng mà không cần giảm kích thước cấu trúc. Phần mềm nhắm riêng vào phần cứng hay một thế hệ nhất định sẽ không chạy được trên một số máy nên không hấp dẫn lắm, nhưng sẽ rất tuyệt nếu có trình biên dịch có thể tạo ra đầu ra như vậy khi bạn muốn tối ưu mã đến cực hạn theo khả năng phần cứng của hệ thống mình

• Chi phí truyền đối số thường không được hiểu rõ, nên những bài viết như thế này rất đáng mừng. Ngay cả ở những nơi như Google, việc truyền đối tượng 24 byte theo giá trị cũng phổ biến, và chi phí của nó trải rộng trên mọi hàm nên khó hiện rõ trong profiler

  • Truyền theo giá trị và truyền theo tham chiếu trên thực tế ảnh hưởng đến ABI/API, nên tạo ra gánh nặng nhận thức khá lớn. Zig cố gắng không ép buộc điều này, nên dù “truyền theo giá trị”, trình biên dịch vẫn có thể quyết định thực tế truyền bằng tham chiếu
    Tuy nhiên cũng lộ ra những điểm vướng víu như thế này: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Những nơi như Google” là chuyện bạn tự trải qua à? Với tư cách cựu Googler, tôi có thể nói chắc rằng có guideline yêu cầu truyền những thứ không phải kiểu nguyên thủy bằng con trỏ hoặc tham chiếu
    Ngoại lệ duy nhất tôi nghĩ tới là khoảng string_view
  • Việc chỉ ra rằng overhead phân tán rộng như thứ được nhúng vào quy ước gọi gần như không thể tìm ra bằng profiling là rất hay
  • Nếu thay vào đó truyền đối tượng 24 byte bằng con trỏ, đánh đổi là khi thực sự cần dùng đối tượng đó, bạn phải dereference con trỏ. Nhưng không có gì đảm bảo đối tượng đó nằm gần
    Nếu không may, có thể bị cache miss và phải đợi khoảng 100 ns để lấy đối tượng 24 byte từ bộ nhớ chính. Nếu truyền trực tiếp cùng đối tượng đó thì nó nằm trên stack, nên nhiều khả năng có trong cache hơn
  • Tôi tò mò không biết C++ ABI có cũng làm tràn đối tượng 24 byte xuống stack ở mỗi lời gọi không. Tôi không kỳ vọng tham số std::string hay std::function sẽ nhanh, nhưng vẫn thấy ngạc nhiên

• Khi lần đầu chuyển sang x64, tôi rất lo việc đối tượng vec3 trong đồ họa (3 float) phình từ sizeof()=12 lên 16 byte, nên đã benchmark engine đồ họa rất nhiều
  Không ngạc nhiên là nhờ căn chỉnh đọc 8 byte, 16 byte nhanh hơn 12 byte. Cả nội bộ lẫn trên GPU đều vậy. Vì thế vec3 lặng lẽ trở thành vec4, và vec4 riêng vẫn tồn tại. Như mọi khi, phải benchmark theo góc nhìn tổng thể, chứ không phải benchmark cục bộ

  • Có một hiệu ứng phụ rất tốt là nó cũng khớp với kích thước SSE. Vì vậy có thể dùng trực tiếp _mm_load_ps, mã sạch hơn và vector hóa cũng dễ hơn rất nhiều
  • Có lẽ không nhanh hơn quá nhiều. Và tôi nghĩ điều đó còn phụ thuộc rất nhiều vào CPU, chưa kể bạn làm gì với dữ liệu này
    Tôi hiểu rằng với 16 byte, nhiều truy cập có thể trở thành 2x8 byte được căn chỉnh hoặc 1x16 byte thay vì 3x4 byte. Nhưng với các kiểu truy cập khác thì có thể ít đúng hơn, và còn vấn đề tăng áp lực cache
  • x64 ABI cũng khá hơn x86 ABI đáng kể

• Theo lẽ thường, giá trị truyền qua thanh ghi có thể được nạp trước nhờ speculative execution nên nhanh hơn ghi vào stack, còn thao tác với stack thì nhanh hơn cấp phát heap
  Vì vậy mã spaghetti bừa bộn với đầy biến toàn cục lại cực nhanh, còn các hàm đệ quy thanh lịch hoặc đối số tuple/struct/list thì chậm đến khó tin. Loại trước dễ tối ưu thành vòng lặp assembly cô đọng hơn nhiều

  • Tất nhiên phải giả định rằng mã spaghetti đó triển khai cùng thuật toán với mã thanh lịch
    Nếu mã thanh lịch là O(n) còn mã spaghetti là O(n^2) thì bạn có thể cảm nhận được khác biệt. Cũng phải tính đến bảo trì. Theo một nghĩa nào đó, trình biên dịch tồn tại để biến lời giải thanh lịch của chúng ta thành mã spaghetti
  • “Hãy truyền tham số qua thanh ghi chứ không phải stack” gần như là lẽ thường, nhưng “tham số lớn hơn 16 byte luôn được truyền qua stack” thì không hiển nhiên đến vậy
  • Một số CPU ngày nay có thể làm memory renaming, nên chi phí spill xuống stack có thể rẻ hơn
    Đối tượng toàn cục cũng cản trở tối ưu hóa của trình biên dịch

• Nhân tiện, trong MSVC, kích thước ngưỡng là 8 byte trước khi struct được truyền qua stack. Đây là chi tiết ABI nên không nên dựa vào trong mã cần portable
  Nhưng nếu hàm không được gọi thường xuyên thì cũng không cần quá căng thẳng. Nếu là hàm nhỏ được gọi thường xuyên như trong ví dụ, hãy để trình biên dịch có thể inline mã bằng các cách như LTO. Khi đó sẽ mở ra nhiều tối ưu hữu ích hơn nhiều so với việc truyền đối số qua thanh ghi

• Tôi xếp những bài kiểu này vào loại “biết vừa đủ để thành rắc rối”. Ngay cả khi làm đúng như hướng dẫn, biên dịch riêng để ép trình biên dịch tạo ra hàm có thể được gọi theo ABI, LTO vẫn có thể đảo ngược lỗi này
  Nếu build chương trình này với LTO, ở cả hai chế độ nó sẽ nhanh hơn đáng kể so với bất kỳ chế độ nào của chương trình không dùng LTO. Với chương trình nhạy cảm về hiệu năng, hãy profile, tối ưu nút thắt đến cực hạn, rồi sau đó mới commit kiểu việc tách struct thành các đối số

  • Lời khuyên hay, nhưng tôi chưa thấy trình biên dịch nào làm lộ ra loại vấn đề này. Trước hết nó nằm rải rác khắp codebase, và nếu không may trở thành hotspot thì cũng chưa thấy profiler nào chỉ ra được tác động của nó
    Điều này áp dụng cho gần như mọi mã do trình biên dịch sinh ra. Valgrind có thể đo được, nhưng profiler lấy mẫu thì có lẽ không, và cũng không có công cụ nào nhấn mạnh các vấn đề sinh mã nằm rải rác
  • Hơn nữa, họ nói hiệu năng là tối quan trọng nhưng lại dùng reference counting

• Trong quy ước gọi cdecl mặc định của Windows, struct lớn hơn 8 byte không được truyền qua thanh ghi [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• Trên amd64, ngay cả khi dùng SysV amd64 ABI, việc truyền và trả về struct lớn hơn 16 byte theo giá trị là hoàn toàn có thể. Chỉ là chậm thôi
  Dù vậy, trong nhiều trường hợp truyền theo giá trị đáng giá vì làm mã rõ ràng hơn. Tất nhiên không phải trường hợp này, nhưng như loeg đã chỉ ra, bên trong ngôn ngữ của chính mình thì có thể dùng ABI tùy chỉnh, giống các trình biên dịch C++, Go, OCaml, SBCL

• Trong ví dụ được đưa ra, có thể sửa bằng cách đổi kiểu tham số từ “struct Vector” sang “const struct Vector &” để truyền theo tham chiếu mà không ảnh hưởng đến bên gọi
  Tôi đã thấy nhiều mã C++ có lỗi con trỏ vì dùng con trỏ không cần thiết, trong khi truyền theo tham chiếu là đủ và dễ dùng, an toàn hơn

  • Không. Thực ra đó chính là vấn đề cốt lõi ở đây. Nhờ ABI, trình biên dịch về cơ bản đã làm đúng việc đó
    Vì ABI yêu cầu truyền giá trị bằng con trỏ, nên phải lưu nó ở đâu đó để lấy con trỏ, và điều tương tự xảy ra như khi khai báo const-ref. Nếu đổi giá trị struct thành các đối số riêng lẻ thì có thể truyền đối số qua thanh ghi
  • Khi phát hiện vấn đề này, đó là đoạn mã có đến hai mươi hay ba mươi alloca chỉ để truyền con trỏ cho byval. Mọi hàm đều bắt đầu bằng một alloca riêng cho từng tham số được truyền vào lời gọi
    Tôi vẫn phần nào luôn giả định LLVM sẽ dọn dẹp tốt những thứ như vậy, nhưng hóa ra không phải
  • Tuy vậy, để truyền con trỏ struct cho hàm được gọi, trình biên dịch vẫn phải tuần tự hóa ba thanh ghi xuống stack
    Lợi ích được mô tả là hoàn toàn tránh việc tuần tự hóa từ thanh ghi xuống stack, còn truyền theo tham chiếu thì có vẻ không tránh được
  • Đây là ví dụ C99, không phải C++. Trong nhiều môi trường, chỉ vì quán tính tối thiểu mà không thể tùy ý thay đổi công cụ
    Nếu cho phép C++ thì sẽ có thêm nhiều lựa chọn như đối số move để giảm sao chép

• Kinh nghiệm truyền miệng tôi luôn nghe trong C++ là: thứ gì không phải kiểu nguyên thủy thì truyền bằng tham chiếu, trừ khi có lý do chính đáng để truyền theo giá trị; còn khi thật sự cần thì truyền bằng con trỏ
  Một phần là vì ABI, một phần là để tránh copy constructor hoặc move constructor. Đây là chi tiết cấp thấp nhàm chán, nhưng nếu muốn hiệu năng tối đa trong C++ thì phải để ý. Nói rõ ra, đây chỉ là tối ưu hiệu năng; mã truyền struct vẫn chạy đúng, chỉ là kém nhanh hơn thôi