Pharo có tối ưu hóa cuộc gọi đuôi không?

Question

Việc thực hiện Integer>>#factorial trong Pharo là:

factorial 
     "Answer the factorial of the receiver." 

     self = 0 ifTrue: [^ 1]. 
     self > 0 ifTrue: [^ self * (self - 1) factorial]. 
     self error: 'Not valid for negative integers' 

một định nghĩa đuôi-đệ quy này. Tuy nhiên, tôi có thể đánh giá 10000 factorial mà không có lỗi trong không gian làm việc.

Pharo có thực hiện tối ưu hóa cuộc gọi đuôi trong mọi trường hợp hay không, liệu nó có đang thực hiện một số tối ưu hóa khác không, hoặc là nó chỉ sử dụng một ngăn xếp thực sự sâu?

Answer 1

Đó là một chồng thực sự sâu sắc. Hay đúng hơn là, không có ngăn xếp nào cả.

Pharo là hậu duệ của Squeak, kế thừa ngữ nghĩa thi hành trực tiếp từ Smalltalk-80. Không có ngăn xếp kích thước cố định tuyến tính, thay vào đó mọi lệnh gọi phương thức tạo đối tượng MethodContext mới cung cấp không gian cho các đối số và các biến tạm thời trong mỗi cuộc gọi đệ quy. Nó cũng trỏ đến ngữ cảnh gửi (để trả về sau) tạo ra một danh sách các ngữ cảnh được liên kết (được hiển thị giống như một ngăn xếp trong trình gỡ lỗi). Các đối tượng ngữ cảnh được phân bổ trên heap giống như bất kỳ đối tượng nào khác. Điều đó có nghĩa là chuỗi cuộc gọi có thể rất sâu, vì tất cả bộ nhớ có sẵn có thể được sử dụng. Bạn có thể kiểm tra thisContext để xem ngữ cảnh phương pháp hiện đang hoạt động.

Phân bổ tất cả các đối tượng ngữ cảnh này là tốn kém. Đối với tốc độ, các máy ảo hiện đại (chẳng hạn như máy ảo Cog được sử dụng trong Pharo) thực sự sử dụng một chồng trong nội bộ, bao gồm các trang được liên kết, vì vậy nó có thể tùy ý lớn. Các đối tượng ngữ cảnh chỉ được tạo theo yêu cầu (ví dụ: trong khi gỡ lỗi) và tham khảo khung ngăn xếp ẩn và ngược lại. Máy móc đằng sau hậu trường này khá phức tạp, nhưng may mắn được ẩn từ lập trình viên Smalltalk.

Answer 2

Không có gì bí ẩn trong mô hình thực hiện của Pharo. Đoạn đệ quy

^ self * (self - 1) factorial 

điều đó xảy ra bên trong thứ hai ifTrue: biên dịch với trình tự sau đây của bytecode:

39 <70> self     ; receiver of outer message * 
40 <70> self     ; receiver of inner message - 
41 <76> pushConstant: 1  ; argument of self - 1 
42 <B1> send: -    ; subtract 
43 <D0> send: factorial  ; send factorial (nothing special here!) 
44 <B8> send: *    ; multiply 
45 <7C> returnTop    ; return 

Lưu ý rằng trong dòng 43 có gì đặc biệt xảy ra. Mã chỉ gửi factorial theo cách tương tự, có bộ chọn là bất kỳ mã nào khác. Đặc biệt, chúng ta có thể thấy rằng không có thao tác đặc biệt nào của ngăn xếp ở đây.

Điều này không có nghĩa là không thể tối ưu hóa trong mã gốc cơ bản. Nhưng đó là một cuộc thảo luận khác. Đó là việc thực hiện mô hình là vấn đề quan trọng đối với lập trình viên bởi vì bất kỳ tối ưu hóa nào bên dưới bytecode đều có nghĩa là hỗ trợ mô hình này ở cấp độ khái niệm.

CẬP NHẬT

Điều thú vị là phiên bản không đệ quy

factorial2 
    | f | 
    f := 1. 
    2 to: self do: [:i | f := f * i]. 
    ^f 

là một chút chậm mà một trong những đệ quy (Pharo). Lý do phải là chi phí liên quan đến việc tăng i lớn hơn một chút so với cơ chế gửi đệ quy.

Dưới đây là những biểu hiện tôi đã cố gắng:

[25000 factorial] timeToRun 
[25000 factorial2] timeToRun