Mảng enum tiết kiệm bộ nhớ trong Zig

 (alic.dev)
3 điểm bởi GN⁺ 2023-09-19 | 1 bình luận | Chia sẻ qua WhatsApp
  • Khi lưu trữ số lượng lớn enum/tagged union có các variant kích thước khác nhau, chi phí padding và phân mảnh trong Vec·HashMap tăng mạnh vì phải dành chỗ theo variant lớn nhất
  • Zig có thể dùng comptime và phản chiếu kiểu để kiểm tra kích thước trường, căn chỉnh và discriminant, rồi biến đổi container enum một cách generic theo bố cục bộ nhớ
  • Vec<Enum> đơn giản khiến mỗi phần tử dùng không gian bằng kích thước variant lớn nhất; SoA giảm được padding của tag nhưng vẫn còn phân mảnh variant ở vùng giá trị
  • Dense AoVA nhóm các variant cùng kích thước có thể giảm 15 vector xuống còn 3 cụm 2·4·8 byte trong enum ví dụ, nhưng khi nhiều variant nằm chung một allocation thì việc duyệt kiểu-an-toàn trở nên khó hơn
  • Proc macro của Rust khó truy cập thông tin kích thước và căn chỉnh kiểu, đồng thời cũng bị hạn chế khi tính độ dài mảng generic, nên cơ chế staging nhận thức kiểu của Zig thể hiện rõ hơn tính kết hợp của hiệu quả bộ nhớ trong mã hệ thống

Rust lãng phí không gian với mảng enum như thế nào

  • Enum/tagged union có các variant kích thước khác nhau phải dành đủ bộ nhớ để chứa được variant lớn nhất
  • Enum ví dụ Foo có các variant u8, u16, u32, u64, và do tag cùng căn chỉnh nên kích thước kiểu trở thành 16 byte
  • Khi đưa nhiều enum như vậy vào Vec hay HashMap, mỗi phần tử sẽ chiếm không gian theo variant lớn nhất, làm tăng padding và phân mảnh
  • Chuyển sang struct of arrays(SoA) bằng cách đặt tag ở allocation riêng có thể giảm một phần padding, nhưng không loại bỏ được phân mảnh ở vùng giá trị do chênh lệch kích thước variant
  • Trong Rust cũng có thể tự làm cấu trúc dữ liệu cho một enum cụ thể, nhưng để tạo một cấu trúc dữ liệu generic tối ưu bộ nhớ nhất có thể cho enum bất kỳ thì rất khó, gần như bất khả thi
    • Proc macro khó gắn #[derive] vào kiểu của bên thứ ba hoặc type alias, và tính kết hợp thấp
    • Nó không có nhận thức kiểu; các cách lách dựa trên generic_const_expr làm các mệnh đề where dài dòng lan khắp call graph và không hợp với generic type parameter

Vì sao vấn đề đặc biệt rõ trong AST của trình biên dịch

  • Một động lực lớn để làm mảng enum hiệu quả là lượng bộ nhớ mà AST của trình biên dịch tiêu thụ
  • AST lớn gây ra độ trễ bộ nhớ và cache eviction trong lúc biên dịch, tạo chi phí lớn cho hiệu năng frontend
  • Trong video về Carbon compiler của Chandler Carruth, AST của clang sau khi parse thường tiêu tốn bộ nhớ gấp 50 lần mã nguồn gốc
  • Ví dụ biểu diễn node biểu thức trong Rust được cấu thành bằng enum Expr
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • OCaml có thể biểu diễn kiểu dữ liệu đệ quy mà không cần indirection tường minh vì hệ runtime và GC đảm nhận việc quản lý bộ nhớ
  • Vec<Expr> trong Rust khiến mọi phần tử đều dùng không gian bằng sizeof(Enum), bao gồm kích thước của variant lớn nhất, tag và padding

