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

 (cs.cornell.edu)
3 điểm bởi GN⁺ 2023-07-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Arena hoặc region là một kỹ thuật đơn giản và hiệu quả cho trình biên dịch và các hệ thống tương tự trình biên dịch.
  • Việc làm phẳng cây cú pháp trừu tượng (AST) bằng arena có thể cải thiện hiệu năng và tăng tính tiện dụng.
  • Làm phẳng có nghĩa là đóng gói các nút AST vào một mảng duy nhất và dùng chỉ mục mảng thay cho con trỏ.
  • AST đã làm phẳng mang lại các lợi ích như tính cục bộ tốt hơn, tham chiếu nhỏ hơn, cấp phát và giải phóng rẻ hơn.
  • AST đã làm phẳng có thể đơn giản hóa việc quản lý bộ nhớ và cho phép khử trùng lặp một cách thuận tiện.
  • Kết quả hiệu năng cho thấy phiên bản trình thông dịch làm phẳng có thể nhanh hơn 2,4 lần so với phiên bản thông thường.
  • Có thể tiếp tục cải thiện hiệu năng bằng cách tận dụng biểu diễn AST dạng phẳng để loại bỏ đệ quy và dùng duyệt tuyến tính.
  • Bài viết này thảo luận về các cải thiện hiệu năng đạt được nhờ làm phẳng cấu trúc dữ liệu trong một trình thông dịch ngôn ngữ lập trình.
  • Ngoài ra, trình thông dịch làm phẳng cho thấy mức cải thiện hiệu năng 8,2% so với trình thông dịch đệ quy, với thời gian 1,2 giây so với 1,3 giây.
  • Kỹ thuật này về cơ bản là tái tạo lại ý tưởng của trình thông dịch bytecode, trong đó cấu trúc Expr được dùng như lệnh bytecode.
  • Bài viết cũng nhắc tới các bài viết và dự án khác về làm phẳng cấu trúc dữ liệu liên quan đến LuaJIT, bộ kiểm tra kiểu Sorbet và shell Oil.
  • Những khái niệm tương tự về làm phẳng và tối ưu tính cục bộ cũng xuất hiện trong các lĩnh vực như trò chơi điện tử, xử lý dữ liệu tuần tự hóa, thiết kế hướng dữ liệu và hệ thống thực thể-thành phần.
  • Bài viết khuyến nghị đọc bài đăng của Inanna Malick, trong đó áp dụng cùng kỹ thuật này cho một ngôn ngữ "máy tính" đồ chơi được triển khai bằng Rust.
  • Bài viết thảo luận các hạn chế khi dùng kỹ thuật này trong Rust, bao gồm việc không thể nhúng inline một Expr khác bên trong cấu trúc Expr.
  • So sánh hiệu năng được thực hiện trên MacBook Pro dùng bộ xử lý M1 Max và 32GB bộ nhớ, chạy macOS 13.3.1 và Rust 1.69.0.

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-04
Ý kiến trên Hacker News
  • Blender sử dụng cùng một cách biểu diễn trên đĩa và trong bộ nhớ để tải và lưu tệp nhanh, không mất dữ liệu.
  • AST được làm phẳng được sử dụng trong pulldown-cmark để phân tích cú pháp inline markup hiệu quả.
  • Biểu diễn AST làm phẳng cho phép biến đổi cây với độ phức tạp O(1), bất kể số lượng nút hay độ sâu ngăn xếp.
  • Hiệu năng của pulldown-cmark nổi bật khi so sánh với các trình phân tích CommonMark khác.
  • Warren Abstract Machine (WAM) sử dụng biểu diễn làm phẳng cho Prolog trên heap.
  • Việc làm phẳng AST là một khái niệm đã được sử dụng từ trước trong các ngôn ngữ như Lisp.
  • Lưu các nút trong mảng có thể thay đổi kích thước có thể gây ra vấn đề cấp phát bộ nhớ, nhưng có thể giảm nhẹ bằng cách gom nhóm theo các khối kích thước trang.
  • Cần chú ý đến cách các nút AST được biểu diễn trong mã và nên tránh phần đệm không cần thiết.
  • Sử dụng chỉ số thay cho con trỏ có thể tạo ra mã nhỏ hơn và nhanh hơn.
  • Có thể triển khai bộ nhớ làm phẳng bằng cách dùng trình cấp phát bộ nhớ tùy chỉnh, hữu ích trong một số kịch bản cụ thể.
  • Cấu trúc AST gọn nhẹ đã được dùng để triển khai trình phân tích cú pháp và trình thông dịch JavaScript trong các môi trường bị hạn chế bộ nhớ.