stack tràn trong OCaml và F # nhưng không phải trong Haskell

Question

Tôi đã so sánh cho các ngôn ngữ khác nhau vui vẻ cho tốc độ trong thực hiện các chương trình sau đây: cho tôi 1-1.000.000 tổng sản phẩm i * (sqrt i)

Một trong những triển khai của tôi (không phải là duy nhất) đang xây dựng danh sách [1..1000000] và sau đó gấp với một hàm cụ thể.

Chương trình hoạt động tốt và nhanh trong Haskell (ngay cả khi sử dụng nếp gấp và không gấp) 'nhưng ngăn xếp tràn trong OCaml và F #.

Đây là mã Haskell:

test = foldl (\ a b -> a + b * (sqrt b)) 0 

create 0 = [] 
create n = n:(create (n-1)) 

main = print (test (create 1000000)) 

Và đây là OCaml một:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;; 

let rec create = function 
    | 0 -> [] 
    | n -> n::(create (n-1)) ;; 

print_float (test (create 1000000));; 

Tại sao OCaml/F # thực hiện stack tràn?

Answer 1

Mã Haskell cho create đánh giá danh sách một cách uể oải, tức là các thành phần là cần thiết bởi foldl. Toàn bộ danh sách là không cần thiết cùng một lúc.

Ngược lại, F # và OCaml đánh giá đúng danh sách create, tức là mã cố gắng tạo toàn bộ danh sách trong một lần trước khi chuyển nó đến fold_left.

Một khả năng trong F # là sử dụng biểu thức seq trong chức năng create: điều này tạo danh sách lười biếng theo cùng cách với Haskell. (Tôi không chắc liệu OCaml có một tính năng tương đương hay không.)

Answer 2

Trong biểu mẫu này, hàm create của bạn không phải là đệ quy đuôi. Bạn có thể viết lại nó trong một hình thức đệ quy đuôi mà không gây ra một chồng tràn:

let rec create n l = 
    match n with 
    | 0 -> l 
    | n -> create (n-1) (n::l) 

print_float (test (create 1000000 []));; 

Answer 3

Một cách khác để sửa chữa đoạn code để nó hoạt động trong F # là sử dụng biểu thức chuỗi đó cũng được tạo ra một cách lười biếng và trong một cách không gây ra StackOverflow (điều này sẽ không hoạt động trong OCaml, vì các biểu thức trình tự là F # cụ thể). Đây là mã:

let test nums = Seq.fold (fun a b -> 
    a + (float b) * (sqrt (float b))) 0.0 nums 

let rec create count = seq { 
    match count with 
    | 0 -> do() 
    | n -> yield n 
     yield! create (n-1) } 

printf "%f" (test (create 1000000));; 

Tôi không chắc chắn về hiệu suất, tuy nhiên trình biên dịch chắc chắn không một tối ưu hóa trong create chức năng, do đó lặp lại trong chuỗi tạo nên một cách hợp lý nhanh. Tuy nhiên, mục đích của các biểu thức chuỗi chủ yếu là khả năng đọc (vì F # không thuần túy, nó cho bạn nhiều không gian để tối ưu hóa thủ công nếu bạn thực sự cần chúng thay vì Haskell cần tối ưu hóa mã thuần túy mà bạn viết). Dù sao, nếu bạn có một số xét nghiệm, bạn có thể dùng thử!

Answer 4

Thứ nhất, nếu bạn đang so sánh hiệu suất cho công cụ số, danh sách không phải là lựa chọn tốt nhất. Hãy thử một gói như gói vector cho các mảng nhanh.

Và lưu ý rằng bạn có thể làm tốt hơn nữa trong Haskell, nhờ vào phản ứng tổng hợp vòng lặp. Bằng cách viết hàm tạo ra như một điều tra, trình biên dịch có thể kết hợp bước tạo và vòng lặp, thành một vòng lặp đơn lẻ mà không phân bổ cấu trúc dữ liệu trung gian. Khả năng kết hợp tổng quát như thế này là duy nhất đối với GHC Haskell.

tôi sẽ sử dụng thư viện vector (stream-based loop fusion):

import qualified Data.Vector as V 

test = V.foldl (\ a b -> a + b * sqrt b) 0 

create n = (V.enumFromTo 1 n) 

main = print (test (create 1000000)) 

Bây giờ, trước đó, với mã của bạn, trình biên dịch là không thể loại bỏ tất cả các danh sách, và chúng tôi kết thúc với một bên vòng lặp như:

$wlgo :: Double# -> [Double] -> Double# 

$wlgo = 
    \ (ww_sww :: Double#) (w_swy :: [Double]) -> 
    case w_swy of _ { 
     [] -> ww_sww; 
     : x_aoY xs_aoZ -> 
     case x_aoY of _ { D# x1_aql -> 
     $wlgo 
      (+## 
      ww_sww (*## x1_aql (sqrtDouble# x1_aql))) 
      xs_aoZ 
     } 
    } 

$wcreate :: Double# -> [Double] 

$wcreate = 
    \ (ww_swp :: Double#) -> 
    case ==## ww_swp 0.0 of _ { 
     False -> 
     : 
      @ Double 
      (D# ww_swp) 
      ($wcreate (-## ww_swp 1.0)); 
     True -> [] @ Double 
    } 

Lưu ý cách có hai vòng: tạo danh sách (lười) và gấp nếp gấp. Nhờ sự lười biếng, chi phí của danh sách đó rẻ, vì vậy nó có giá trị đáng kính:

$ time ./C 
4.000004999999896e14 
./C 0.06s user 0.00s system 98% cpu 0.058 total 

Theo hợp nhất, chúng tôi chỉ nhận được một vòng lặp!

main_$s$wfoldlM_loop :: Double# -> Double# -> Double# 

main_$s$wfoldlM_loop = 
    \ (sc_sYc :: Double#) (sc1_sYd :: Double#) -> 
    case <=## sc_sYc 1000000.5 of _ { 
     False -> sc1_sYd; 
     True -> 
     main_$s$wfoldlM_loop 
      (+## sc_sYc 1.0) 
      (+## 
      sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc))) 

GHC giảm các bước tạo và thử nghiệm của chúng tôi thành một vòng lặp không có danh sách được sử dụng. Chỉ cần 2 đôi trong sổ đăng ký. Và với một nửa như nhiều vòng, nó chạy gần gấp đôi càng nhanh:

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make 
$ time ./D 
4.000005000001039e14 
./D 0.04s user 0.00s system 95% cpu 0.038 total 

Đây là một ví dụ tốt đẹp của sức mạnh mà đảm bảo độ tinh khiết cung cấp - trình biên dịch có thể rất hung hăng tại reording mã của bạn.

Answer 5

Chương trình hoạt động tốt và nhanh trong Haskell (ngay cả khi sử dụng nếp gấp và không gấp) 'nhưng ngăn xếp tràn trong OCaml và F #.

Haskell của bạn đang sử dụng danh sách lười nhưng OCaml/F # của bạn đang sử dụng danh sách nghiêm ngặt, vì vậy chương trình của bạn không thể so sánh.

FWIW, một giải pháp sử dụng chuỗi theo yêu cầu trong F # là:

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})