Tại sao phiên bản so khớp mẫu lười của hàm splitAt nhanh hơn?

Question

Các splitAt chức năng có thể được thực hiện như sau (https://wiki.haskell.org/Lazy_pattern_match):

import Prelude hiding (splitAt) 
splitAt :: Int -> [a] -> ([a], [a]) 
splitAt n xs = 
    if n<=0 
    then ([], xs) 
    else 
     case xs of 
      [] -> ([], []) 
      y:ys -> 
      case splitAt (n-1) ys of 
       ~(prefix, suffix) -> (y : prefix, suffix) -- Here using lazy pattern match 

main :: IO() 
main = do 
    let r = splitAt 1000000 $ repeat 'a' 
    print $ length $ fst r 

Và sử dụng các mô hình phù hợp chặt chẽ có thể làm chậm tốc độ rất nhiều.

time ./lazy  -- 0.04s user 0.00s system 90% cpu 0.047 total 
time ./strict -- 0.12s user 0.02s system 96% cpu 0.147 total 

Tôi không thể hiểu lý do. Theo bài báo, phiên bản nghiêm ngặt có thể cần nhiều bộ nhớ hơn và tất cả các cuộc gọi đệ quy để kiểm tra xem mẫu có phù hợp hay không. Nhưng tôi nghĩ rằng phiên bản lười biếng cũng cần tất cả các cuộc gọi đệ quy và cần bộ nhớ để chứa kết quả của các cuộc gọi hàm đệ qui. Điều gì tạo ra sự khác biệt đó?

Answer 1

Có nhiều sự khác biệt.

Chúng ta hãy nhìn vào sự khác biệt giữa hoạt động các biến thể có và không có ~ trên dòng 11.

đánh giá trong GHC Haskell được thúc đẩy bởi mô hình khớp. Khi một mẫu được khớp trong một biểu thức trường hợp hoặc LHS của một định nghĩa hàm, nó yêu cầu các hàm tạo trong mẫu được đánh giá. Vì vậy, đó có nghĩa là đánh giá splitAt 1000000 (repeat 'a') phụ thuộc vào việc kết hợp các nhà xây dựng (,) kết quả từ các cuộc gọi đệ quy đến splitAt 999999 ..., và như vậy, tất cả các con đường xuống cuộc gọi cuối cùng của splitAt 0 .... Điều này đòi hỏi không gian ngăn xếp để đánh giá. Khá nhiều, trên thực tế. Nó rất có thể ngăn xếp phải được trồng nhiều lần để tránh bị rơi.

Ngoài ra, toàn bộ chuỗi kết quả "aaaaa..." được tạo trên heap trong khi điều này đang diễn ra, trước khi length bắt đầu xử lý nó. (Do tối ưu hóa trong repeat, yếu tố thứ hai của kết quả thực sự là một danh sách được liên kết theo vòng tròn mà không bao giờ phân bổ bất kỳ điều gì mới trong toàn bộ đánh giá đệ quy.)

Khi khớp mẫu được thực hiện, mọi thứ thay đổi. Giá trị trả lại từ splitAt 1000000 (repeat 'a') được đánh giá là ('a':_thunk1, _thunk2) mà không bao giờ thực hiện cuộc gọi đệ quy đến splitAt. Đây là một mô hình được gọi là corecursion bảo vệ. Việc đánh giá thêm được ẩn đằng sau các nhà xây dựng dữ liệu như (,) và (:) và do đó chỉ được thực hiện nếu được yêu cầu bởi một biểu thức trường hợp khác.

Cuộc gọi đến fst ném đi _thunk2, vì vậy nó sẽ không bao giờ được đánh giá. Cuộc gọi đến length bắt đầu bằng cách sử dụng hàm tạo (:) đầu tiên, ném ra giá trị 'a' và sau đó thực hiện cuộc gọi đệ quy trên _thunk1. Tại thời điểm này, không có gì trong bộ nhớ vẫn còn đề cập đến các nhà xây dựng (:), do đó, các bộ thu rác là miễn phí để lấy lại nó khi nó chạy tiếp theo. (Giá trị 'a' được chia sẻ, do đó, vẫn có con trỏ đến nó, do đó, nó không được thu thập cũng không được phân bổ trong quá trình này.)

Điều gì xảy ra khi _thunk1 được đánh giá là một chút tinh tế. Nó thực hiện cuộc gọi đệ quy đến splitAt 999999 .... Nó kết quả trong ('a':_thunk3, _thunk4). Không có gì đang giữ trên _thunk4, do đó, bạn có thể lấy rác miễn phí bất cứ khi nào. Đánh giá số tiền thu được là length như trên. Các nhà xây dựng (:) không còn được giữ trong bộ nhớ, và là miễn phí để được thu thập.

Quá trình đánh giá diễn ra theo cách đó, chỉ bao giờ giữ một nhà xây dựng đơn lẻ (:) trên heap tại một thời điểm và không cần phải đốt bất kỳ không gian ngăn xếp nào. Và thời gian chạy của người thu gom rác của GHC phụ thuộc vào quy mô của bộ dân cư. Vì có tối đa (:) người xây dựng thường trú, nó hoạt động nhanh chóng trong trường hợp này là .

Tôi nghi ngờ trong trường hợp này, đó là sự khác biệt về tốc độ mà bạn thấy. Bạn nên thử chạy hai chương trình với đối số +RTS -s và xem số liệu thống kê liên quan đến thời gian chạy tối đa của cư dân và thời gian chạy bộ gom rác.

Có thể GHC đang được thực sự là thông minh trong tối ưu hóa. Tôi đã không kiểm tra nó ra, nhưng tôi biết trong một số trường hợp nó có thể viết lại các thuật toán trong điều khoản của ứng dụng (:) rõ ràng về chức năng build. Nếu nó được làm như vậy, nó sẽ cho phép foldr/xây dựng phản ứng tổng hợp để loại bỏ sự phân bổ của các nhà xây dựng (:) hoàn toàn. (Có, length được xác định theo điều khoản của foldr thông qua một số thủ thuật thực sự thú vị cho hiệu quả, chủ yếu là để cho phép foldr/xây dựng phản ứng tổng hợp để hoạt động.)

Nếu bạn gặp phải vấn đề này, trường hợp - nhưng trường hợp nghiêm ngặt sẽ chỉ là xấu. Tôi không nghĩ rằng điều đó có thể xảy ra ở đây, nhưng tôi không chắc chắn, vì tôi chưa thử nghiệm.