Pytanie Optymalizacja GHC: domysły Collatza


Napisałem kod dla Projekt Euler's Challenge 14, zarówno Haskell i C ++ (ideone linki). Oboje pamiętają wszelkie obliczenia, które poprzednio zrobili w tablicy.

Za pomocą ghc -O2 i g++ -O3 odpowiednio, C ++ działa 10-15 razy szybciej niż wersja Haskella.

Chociaż rozumiem, że wersja Haskella może działać wolniej, a Haskell jest ładniejszym językiem do napisania, byłoby miło wiedzieć, że niektóre zmiany kodu mogę wprowadzić do wersji Haskell, aby działały szybciej (najlepiej w granicach 2 lub 3 wersji C ++)?


Kod Haskella jest tutaj:

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)

Edytować:

Zrobiłem też teraz wersję za pomocą unboxed mutable tablic. Jest wciąż 5 razy wolniejsza od wersji C ++, ale stanowi znaczną poprawę. Kod jest na idee tutaj.

Chciałbym poznać ulepszenia w wersji tablicy mutable, która przybliża ją do wersji C ++.


12
2018-06-04 03:47


pochodzenie


Tylko FYI, kompilując się z -fllvm poprawia wydajność o ~ 10% na moim komputerze. - Greg E.
Twój seq nie robić różnicy; obie twoje funkcje są ściśle określone i. GHC był dość zły na 64-bitowej arytmetyki na platformach 32-bitowych, ale nie wiem, z której platformy korzystasz. - augustss
Nie używaj div, posługiwać się quot. - augustss
nie wyjaśnia twojego problemu z wydajnością, ale ani C ++ (przynajmniej to, co napisał nanothief), ani kod Haskella nie daje prawidłowej odpowiedzi. Nie mogę skompilować twojego C ++, ale mam czyste rozwiązanie Haskella o tej samej długości co twój kod, który jest około 25% szybszy na moim komputerze i daje prawidłowy wynik. W tym momencie około połowa czasu wygląda na narzut związany z uruchomieniem programu Haskell. - Philip JF
@PhilipJF W jakim stopniu kod nie daje prawidłowego wyniku? Zauważ, że Clinton używa nieco innego kroku, a mianowicie nieparzystego n, on idzie bezpośrednio do (3*n+1)/2 zamiast robić dwa kroki. W ten sposób otrzymuje różne długości łańcucha, ale punkty początkowe najdłuższych łańcuchów są takie same. - Daniel Fischer


Odpowiedzi:


Niektóre problemy z twoim kodem (tablicy tablic):

  • Za pomocą klapki można znaleźć maksymalną długość łańcucha, ponieważ tablica musi zostać przekonwertowana na listę powiązań, która wymaga czasu i alokacji, której wersja C ++ nie potrzebuje.
  • Używasz even i div do testowania lub dzielenia przez 2. Są to powolne. g ++ optymalizuje obie operacje do szybszych operacji bitowych (na platformach, gdzie jest to rzekomo szybsze, przynajmniej), ale GHC nie robi tych optymalizacji niskiego poziomu (jeszcze), więc na razie muszą być wykonywane ręcznie .
  • Używasz readArray i writeArray. Dodatkowe sprawdzanie granic, które nie jest wykonywane w kodzie C ++, zajmuje również czas, gdy inne problemy zostaną rozwiązane, co stanowi znaczną część czasu działania (około 25% na moim polu), ponieważ są one wykonywane wiele odczytów i zapisów w algorytmie.

Włączając to do wdrożenia, otrzymuję

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)

A czasy (oba dla 10 milionów):

$ 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

który nie wygląda zbyt źle.

Ważna uwaga: Ten kod działa tylko w 64-bitowym GHC (w szczególności w Windowsie, potrzebujesz ghc-7.6.1 lub nowszego, poprzednie GHC były 32-bitowe nawet w 64-bitowym Windows), ponieważ elementy pośredniego łańcucha przekraczają zakres 32-bitowy . W systemach 32-bitowych trzeba będzie użyć Integer lub 64-bitowy typ całkowity (Int64 lub Word64) do śledzenia łańcuchów przy drastycznych kosztach wydajności, ponieważ prymitywne 64-bitowe operacje (arytmetyczne i przesunięcia) są implementowane jako obce wywołania funkcji C w 32-bitowych GHC (szybki połączenia zagraniczne, ale nadal znacznie wolniejsze niż bezpośrednie operacje maszynowe).


4
2018-06-04 10:57



(3*h+1) shiftR` 1` jest taki sam jak (shiftR h 1) + h + 1 które na niektórych maszynach może być szybsze - Philip JF
W rzeczy samej. Nie generuje niezawodnie mierzalnej różnicy na mojej, więc jeśli jest różnica, jest mniejsza niż naturalne drgania tutaj. Ale na maszynach z powolnym mnożeniem, to zdecydowanie coś do wypróbowania. - Daniel Fischer


Witryna ideone korzysta z ghc 6.8.2, która jest dość stara. W wersji 7.4.1 ghc różnica jest znacznie mniejsza.

Z ghc:

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

Z 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

Dla mnie wersja ghc jest tylko 2,7 razy wolniejsza niż wersja c ++. Te dwa programy nie dają tego samego rezultatu ... (nie jest to dobry znak, szczególnie w przypadku testów porównawczych)


2
2018-06-04 07:03



Ups, wysłałem 10 milionów, a nie 1 milion testów. Link jest poprawiony. Zauważ, że wersja c ++ zrobiła 10 milionów 2.7 razy szybciej niż Haskell zrobił milion. - Clinton