Tối ưu hóa chức năng danh sách tạo ra quá nhiều rác (không tràn ngăn xếp)

Question

Tôi có chức năng Haskell, điều này gây ra hơn 50% tất cả phân bổ chương trình của tôi, làm cho 60% thời gian chạy của tôi . Tôi chạy với một ngăn xếp nhỏ (-K10K) do đó không có tràn ngăn xếp, nhưng tôi có thể làm cho chức năng này nhanh hơn, với phân bổ ít hơn?

Mục tiêu ở đây là tính sản phẩm của ma trận bằng vectơ. Ví dụ: tôi không thể sử dụng hmatrix vì đây là một phần của chức năng lớn hơn bằng gói ad Automatic Differentiation, vì vậy tôi cần sử dụng danh sách Num. Khi chạy, tôi giả sử việc sử dụng mô-đun Numeric.AD có nghĩa là các loại của tôi phải là Scalar Double.

listMProd :: (Num a) => [a] -> [a] -> [a] 
listMProd mdt vdt = go mdt vdt 0 
    where 
    go [] _ s = [s] 
    go ls [] s = s : go ls vdt 0 
    go (y:ys) (x:xs) ix = go ys xs (y*x+ix) 

Về cơ bản chúng ta lặp qua ma trận, nhân và thêm một ắc cho đến khi chúng ta đạt được kết thúc của vector, lưu trữ kết quả, sau đó tiếp tục khởi động lại vector một lần nữa. Tôi có một thử nghiệm quickcheck xác minh rằng tôi nhận được kết quả tương tự so với sản phẩm ma trận/vector trong hmatrix.

Tôi đã thử với foldl, foldr, v.v. Không có gì tôi đã thử làm cho chức năng nhanh hơn (và một số thứ như foldr gây rò rỉ không gian).

Chạy với hồ sơ cho tôi biết, trên thực tế chức năng này là nơi hầu hết thời gian và phân bổ được chi tiêu, có vô số Cells đang được tạo, Cells là loại dữ liệu từ gói ad.

Một xét nghiệm đơn giản để chạy:

import Numeric.AD 

main = do 
    let m :: [Double] = replicate 400 0.2 
     v :: [Double] = replicate 4 0.1 
     mycost v m = sum $ listMProd m v 
     mygrads = gradientDescent (mycost (map auto v)) (map auto m) 
    print $ mygrads !! 1000 

này trên máy tính của tôi nói với tôi GC đang bận 47% thời gian.

Bất kỳ ý tưởng nào?

Answer 1

Một tối ưu hóa rất đơn giản là làm cho go chức năng nghiêm ngặt bởi tham số ắc nó, bởi vì nó nhỏ, có thể là không có hộp bọc nếu a là nguyên thủy và luôn luôn cần phải được đánh giá đầy đủ:

{-# LANGUAGE BangPatterns #-} 
listMProd :: (Num a) => [a] -> [a] -> [a] 
listMProd mdt vdt = go mdt vdt 0 
    where 
    go [] _ !s = [s] 
    go ls [] !s = s : go ls vdt 0 
    go (y:ys) (x:xs) !ix = go ys xs (y*x+ix) 

Trên máy tính của tôi, nó cho tốc độ 3-4x (được biên dịch với -O2).

Mặt khác, danh sách trung gian không được nghiêm ngặt để chúng có thể hợp nhất.