Tối ưu hóa tính toán một phần trong Haskell

Question

tôi tò mò làm thế nào để tối ưu hóa mã này:

fun n = (sum l, f $ f0 l, g $ g0 l) 
    where l = map h [1..n] 

Giả sử rằng f, f0, g, g0, và h đều tốn kém, nhưng việc tạo ra và lưu trữ của l là cực kỳ đắt.

Khi được viết, l được lưu trữ cho đến khi bộ trả về được đánh giá đầy đủ hoặc thu thập rác. Thay vào đó, length l, f0 l và g0 l tất cả sẽ được thực hiện bất kỳ khi nào một trong số chúng được thực thi, nhưng f và g sẽ bị trì hoãn.

Nó xuất hiện hành vi này có thể được cố định bằng cách viết:

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

Hoặc rất giống nhau:

fun n = (a,b,c) `deepSeq` (a, f b, g c) 
    where ... 

Chúng tôi có lẽ có thể chỉ định một loạt các loại nội bộ để đạt được hiệu quả tương tự như tốt, trông rất đau đớn. Có sự lựa chọn nào khác không?

Ngoài ra, tôi rõ ràng là hy vọng với inline s của tôi rằng trình biên dịch cầu chì sum, f0, và g0 vào một vòng lặp duy nhất xây dựng và tiêu thụ l hạn bởi hạn. Tôi có thể làm cho điều này rõ ràng thông qua inlining hướng dẫn sử dụng, nhưng that'd suck. Có cách nào để ngăn chặn một cách rõ ràng danh sách l từ khi được tạo và/hoặc bắt buộc nội tuyến không? Pragmas tạo ra cảnh báo hoặc lỗi nếu nội tuyến hoặc lỗi kết hợp thất bại trong quá trình biên dịch có lẽ?

Là một sang một bên, tôi rất tò mò về lý do tại sao seq, inline, lazy, v.v. đều được xác định theo let x = x in x trong chế độ Prelude. Điều này chỉ đơn giản là để cung cấp cho họ một định nghĩa cho trình biên dịch để ghi đè?

Answer 1

Nếu bạn muốn chắc chắn, cách duy nhất là tự làm điều đó. Đối với bất kỳ phiên bản trình biên dịch nào, bạn có thể thử một số công thức mã nguồn và kiểm tra mã nguồn lõi/assembly/llvm được tạo/bất kể nó có làm những gì bạn muốn hay không. Nhưng điều đó có thể phá vỡ với mỗi phiên bản trình biên dịch mới.

Nếu bạn viết

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

hoặc phiên bản deepseq đó, trình biên dịch có thể có thể kết hợp các tính toán của a, b và c phải được thực hiện song song (không phải theo nghĩa đồng thời) trong một đơn traversal của l, nhưng trong thời gian này, tôi khá tin rằng GHC không, và tôi sẽ ngạc nhiên nếu JHC hoặc UHC đã làm. Và cho rằng cấu trúc của máy tính b và c cần phải đơn giản.

Cách duy nhất để có được kết quả mong muốn một cách hợp lý giữa các trình biên dịch và các phiên bản trình biên dịch là tự làm điều đó. Trong vài năm tới, ít nhất.

Tùy thuộc vào f0 và g0, nó có thể là đơn giản như làm một lần trái nghiêm khắc với loại ắc thích hợp và chức năng kết hợp, giống như nổi tiếng trung bình

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double 

average :: [Double] -> Double 
average = ratio . foldl' count (P 0 0) 
    where 
    ratio (P n s) = s/fromIntegral n 
    count (P n s) x = P (n+1) (s+x) 

nhưng nếu cấu trúc của f0 và/hoặc g0 không phù hợp, nói rằng một cái gấp trái và cái kia là một nếp gấp bên phải, nó có thể không thể thực hiện việc tính toán trong một lần truyền tải. Trong những trường hợp như vậy, lựa chọn giữa việc tạo lại l và lưu trữ l. Lưu trữ l dễ dàng đạt được với chia sẻ rõ ràng (where l = map h [1..n]), nhưng việc tạo lại nó có thể khó đạt được nếu trình biên dịch thực hiện một số loại trừ biểu hiện chung (không may, GHC không có xu hướng chia sẻ danh sách của biểu mẫu đó, mặc dù CSE nhỏ). Đối với GHC, cờ fno-cse và -fno-full-laziness có thể giúp tránh chia sẻ không mong muốn.