Tôi đã đọc một chút từ http://c2.com/cgi/wiki?ImplementingMultipleDispatchLàm thế nào để Julia thực hiện đa phương thức?
Tôi đã gặp một số khó khăn khi tìm kiếm tham chiếu về cách Julia triển khai đa phương thức. Độ phức tạp thời gian chạy của công văn là gì và nó đạt được như thế nào?
Dr. Bezanson's thesis chắc chắn là nguồn tốt nhất cho giới thiệu của ruột Julia ngay bây giờ:
4,3 hệ thống văn
hệ thống văn Julia giống mạnh mẽ hệ thống multimethod tìm thấy trong một số hướng đối tượng ngôn ngữ [17, 40 , 110, 31, 32, 33]. Tuy nhiên, chúng tôi thích thuật ngữ dựa trên kiểu chữ, vì hệ thống của chúng tôi thực sự hoạt động bằng cách gửi một kiểu đối số đơn. Sự khác biệt là tinh tế và trong nhiều trường hợp không đáng chú ý, nhưng có ý nghĩa quan trọng về khái niệm. Nó có nghĩa là các phương thức không nhất thiết bị hạn chế để chỉ định một loại cho mỗi "khe" đối số. Ví dụ, một chữ ký phương thức có thể là
Union{Tuple{Any,Int}, Tuple{Int,Any}}, khớp với các cuộc gọi trong đó, nhưng không nhất thiết là cả hai đối số là một Int.
Phần tiếp tục mô tả loại và phương pháp lưu trữ, phân loại theo độ đặc hiệu, công văn tham số và sự mơ hồ. Lưu ý rằng các kiểu tuple là covariant (không giống như tất cả các kiểu Julian khác) để phù hợp với hành vi covariant của phương thức dispatch. Điều quan trọng nhất ở đây là các định nghĩa phương pháp được sắp xếp theo độ đặc hiệu, vì vậy nó chỉ là một tìm kiếm tuyến tính để kiểm tra xem kiểu tuple đối số có phải là một kiểu con của chữ ký hay không. Vì vậy, đó chỉ là O (n), phải không? Vấn đề là việc kiểm tra các kiểu con có tính tổng quát đầy đủ (bao gồm cả Unions và TypeVars, vv) là khó. Rất khó, trên thực tế. Tồi tệ hơn NP-complete, ước tính là Π P (xem polynomial hierarchy) - tức là, ngay cả khi P = NP, sự cố này vẫn sẽ mất thời gian không đa thức! Nó thậm chí có thể là PSPACE hoặc tệ hơn.
Tất nhiên, nguồn tốt nhất cho hoạt động thực tế là thực hiện trong JuliaLang/julia/src/gf.c (gf = chức năng chung). Có một rather useful comment có:
Phương pháp lưu trữ được chia thành ba phần: một cho chữ ký nơi đối số đầu tiên là một loại singleton (
Type{Foo}), một chỉ mục bởi các UID của kiểu đối số đầu tiên trong trường hợp bình thường, và dự phòng bảng mọi thứ khác.
Vì vậy, câu trả lời cho câu hỏi của bạn về tính phức tạp của tra cứu phương pháp là: "tùy thuộc." Lần đầu tiên một phương thức được gọi với một bộ các loại đối số mới, nó phải đi qua tìm kiếm tuyến tính đó, tìm kiếm một kết hợp loại phụ. Nếu nó tìm thấy một, nó chuyên phương pháp cho các đối số cụ thể và đặt nó vào một trong những bộ đệm. Điều này có nghĩa là trước khi bắt tay vào việc tìm kiếm subtype, Julia có thể thực hiện kiểm tra bình đẳng nhanh chóng so với các phương thức đã thấy… và số phương thức cần kiểm tra được giảm thêm vì cache được lưu trữ như hashtables dựa trên đối số đầu tiên.
Nhưng, thực sự, câu hỏi của bạn là về thời gian chạy thời gian chạy phức tạp của công văn. Trong trường hợp đó, câu trả lời là khá thường xuyên "công văn nào?" - bởi vì nó đã được hoàn toàn loại bỏ! Julia sử dụng LLVM như là một trình biên dịch vừa đủ thời gian, trong đó các phương thức được biên dịch theo yêu cầu khi chúng cần thiết. Trong mã Julia thực hiện, các kiểu nên Điều này hoàn toàn loại bỏ các chi phí thời gian chạy công văn, và thậm chí có khả năng inlines phương pháp tìm thấy trực tiếp vào cơ thể của người gọi (nếu nó nhỏ) để loại bỏ tất cả các chức năng cuộc gọi trên không Nếu các loại không được suy ra cụ thể, có những cạm bẫy hiệu suất khác, và tôi đã không lược tả để xem bao nhiêu thời gian thường được chi tiêu trong công văn. Có nhiều cách để tối ưu hóa trường hợp này hơn nữa, nhưng có có khả năng lớn hơn cá để chiên trước ... và bây giờ nó thường dễ dàng nhất để chỉ làm cho các vòng nóng gõ e-ổn định ở nơi đầu tiên.