Làm phẳng AST và các cấu trúc dữ liệu của trình biên dịch

 (cs.cornell.edu)
3 điểm bởi GN⁺ 2023-07-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Nếu biểu diễn AST bằng một mảng duy nhất và chỉ số thay vì một đồ thị đối tượng nối với nhau bằng con trỏ, cách bố trí và quản lý bộ nhớ của cấu trúc dữ liệu kiểu trình biên dịch sẽ trở nên đơn giản hơn
  • Ví dụ bằng Rust triển khai AST đã làm phẳng chỉ với các thay đổi nhỏ: thay Box<Expr> bằng ExprRef và thêm add/get vào ExprPool
  • Trong một microbenchmark tạo khoảng 100 triệu nút AST rồi diễn giải ngay lập tức, bản triển khai thông thường mất 3,1 giây, còn bản làm phẳng mất 1,3 giây, tức nhanh hơn 2,4×
  • Chênh lệch hiệu năng đến từ tính cục bộ nhờ bố trí bộ nhớ liên tục, tham chiếu nhỏ hơn dùng chỉ số 32-bit thay cho con trỏ 64-bit, chi phí cấp phát thấp hơn và giải phóng theo cả pool
  • Nếu tận dụng tính chất trong mảng rằng nút con nằm trước nút cha, việc duyệt cây đệ quy có thể được biến thành thực thi tuyến tính, tiến gần tới dạng của một bytecode interpreter

Ý tưởng cơ bản của việc làm phẳng

  • Arena hoặc region được dùng rất rộng rãi trong các triển khai ngôn ngữ hiện đại; cách làm ở đây là dùng arena chỉ chứa một kiểu như một mảng đơn giản, tức làm phẳng cấu trúc dữ liệu
  • Đây là kỹ thuật thay con trỏ bằng chỉ số mảng trong các cấu trúc dữ liệu nhiều con trỏ; ví dụ trung tâm là AST nhưng cũng có thể áp dụng cho các cấu trúc dữ liệu khác của trình biên dịch
  • Mã ví dụ có trong kho flatcalc, và khác biệt giữa bản thường với bản làm phẳng có thể xem trong so sánh nhánh
  • Mức thay đổi trong mã là nhỏ, nhưng microbenchmark cho thấy cải thiện tốc độ 2,4×, và ngoài hiệu năng còn có lợi ích về tính tiện dụng của mã

Biểu diễn AST thông thường

  • Ngôn ngữ ví dụ là một ngôn ngữ biểu thức số học rất đơn giản, chỉ hỗ trợ literal số nguyên và bốn toán tử số học nhị phân
    • Ví dụ chương trình có thể là 42, 0 + 14 * 3, (100 - 16) / 2
  • Biểu diễn trong Rust gồm enum BinOp và Expr
    • Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
    • Expr::Literal(i64)
  • Box<Expr> trong Rust tương ứng với một con trỏ trỏ tới Expr, đóng vai trò gần giống Expr* trong C
  • Parser, bộ định dạng đầu ra và interpreter đều có cấu trúc điển hình; interpreter được viết dưới dạng phương thức đệ quy trên Expr
  • Ngữ nghĩa số học được thiết kế để mọi biểu thức cuối cùng đều được đánh giá thành i64
    • Cộng, trừ, nhân dùng phép toán wrapping
    • Chia cho 0 được xử lý bằng checked_div để trả về 0
  • Một bộ sinh chương trình ngẫu nhiên với PRNG seed cố định được dùng để đo hiệu năng thao tác AST mà không có chi phí parse và in ra

Chuyển AST sang mảng và chỉ số

  • Việc làm phẳng gồm hai thay đổi
    • Không cấp phát riêng từng đối tượng Expr trên heap mà lưu chúng trong một mảng liên tục duy nhất
    • Tham chiếu nút con bằng chỉ số trong mảng thay vì con trỏ
  • Trong ví dụ Rust, ExprPool được định nghĩa là newtype của Vec<Expr>
struct ExprPool(Vec<Expr>);
  • Vai trò con trỏ cũ được thay bằng ExprRef dựa trên số nguyên 32-bit
