Dlaczego znajdując ostatni, ale drugi element listy, używa „last” najszybszego spośród nich?

Poniżej podano 3 funkcje, które znajdują ostatni, ale drugi element na liście. Ten, który używa last . initwydaje się znacznie szybszy niż reszta. Nie mogę zrozumieć, dlaczego.

Do testów wykorzystałem listę danych wejściowych [1..100000000](100 milionów). Ostatni działa prawie natychmiast, a pozostałe trwają kilka sekund.

-- 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

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.