Làm cách nào để cải thiện hiệu suất của chương trình Haskell này?

Question

Tôi đang làm việc thông qua các vấn đề trong Project Euler như một cách để học Haskell và tôi thấy rằng các chương trình của tôi chậm hơn rất nhiều so với phiên bản C so sánh, ngay cả khi được biên dịch. Tôi có thể làm gì để tăng tốc các chương trình Haskell của mình?

Ví dụ, giải pháp brute-force của tôi để Problem 14 là:

import Data.Int 
import Data.Ord 
import Data.List 

searchTo = 1000000 

nextNumber :: Int64 -> Int64 
nextNumber n 
    | even n = n `div` 2 
    | otherwise = 3 * n + 1 

sequenceLength :: Int64 -> Int 
sequenceLength 1 = 1 
sequenceLength n = 1 + (sequenceLength next) 
    where next = nextNumber n 

longestSequence = maximumBy (comparing sequenceLength) [1..searchTo] 

main = putStrLn $ show $ longestSequence 

nào mất khoảng 220 giây, trong khi một phiên bản "tương đương" brute-force C chỉ mất 1,2 giây.

#include <stdio.h> 

int main(int argc, char **argv) 
{ 
    int longest = 0; 
    int terms = 0; 
    int i; 
    unsigned long j; 

    for (i = 1; i <= 1000000; i++) 
    { 
     j = i; 
     int this_terms = 1; 

     while (j != 1) 
     { 
      this_terms++; 

      if (this_terms > terms) 
      { 
       terms = this_terms; 
       longest = i; 
      } 

      if (j % 2 == 0) 
       j = j/2; 
      else 
       j = 3 * j + 1; 
     } 
    } 

    printf("%d\n", longest); 
    return 0; 
} 

Tôi đang làm gì sai? Hay tôi ngây thơ khi nghĩ rằng Haskell thậm chí có thể tiếp cận tốc độ của C?

(Tôi đang biên dịch phiên bản C với gcc -O2 và phiên bản Haskell có ghc --make -O).

Answer 1

Với mục đích thử nghiệm, tôi vừa thiết lập searchTo = 100000. Thời gian thực hiện là 7.34s. Một vài sửa đổi dẫn đến một số cải tiến lớn:

1. Sử dụng số Integer thay vì Int64. Điều này cải thiện thời gian tới 1.75s.

2. Sử dụng bộ tích lũy (bạn không cần trình tựLength phải lười?) 1.54s.

   seqLen2 :: Int -> Integer -> Int 
   seqLen2 a 1 = a 
   seqLen2 a n = seqLen2 (a+1) (nextNumber n) 
   
   sequenceLength :: Integer -> Int 
   sequenceLength = seqLen2 1 
   

3. Viết lại nextNumber sử dụng quotRem, như vậy tránh được tính toán phân chia hai lần (một lần trong even và một lần trong div). 1.27s.

   nextNumber :: Integer -> Integer 
   nextNumber n 
       | r == 0 = q 
       | otherwise = 6*q + 4 
       where (q,r) = quotRem n 2 
   

4. Sử dụng Schwartzian transform thay vì maximumBy. Vấn đề của maximumBy . comparing là chức năng sequenceLength được gọi nhiều lần cho mỗi giá trị. 0,32s.

   longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]] 
   

---

Lưu ý:

• tôi kiểm tra thời gian bằng cách biên soạn với ghc -O và chạy với +RTS -s)
• máy của tôi đang chạy trên Mac OS X 10.6. Phiên bản GHC là 6.12.2. Tệp được biên dịch có trong kiến ​​trúc i386.)
• Sự cố C chạy tại 0.078s với thông số tương ứng. Nó được biên dịch với gcc -O3 -m32.

Answer 2

Danh sách của Haskell dựa trên heap, trong khi mã C của bạn cực kỳ chặt chẽ và không hề sử dụng hết. Bạn cần phải cấu trúc lại để loại bỏ sự phụ thuộc vào danh sách.

Answer 3

So sánh có thể là chuỗi giới thiệu lại quá nhiều. Đây là phiên bản tốt nhất của tôi:

type I = Integer 
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show) 

searchTo = 1000000 

nextNumber :: I -> I 
nextNumber n = case quotRem n 2 of 
        (n2,0) -> n2 
        _ -> 3*n+1 

sequenceLength :: I -> Int 
sequenceLength x = count x 1 where 
    count 1 acc = acc 
    count n acc = count (nextNumber n) (succ acc) 

longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo] 

main = putStrLn $ show $ longestSequence 

Câu trả lời và thời gian là chậm hơn so với C, nhưng nó sử dụng tùy tiện chính xác Integer:

ghc -O2 --make euler14-fgij.hs 
time ./euler14-fgij 
P 525 837799 

real 0m3.235s 
user 0m3.184s 
sys 0m0.015s 

Answer 4

Thậm chí nếu tôi hơi muộn, đây là của tôi, Tôi đã loại bỏ sự phụ thuộc vào danh sách và giải pháp này cũng không sử dụng tất cả.

