Dlaczego ten kod Haskell działa wolniej z -O?

87

Ten fragment kodu Haskella działa znacznie wolniej -O, ale nie -Opowinien być niebezpieczny . Czy ktoś może mi powiedzieć, co się stało? Jeśli ma to znaczenie, jest to próba rozwiązania tego problemu i wykorzystuje wyszukiwanie binarne i trwałe drzewo segmentów:

import Control.Monad
import Data.Array

data Node =
      Leaf   Int           -- value
    | Branch Int Node Node -- sum, left child, right child
type NodeArray = Array Int Node

-- create an empty node with range [l, r)
create :: Int -> Int -> Node
create l r
    | l + 1 == r = Leaf 0
    | otherwise  = Branch 0 (create l m) (create m r)
    where m = (l + r) `div` 2

-- Get the sum in range [0, r). The range of the node is [nl, nr)
sumof :: Node -> Int -> Int -> Int -> Int
sumof (Leaf val) r nl nr
    | nr <= r   = val
    | otherwise = 0
sumof (Branch sum lc rc) r nl nr
    | nr <= r   = sum
    | r  > nl   = (sumof lc r nl m) + (sumof rc r m nr)
    | otherwise = 0
    where m = (nl + nr) `div` 2

-- Increase the value at x by 1. The range of the node is [nl, nr)
increase :: Node -> Int -> Int -> Int -> Node
increase (Leaf val) x nl nr = Leaf (val + 1)
increase (Branch sum lc rc) x nl nr
    | x < m     = Branch (sum + 1) (increase lc x nl m) rc
    | otherwise = Branch (sum + 1) lc (increase rc x m nr)
    where m = (nl + nr) `div` 2

