Tôi đang làm việc trên một ngôn ngữ trung gian và một máy ảo để chạy một ngôn ngữ chức năng với một vài thuộc tính "có vấn đề":Một số tối ưu hóa rõ ràng cho một máy ảo thực hiện một ngôn ngữ chức năng là gì?
namespace- từ vựng (đóng cửa)
- phát triển động gọi stack
- Một loại số nguyên chậm (bignums)
Ngôn ngữ trung gian dựa trên ngăn xếp, với bảng băm đơn giản cho không gian tên hiện tại. Chỉ cần để bạn có được một ý tưởng về những gì có vẻ như, đây là McCarthy91 chức năng:
# McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
args
sto n
rcl n
float 100
gt
.if
.sub
rcl n
float 10
sub
.end
.sub
rcl n
float 11
add
list 1
rcl M
call-fast
list 1
rcl M
tail
.end
call-fast
.end
Các "vòng lặp lớn" là đơn giản:
- lấy một lệnh
- tăng con trỏ lệnh (hoặc chương trình truy cập)
- đánh giá giảng dạy
Cùng với sto, rcl và nhiều thứ khác, có ba hướng dẫn chức năng cuộc gọi:
callbản không gian tên (bản sao sâu) và đẩy con trỏ hướng dẫn vào các cuộc gọi stackcall-fastlà tương tự, nhưng chỉ tạo ra một bản sao cạntailcơ bản là một 'goto'
Việc thực hiện thực sự đơn giản. Để cung cấp cho bạn một ý tưởng tốt hơn, đây chỉ là một đoạn mã ngẫu nhiên từ giữa "vòng lặp lớn" (cập nhật, xem dưới đây)
} else if inst == 2 /* STO */ {
local[data] = stack[len(stack) - 1]
if code[ip + 1][0] != 3 {
stack = stack[:len(stack) - 1]
} else {
ip++
}
} else if inst == 3 /* RCL */ {
stack = append(stack, local[data])
} else if inst == 12 /* .END */ {
outer = outer[:len(outer) - 1]
ip = calls[len(calls) - 1]
calls = calls[:len(calls) - 1]
} else if inst == 20 /* CALL */ {
calls = append(calls, ip)
cp := make(Local, len(local))
copy(cp, local)
outer = append(outer, &cp)
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
} else if inst == 21 /* TAIL */ {
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
Vấn đề là thế này: Gọi McCarthy91 16 lần với giá trị là -10.000 mất , gần như không tạo ra sự khác biệt, 3 giây (sau khi tối ưu hóa bản sao sâu, bổ sung gần một giây).
Câu hỏi của tôi là: Một số kỹ thuật phổ biến để tối ưu hóa việc diễn giải loại ngôn ngữ này là gì? Có trái cây treo thấp nào không?
Tôi đã sử dụng các lát cho danh sách của mình (đối số, các ngăn xếp khác nhau, lát bản đồ cho các không gian tên, ...), vì vậy tôi làm điều này ở mọi nơi: call_stack[:len(call_stack) - 1]. Ngay bây giờ, tôi thực sự không có một đầu mối những gì đoạn mã làm cho chương trình này chậm. Mọi lời khuyên sẽ được đánh giá cao, mặc dù tôi chủ yếu đang tìm kiếm các chiến lược tối ưu hóa chung.
Bên cạnh:
Tôi có thể giảm thời gian thực hiện một chút bằng cách phá vỡ quy ước gọi điện của tôi. Lệnh list <n> tìm nạp n đối số của ngăn xếp và đẩy danh sách trở lại vào ngăn xếp, lệnh args bật ra khỏi danh sách đó và đẩy từng mục trở lại ngăn xếp. Đây là trước hết là kiểm tra các hàm được gọi với số lượng đối số chính xác và thứ hai để có thể gọi hàm với các danh sách đối số biến (tức là(defun f x:xs)). Loại bỏ điều đó, và cũng có thể thêm một hướng dẫn sto* <x>, thay thế sto <x>; rcl <x>, tôi có thể làm cho nó xuống đến 2 giây. Vẫn không rực rỡ, và tôi phải có công việc này list/args. :)
Một sang một bên (đây là một câu hỏi dài tôi biết, xin lỗi):
Profiling chương trình với pprof nói với tôi rất ít (Tôi mới to Go trong trường hợp đó không rõ ràng) :-). Đây là 3 mặt hàng đầu theo báo cáo của pprof:
16 6.1% 6.1% 16 6.1% sweep pkg/runtime/mgc0.c:745
9 3.4% 9.5% 9 3.4% fmt.(*fmt).fmt_qc pkg/fmt/format.go:323
4 1.5% 13.0% 4 1.5% fmt.(*fmt).integer pkg/fmt/format.go:248
Đây là những thay đổi mà tôi đã thực hiện cho đến nay:
- tôi loại bỏ các bảng băm. Thay vào đó, bây giờ tôi chỉ chuyển các con trỏ tới các mảng và tôi chỉ sao chép hiệu quả phạm vi cục bộ khi tôi phải thực hiện.
- Tôi đã thay thế tên lệnh bằng các mã nguyên dương. Trước đây, tôi đã lãng phí khá nhiều thời gian so sánh các chuỗi.
- Các hướng dẫn
call-fastđã biến mất (tăng tốc là không thể đo lường được nữa sau khi thay đổi khác) - Thay vì phải "int", "phao" và "str" hướng dẫn, tôi chỉ có một
evalvà tôi đánh giá hằng tại thời gian biên dịch (biên dịch bytecode). Sau đó,evalchỉ cần đẩy một tham chiếu đến chúng. - Sau khi thay đổi ngữ nghĩa của
.if, tôi có thể loại bỏ các hàm giả này. bây giờ là.if,.elsevà.endif, với ngầm gotos và khối ngữ nghĩa tương tự như.sub. (some example code)
Sau khi triển khai trình biên dịch lexer, parser và bytecode, tốc độ giảm xuống một chút, nhưng không quá khủng khiếp. Tính toán MC (-10000) 16 lần giúp nó đánh giá 4,2 triệu lệnh bytecode trong 1,2 giây. Đây là a sample of the code it generates (từ this).
Vui lòng không sử dụng hashtables và bất kỳ loại tra cứu tên nào khác cho các ngôn ngữ phạm vi từ vựng! Nó không có ý nghĩa gì cả. Trình biên dịch của bạn có thể cấp phát thanh ghi tĩnh. Rất dễ suy ra môi trường đã được thiết lập cho mỗi trừu tượng lambda. –
Tôi chưa thực sự hiểu ý của bạn. Bạn có thể roi lên một ví dụ ngắn, nói cho "rcl" và "sto"? –
Sử dụng các khe số cho các đối số, biến và các biến đóng. Giới thiệu opcodes như 'ldarg N', 'starg N', 'ldloc N', 'stloc N', 'ldenv N', 'stenv N'. Giải quyết tên biến thành các số khi biên dịch. Xây dựng các danh sách biến bị bắt bằng cách so sánh các danh sách biến miễn phí và các biến ràng buộc cho mỗi điểm trừu tượng lambda. Giới thiệu một hướng dẫn đặc biệt để xây dựng một thể hiện đóng cửa (nên tương tự như một cuộc gọi với một danh sách các biến được bắt). Đó là cách hầu hết các ngôn ngữ chức năng được triển khai (cả VM lẫn native). Nó có thể rất hiệu quả. –