- Chia sẻ chiến lược tự thiết kế và triển khai Lexer siêu nhanh cho ngôn ngữ purple-garden cùng dữ liệu hiệu năng đo thực tế
- Áp dụng nhiều kỹ thuật tối ưu hóa như Threaded Lexing (dựa trên bảng nhảy), chuỗi cửa sổ không sao chép, interning, bump allocator
- Tối đa hóa tốc độ phân tích bằng băm token và so sánh băm từ khóa dựng sẵn; bảng nhảy vượt trội hơn câu lệnh
switch đơn giản về hiệu quả cache CPU
- mmap toàn bộ tệp và giảm thiểu cấp phát động để cắt giảm mạnh chi phí IO và quản lý bộ nhớ với đầu vào lớn
- Chứng minh tốc độ xử lý nhanh hơn hơn 10 lần so với các lexer nổi tiếng hiện có (ví dụ: flex, handcoded), đồng thời đưa ra số liệu micro-benchmark cho từng giai đoạn parsing/runtime
Tổng quan về Lexing và pipeline biên dịch
- Lexer (tokenizer) chuyển chuỗi đầu vào thành danh sách token có ý nghĩa, sau đó parser nhận chúng để tạo AST (cây cú pháp trừu tượng)
- Thiết kế token trong ngôn ngữ purple-garden giữ cấu trúc tối thiểu, với enum TokenType và chỉ lưu chuỗi cùng thông tin kiểu
Thiết kế Lexer tối giản và ví dụ mã
- Struct Lexer chỉ lưu chuỗi đầu vào và vị trí hiện tại
- Dùng câu lệnh
switch để tạo token theo từng ký tự
- Để debug, sử dụng mảng ánh xạ kiểu-sang-chuỗi và khởi tạo theo từng kiểu
Threaded Lexing (dựa trên bảng nhảy)
- Thay vì câu lệnh
switch, dùng bảng nhảy (jump table) để xử lý phân loại token (computed goto)
- Ánh xạ từng nhãn xử lý vào mảng 256 byte với giá trị ký tự làm chỉ số
- Trong nhánh mã thực tế, dùng macro
JUMP_TARGET để nhảy và thực thi ngay
- Ưu điểm:
- Thực thi nhanh hơn nhờ giảm cache miss và tối ưu dự đoán nhánh
- Nhược điểm:
- Không hỗ trợ trên MSVC (chỉ Clang, GCC), khó debug
Quản lý bộ nhớ và trừu tượng hóa Allocator
- Định nghĩa giao diện cho nhiều chiến lược cấp phát bộ nhớ như bump allocator (struct Allocator)
- Dùng macro
CALL để đơn giản hóa log verbose và truyền context
- Có ví dụ mã cho cấu trúc cấp phát/giải phóng thực tế, thống kê, và các đoạn mã liên quan
Xử lý chuỗi không sao chép, dựa trên cửa sổ
- Đưa vào struct Str (con trỏ, độ dài, hash) để xử lý hiệu quả trong C
- Tự triển khai các thao tác như slice, concat, eq, hashing, chuyển đổi số
- Slice chuỗi được tạo tức thì chỉ bằng cách dịch con trỏ, không cần cấp phát bộ nhớ
- Việc chuyển đổi số cũng dùng thuật toán tự cài đặt để đổi ký tự-thành-số nguyên
Băm token và so sánh từ khóa bằng băm dựng sẵn
- Tính hash khi tạo token (FNV-1a) để tối ưu so sánh trùng lặp và interning
- Với các từ khóa hằng như true/false, so sánh trực tiếp bằng giá trị hash để rẽ nhánh ngay (cải thiện hiệu năng)
- Hàm
is_alphanum (phân biệt chữ/số/ký tự đặc biệt) cũng được tối ưu bằng phép toán bit và tra cứu
Tối ưu parsing số và chuyển sang giai đoạn biên dịch
- Trong Lexer chỉ lưu cửa sổ và hash của token số; việc chuyển đổi số nguyên/số thực thực tế chỉ được thực hiện một lần ở giai đoạn biên dịch để tránh lặp lại
- Khi parsing lặp lại các giá trị số trùng nhau, ghi nhận cải thiện hơn 64% tổng thông lượng xử lý
Tăng tốc IO cho tệp lớn
- Thay vì dùng
fread truyền thống, dùng mmap để ánh xạ trực tiếp toàn bộ tệp vào bộ nhớ
- Hàm
IO_read_file_to_string dùng mmap cho toàn bộ đầu vào, cho thấy cải thiện hiệu năng 6 đến 35 lần với dữ liệu lớn
Benchmark thực chiến và so sánh hiệu năng
- Trên laptop: hơn 1.000.000 dòng, đầu vào 25MB, chỉ 44ms để token hóa
- Trên desktop: đạt 30ms với cùng đầu vào (tối đa 848MB/s)
- So với các lexer khác, nhanh hơn trên 10 lần (0,3 giây so với 2~13 giây)
- Micro-benchmark định lượng tác động của từng tối ưu hóa (ví dụ: dùng bump allocator 1,58 lần, chuỗi 0 alloc 1,4~1,5 lần, chuyển parsing số sang giai đoạn biên dịch 2,8 lần, v.v.)
Tóm tắt chiến lược triển khai
- Phân nhánh trực tiếp dựa trên bảng nhảy (threaded lexing)
- Cấu trúc token cửa sổ không sao chép
- Interning token hằng
- Quản lý bộ nhớ bằng bump allocator
- Băm token và so sánh băm dựng sẵn
- Parsing trễ và interning cho token số/chuỗi
- Xử lý tệp lớn bằng mmap
- Các hướng tiếp theo gồm tận dụng SIMD, thuật toán băm nhanh hơn, căn chỉnh bộ nhớ và prefetch, tối ưu bảng nhảy theo từng kiểu đầu vào
Chưa có bình luận nào.