Giải quyết vấn đề hiệu năng tồn đọng suốt 3 năm của Gleam bằng arena trong Rust

 (giacomocavalieri.me)
1 điểm bởi GN⁺ 6 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Bằng cách thay thế các cấp phát heap riêng lẻ lặp đi lặp lại trong cấu trúc Document đệ quy của bộ định dạng Gleam bằng tham chiếu dựa trên arena, một vấn đề cải thiện hiệu năng tồn đọng suốt 3 năm đã được giải quyết
  • Thay Box<Self> bằng &Self được lưu trong arena, và dùng kiểm tra vòng đời của Rust để bảo đảm dữ liệu bên trong không bị tham chiếu sau khi arena đã bị hủy
  • Bằng cách chỉ cấp phát một lần rồi tái sử dụng hàng trăm Document lặp lại như từ khóa ngôn ngữ và dấu phẩy, thời gian chạy của pretty printer giảm từ 13ms xuống 9.8ms, nhanh hơn 24%
  • Tổng thời gian chạy gleam format, bao gồm cả đọc mã nguồn và parsing, cũng giảm 13%, còn mức dùng bộ nhớ tối đa giảm từ 8.4MB xuống 7.6MB, tức khoảng 10%
  • Dù phải chỉnh sửa thủ công ở quy mô +2963/-1032 vì cần sửa rộng khắp các hàm và điểm gọi để truyền arena, cách giảm các lần cấp phát riêng lẻ lặp lại này đã cải thiện đồng thời cả tốc độ lẫn mức dùng bộ nhớ

Chi phí cấp phát phát sinh từ cấu trúc Document đệ quy

  • Pretty printer của Gleam dùng một cấu trúc dữ liệu Document đệ quy để biểu diễn cách in mã nguồn và vị trí cần xuống dòng khi vượt quá giới hạn độ dài dòng
  • Các variant chính gồm String chứa chuỗi cần in, Break định nghĩa chuỗi trước và sau khi xuống dòng, Group gom nhiều tài liệu lại với nhau, Nest tăng mức thụt lề khi xuống dòng, v.v.
  • Danh sách [1, 2] cũng được biểu diễn bằng cách kết hợp String, Break, Nest, Group
    • Nếu vừa trong dòng hiện tại, nó sẽ được in trên một dòng như [1, 2]
    • Nếu vượt giới hạn dòng, nó sẽ được tách thành nhiều dòng theo Break đã chỉ định, có thụt lề và vẫn in cả dấu phẩy cuối
  • Các variant chứa Document khác bên trong như Nest trước đây dùng Box<Self>, nên mỗi tài liệu lồng nhau đều phải cấp phát riêng trên heap, và công việc này có thể chiếm phần đáng kể trong thời gian chạy
  • Thuật toán nền tảng của pretty printer trong Gleam có thể tham khảo trong bài báo Strictly Pretty

