Anomalia wydajności Runhaskella

Próbuję zrozumieć występującą anomalię wydajności podczas uruchamiania programu pod numerem runhaskell.Anomalia wydajności Runhaskella

Program w pytaniu:

isFactor n = (0 ==) . (mod n) 
factors x = filter (isFactor x) [2..x] 
main = putStrLn $ show $ sum $ factors 10000000

Kiedy uruchomić ten, trwa 1,18 sekundy.

Jednak gdybym przedefiniować isFactor jak:

isFactor n f = (0 ==) (mod n f)

następnie program trwa 17,7 sekundy.

To ogromna różnica w wydajności i oczekuję, że programy będą równoważne. Czy ktoś wie, czego tu brakuje?

Uwaga: Nie dzieje się to podczas kompilacji w ramach GHC.

Źródło

2012-02-17 Steve

Domyślam się, że jak Runhaskell wykonuje tylko kilka optymalizacji, drugi cierpi na pewne problemy ze ścisłością. – fuz

Mimo że funkcje powinny być identyczne, istnieje różnica w sposobie ich stosowania . Z pierwszą definicją, isFactor jest w pełni zastosowany na stronie połączenia isFactor x. W drugiej definicji nie jest, ponieważ teraz isFactor jawnie przyjmuje dwa argumenty.

Nawet minimalne optymalizacje wystarczą, aby GHC mógł je przejrzeć i utworzyć identyczny kod dla obu, jednak jeśli skompilujesz z -O0 -ddump-simpl możesz stwierdzić, że bez optymalizacji robi to różnicę (przynajmniej z ghc-7.2.1 , YMMV w innych wersjach).

Z pierwszym GHC tworzy pojedynczą funkcję, która jest przekazywana jako predykat do "GHC.List.Filter", z wywoływanymi znakami mod 10000000 i (==). W przypadku drugiej definicji, zamiast tego, większość wywołań w ramach isFactor jest odwołaniami do funkcji klas i nie są one dzielone między wieloma wywołaniami isFactor. Jest dużo niepotrzebnego słownika.

To prawie nigdy nie jest problemem, ponieważ nawet domyślne ustawienia kompilatora zoptymalizują go, jednak runhaskell najwyraźniej nawet nie robi tak wiele. Mimo to, mam sporadycznie kod strukturalny jako someFun x y = \z ->, ponieważ wiem, że someFun zostanie częściowo zastosowany i był to jedyny sposób na zachowanie współdzielenia połączeń (tj. Optymalizator GHC nie był wystarczająco sprytny).

Źródło

2012-02-17 12:48:53

Jak rozumiem, runhaskell ma niewiele do zoptymalizowania. Jest przeznaczony do szybkiego ładowania i uruchamiania kodu. Jeśli zrobi więcej optymalizacji, Twój kod zacznie działać dłużej. Oczywiście w tym przypadku kod działa szybciej z optymalizacją.

Jak rozumiem, jeśli istnieje skompilowana wersja kodu, to użyje go runhaskell. Jeśli więc wydajność ma dla Ciebie znaczenie, po prostu upewnij się, że kompilujesz z włączonymi optymalizacjami. (Myślę, że możesz nawet przekazać przełączniki do runhaskell, aby włączyć optymalizacje - musisz sprawdzić dokumentację ...)

Źródło

2012-02-17 09:23:20 MathematicalOrchid

Dzięki za odpowiedź! Rozumiem, że runhaskell nie wykonuje wielu optymalizacji, ale w mojej głowie myślę, że 'foo x = bar x' i' foo = bar' powinny generować dokładnie ten sam kod. Stąd bierze się moje zamieszanie. Nawet bez optymalizacji staram się po prostu zrozumieć, dlaczego te dwie osoby będą inaczej grać. – Steve

Wyobrażam sobie, że istnieje pewna drobna różnica w tym, w jaki sposób struny są zbudowane w zależności od tego, w jaki sposób zdefiniujesz funkcję. Coś podobnego do jednej wersji dzieli jedno odbicie wszystkich wywołań, podczas gdy drugie tworzy kopię dla każdego wywołania, co prowadzi do znacznie większej alokacji i deallokacji. W każdym razie to byłby mój przypuszczenie; musielibyście poprosić twórców GHC o "prawdziwy" powód. Oczywiście przy włączonych optymalizacjach oba sposoby powinny zakończyć się tworzeniem identycznego kodu. Po prostu bez podania optymalizacji tak się nie dzieje. – MathematicalOrchid

Wszystkie optymalizacje są wyłączone w ghci i runhaskell AFAIK, ponieważ interpreter nie obsługuje wartości unboxed. – fuz

Anomalia wydajności Runhaskella

Odpowiedz

Powiązane problemy