Tối ưu hóa mô-đun chéo trong GHC

Question

Tôi có một hàm không đệ quy để tính toán các chuỗi phổ biến dài nhất có vẻ hoạt động tốt (ghc 7.6.1, được biên dịch với -O2 -fllvm cờ) nếu tôi đo nó bằng Criterion trong cùng một mô-đun. Mặt khác, nếu tôi chuyển đổi hàm thành một mô-đun, chỉ xuất hàm đó (như được đề xuất here) và sau đó đo lại với Tiêu chí, tôi nhận được ~ 2x chậm lại (biến mất nếu tôi di chuyển kiểm tra tiêu chí trở lại mô-đun nơi hàm được xác định). Tôi đã thử đánh dấu hàm bằng INLINE pragma mà không tạo ra bất kỳ sự khác biệt nào về các phép đo hiệu suất mô-đun chéo. Dường như với tôi rằng GHC có thể phân tích nghiêm ngặt hoạt động tốt khi chức năng và chức năng chính (từ đó chức năng có thể truy cập) nằm trong cùng một mô-đun, nhưng không phải khi chúng được phân chia. Tôi sẽ đánh giá cao con trỏ về cách mô đun hóa chức năng để nó hoạt động tốt khi được gọi từ các mô-đun khác. Mã được đề cập quá lớn để dán ở đây - bạn có thể thấy mã số here nếu bạn muốn dùng thử. Một ví dụ nhỏ về những gì tôi đang cố gắng làm là bên dưới (với đoạn mã):

-- Function to find longest common subsequence given unboxed vectors a and b 
-- It returns indices of LCS in a and b 
lcs :: (U.Unbox a, Eq a) => Vector a -> Vector a -> (Vector Int,Vector Int) 
lcs a b | (U.length a > U.length b) = lcsh b a True 
     | otherwise = lcsh a b False 

-- This section below measures performance of lcs function - if I move it to 
-- a different module, performance degrades ~2x - mean goes from ~1.25us to ~2.4us 
-- on my test machine 
{-- 
config :: Config 
config = defaultConfig { cfgSamples = ljust 100 } 

a = U.fromList ['a'..'j'] :: Vector Char 
b = U.fromList ['a'..'k'] :: Vector Char 

suite :: [Benchmark] 
suite = [ 
      bench "lcs 10" $ whnf (lcs a) b 
     ] 

main :: IO() 
main = defaultMainWith config (return()) suite 
--} 

Answer 1

hammaris right, vấn đề quan trọng là trình biên dịch có thể xem các loại mà lcs được sử dụng ở cùng một lúc vì nó có thể thấy mã, do đó, nó có thể chuyên mã cho loại cụ thể đó.

Nếu trình biên dịch không biết loại mã sẽ được sử dụng, nó không thể chỉ tạo mã đa hình. Và đó là xấu cho hiệu suất - Tôi khá ngạc nhiên nó chỉ là một sự khác biệt ~ 2 × ở đây. Mã đa hình có nghĩa là đối với nhiều hoạt động, cần tra cứu loại lớp và ít nhất là không thể nội tuyến chức năng tra cứu hoặc kích thước nếp gấp [ví dụ: cho truy cập mảng/véc tơ không được hộp].

Bạn không thể có được hiệu suất tương đương với trường hợp một mô-đun với việc triển khai và sử dụng trong các mô-đun riêng biệt mà không cần tạo mã cần hiển thị tại trang web sử dụng (hoặc, nếu bạn biết các loại cần thiết tại trang web triển khai , {-# SPECIALISE foo :: Char -> Int, foo :: Bool -> Integer #-} v.v.).

Làm cho mã hiển thị tại trang web sử dụng thường được thực hiện bằng cách phơi bày phần mở ra trong tệp giao diện bằng cách đánh dấu chức năng {-# INLINABLE #-}.

Tôi đã thử đánh dấu hàm bằng INLINE pragma không tạo ra bất kỳ sự khác biệt nào về các phép đo hiệu suất mô-đun chéo.

đánh dấu chỉ

lcs :: (U.Unbox a, Eq a) => Vector a -> Vector a -> (Vector Int,Vector Int) 
lcs a b | (U.length a > U.length b) = lcsh b a True 
     | otherwise = lcsh a b False 

INLINE hoặc INLINABLE không tạo sự khác biệt tất nhiên, chức năng đó là tầm thường, và trình biên dịch cho thấy diễn tiến của nó dù sao, vì nó quá nhỏ. Ngay cả khi nó mở ra không được tiếp xúc, sự khác biệt sẽ không thể đo lường được.

Bạn cần phải phơi bày các unfoldings các chức năng làm việc thực tế quá, ít nhất đó của những người đa hình, lcsh, findSnakes, gridWalk và cmp (cmp là một trong đó là rất quan trọng ở đây, nhưng những người khác là cần thiết để 1 thấy rằng cmp là cần thiết, 2. hãy gọi cho chuyên ngành cmp từ họ).

Làm những INLINABLE, sự khác biệt giữa các trường hợp riêng biệt-mô-đun

$ ./diffBench 
warming up 
estimating clock resolution... 
mean is 1.573571 us (320001 iterations) 
found 2846 outliers among 319999 samples (0.9%) 
    2182 (0.7%) high severe 
estimating cost of a clock call... 
mean is 40.54233 ns (12 iterations) 

benchmarking lcs 10 
mean: 1.628523 us, lb 1.618721 us, ub 1.638985 us, ci 0.950 
std dev: 51.75533 ns, lb 47.04237 ns, ub 58.45611 ns, ci 0.950 
variance introduced by outliers: 26.787% 
variance is moderately inflated by outliers 

và trường hợp đơn mô-đun

$ ./oneModule 
warming up 
estimating clock resolution... 
mean is 1.726459 us (320001 iterations) 
found 2092 outliers among 319999 samples (0.7%) 
    1608 (0.5%) high severe 
estimating cost of a clock call... 
mean is 39.98567 ns (14 iterations) 

benchmarking lcs 10 
mean: 1.523183 us, lb 1.514157 us, ub 1.533071 us, ci 0.950 
std dev: 48.48541 ns, lb 44.43230 ns, ub 55.04251 ns, ci 0.950 
variance introduced by outliers: 26.791% 
variance is moderately inflated by outliers 

là bearably nhỏ.