struct ExprRef(u32);
  • Thay đổi kiểu cốt lõi là đổi các trường con của Binary từ Box<Expr> sang ExprRef
enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}
  • ExprPool được bổ sung các tiện ích add để thêm Expr mới và get để tìm Expr từ ExprRef
  • Parser không còn trả về trực tiếp Expr, mà thêm nút vào ExprPool rồi trả về ExprRef
  • Interpreter cũng trở thành phương thức của ExprPool thay vì của Expr; trước khi pattern match, nó giải tham chiếu bằng self.get(expr)
  • Toàn bộ thay đổi nhìn chung chỉ là thay Box<Expr> bằng ExprRef và thêm add cùng get ở những chỗ cần thiết

Lợi ích về hiệu năng

  • Ưu điểm tiêu biểu của AST đã làm phẳng là tính cục bộ bộ nhớ
    • Expr dựa trên con trỏ thông thường có nguy cơ phân mảnh bộ nhớ
    • Expr đã làm phẳng nằm dày đặc trong vùng nhớ liên tục, giúp data cache và prefetcher hoạt động hiệu quả hơn
    • Một bộ cấp phát bộ nhớ đủ thông minh có thể tạo hiệu ứng tương tự, nhưng dùng mảng dày đặc giúp giảm bớt tính bất định
  • Kích thước tham chiếu cũng giảm đi
    • Con trỏ thông thường trên kiến trúc hiện đại là 64-bit
    • Nếu chỉ cần không quá 4.294.967.295 nút AST thì tham chiếu 32-bit là đủ
    • Có thể tiết kiệm 50% dung lượng cho mỗi tham chiếu, và với AST nhiều con trỏ điều này có thể làm giảm tổng bộ nhớ sử dụng
    • Với cấu trúc dữ liệu nhỏ hơn, thậm chí có thể dùng tham chiếu 16-bit hoặc 8-bit
  • Chi phí cấp phát thấp hơn
    • Không cần gọi malloc cho từng nút
    • Nếu đã dành trước đủ bộ nhớ, có thể tạo chỗ cho Expr mới bằng bump allocation chỉ với việc tăng tail pointer
  • Việc giải phóng có thể xử lý theo cả pool
    • Giả định ở đây là không giải phóng từng Expr riêng lẻ
    • Trong nhiều triển khai ngôn ngữ, AST thường được tạo cùng nhau và biến mất cùng nhau
    • AST thông thường phải lần theo con trỏ để giải phóng từng nút, còn AST đã làm phẳng chỉ cần giải phóng toàn bộ ExprPool một lần
  • Trong các phần giới thiệu arena allocation, giải phóng rẻ thường được nhấn mạnh là lý do chính; nhưng trong bối cảnh trình biên dịch, AST có thể tồn tại đến hết quá trình biên dịch nên đây lại có thể là lý do kém quan trọng nhất

Lợi ích về tính tiện dụng của mã

  • Việc làm phẳng giúp đơn giản hóa quản lý lifetime
    • Thay vì nghĩ về AST có n nút với n lifetime, có thể coi nó chỉ có một lifetime của toàn AST
    • Trong Rust, sự đơn giản hóa này tác động trực tiếp lên cách biểu diễn lifetime trong mã
    • Thay vì quản lý lifetime của các &Expr, ta có thể truyền ExprRef là u32 và dựa vào lifetime của ExprPool
  • Sự đơn giản tương tự cũng có thể áp dụng trong các ngôn ngữ quản lý bộ nhớ thủ công như C++
  • Mảng đã làm phẳng cũng thuận tiện cho việc khử trùng lặp
    • Có thể tránh tạo ra các biểu thức giống nhau bằng hash consing hoặc các cách đơn giản hơn
    • Ví dụ, có thể dành sẵn 128 vị trí đầu của ExprPool cho các biểu thức Literal thường dùng từ 0 đến 127
    • Khi cần literal số nguyên 42, không cần tạo Expr mới mà chỉ việc trả về ExprRef(42)
  • Trong biểu diễn dựa trên con trỏ cũng có thể làm điều tương tự, nhưng nhiều khả năng sẽ cần các cấu trúc dữ liệu phụ trợ