Giảm phân mảnh bằng SoA và AoVA

  • Khi một enum 3-variant đơn giản có các phần tử 8, 16, 32 bit, Vec thông thường phải dành nhiều chỗ cho mọi phần tử để phù hợp với variant 32 bit và yêu cầu căn chỉnh
  • Một cách cải tiến phổ biến là giữ bản thân enum variant thật nhỏ bằng tagged index hoặc kỹ thuật tương tự
    • Crate tagged_index của Rust compiler
    • Các trường hợp tối ưu small-string
    • Đây là tối ưu thường gặp trong mã hiệu năng cao như runtime ngôn ngữ, GC, trình biên dịch, game engine và kernel hệ điều hành
  • Cũng có thể đổi container sang kiểu SoA lưu discriminant và giá trị ở các allocation riêng
    • Trình biên dịch Zig self-hosted dùng cách này
    • Nó giảm padding do tag tạo ra, nhưng collection giá trị union vẫn còn phân mảnh variant
  • Cơ chế staged compilation của Zig cho phép tạo container generic thực hiện biến đổi SoA với kiểu bất kỳ
  • Rust phải dựa vào proc macro như soa_derive, và bị giới hạn ở chỗ không thể thêm #[derive] mà không sửa mã nguồn của kiểu bên thứ ba

Mảng theo variant và gom cụm theo kích thước

  • Để giảm thêm phân mảnh ở vùng giá trị, có thể dùng một vector cho mỗi variant
  • Khi chèn phần tử, hàm sẽ trả về một tagged index chứa cả tag của enum lẫn chỉ số trong mảng của variant tương ứng
  • Mô hình này được gọi là array of variant arrays(AoVA)
  • AoVA có thể được hiện thực bằng proc macro trong Rust và bằng comptime trong Zig
  • Nếu có nhiều variant và nhiều variant cùng kích thước, số lượng vector theo-variant có thể tăng quá nhiều
    • Enum ví dụ Foo có 15 variant
    • Cách một vector mỗi variant sẽ thêm 15 vector
    • Số lần realloc và system call có thể tăng, và có thể cần nhiều bộ nhớ hơn cho amortization so với Vec ngây thơ
    • Các vector có thể nằm rải rác ngẫu nhiên trong bộ nhớ, làm tăng khả năng xung đột cache
    • Bản thân container AoVA cũng dùng nhiều bộ nhớ, có thể làm phình struct chứa nó
  • Nếu gom theo kích thước, enum ví dụ sẽ được chia thành ba cụm 2 byte, 4 byte, 8 byte
    • c_2: Vec<[u8; 2]> lưu từ A đến D
    • c_4: Vec<[u8; 4]> lưu từ E đến I
    • c_8: Vec<[u8; 8]> lưu từ J đến O
  • Cách dense AoVA có thể giảm tổng số vector tới 80%
  • Nhưng khi đặt các variant khác nhau vào cùng một allocation, việc duyệt vector theo cách kiểu-an-toàn trở nên khó khăn
    • Việc truy cập chỉ có thể thực hiện qua tagged pointer được tạo lúc chèn
    • Với cấu trúc cây dựa trên flattened index không cần blind iteration, đây có thể là một trade-off chấp nhận được
  • Nếu cần duyệt kiểu-an-toàn, có thể chấp nhận chi phí padding và thêm lại tag
  • Nếu padding quá lớn, có thể áp dụng biến đổi SoA cho từng mảng variant, nhưng khi đó số vector sẽ tăng gấp đôi