Thay Box bằng tham chiếu arena

  • Cấu trúc trước đây Nest(Box<Self>) được đổi thành Nest(&'doc Self) để nó tham chiếu tới một Document khác được lưu trong arena
  • Để chứa tham chiếu, Document được bổ sung thêm vòng đời 'doc cho dữ liệu tài liệu, tách biệt với vòng đời chuỗi 'string
  • Việc triển khai sử dụng crate typed_arena
    • Dùng alloc để lưu giá trị vào arena thì sẽ nhận lại tham chiếu tới giá trị đó
    • Dữ liệu đã cấp phát có thể được dùng chừng nào arena còn tồn tại
    • Khi arena ra khỏi phạm vi, toàn bộ dữ liệu bên trong cũng bị hủy theo
  • Tham chiếu do alloc(&self, value: T) -> &mut T trả về không thể sống lâu hơn arena, và borrow checker của Rust sẽ chặn các tham chiếu không hợp lệ sau khi arena bị hủy

Chỉ cấp phát một lần và tái sử dụng các tài liệu lặp lại

  • Arena không chỉ dùng để cho các tài liệu tham chiếu lẫn nhau mà còn được tận dụng để cache các Document lặp lại trên khắp codebase
  • Không còn cần tạo mới mỗi lần các tài liệu biểu diễn từ khóa ngôn ngữ như String("fn"), String("pub"), String("type")
  • Các tài liệu như Break { unbroken: ", ", broken: "," } dùng giữa các phần tử danh sách cũng được cấp phát một lần rồi tái sử dụng
  • Hàng trăm tài liệu nhỏ trước đây luôn phải bọc trong Box nay đều có thể chỉ cấp phát một lần

API đơn giản nhưng phải sửa rất nhiều điểm gọi

  • Bản thân API của arena khá đơn giản, nhưng quá trình chuyển đổi phần lớn code hiện có đòi hỏi rất nhiều chỉnh sửa lặp đi lặp lại
  • Những hàm trước đây chỉ gọi Box::new nay phải nhận thêm một đối số arena để cấp phát dữ liệu
  • Các hàm như format_list cũng được sửa để truyền cùng arena xuống các hàm con định dạng phần tử danh sách, và tạo tài liệu lồng nhau bằng arena.alloc thay vì Box::new
  • Sau nhiều ngày tìm kiếm và thay thế cẩn thận, công việc đã hoàn tất trong một pull request quy mô +2963/-1032
  • Đây là công việc lặp đi lặp lại và thủ công, và trong quá trình này không dùng LLM

Cải thiện tốc độ và mức dùng bộ nhớ tối đa

  • Khi định dạng dự án Gleam thực tế squirrel, thời gian chạy của pretty printer giảm từ 13ms xuống 9.8ms
    • Nếu chỉ tính riêng pretty printer thì đây là mức cải thiện hiệu năng 24%
  • gleam format ngoài việc định dạng còn phải đọc và parse mã nguồn của dự án, nên pretty printer chỉ là một phần của toàn bộ công việc, nhưng thời gian chạy tổng thể vẫn giảm 13%
  • Mức dùng bộ nhớ tối đa giảm từ 8.4MB xuống 7.6MB, tức khoảng 10%
  • Kết quả của việc dùng arena để giảm số lần cấp phát heap riêng lẻ là bộ định dạng chạy nhanh hơn và cũng dùng ít bộ nhớ hơn

Bài viết liên quan

1 bình luận

 
GN⁺ 6 giờ trước
Các ý kiến trên Lobste.rs

  • Nếu muốn giảm thêm 10% mức sử dụng bộ nhớ đỉnh, có thể cân nhắc một arena khác trả về handle mờ thay vì tham chiếu. Có thể làm handle 16-bit hoặc 32-bit thay vì 64-bit, nên rất hiệu quả khi có nhiều cấp phát nhỏ
    Theo https://donsz.nl/blog/arenas/, crate duy nhất hỗ trợ điều này là compact_arena, nhưng nếu không phù hợp yêu cầu thì tự triển khai cũng không khó

    • Dùng handle mờ cũng có thể lưu trữ dữ liệu dày đặc hơn. Dự án cá nhân columnar tách danh sách Option<T> thành phần biểu diễn sự tồn tại chỉ hơn 1 bit mỗi mục và các giá trị T của những mục thực sự tồn tại
      Đổi lại, ở dạng tham chiếu nó trả về Option<&T> chứ không phải &Option<T>; nói tổng quát hơn, đây là cách đệ quy theo cấu trúc qua tham chiếu, thay vì đặt tham chiếu bên trong đệ quy cấu trúc
    • Bài viết đó dựa trên khảo sát từ 2 năm trước và không bao quát hoàn hảo mọi crate, nên nếu phát hiện lỗi hoặc thư viện mới bị thiếu thì cứ gửi PR
      Arena xứng đáng được dùng rộng rãi hơn; và nếu trả về tham chiếu thay vì handle hay smart pointer, pattern matching enum đệ quy trong Rust sẽ rất tiện. Thông thường, dù muốn viết kiểu if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {} thì cũng không thể vì box hoặc pointer ở giữa, nhưng tham chiếu có thể pattern match một cách trong suốt mà không cần tính năng nightly. Nếu mọi tham chiếu đều trỏ vào cùng một arena, lifetime nối toàn bộ cây cũng được duy trì nhất quán
    • Vì kết quả tốt nên đang cân nhắc chuyển các phần khác của compiler sang cách dùng arena, và sẽ tiếp tục theo dõi hướng tiếp cận này

  • Cách này khá giống hướng mà pretty, một thư viện pretty-printing khác theo phong cách Wadler, hỗ trợ. Tuy nhiên, vì hỗ trợ nhiều cách cấp phát bộ nhớ nên API có thể tạo cảm giác hơi nặng nề

  • Thật bất ngờ khi tác giả của bài báo được trích trong bài lại làm việc tại một công ty IT bình thường ở Brunswick

    • Đó chính là cái hay của mã nguồn mở. Chuyên môn và công việc mưu sinh thường không liên quan nhiều đến nhau