Kết quả microbenchmark

  • Benchmark tạo một chương trình ngẫu nhiên với khoảng 100 triệu nút AST rồi đưa ngay vào interpreter
    • Không bao gồm parser và bộ định dạng đầu ra
    • Đây không phải benchmark thực tế vì nó tạo một chương trình rồi chạy ngay lập tức
  • Điều kiện thí nghiệm có một số giới hạn
    • Vec<Expr> được dành trước đủ chỗ để chứa toàn bộ chương trình
    • Trong môi trường thực tế sẽ cần ước lượng kích thước arena nhiều hơn
    • Gần như không có công việc nào ngoài tạo và thực thi, nên lợi thế cấp phát/giải phóng rẻ có thể bị phóng đại
    • Chương trình quá lớn nên tỷ lệ nằm trong cache CPU là nhỏ, khiến hiệu ứng về tính cục bộ có thể bị đánh giá thấp
  • Dùng Hyperfine để so sánh trung bình 10 lần chạy trên laptop
    • Môi trường là M1 Max 10 lõi 3.2GHz, bộ nhớ 32GB, macOS 13.3.1, Rust 1.69.0
  • Bản triển khai thông thường mất 3,1 giây, bản làm phẳng mất 1,3 giây, cho thấy tăng tốc 2,4×
  • Để xem riêng chi phí giải phóng, tác giả tạo các phiên bản bỏ qua deallocation cho cả hai cách triển khai
    • Với bản làm phẳng, thời gian của phiên bản no-free gần như giống hệt bản tiêu chuẩn, cho thấy chi phí giải phóng không lớn
    • Với bản thông thường, thời gian giảm từ 3,1 giây xuống 1,9 giây, nghĩa là khoảng 38% thời gian được dùng để giải phóng bộ nhớ
    • Ngay cả khi so sánh giữa các phiên bản no-free, bản làm phẳng vẫn nhanh hơn 1,5× so với bản thông thường

Interpreter tận dụng trực tiếp biểu diễn đã làm phẳng

  • Ban đầu, việc làm phẳng được dùng như một thay đổi triển khai nội bộ để thay cho cấp phát thông thường và con trỏ, nhưng cũng có thể khai thác trực tiếp tính chất của biểu diễn dạng mảng
  • Nếu Expr là bất biến thì phải tạo nút con trước, nút cha sau
    • Khi tạo a * b, a và b sẽ nằm trước phép * tham chiếu tới chúng trong ExprPool
    • Mũi tên tham chiếu trong mảng luôn hướng từ sau về trước, còn luồng dữ liệu thì tiến về phía trước
  • Có thể dùng bất biến này để tạo một interpreter quét ExprPool từ đầu tới cuối thay vì đệ quy đi xuống từ nút gốc
    • Quá trình duyệt luôn thăm nút con trước nút cha
    • Kết quả của từng biểu thức được lưu trong vector state
    • Với biểu thức nhị phân, giá trị được lấy từ state bằng chỉ số ExprRef của các nút con
    • Cuối cùng trả về kết quả tương ứng với root được yêu cầu
  • Interpreter “extra-flat” này không có chi phí quản lý stack của lời gọi đệ quy và có thể duyệt ExprPool theo tuyến tính
  • Ngược lại, nó phải truy cập ngẫu nhiên vào một vector state lớn nên có thể bất lợi về tính cục bộ
  • Kết quả là interpreter extra-flat mất 1,2 giây, còn interpreter làm phẳng dựa trên đệ quy mất 1,3 giây, tức cải thiện 8,2%

Liên hệ với bytecode interpreter

  • Một bình luận trên Reddit của Bob Nystrom cho rằng cách này thực chất là tái phát minh ý tưởng bytecode interpreter
  • Cấu trúc Expr hoạt động như lệnh bytecode, còn tham chiếu biến được mã hóa như các tham chiếu u32
  • Nếu thay bảng state đơn giản bằng một cấu trúc giống stack, nó sẽ gần như không khác gì một bytecode interpreter được thiết kế ngay từ đầu
  • Chỉ bằng việc thay đổi cấu trúc dữ liệu AST, cách duyệt cây cũng tự nhiên dịch chuyển sang kiểu bytecode

