GHC Optimierung: Collatz Vermutung

Question

Ich habe Code für die Project Euler's Challenge 14, in Haskell und C++ (Ideone Links) geschrieben. Beide erinnern sich an Berechnungen, die sie zuvor in einem Array durchgeführt haben.

Mit ghc -O2 bzw. g++ -O3 läuft das C++ 10-15 Mal schneller als die Haskell-Version.

Während ich verstehe, dass die Haskell - Version möglicherweise langsamer läuft, und dass Haskell eine bessere Sprache zum Schreiben ist, wäre es schön, einige Codeänderungen zu kennen, die ich machen kann, um die Haskell - Version schneller laufen zu lassen (idealerweise innerhalb einer Faktor 2 oder 3 der C++ Version)?

---

Haskell-Code ist hier:

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) 

---

Edit:

Ich habe jetzt getan auch eine Version unboxed änderbare Arrays. Es ist immer noch 5 mal langsamer als die C++ - Version, aber eine deutliche Verbesserung. Der Code ist auf Ideone here.

Ich würde gerne Verbesserungen an der veränderbaren Array-Version wissen, die es näher an der C++ - Version bringen.

Answer 1

Einige Probleme mit Ihrem (änderbaren Array) Code:

• Sie verwenden eine Falte Um die maximale Kettenlänge zu finden, muss das Array in eine Assoziationsliste konvertiert werden, die Zeit braucht und die C++ - Version nicht benötigt.
• Sie verwenden even und div zum Testen bzw. Dividieren von 2. Diese sind langsam. g ++ optimiert beide Operationen auf die schnelleren Bitoperationen (auf Plattformen, auf denen dies angeblich mindestens schneller ist), aber GHC führt diese Low-Level-Optimierungen (noch) nicht aus, so dass sie zunächst manuell ausgeführt werden müssen .
• Sie verwenden readArray und writeArray. Die zusätzliche Überprüfung der Grenzen, die im C++ Code nicht gemacht wird, braucht auch Zeit, wenn die anderen Probleme gelöst sind, was einen beträchtlichen Teil der Laufzeit ausmacht (ca. 25% auf meiner Box), da dies erledigt ist viele Lese- und Schreibvorgänge im Algorithmus.

, dass in der Umsetzung Einbeziehung, erhalte ich

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) 

Und die Zeiten (für 10 Millionen):

$ 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 

, die nicht so schlecht aussieht.

Wichtiger Hinweis: Dieser Code funktioniert nur auf 64-Bit-GHC (so, insbesondere unter Windows, müssen Sie ghc-7.6.1 oder später vorheriger GHCs waren 32-Bit auch auf 64-Bit-Windows) da Zwischenkettenelemente den 32-Bit-Bereich überschreiten. Auf 32-Bit-Systemen müsste man Integer oder einen 64-Bit-Integer-Typ (Int64 oder Word64) verwenden, um die Ketten zu verfolgen, mit drastischen Leistungskosten, da die primitiven 64-Bit-Operationen (Arithmetik und Verschiebungen) implementiert sind ausländische Anrufe zu C-Funktionen in 32-Bit-GHCs (schnelle Auslandsgespräche, aber immer noch viel langsamer als direkte Maschine ops).

Answer 2

Die Ideone-Site verwendet eine ghc 6.8.2, die ziemlich alt wird. Bei der ghc-Version 7.4.1 ist der Unterschied viel kleiner.

Mit ghc:

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

mit g ++ 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 

Für mich ist die ghc Version ist nur 2,7-mal langsamer als die C++ Version. Auch sind die beiden Programme nicht das gleiche Ergebnis geben ... (kein gutes Zeichen, vor allem für Benchmarking)