comptime của Zig tạo ra tính kết hợp về bố cục bộ nhớ

  • Nguyên mẫu Zig được triển khai trong osmium
  • Cốt lõi là phản chiếu lúc biên dịch thông qua built-in của compiler để kiểm tra kiểu trường, kích thước byte, kích thước bit và discriminant
  • Mã ví dụ dùng @typeInfo(inner) để kiểm tra loại kiểu và chỉ xử lý khi đó là union
    • Duyệt qua các field của union
    • Tính không gian cần thiết bằng @max(field.alignment, @sizeOf(field.type))
    • Lưu thông tin kích thước vào vector cấp phát trên stack
    • Xây dựng ánh xạ từ field của union sang chỉ số cụm
    • Nếu không phải union thì phát sinh compile error
  • Đoạn mã chính xác có trong mã nguồn này
  • Việc tạo ví dụ tương tự bằng proc macro của Rust về cơ bản là không thể
    • Proc macro không truy cập được thông tin size hay alignment của kiểu
    • Có thể tạo const fn tính cụm cho một enum cụ thể, nhưng không thể dùng nó để chỉ định độ dài mảng của kiểu generic
  • Trong Rust, việc hiện thực generic container khó có thể thay đổi điều kiện theo việc kiểu được cho là enum hay struct
  • Trong Zig, về mặt khái niệm có thể chọn giữa EfficientEnumArray<T> và EfficientStructArray<T> tùy theo T.isEnum()
  • Việc hiện thực AoVA cũng có thể được chọn dựa trên đặc tính của enum
    • Ví dụ có thể chuyên biệt theo kiểu chỉ coi việc đặt nhiều variant khác nhau chung chỗ là có ý nghĩa khi nó giảm số vector xuống hơn 90%
  • Nếu biết capacity tối đa ở thời điểm biên dịch, hàm tạo kiểu có thể quyết định bitwidth cần thiết cho tagged index
  • Khi tagged index này lại được nhúng vào cấu trúc dữ liệu khác, ví dụ bên trong một enum khác, các bit còn dư có thể dùng cho discriminant
  • Zig cho phép chỉ định chính xác số bit cần thiết, để các phần khác của mã tự nhiên tận dụng thông tin đó và tạo ra hiệu quả bộ nhớ có tính kết hợp
  • Nhờ implicit widening integer coercion, khả năng sử dụng vẫn được giữ nguyên ngay cả khi làm việc với API có bitwidth khác nhau
  • Với một ngôn ngữ lập trình hệ thống coi trọng hiệu quả và zero-cost abstraction, staged programming — đặc biệt là comptime của Zig — là thứ đáng để nhìn lại

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-19
Các ý kiến trên Hacker News

  • Có một chiến lược khác vừa hiệu quả về lưu trữ vừa vẫn giữ được việc duyệt qua các phần tử. Vector thứ nhất là danh sách tag, vector thứ hai là offset byte của từng phần tử, còn vector thứ ba, đúng hơn không hẳn là vector, là dữ liệu variant đã được nén mà vector thứ hai trỏ tới
    Cách này dùng số vector chỉ bằng một nửa so với giải pháp cuối cùng của tác giả (6 so với 3), không lãng phí byte padding trừ khi cần vì lý do căn chỉnh, và dữ liệu được đặt tuần tự trong bộ nhớ bất kể kiểu nên có thể duyệt thân thiện với cache. Cũng có thể truy cập O(1) vào phần tử bằng index. Nhìn chung, với dữ liệu dị thể, nó có các đặc tính hiệu năng tương tự Vec

    • Lưu offset byte inline là một ý tưởng hay. Tuy nhiên, nếu offset được lưu trong bộ nhớ thì quá trình duyệt sẽ phát sinh phụ thuộc dữ liệu, nên dù thân thiện với cache, nó vẫn có thể gây nghẽn bộ nhớ nghiêm trọng trong pipeline của bộ xử lý
    • Nếu cần thay đổi collection kiểu này, cuối cùng rất có thể bạn sẽ phải tự dùng bộ cấp phát bộ nhớ để xử lý xóa, thay đổi sang variant lớn hơn và phân mảnh
    • Nếu không tối ưu kích thước offset, nó có thể chiếm khá nhiều dung lượng so với T nhỏ. Ví dụ như tổ hợp size_t 64-bit với uint8_t T; chỉ cần cẩn thận với kích thước offset thì đây có vẻ là một cách tiếp cận hợp lý

  • Tôi tò mò cấu trúc dữ liệu AoVA này thực tế hoạt động ra sao. Từ góc nhìn mảng, có phải ta sẽ mất truy cập dựa trên index, vì số học index có thể không còn ý nghĩa nữa? Việc duyệt cũng có vẻ sẽ không bảo toàn thứ tự chèn
    Trong ngữ cảnh này, tôi nghĩ TLV(tag-length-value), với đặc tính cache tốt hơn, được dùng phổ biến hơn. Độ dài có thể được ngụ ý bởi tag, và ít nhất nó cung cấp khả năng duyệt tiến có ý nghĩa. Hãy xem getdents, inotify, thông điệp Netlink

    • Nhìn chú thích của Hình 4, có thể xem mẫu AoVA không phù hợp lắm khi cần duy trì toàn bộ thứ tự của các phần tử được chèn
      So với layout SoA trước đó, nó tạo ra thứ tự cục bộ chứ không phải thứ tự toàn cục. Khi chèn, cấu trúc sẽ trả về một index có tag, chứa cả tag enum lẫn index bên trong mảng variant tương ứng. Vì vậy truy cập theo thứ tự dường như nằm ngoài phạm vi ở đây. Nếu lưu index toàn cục cho từng phần tử thì có thể khôi phục việc duyệt có thứ tự, nhưng nó vẫn không giúp ích cho truy cập ngẫu nhiên có thứ tự, và nhiều khả năng mã sẽ có khá nhiều nhánh
    • “Tag enum và index bên trong mảng variant tương ứng” được trả về khi chèn về bản chất là con trỏ. Nếu muốn duyệt, hãy lưu các con trỏ vào một mảng theo thứ tự sử dụng mong muốn. Điều này giống những gì một chương trình cấp phát bộ nhớ trên heap vẫn làm
      Cách lưu vật theo kích thước cũng được dùng trong garbage collector và bộ cấp phát đa dụng. Có thể đạt hiệu quả nhờ biết trước tất cả kích thước đối tượng khả dĩ, và cũng có thể đạt hiệu quả bằng cách giải phóng đơn giản hơn như arena
    • Việc AoVA không có thứ tự toàn cục riêng cho các index có thể là vấn đề trong một số trường hợp sử dụng, nhưng với node AST được đề xuất ở đây thì không nhất thiết là vấn đề
      Trong trường hợp này, các mảng có thể được xem là một thành phần của cấu trúc giống heap, tức giống arena. Cái giá là index phải trở thành hai chiều, như (tag_idx, va_for_tag_idx). Nhưng vì số lượng tag đã biết tại thời điểm biên dịch, có thể tối ưu lưu trữ bằng cách đóng gói tag_idx vào 4–5 bit cao và để va_for_tag_idx dùng phần còn lại. Tham khảo: https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • Việc ghi vào mảng làm thay đổi kiểu của index có vẻ sẽ cực kỳ đắt

  • Hơi tiếc là pattern matching của Rust không thể được biểu diễn nhiều hơn dưới dạng một thứ giống trait trong hệ thống kiểu mà bất kỳ struct nào cũng có thể tuân theo, thay vì là một kiểu object hạng nhất, tường minh, được hard-code và có cấu trúc lưu trữ riêng
    Gần đây tôi cũng đã triển khai AST như bài này và cả một trình thông dịch opcode/bytecode, và tôi cảm thấy enum của Rust không thật sự lý tưởng hoàn toàn cho cả hai. Với AST, tôi muốn gắn thuộc tính số dòng/cột cho mọi node statement, nhưng nếu đưa dòng/cột vào mọi trường hợp của enum Stmt thì boilerplate rất rối; còn nếu bọc enum bằng một struct Stmt mới chứa cả enum gốc lẫn thuộc tính dòng/cột thì phải refactor nhiều và không thanh nhã. Với opcode cũng vậy, khó có thể nói một enum Rust được pattern match là encoding lý tưởng cho hiệu năng của trình thông dịch opcode VM, nhưng ngôn ngữ lại dẫn dắt theo hướng này và tính năng destructuring pattern thì rất hấp dẫn. Có vẻ còn dư địa cải thiện hệ thống kiểu để vừa dùng được triển khai cấp thấp mong muốn, vừa có được tính năng pattern matching

    • Sẽ tốt hơn nếu có ví dụ cụ thể hơn. Điều đầu tiên tôi nghĩ tới là một dạng hệ thống kiểu cấu trúc, nhưng không chắc mình hiểu đúng là như vậy hay không
      https://en.wikipedia.org/wiki/Structural_type_system
    • Một kỹ thuật cũ trong trình thông dịch bytecode là dùng nhảy gián tiếp khi chuyển sang phần triển khai opcode tiếp theo. gcc từng có extension computed goto cho việc này; còn với Rust thì có lẽ cần thứ gì đó để ép dùng con trỏ hàm và tối ưu hóa tail call
      Nếu đặt kiểu nhảy gián tiếp này ở đầu phần triển khai của mỗi opcode, bộ dự đoán nhảy gián tiếp mà CPU có vì OOP sẽ có các mô hình riêng cho phần cuối của các opcode khác nhau, nhờ đó tăng tỉ lệ dự đoán đúng. Bản thân lệnh tiếp theo có thể khó dự đoán, nhưng chẳng hạn sau test thì khả năng branch theo sau có thể cao hơn nhiều. Tuy vậy, tôi nghĩ các kỹ thuật khác như lưu đỉnh stack của stack machine vào thanh ghi có thể quan trọng hơn, và cũng không rõ kỹ thuật trên hiện nay còn có ý nghĩa không
    • Nhiều ngôn ngữ có tính năng khá giống điều bạn muốn. Hãy xem extractor của Scala hoặc active view của F#

  • Việc “AST của clang sau khi phân tích cú pháp thường ngốn bộ nhớ gấp 50 lần mã nguồn gốc” nghe có vẻ khá lớn, nhưng ngữ cảnh còn thiếu là nó có thể tốt hơn đến mức nào. Nếu phải bảo toàn vị trí nguồn của từng token và mã hóa đủ thông tin để có thể khôi phục đúng từ AST, thì tôi tò mò mức tăng lý tưởng so với bản gốc là 1,5 lần hay 15 lần

    • Ví dụ nếu có thể giảm 30% bộ nhớ thì đó là tin khá lớn. Tuy nhiên, nếu làm cho compiler khó bảo trì về sau chỉ để giảm 30% thì có thể không đáng. Ngược lại, nếu chấp nhận “mạnh tay” với compiler một chút mà giảm được 80% thì đáng thử
      Rất khó nói tỷ lệ phình từ source→AST lý tưởng là bao nhiêu đối với một ngôn ngữ vừa thân thiện với người dùng vừa thân thiện với nhà phát triển compiler, nhưng 50 lần vẫn hoạt động được. Bài gốc dùng tỷ lệ phình 50 lần làm động lực để tự động hóa một tối ưu hóa cụ thể. Sẽ rất thú vị nếu vector enum của Rust có thể tự động tách giá trị enum thành tag và giá trị opaque, rồi lưu dưới dạng structure of arrays như bài gốc làm trong Zig. Có vẻ cũng không có nhiều chỗ để giấu việc dùng unsafe
    • Để so sánh, simdjson tape chỉ lớn hơn tài liệu gốc khoảng 3 lần. Có thể giảm đáng kể phần này nếu đặt số chỉ trong một tape slot, hoặc với chuỗi không có escape sequence thì không sao chép mà tham chiếu đến vị trí trong tài liệu gốc
      Với các tài liệu mà phần lớn là ký tự [] hoặc ký tự 0,, overhead tối đa có vẻ vào khoảng 8 lần
    • Mã nguồn dày đặc đến đáng ngạc nhiên. Một dữ liệu cho thấy có thể cải thiện đến mức nào là kết quả parser của chính Zig phân tích chính parser của Zig
      Số byte nguồn: 139 KiB, token: 24646 cái (120 KiB), nút AST: 10998 cái (140 KiB). Mỗi token khá tối giản ở 5 byte (tag 1 byte + offset file 4 byte), và nút AST cũng được mã hóa dày đặc, không đồng nhất; trong trường hợp này khoảng 13 byte mỗi nút. Ngay cả với cách mã hóa tối thiểu như vậy, parse tree vẫn gần gấp 2 lần kích thước file nguồn. Dù vậy, 2 lần vẫn tốt hơn 50 lần rất nhiều. Nguồn: zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • Tốt nhất là cứ xem bài thuyết trình được liên kết. Đó là một bài rất hay. Theo tôi nhớ thì có vẻ họ không đưa ra con số chính xác, và có lẽ khi đó vẫn còn quá sớm để chắc chắn. Cũng có thể các con số trông nhỏ vì còn thiếu những dữ liệu mà họ chưa nhận ra là cần thiết

  • Không gian vấn đề này có cảm giác như một biến thể của bài toán đóng gói
    Sẽ rất hay nếu có thể bắt đầu từ cấu trúc cuối cùng dễ thao tác cho con người, rồi sinh ra các gợi ý cấu trúc dữ liệu giúp giảm lãng phí bộ nhớ, tuân thủ quy tắc căn chỉnh và tăng tính cục bộ không gian. https://en.wikipedia.org/wiki/Packing_problems

  • Mong là proc macro sẽ phát triển theo hướng có thể truy vấn thông tin từ compiler. Điều đó đòi hỏi thiết kế cẩn trọng về việc thêm giai đoạn biên dịch, nhưng những thứ như “struct này có implement trait này không”, “hãy cho tôi danh sách tất cả trait được implement cụ thể” thường rất hữu ích trong proc macro

    • Nếu tôi nhớ đúng, compiler chạy plugin theo hai giai đoạn. Giai đoạn đầu nhận AST trước khi kiểm tra kiểu và có thể sửa AST; macro và một số lint của clippy chạy ở đây. Giai đoạn thứ hai là sau khi kiểm tra kiểu, nên nhận được thông tin kiểu nhưng không thể sửa đổi; các lint clippy khác chạy ở đây

  • Tôi chỉ hiểu một phần bài viết, nhưng với tư cách người muốn viết spreadsheet engine bằng Rust, nó có vẻ rất liên quan. Giá trị ô cần có dạng như sau
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    Tôi sẽ tiếp tục đọc và tìm hiểu, và rất hoan nghênh nếu có tài liệu tham khảo

    • Vấn đề được nhấn mạnh ở đây là kích thước các variant rất khác nhau, và nếu có nhiều giá trị như vậy trong một mảng thì hiệu năng sẽ kém đi do không gian bị lãng phí bởi padding
      Một kỹ thuật phổ biến từ phía game là tách array of structs (AoS) thành structure of arrays (SoA). Ví dụ, nếu để struct Humans { healths: Vec, ammo: Vec, … } thì chỉ mục thứ i của mỗi vector tương ứng với Human thứ i trong layout AoS. Các vector song song như vậy chỉ là ví dụ chứ chưa phải hiệu quả tối ưu, vì sổ sách về độ dài và dung lượng bị lặp lại cho từng field, gây lãng phí. Bài này về cơ bản muốn tự động áp dụng ý tưởng tương tự cho enum, và trong Rust thì khó làm nguyên xi. Mức độ thực sự nghiêm trọng của vấn đề này có thể hơi bị phóng đại. Với spreadsheet, trước hết chỉ nên xem đây là một tối ưu hóa tiềm năng, và cần xác định trước là bạn làm vì tốc độ hay vì sự đơn giản và dễ hiểu
    • Nghe như một dự án thú vị. Nếu nhắm đến người dùng phổ thông, bạn nên dự đoán rằng người dùng sẽ nhập nội dung vào bốn góc cực hạn của sheet để xem engine có sập không
      Nếu cho phép 1 triệu × 1 triệu ô và lưu null cho mọi ô chưa được điền, bộ nhớ sẽ cạn. Vì vậy có thể cân nhắc cách lưu thưa nội dung ô. Một cách là dùng triển khai hash map như hashbrown. Trọng tâm của bài này là chi tiết cấp thấp, nên nếu ngay từ đầu bạn dùng hash map để tránh ràng buộc bộ nhớ ban đầu thì hiện tại chưa cần nghĩ quá sâu về nó
    • Tôi từng thực sự làm spreadsheet engine bằng Rust. Nó không phải mã nguồn mở, nhưng tôi có thể đưa vài lời khuyên. Bạn sẽ gặp nhiều vấn đề hiệu năng khác trước khi hưởng lợi từ phương pháp trong bài này
      Vấn đề đơn lẻ khó nhất là chiến lược đánh giá

  • https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers thì sao

  • Có vẻ code ví dụ có bug
    field_map[idx] = svec.len - 1;
    Nếu svec đã chứa size ở vị trí không phải entry cuối cùng thì sẽ sai