Tài liệu liên quan

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-04
Ý kiến trên Hacker News

  • Blender (phần mềm dựng hình 3D) là một ví dụ thú vị của cách làm này. Để việc tải/lưu tệp nhanh và không mất mát, nó dùng biểu diễn trên đĩa và trong bộ nhớ giống hệt nhau
    Nghĩa là mọi thứ đều nằm trong arena, và việc lưu/tải gần như tương đương với memcpy toàn bộ arena. Xét đến độ phức tạp tiềm tàng của dự án Blender và các vấn đề serialize/deserialize, đây có vẻ là một thiết kế rất xuất sắc
    Nhược điểm là vì vẫn phải mở được các tệp phiên bản cũ, nên thiết kế cấu trúc dữ liệu dễ bị đóng băng

    • Phần còn thiếu trong ý “thiết kế cấu trúc dữ liệu bị đóng băng vì phải mở được tệp phiên bản cũ” là một cách để tiến hóa cấu trúc dữ liệu theo thời gian, giống như migration cơ sở dữ liệu
      Chỉ chạy các phép chuyển đổi này khi tải dữ liệu từ phiên bản ứng dụng cũ, rồi sau đó lưu ngay xuống đĩa bằng phiên bản đã cập nhật để không phải trả lại chi phí đó lần nữa
      https://www.inkandswitch.com/cambria/ được tạo ra trong bối cảnh CRDT là một ví dụ triển khai của ý tưởng này, và dù không áp dụng trực tiếp thì vẫn có thể mang lại cảm hứng tốt
    • Tôi từng làm ở một ứng dụng thương mại lớn dựa trên framework I/O tự xây hoạt động theo nguyên lý tương tự, và nó thực sự rất khổ sở
      Dù thích hay ghét framework I/O đó thì nó vẫn serialize nguyên xi các struct, nên lúc nào cũng phải thiết kế cấu trúc dữ liệu để chịu được tương lai, vì biết rằng sẽ bị trói vào cấu trúc đó mãi mãi. Đó đúng là thời kỳ tăm tối
    • Có phải Microsoft Word thời “doc” ngày xưa cũng dùng cách dump thẳng các struct xuống đĩa không nhỉ
      Vì thế việc viết bộ chuyển đổi trở thành một vấn đề lớn, và tôi nhớ là người ta phải giải mã các cấu trúc dữ liệu nội bộ không được tài liệu hóa của Word
    • Trò chơi PlayStation mà tôi từng làm cũng chính xác theo kiểu này, và mọi thứ đều được ký nên hoàn toàn không lo về kẻ tấn công
      Nếu ai đó có thể sửa tệp trên đĩa thì điều đó đồng nghĩa họ đã kiểm soát được thiết bị rồi. Nhờ vậy thời gian tải nhanh đến mức vô lý: chỉ cần đọc mọi thứ vào bộ nhớ rồi vá vị trí con trỏ sang địa chỉ thực tế đã được tải
    • Tôi cũng biết là Microsoft Word ban đầu từng dùng cách này, và khi định dạng tệp tiến hóa thì nó trở thành một nỗi đau lớn

  • Tôi thích AST được làm phẳng. Tôi đặc biệt thích cách này được dùng trong xử lý inline markup của pulldown-cmark. Có một giải thích ngắn gọn tại https://fullyfaithful.eu/pulldown-cmark/
    Đầu vào thô được tách thành một chuỗi node, và những thứ như * có thể trở thành nhấn mạnh hoặc nếu không có cặp thì vẫn là văn bản, nên chúng được biểu diễn thành node MaybeEmphasis
    Ở bước tiếp theo, một stack được dùng để duyệt lần lượt qua các node và tìm các cặp có thể ghép. Khi tìm thấy cặp, node MaybeEmphasis được đổi thành node nhấn mạnh thích hợp, và toàn bộ chuỗi node giữa node mở và node đóng được cắt ra để trở thành cây con của node mới
    Phép biến đổi cây này khá đặc biệt nên cách cài đặt đơn giản rất dễ thành O(n), nhưng với biểu diễn AST phẳng thì có thể xử lý trong O(1) bất kể số lượng node hay độ sâu của stack
    Chi tiết về biểu diễn cây có tại https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6..., về cơ bản là giữ các chỉ số child, next cùng với phần thân node. Mã “phẫu thuật cây” khi ghép nhấn mạnh nằm ở https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...
    Hiệu năng rất ấn tượng. pulldown-cmark có thể không phải là parser CommonMark nhanh nhất tuyệt đối, nhưng đủ sức cạnh tranh và, chẳng hạn, nhanh hơn rất nhiều so với cách tiếp cận cấp phát cho từng node

  • Nhớ lại một bài trình bày ở GDC từng ca ngợi Rust. Nội dung là Rust либо khiến bạn phát điên vì borrow checker, hoặc buộc bạn phải cấu trúc mã theo kiểu entity component system
    Điều thú vị là trong các trường hợp thực tế có vấn đề vòng đời phức tạp, giá trị của borrow checker rốt cuộc lại nằm ở chỗ nó khiến bạn tìm cách nhét mọi thứ vào mảng và tham chiếu bằng chỉ số để né borrow checker nhiều nhất có thể

    • Theo chút kinh nghiệm của tôi khi dùng thử game engine Bevy của Rust, entity component system cho cảm giác như đang viết mã spaghetti hạng sang
      Vì các đối tượng không còn tham chiếu trực tiếp tới nhau, tính hữu dụng của hệ thống kiểu giảm đi rất nhiều, và việc suy luận mã trở nên cực kỳ khó. Tôi tin rằng nó có thể hữu ích trong các hệ thống rất lớn, nhưng với chương trình nhỏ tôi đang viết thì nó gần như là vật cản
    • Đúng vậy. Lifetime của Rust yếu thế hơn trong một số lĩnh vực lập trình hiệu năng cao, nơi người ta tránh heap hoặc thậm chí hoàn toàn không có heap
      Game, cơ sở dữ liệu, embedded, các tác vụ batch kiểu high-performance computing, thậm chí cả compiler đều thuộc nhóm này
      Tất nhiên vẫn còn các hạn chế aliasing nên sẽ không có data race, nhưng các lỗi về bản chất giống với lỗi phát sinh từ con trỏ thô thì vẫn có thể xảy ra
    • Nói cách khác, có thể xem đây là việc ép các thực thể sống lâu phải sở hữu bộ nhớ và cho các đối tượng sống ngắn hơn mượn
      Trong quá trình đó, bên đi mượn luôn sống ngắn hơn bên sở hữu và chỉ có thể truy cập phần bộ nhớ đã được cấp phát khi đang được sở hữu. Khi chủ sở hữu chết thì bộ nhớ được giải phóng, sau đó không ai có thể dùng nó hay giải phóng lại nữa, nên tránh được use-after-free, giải phóng kép, và truy cập bộ nhớ chưa được cấp phát
    • Đúng vậy. Tôi liên tục thấy người ta nhắc đến arena hay cấu trúc cây/đồ thị được làm phẳng mà lại bỏ qua an toàn bộ nhớ
      Thậm chí còn có những khẳng định kỳ lạ rằng arena trong C giải quyết được vấn đề an toàn bộ nhớ, trong khi tùy chương trình nó vẫn hoàn toàn có thể gây ra dangling pointer hay use-after-free
      Cùng một vấn đề xuất hiện ở cả C/C++ và Rust theo những cách hơi khác nhau
      Bình luận của tôi trong bài viết này từ hai tháng trước: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
      Tóm lại, lợi ích là rất thực tế nhưng cũng phải nói đến nhược điểm. Arena đẩy vấn đề an toàn bộ nhớ về sau, quyền sở hữu có thể trở nên rắc rối, việc sửa đổi và thêm list/vector cũng phức tạp hơn, còn biểu diễn bằng con trỏ thì thân thiện với debugger hơn
      Ở cuối bài này có liên kết tới trang wiki của tôi, tôi rất cảm kích vì có mã thực tế và số liệu đo đạc: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
    • Pointer chỉ là chỉ số cho một không gian bộ nhớ. Nếu Rust muốn giải quyết các bài toán lập trình nói chung, có vẻ như borrow checker phải xử lý được mọi loại chỉ số, chứ không chỉ các chỉ số chuyên biệt cho không gian bộ nhớ

  • Term của Prolog cũng được biểu diễn trên heap theo kiểu này trong Warren Abstract Machine (WAM). Theo ví dụ trong bài, nếu viết term Prolog +(*(a,b), c) dưới dạng ký pháp toán tử thì sẽ là
    expr(E) :- E = a*b + c.
    Khi đó một biểu diễn đã được làm phẳng sẽ được tạo ra trên stack toàn cục của máy ảo. Trong Scryer Prolog, bạn có thể xem lệnh WAM bằng ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).
    Kết quả sẽ trông như put_structure(*,2,x(3))., set_constant(a)., set_constant(b)., put_structure(+,2,x(2))., set_value(x(3))., set_constant(c)., execute(=,2).
    Cả hai term phức hợp đều được tuyến tính hóa, nên trên heap chúng được đặt theo dạng sau functor là các đối số, và mỗi phần tử chiếm đúng một ô nhớ của WAM. Các đối số có thể trỏ tới các ô nhớ khác
    Heap là một mảng gồm các ô như vậy, và mọi ô đều có cùng một kiểu cụ thể. Ví dụ, Scryer Prolog dùng 8 byte cho mỗi ô, nên việc truy cập và sửa ô trên kiến trúc 64-bit rất hiệu quả

  • Việc “thay vì cấp phát bừa bãi các đối tượng Expr trên heap thì đặt chúng vào một mảng liên tiếp, còn con thì tham chiếu bằng chỉ số của mảng đó thay vì con trỏ” gần với một cách biểu diễn heap thay thế hơn là làm phẳng. Bản thân hình dạng của AST không thay đổi
    Đây là cách nhiều ngôn ngữ đã làm từ lâu, như trong họ Lisp: đặt cons cell và các đối tượng khác vào mảng, rồi dùng bump allocation và pointer dạng chỉ số
    Khi đối tượng nằm trong mảng, garbage collector sau khi mark xong sẽ dễ duyệt ở bước sweep hơn. Bước mark đi qua đồ thị để tìm các đối tượng còn reachable, còn bước sweep đi qua mảng phẳng để xóa bit GC và đánh dấu các đối tượng không còn reachable để tái sử dụng
    Khó mà tìm được một hiện thực Lisp nghiêm túc nào lại gọi riêng malloc cho từng cons cell. Nếu làm vậy thì sẽ cần đưa chúng vào một danh sách liên kết toàn cục cho bước sweep của GC, hoặc cần một mảng toàn cục chỉ chứa các con trỏ
    Tôi đã thấy ít nhất hai dự án Lisp đồ chơi làm cuối tuần mà cons cell được malloc, rồi bị rò rỉ bộ nhớ, còn GC thì bị để lại như một TODO khổng lồ
    Ngay cả khi ô nhớ đến từ một heap mảng nén, cuối cùng vẫn có thể xuất hiện mảng toàn cục. Ví dụ, khi hiện thực garbage collection thế hệ với allocator không sao chép, người ta có thể thêm các đối tượng trẻ vào một mảng phụ để quét trong các chu kỳ GC nhanh, và mảng đó sẽ đại diện cho nursery

  • Bài viết hay, nhưng có hai cạm bẫy

    1. Nếu lưu các nút trong một mảng có thể thay đổi kích thước, thì khi chương trình đầu vào lớn dần, trình biên dịch sẽ cần một khối bộ nhớ liên tục lớn hơn. Khối đó có thể có hoặc không có sẵn. Có thể lách vấn đề này bằng cách cấp phát các khối cỡ trang và dùng chúng như một pool
    2. Cần cẩn thận với cách biểu diễn nút AST trong mã. Ví dụ, nếu lưu nút bằng kiểu union thì union sẽ có kích thước bằng thành viên lớn nhất, và vì không phải mọi nút AST đều có cùng kích thước, các nút nhỏ sẽ bị đệm không cần thiết để khớp với kích thước của nút lớn nhất
    • Việc các nút AST nhỏ bị đệm không cần thiết vì kích thước của nút AST lớn nhất đúng là một ý rất hay, và tôi cũng đã nhắc đến nó trong bài blog của mình về kiểu số nguyên có độ rộng bit do người dùng định nghĩa: https://alic.dev/blog/custom-bitwidth
      Tagged union cũng khả thi, nhưng phải xử lý việc dùng bộ nhớ thật khôn ngoan
    • Thỉnh thoảng tôi nghĩ giá như chúng ta đã không đi đến không gian địa chỉ phẳng
      Kỹ thuật “bộ nhớ ảo” cho phép ghép các vùng bộ nhớ vật lý bị phân mảnh thành một vùng bộ nhớ ảo liên tục. Nếu không gian địa chỉ ảo được phân đoạn thì ngay từ đầu đã không bị phân mảnh, và mọi vùng nhớ đều có thể luôn tăng kích thước tại chỗ mà không va chạm với vùng khác
      Khi đó, cách hiện thực realloc() hẳn đã có thể loại bỏ nhánh memcpy(), tiếc thật
    • Có thể giảm nhẹ bằng cấu trúc giống rope chia vector thành các chunk kích thước cố định và dùng con trỏ thật. Sẽ không còn cần tái cấp phát nữa
      Bên trong sẽ không an toàn, nhưng có vẻ vẫn có thể có một giao diện an toàn chỉ đọc. Giải phóng sẽ là O(n), nhưng dù vậy vẫn nhanh hơn cây rất nhiều

  • Tôi ngạc nhiên khi vẫn còn hai con trỏ (“tham chiếu”) trong nút dù giờ đã biết con trỏ đầu tiên luôn trỏ chính xác đến nút tiếp theo
    Tôi từng thấy https://github.com/rswier/c4 dùng cách đó. Tất nhiên mã không dễ đọc lắm, nhưng nhỏ hơn và nhanh hơn

  • Trong quản lý bộ nhớ, khi nói arena thì tôi nghĩ đến arena allocator hơn là “làm phẳng”
    Khi cần cấp phát nhiều mục có cùng vòng đời, cách này cấp phát hiệu quả hơn từ một hoặc nhiều khối bộ nhớ lớn, rồi khi vòng đời chung kết thúc thì giải phóng cả khối lớn thay vì từng mục riêng lẻ
    Vì chỉ cần dùng tuần tự phần không gian của khối cha, nên cũng không cần danh sách trống như heap allocator đa dụng, nhờ đó việc cấp phát có thể hiệu quả hơn
    Trong ngữ cảnh này, “làm phẳng” bằng cách dùng chỉ số thay cho con trỏ cũng có thể được xem như dùng con trỏ tương đối theo khối cha, tức là offset

  • Tôi đã dùng kiểu cấu trúc AST gọn nhẹ này khi hiện thực V7(https://github.com/cesanta/v7), một trình phân tích cú pháp và thông dịch JavaScript cho môi trường nhúng có bộ nhớ cực kỳ hạn chế
    Về sau tôi chuyển sang bước biên dịch từ AST sang bytecode, nhưng trong một thời gian tôi đã duyệt trực tiếp AST ngầm trong lúc thông dịch

  • Tôi cũng đã làm điều tương tự trong trình biên dịch Yaml to Sql của mình tại https://yaml2sql.netlify.app
    Quá trình làm phẳng hơi kỳ lạ nhưng thú vị, và rốt cuộc xứng đáng với công sức bỏ ra
    Ví dụ, làm phẳng biểu thức boolean là một bài tập rất hay cho ai muốn thử: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...