{-# LANGUAGE BangPatterns #-} 
-- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs 
module Main (main) where 

searchTo :: Int 
searchTo = 1000000 

nextNumber :: Int -> Int 
nextNumber n = case n `divMod` 2 of 
    (k,0) -> k 
    _  -> 3*n + 1 

sequenceLength :: Int -> Int 
sequenceLength n = sl 1 n where 
    sl k 1 = k 
    sl k x = sl (k + 1) (nextNumber x) 

longestSequence :: Int 
longestSequence = testValues 1 0 0 where 
    testValues number !longest !longestNum 
    | number > searchTo  = longestNum 
    | otherwise   = testValues (number + 1) longest' longestNum' where 
    nlength = sequenceLength number 
    (longest',longestNum') = if nlength > longest 
     then (nlength,number) 
     else (longest,longestNum) 

main :: IO() 
main = print longestSequence 

Tôi đã biên soạn mẫu này với ghc -O2 -fvia-C -optc-O3 -Wall euler.hs và chạy trong 5 giây, so với 80 giây khi triển khai bắt đầu. Nó không sử dụng Integer, nhưng vì tôi đang ở trên một máy 64-bit, kết quả có thể bị lừa.

Trình biên dịch có thể unbox tất cả các Int trong trường hợp này, dẫn đến mã thực sự nhanh. Nó chạy nhanh hơn tất cả các giải pháp khác mà tôi đã thấy cho đến nay, nhưng C vẫn nhanh hơn.

Answer 5

Mặc dù điều này đã khá cũ, hãy để tôi kêu vang, có một điểm quan trọng chưa được giải quyết trước đây.

Đầu tiên, thời gian của các chương trình khác nhau trên hộp của tôi. Vì tôi đang sử dụng hệ thống Linux 64 bit, chúng hiển thị một số đặc điểm khác nhau: sử dụng Integer thay vì Int64 không cải thiện hiệu suất như với GHC 32 bit, trong đó mỗi hoạt động Int64 sẽ phải chịu chi phí của cuộc gọi C trong khi các tính toán với số nguyên 32 bit đã ký không cần một cuộc gọi nước ngoài (vì chỉ có một vài thao tác vượt quá phạm vi đó ở đây, Integer là lựa chọn tốt hơn trên GHC 32 bit).

• C: 0,3 giây
• gốc Haskell: 14.24 giây, sử dụng Integer thay vì Int64: 33,96 giây
• phiên bản cải tiến KennyTM của: 5,55 giây, sử dụng Int: 1,85 giây
• phiên bản Chris Kuklewicz của: 5,73 giây, sử dụng Int: 1.90 giây
• Phiên bản FUZxxl: 3.56 giây, sử dụng quotRem thay vì divMod: 1.79 giây

Vậy chúng ta có gì?

1. Tính chiều dài với một ắc quá trình biên dịch có thể chuyển đổi nó (về cơ bản) vào một vòng lặp
2. Đừng tính toán lại các chuỗi độ dài cho sự so sánh
3. Không sử dụng div resp. divMod khi không cần thiết, quot resp. quotRem nhanh hơn nhiều

Điều gì vẫn còn thiếu?

if (j % 2 == 0) 
    j = j/2; 
else 
    j = 3 * j + 1; 

Bất kỳ trình biên dịch C nào tôi đã sử dụng biến đổi thử nghiệm j % 2 == 0 thành bit-masking và không sử dụng lệnh chia. GHC không (chưa) làm điều đó.Vì vậy, kiểm tra even n hoặc tính toán n `quotRem` 2 là một hoạt động khá tốn kém. Thay nextNumber trong phiên bản KennyTM của Integer với

nextNumber :: Integer -> Integer 
nextNumber n 
    | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2 
    | otherwise = 3*n+1 

giảm thời gian chạy tới 3,25 giây (Lưu ý: cho Integer, n `quot` 2 nhanh hơn n `shiftR` 1, mà mất 12,69 giây).

Làm tương tự trong phiên bản Int sẽ giảm thời gian chạy xuống 0,41 giây. Đối với Int s, bit-shift cho phép chia cho 2 nhanh hơn một chút so với hoạt động quot, giảm thời gian chạy của nó xuống 0,39 giây.

Loại bỏ việc xây dựng danh sách (mà không xuất hiện trong phiên bản C hoặc),

module Main (main) where 

import Data.Bits 

result :: Int 
result = findMax 0 0 1 

findMax :: Int -> Int -> Int -> Int 
findMax start len can 
    | can > 1000000 = start 
    | canlen > len = findMax can canlen (can+1) 
    | otherwise = findMax start len (can+1) 
     where 
     canlen = findLen 1 can 

findLen :: Int -> Int -> Int 
findLen l 1 = l 
findLen l n 
    | n .&. 1 == 0 = findLen (l+1) (n `shiftR` 1) 
    | otherwise  = findLen (l+1) (3*n+1) 

main :: IO() 
main = print result 

mang lại sự tăng tốc nhỏ hơn nữa, kết quả trong một thời gian chạy là 0,37 giây.

Vì vậy, phiên bản Haskell gần giống với phiên bản C không mất nhiều thời gian hơn nữa, đó là hệ số của ~ 1.3.

Vâng, chúng ta hãy công bằng, có một sự kém hiệu quả trong phiên bản C đó là không có mặt trong phiên bản Haskell,

if (this_terms > terms) 
{ 
    terms = this_terms; 
    longest = i; 
} 

xuất hiện trong các vòng trong. Nâng nó ra khỏi vòng lặp bên trong trong phiên bản C giảm thời gian chạy của nó xuống 0.27 giây, làm cho hệ số ~ 1.4.