Warum ist die Verwendung von "last" das schnellste unter diesen, wenn Sie das vorletzte Element einer Liste finden?

Es gibt 3 Funktionen, die das vorletzte Element in einer Liste finden. Der mitlast . init scheint viel schneller als der Rest. Ich kann nicht herausfinden warum.

Zum Testen habe ich eine Eingabeliste von [1..100000000](100 Millionen) verwendet. Der letzte läuft fast sofort, während die anderen einige Sekunden dauern.

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

Wenn man Geschwindigkeit und Optimierung studiert, ist das sehr einfach , völlig falsche Ergebnisse erzielen . Insbesondere können Sie nicht wirklich sagen, dass eine Variante schneller als eine andere ist, ohne die Compilerversion und den Optimierungsmodus Ihres Benchmarking-Setups zu erwähnen. Selbst dann sind moderne Prozessoren so ausgefeilt, dass sie Verzweigungsprädiktoren auf der Basis neuronaler Netzwerke sowie alle Arten von Caches enthalten. Selbst bei sorgfältiger Einrichtung sind die Benchmarking-Ergebnisse verschwommen.

Davon abgesehen ...

Benchmarking ist unser Freund.

criterionist ein Paket, das erweiterte Benchmarking-Tools bietet. Ich habe schnell einen Benchmark wie diesen entworfen:

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 ]

Wie Sie sehen, habe ich die Variante hinzugefügt, die explizit mit zwei Elementen gleichzeitig übereinstimmt, ansonsten handelt es sich jedoch wörtlich um denselben Code. Ich führe die Benchmarks auch in umgekehrter Reihenfolge aus, um mir der Verzerrung durch Caching bewusst zu werden. Also, lass uns rennen und sehen!

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

Sieht so aus, als ob unsere "langsame" Version überhaupt nicht langsam ist! Und die Feinheiten des Mustervergleichs tragen nichts dazu bei. (Eine leichte Beschleunigung, die wir zwischen zwei aufeinanderfolgenden Läufen von sehen, match2schreibe ich den Effekten des Caching zu.)

Es gibt eine Möglichkeit, mehr "wissenschaftliche" Daten zu erhalten: Wir können -ddump-simplund sehen, wie der Compiler unseren Code sieht.

Die Inspektion von Zwischenstrukturen ist unser Freund.

"Core" ist eine interne Sprache von GHC. Jede Haskell-Quelldatei wird zu Core vereinfacht, bevor sie in das endgültige Funktionsdiagramm für die Ausführung durch das Laufzeitsystem umgewandelt wird. Wenn wir uns diese Zwischenstufe ansehen, wird sie uns das sagen myButLastund butLast2sind gleichwertig. Es braucht einen Blick, da beim Umbenennen alle unsere netten Kennungen zufällig entstellt werden.

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

Es scheint das A1und A4sind am ähnlichsten. Eine gründliche Inspektion wird zeigen , dass in der Tat die Codestrukturen A1und A4sind identisch. Das A2und das A3Gleiche sind auch sinnvoll, da beide als Zusammensetzung zweier Funktionen definiert sind.

Wenn Sie die coreAusgabe ausführlich untersuchen möchten, ist es sinnvoll, auch Flags wie -dsuppress-module-prefixesund anzugeben-dsuppress-uniques . Sie machen es so viel einfacher zu lesen.

Eine kurze Liste unserer Feinde.

Was kann also beim Benchmarking und der Optimierung schief gehen?

• ghciDa die Haskell-Quelle für interaktives Spielen und schnelle Iteration konzipiert ist, kompiliert sie die Haskell-Quelle auf eine bestimmte Art von Bytecode anstatt auf die endgültige ausführbare Datei und verzichtet auf teure Optimierungen zugunsten eines schnelleren Neuladens.
• Die Profilerstellung scheint ein nützliches Werkzeug zu sein, um die Leistung einzelner Teile eines komplexen Programms zu untersuchen. Sie kann jedoch die Compiler-Optimierungen so stark beeinträchtigen, dass die Ergebnisse um Größenordnungen von der Basis abweichen.
  • Ihr Schutz besteht darin, jedes kleine Stück Code als separate ausführbare Datei mit einem eigenen Benchmark-Runner zu profilieren.
• Die Speicherbereinigung ist einstellbar. Erst heute wurde ein neues Hauptfeature veröffentlicht.Verzögerungen bei der Speicherbereinigung wirken sich auf die Leistung auf eine Weise aus, die nicht einfach vorherzusagen ist.
• Wie bereits erwähnt, erstellen verschiedene Compilerversionen unterschiedlichen Code mit unterschiedlicher Leistung. Sie müssen also wissen, welche Version der Benutzer Ihres Codes wahrscheinlich zum Erstellen verwenden wird, und mit dieser vergleichen, bevor Sie irgendwelche Versprechungen machen.

Das mag traurig aussehen. Aber es ist wirklich nicht das, was einen Haskell-Programmierer die meiste Zeit betreffen sollte. Echte Geschichte: Ich habe einen Freund, der erst kürzlich angefangen hat, Haskell zu lernen. Sie hatten ein Programm zur numerischen Integration geschrieben, und es war schildkrötenlang. Also setzten wir uns zusammen und schrieben eine kategoriale Beschreibung des Algorithmus mit Diagrammen und Dingen. Als sie den Code neu schrieben, um ihn an die abstrakte Beschreibung anzupassen, wurde er auf magische Weise schnell wie ein Gepard und schlank im Gedächtnis. Wir haben π in kürzester Zeit berechnet. Moral der Geschichte? Perfekte abstrakte Struktur, und Ihr Code wird sich selbst optimieren.