-- signature said it all
tonodes :: Int -> [Int] -> [Node]
tonodes n = reverse . tonodes' . reverse
    where
        tonodes' :: [Int] -> [Node]
        tonodes' (h:t) = increase h' h 0 n : s' where s'@(h':_) = tonodes' t
        tonodes' _ = [create 0 n]

-- find the minimum m in [l, r] such that (predicate m) is True
binarysearch :: (Int -> Bool) -> Int -> Int -> Int
binarysearch predicate l r
    | l == r      = r
    | predicate m = binarysearch predicate l m
    | otherwise   = binarysearch predicate (m+1) r
    where m = (l + r) `div` 2

-- main, literally
main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine
    nodes <- fmap (listArray (0, n) . tonodes n . map (subtract 1) . map read . words) getLine
    replicateM_ m $ query n nodes
    where
        query :: Int -> NodeArray -> IO ()
        query n nodes = do
            [p, k] <- fmap (map read . words) getLine
            print $ binarysearch (ok nodes n p k) 0 n
            where
                ok :: NodeArray -> Int -> Int -> Int -> Int -> Bool
                ok nodes n p k s = (sumof (nodes ! min (p + s + 1) n) s 0 n) - (sumof (nodes ! max (p - s) 0) s 0 n) >= k

(To jest dokładnie ten sam kod z przeglądem kodu, ale to pytanie dotyczy innego problemu).

To jest mój generator danych wejściowych w C ++:

#include <cstdio>
#include <cstdlib>
using namespace std;
int main (int argc, char * argv[]) {
    srand(1827);
    int n = 100000;
    if(argc > 1)
        sscanf(argv[1], "%d", &n);
    printf("%d %d\n", n, n);
    for(int i = 0; i < n; i++)
        printf("%d%c", rand() % n + 1, i == n - 1 ? '\n' : ' ');
    for(int i = 0; i < n; i++) {
        int p = rand() % n;
        int k = rand() % n + 1;
        printf("%d %d\n", p, k);
    }
}

Jeśli nie masz dostępnego kompilatora C ++, jest to wynikiem działania./gen.exe 1000 .

Oto wynik wykonania na moim komputerze:

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.3
$ ghc -fforce-recomp 1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ time ./gen.exe 1000 | ./1827.exe > /dev/null
real    0m0.088s
user    0m0.015s
sys     0m0.015s
$ ghc -fforce-recomp -O 1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ time ./gen.exe 1000 | ./1827.exe > /dev/null
real    0m2.969s
user    0m0.000s
sys     0m0.045s

Oto podsumowanie profilu sterty:

$ ghc -fforce-recomp -rtsopts ./1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ ./gen.exe 1000 | ./1827.exe +RTS -s > /dev/null
      70,207,096 bytes allocated in the heap
       2,112,416 bytes copied during GC
         613,368 bytes maximum residency (3 sample(s))
          28,816 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)
                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       132 colls,     0 par    0.00s    0.00s     0.0000s    0.0004s
  Gen  1         3 colls,     0 par    0.00s    0.00s     0.0006s    0.0010s
  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.03s  (  0.03s elapsed)
  GC      time    0.00s  (  0.01s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.03s  (  0.04s elapsed)
  %GC     time       0.0%  (14.7% elapsed)
  Alloc rate    2,250,213,011 bytes per MUT second
  Productivity 100.0% of total user, 83.1% of total elapsed
$ ghc -fforce-recomp -O -rtsopts ./1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ ./gen.exe 1000 | ./1827.exe +RTS -s > /dev/null
   6,009,233,608 bytes allocated in the heap
     622,682,200 bytes copied during GC
         443,240 bytes maximum residency (505 sample(s))
          48,256 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)
                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     10945 colls,     0 par    0.72s    0.63s     0.0001s    0.0004s
  Gen  1       505 colls,     0 par    0.16s    0.13s     0.0003s    0.0005s
  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    2.00s  (  2.13s elapsed)
  GC      time    0.87s  (  0.76s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    2.89s  (  2.90s elapsed)
  %GC     time      30.3%  (26.4% elapsed)
  Alloc rate    3,009,412,603 bytes per MUT second
  Productivity  69.7% of total user, 69.4% of total elapsed
johnchen902
źródło
1
Dziękujemy za dołączenie wersji GHC!
dfeuer
2
@dfeuer Wynik jest teraz wpisany w moje pytanie.
johnchen902
13
Jeszcze jedna opcja spróbować: -fno-state-hack. Wtedy będę musiał spróbować przyjrzeć się szczegółom.
dfeuer
17
Nie znam zbyt wielu szczegółów, ale w zasadzie jest to heurystyka do odgadywania, że ​​pewne funkcje, które tworzy twój program (a mianowicie te ukryte w typach IOlub ST), są wywoływane tylko raz. Zwykle jest to dobre przypuszczenie, ale jeśli jest to błędne, GHC może wygenerować bardzo zły kod. Deweloperzy od dłuższego czasu próbowali znaleźć sposób na dobro bez zła. Myślę, że obecnie Joachim Breitner nad tym pracuje.
dfeuer
2
Wygląda to bardzo podobnie do ghc.haskell.org/trac/ghc/ticket/10102 . Zauważ, że oba programy używają replicateM_i tam GHC błędnie przeniesie obliczenia z zewnątrz replicateM_do wewnątrz, dlatego je powtórzy.
Joachim Breitner

Odpowiedzi:

42

Myślę, że nadszedł czas, aby to pytanie uzyskało właściwą odpowiedź.

Co się stało z twoim kodem z -O

Pozwól mi powiększyć twoją główną funkcję i nieco ją przepisać:

main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine
    line <- getLine
    let nodes = listArray (0, n) . tonodes n . map (subtract 1) . map read . words $ line
    replicateM_ m $ query n nodes

Jasne jest, że intencją jest to, że NodeArrayjest on tworzony raz, a następnie używany w każdym z minwokacji query.

Niestety GHC przekształca ten kod w efektywny

main = do
    [n, m] <- fmap (map read . words) getLine
    line <- getLine
    replicateM_ m $ do
        let nodes = listArray (0, n) . tonodes n . map (subtract 1) . map read . words $ line
        query n nodes

i od razu widać problem tutaj.

Co to jest hackowanie stanu i dlaczego niszczy wydajność moich programów

Powodem jest hack stanu, który mówi (z grubsza): „Kiedy coś jest typu IO a, załóżmy, że jest wywoływane tylko raz”. Oficjalna dokumentacja nie jest o wiele bardziej skomplikowany:

-fno-state-hack

Wyłącz „hackowanie stanu”, zgodnie z którym każda lambda z tokenem State # jako argumentem jest traktowana jako pojedynczy wpis, dlatego uważa się, że wstawianie elementów wewnątrz niej jest w porządku. Może to poprawić wydajność kodu monad we / wy i ST, ale stwarza ryzyko ograniczenia współużytkowania.

Z grubsza idea jest następująca: Jeśli zdefiniujesz funkcję z IOtypem i klauzulą ​​where, np

foo x = do
    putStrLn y
    putStrLn y
  where y = ...x...

Coś typu IO amoże być postrzegane jako coś typu RealWord -> (a, RealWorld). W tym widoku powyższe staje się (z grubsza)

foo x = 
   let y = ...x... in 
   \world1 ->
     let (world2, ()) = putStrLn y world1
     let (world3, ()) = putStrLn y world2
     in  (world3, ())

Wezwanie do foo(zazwyczaj) wyglądałoby tak foo argument world. Ale definicja fooprzyjmuje tylko jeden argument, a drugi jest dopiero później konsumowany przez lokalne wyrażenie lambda! To będzie bardzo powolna rozmowa foo. Byłoby znacznie szybciej, gdyby kod wyglądał tak:

foo x world1 = 
   let y = ...x... in 
   let (world2, ()) = putStrLn y world1
   let (world3, ()) = putStrLn y world2
   in  (world3, ())

Nazywa się to rozwinięciem eta i dokonuje się tego z różnych powodów (np. Analizując definicję funkcji , sprawdzając, jak jest wywoływana , oraz - w tym przypadku - heurystyki kierowane typem).

Niestety, pogarsza to wydajność, jeśli wywołanie fooma faktycznie postać let fooArgument = foo argument, tj. Z argumentem, ale nie worldprzeszło (jeszcze). W oryginalnym kodzie, jeśli fooArgumentzostanie użyty kilka razy, ynadal będzie obliczany tylko raz i udostępniany. W zmodyfikowanym kodzie yzostanie za każdym razem przeliczona - dokładnie to, co stało się z Twoim nodes.

Czy można to naprawić?

Możliwie. Zobacz # 9388, aby dowiedzieć się, jak to zrobić. Problem z naprawieniem tego polega na tym, że będzie to kosztować wydajność w wielu przypadkach, w których transformacja okaże się dobra, nawet jeśli kompilator nie może wiedzieć tego na pewno. I prawdopodobnie są przypadki, w których nie jest to technicznie w porządku, tj. Udostępnianie jest utracone, ale nadal jest korzystne, ponieważ przyspieszenia spowodowane szybszym połączeniem przeważają nad dodatkowym kosztem ponownego obliczenia. Nie jest więc jasne, dokąd się stąd udać.

Joachim Breitner
źródło
4
Bardzo interesujące! Ale nie do końca zrozumiałem, dlaczego: „drugi jest dopiero później konsumowany przez lokalne wyrażenie lambda! To będzie bardzo powolne wywołanie foo”?
imz - Ivan Zakharyaschev
Czy istnieje obejście dla konkretnego przypadku lokalnego? -f-no-state-hackkiedy kompilacja wydaje się dość ciężka. {-# NOINLINE #-}wydaje się oczywistą rzeczą, ale nie mogę wymyślić, jak to zastosować tutaj. Może wystarczyłoby po prostu wykonać nodesakcję IO i polegać na sekwencjonowaniu >>=?
Barend Venter
Widziałem też, że zastąpienie replicateM_ n fooze forM_ (\_ -> foo) [1..n]pomaga.
Joachim Breitner