GHC優化：Collat​​z猜想

Question

我已經編寫代碼爲Project Euler's Challenge 14，在Haskell和C++（ideone鏈接）。他們都記得他們之前在數組中做過的任何計算。

分別使用ghc -O2和g++ -O3，C++運行速度比Haskell版本快10-15倍。

儘管我明白Haskell版本可能運行速度較慢，並且Haskell是一種更好的語言編寫方式，但知道我可以對Haskell版本進行一些代碼更改以使其運行速度更快（理想情況下， C++版本的2或3的因子）？

---

Haskell代碼是在這裏：

import Data.Array 
import Data.Word 
import Data.List 

collatz_array = 
    let 
    upperbound = 1000000 
    a = array (1, upperbound) [(i :: Word64, f i :: Int) | i <- [1..upperbound]] 
    f i = i `seq` 
     let 
     check_f i = i `seq` if i <= upperbound then a ! i else f i 
     in 
     if (i == 1) then 0 else (check_f ((if (even i) then i else 3 * i + 1) `div` 2)) + 1 
    in a 

main = 
    putStrLn $ show $ 
    foldl1' (\(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array) 

---

編輯：

現在我也做使用未裝箱的可變陣列版本。它仍然比C++版本慢5倍，但是是一個顯着的改進。代碼在ideone here。

我想知道改進的可變陣列版本，使其更接近C++版本。

Answer 1

與你（可變數組）代碼的一些問題：

• 您使用倍找到最大鏈長，因爲數組必須轉換爲關聯列表，這需要花費時間和C++版本不需要的分配。
• 您使用even和div測試resp除以2.這些很慢。 g ++將操作優化爲更快的位操作（至少在更快的平臺上），但GHC不會進行這些低級優化（暫時），所以暫時必須手工完成。
• 您使用readArray和writeArray。在C++代碼中沒有完成的額外邊界檢查也需要時間，一旦其他問題得到處理，這相當於運行時間的很大一部分（我的框中約爲25％），因爲已經完成了算法中有很多讀寫操作。

納入到這一點的實現，我得到

import Data.Array.ST 
import Data.Array.Base 
import Control.Monad.ST 
import Data.Bits 

collatz_array :: ST s (STUArray s Int Int) 
collatz_array = do 
    let upper = 10000000 
    arr <- newArray (0,upper) 0 
    unsafeWrite arr 2 1 
    let check i 
      | upper < i = return arr 
      | i .&. 1 == 0 = do 
       l <- unsafeRead arr (i `shiftR` 1) 
       unsafeWrite arr i (l+1) 
       check (i+1) 
      | otherwise = do 
       let j = (3*i+1) `shiftR` 1 
        find k l 
         | upper < k = find (next k) $! l+1 
         | k < i  = do 
          m <- unsafeRead arr k 
          return (m+l) 
         | otherwise = do 
          m <- unsafeRead arr k 
          if m == 0 
           then do 
            n <- find (next k) 1 
            unsafeWrite arr k n 
            return (n+l) 
           else return (m+l) 
          where 
          next h 
           | h .&. 1 == 0 = h `shiftR` 1 
           | otherwise = (3*h+1) `shiftR` 1 
       l <- find j 1 
       unsafeWrite arr i l 
       check (i+1) 
    check 3 

collatz_max :: ST s (Int,Int) 
collatz_max = do 
    car <- collatz_array 
    (_,upper) <- getBounds car 
    let find w m i 
      | upper < i = return (w,m) 
      | otherwise = do 
       l <- unsafeRead car i 
       if m < l 
        then find i l (i+1) 
        else find w m (i+1) 
    find 1 0 2 

main :: IO() 
main = print (runST collatz_max) 

而且定時（均爲10元）：

$ time ./cccoll 
8400511 429 

real 0m0.210s 
user 0m0.200s 
sys  0m0.009s 
$ time ./stcoll 
(8400511,429) 

real 0m0.341s 
user 0m0.307s 
sys  0m0.033s 

看起來並不太壞。

重要提示：該代碼只能在64位GHC（因此，特別是在Windows，你需要GHC-7.6.1或更高版本，以前GHCs是32位甚至64位Windows）因爲中間鏈元素超過32位範圍。在32位系統上，由於原始的64位操作（算術和移位）被實現爲32位系統，所以必須使用Integer或64位整數類型（Int64或Word64）外部調用32位GHC中的C函數（快速外部調用，但仍然比直接機器操作慢得多）。

Answer 2

ideone網站正在使用一個ghc 6.8.2，這是越來越古老。在ghc版本7.4.1上，差異要小得多。

隨着GHC：

$ ghc -O2 euler14.hs && time ./euler14 
(837799,329) 
./euler14 0.63s user 0.04s system 98% cpu 0.685 total 

隨着克++ 4.7.0：

$ g++ --std=c++0x -O3 euler14.cpp && time ./a.out 
8400511 429 
./a.out 0.24s user 0.01s system 99% cpu 0.252 total 

對我來說，GHC版本比C++版本僅慢2.7倍。 另外，兩個方案都沒有給予同樣的結果......（不是一個好兆頭，特別是對於基準）