Studiowanie szybkości i optymalizacji jest bardzo łatwe uzyskać bardzo błędne wyniki . W szczególności nie można tak naprawdę powiedzieć, że jeden wariant jest szybszy od drugiego, nie wspominając o wersji kompilatora i trybie optymalizacji konfiguracji testów porównawczych. Nawet wtedy nowoczesne procesory są tak wyrafinowane, że zawierają predyktory gałęzi oparte na sieci neuronowej, nie wspominając już o wszelkiego rodzaju pamięciach podręcznych, więc nawet przy starannej konfiguracji wyniki testów porównawczych będą rozmyte.
Biorąc to pod uwagę ...
Benchmarking jest naszym przyjacielem.
criterionto pakiet, który zapewnia zaawansowane narzędzia do testów porównawczych. Szybko opracowałem taki test porównawczy:
module Main where
import Criterion
import Criterion.Main
-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"
-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse
-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init
butLast2 :: [a] -> a
butLast2 (x : _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"
setupEnv = do
let xs = [1 .. 10^7] :: [Int]
return xs
benches xs =
[ bench "slow?" $ nf myButLast xs
, bench "decent?" $ nf myButLast' xs
, bench "fast?" $ nf myButLast'' xs
, bench "match2" $ nf butLast2 xs
]
main = defaultMain
[ env setupEnv $ \ xs -> bgroup "main" $ let bs = benches xs in bs ++ reverse bs ]
Jak widzisz, dodałem wariant, który wyraźnie pasuje do dwóch elementów jednocześnie, ale poza tym jest to ten sam kod, dosłownie. Testy porównawcze przeprowadzam również w odwrotnej kolejności, aby mieć świadomość stronniczości wynikającej z buforowania. Więc biegnijmy i zobaczmy!
% ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5
% ghc -O2 -package criterion A.hs && ./A
benchmarking main/slow?
time 54.83 ms (54.75 ms .. 54.90 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 54.86 ms (54.82 ms .. 54.93 ms)
std dev 94.77 μs (54.95 μs .. 146.6 μs)
benchmarking main/decent?
time 794.3 ms (32.56 ms .. 1.293 s)
0.907 R² (0.689 R² .. 1.000 R²)
mean 617.2 ms (422.7 ms .. 744.8 ms)
std dev 201.3 ms (105.5 ms .. 283.3 ms)
variance introduced by outliers: 73% (severely inflated)
benchmarking main/fast?
time 84.60 ms (84.37 ms .. 84.95 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 84.46 ms (84.25 ms .. 84.77 ms)
std dev 435.1 μs (239.0 μs .. 681.4 μs)
benchmarking main/match2
time 54.87 ms (54.81 ms .. 54.95 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 54.85 ms (54.81 ms .. 54.92 ms)
std dev 104.9 μs (57.03 μs .. 178.7 μs)
benchmarking main/match2
time 50.60 ms (47.17 ms .. 53.01 ms)
0.993 R² (0.981 R² .. 0.999 R²)
mean 60.74 ms (56.57 ms .. 67.03 ms)
std dev 9.362 ms (6.074 ms .. 10.95 ms)
variance introduced by outliers: 56% (severely inflated)
benchmarking main/fast?
time 69.38 ms (56.64 ms .. 78.73 ms)
0.948 R² (0.835 R² .. 0.994 R²)
mean 108.2 ms (92.40 ms .. 129.5 ms)
std dev 30.75 ms (19.08 ms .. 37.64 ms)
variance introduced by outliers: 76% (severely inflated)
benchmarking main/decent?
time 770.8 ms (345.9 ms .. 1.004 s)
0.967 R² (0.894 R² .. 1.000 R²)
mean 593.4 ms (422.8 ms .. 691.4 ms)
std dev 167.0 ms (50.32 ms .. 226.1 ms)
variance introduced by outliers: 72% (severely inflated)
benchmarking main/slow?
time 54.87 ms (54.77 ms .. 55.00 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 54.95 ms (54.88 ms .. 55.10 ms)
std dev 185.3 μs (54.54 μs .. 251.8 μs)
Wygląda na to, że nasza „wolna” wersja wcale nie jest wolna! A zawiłości dopasowywania wzorów nic nie dodają. (Nieznaczne przyspieszenie widzimy między dwoma kolejnymi seriamimatch2 I przypisuję efekt buforowania).
Istnieje sposób na uzyskanie większej liczby „naukowych” danych: możemy -ddump-simpli przyjrzeć się sposobowi, w jaki kompilator widzi nasz kod.
Kontrola konstrukcji pośrednich jest naszym przyjacielem.
„Rdzeń” to wewnętrzny język GHC. Każdy plik źródłowy Haskell jest uproszczony do Core, zanim zostanie przekształcony w końcowy wykres funkcjonalny do wykonania przez system czasu wykonywania. Jeśli spojrzymy na ten etap pośredni, powie nam to myButLasti butLast2są równoważne. Potrzeba patrzenia, ponieważ na etapie zmiany nazwy wszystkie nasze ładne identyfikatory są losowo zniekształcane.
% for i in `seq 1 4`; do echo; cat A$i.hs; ghc -O2 -ddump-simpl A$i.hs > A$i.simpl; done
module A1 where
-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"
module A2 where
-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse
module A3 where
-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init
module A4 where
butLast2 :: [a] -> a
butLast2 (x : _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"
% ./EditDistance.hs *.simpl
(("A1.simpl","A2.simpl"),3866)
(("A1.simpl","A3.simpl"),3794)
(("A2.simpl","A3.simpl"),663)
(("A1.simpl","A4.simpl"),607)
(("A2.simpl","A4.simpl"),4188)
(("A3.simpl","A4.simpl"),4113)
Wydaje się, że A1i A4są najbardziej podobne. Dokładna kontrola wykaże, że rzeczywiście struktury kodu w A1i A4są identyczne. To A2iA3 podobne są również uzasadnione, ponieważ obie są zdefiniowane jako zestaw dwóch funkcji.
Jeśli zamierzasz dokładnie zbadać dane corewyjściowe, sensowne jest także podanie flag takich jak -dsuppress-module-prefixesi -dsuppress-uniques. Ułatwiają czytanie.
Krótka lista naszych wrogów.
Co może pójść nie tak z testami porównawczymi i optymalizacją?
ghci, zaprojektowany do interaktywnej gry i szybkiej iteracji, kompiluje kod źródłowy Haskella do pewnego rodzaju kodu bajtowego, a nie końcowego pliku wykonywalnego, i unika kosztownych optymalizacji na rzecz szybszego przeładowania.- Profilowanie wydaje się być dobrym narzędziem do sprawdzania wydajności poszczególnych bitów i kawałków złożonego programu, ale może tak bardzo zniszczyć optymalizacje kompilatora, że wyniki będą rzędu rzędów wielkości od podstawy.
- Twoje zabezpieczenie polega na profilowaniu każdego drobnego kodu jako osobnego pliku wykonywalnego z własnym programem porównawczym.
- Możliwość wyrzucania elementów bezużytecznych. Właśnie dziś została wydana nowa ważna funkcja. Opóźnienia związane z odśmiecaniem pamięci wpłyną na wydajność w sposób, który nie jest łatwy do przewidzenia.
- Jak wspomniałem, różne wersje kompilatora będą budować różne kody o różnej wydajności, więc musisz wiedzieć, jakiej wersji użytkownik twojego kodu prawdopodobnie użyje do zbudowania go, i przetestuj go, zanim złożysz jakiekolwiek obietnice.
To może wyglądać smutno. Ale tak naprawdę to nie powinno dotyczyć programisty Haskell, przez większość czasu. Prawdziwa historia: mam przyjaciela, który niedawno zaczął uczyć się Haskell. Napisali program do integracji numerycznej i był to żółw powolny. Usiedliśmy więc razem i napisaliśmy kategoryczny opis algorytmu wraz ze schematami i innymi rzeczami. Kiedy ponownie napisali kod, aby dostosować go do abstrakcyjnego opisu, magicznie stał się, jakby, gepardem szybkim i mało pamięci. Obliczyliśmy π w krótkim czasie. Morał historii? Idealna abstrakcyjna struktura, a Twój kod sam się zoptymalizuje.
initzostał zoptymalizowany, aby uniknąć wielokrotnego „rozpakowywania” listy.