Lors de la recherche du dernier mais du deuxième élément d'une liste, pourquoi utiliser «dernier» le plus rapide parmi ceux-ci?

10

Il y a 3 fonctions données ci-dessous qui trouvent le dernier mais le deuxième élément d'une liste. Celui qui utilise last . initsemble beaucoup plus rapide que les autres. Je n'arrive pas à comprendre pourquoi.

Pour les tests, j'ai utilisé une liste d'entrée de [1..100000000](100 millions). Le dernier s'exécute presque instantanément tandis que les autres prennent plusieurs secondes.

-- 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
haskell storm125
la source
5
inita été optimisé pour éviter de "déballer" la liste plusieurs fois.
Willem Van Onsem
1
@WillemVanOnsem mais pourquoi est-ce myButLastbeaucoup plus lent?. Il semble que cela ne déballe aucune liste, mais la traverse simplement comme une initfonction le fait ...
lsmor
1
@Ismor: il est l' [x, y]abréviation de (x:(y:[])), donc il décompresse le contre externe, un deuxième contre, et vérifie si la queue du second l' consest []. De plus, la deuxième clause déballera à nouveau la liste dans (x:xs). Oui, le déballage est raisonnablement efficace, mais bien sûr, si cela se produit très souvent, cela ralentira le processus.
Willem Van Onsem
1
En regardant dans hackage.haskell.org/package/base-4.12.0.0/docs/src/… , l'optimisation semble initne pas vérifier à plusieurs reprises si son argument est une liste singleton ou une liste vide. Une fois que la récursion commence, elle suppose simplement que le premier élément sera cloué sur le résultat de l'appel récursif.
chepner
2
@WillemVanOnsem Je pense que le déballage n'est probablement pas le problème ici: GHC fait une spécialisation de modèle d'appel qui devrait vous donner la version optimisée de myButLastautomatiquement. Je pense que c'est plus probablement la fusion de listes qui est à blâmer pour l'accélération.
oisdk

Réponses:

9

Lorsque vous étudiez la vitesse et l'optimisation, il est très facile d' obtenir des résultats complètement faux . En particulier, vous ne pouvez pas vraiment dire qu'une variante est plus rapide qu'une autre sans mentionner la version du compilateur et le mode d'optimisation de votre configuration d'analyse comparative. Même alors, les processeurs modernes sont si sophistiqués qu'ils comportent des prédicteurs de branche basés sur un réseau neuronal, sans parler de toutes sortes de caches, donc, même avec une configuration soignée, les résultats de l'analyse comparative seront flous.

Cela étant dit...

Le benchmarking est notre ami.

criterionest un package qui fournit des outils d'analyse comparative avancés. J'ai rapidement rédigé une référence comme celle-ci:

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 ]

Comme vous le voyez, j'ai ajouté la variante qui correspond explicitement à deux éléments à la fois, mais sinon c'est le même code textuellement. J'exécute également les benchmarks à l'envers, afin d'être conscient du biais dû à la mise en cache. Alors, courons et voyons!

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

On dirait que notre version "lente" n'est pas du tout lente! Et les subtilités de la correspondance de motifs n'ajoutent rien. (Une légère accélération se produit entre deux exécutions consécutives de match2J'attribue les effets de la mise en cache.)

Il existe un moyen d'obtenir plus de données "scientifiques" : nous pouvons -ddump-simplet jeter un œil à la façon dont le compilateur voit notre code.

L'inspection des structures intermédiaires est notre amie.

"Core" est un langage interne de GHC. Chaque fichier source Haskell est simplifié dans Core avant d'être transformé en graphique fonctionnel final pour que le système d'exécution s'exécute. Si nous regardons cette étape intermédiaire, cela nous le dira myButLastet butLast2sont équivalents. Il faut regarder, car, au stade du changement de nom, tous nos jolis identifiants sont mutilés au hasard.

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

Il semble que A1et A4sont les plus similaires. Une inspection approfondie montrera qu'en effet les structures de code dans A1et A4sont identiques. Cela A2et le même A3sont également raisonnables car les deux sont définis comme une composition de deux fonctions.

Si vous allez examiner la coresortie en profondeur, il est logique de fournir également des indicateurs tels que -dsuppress-module-prefixeset -dsuppress-uniques. Ils le rendent tellement plus facile à lire.

Une courte liste de nos ennemis aussi.

Alors, qu'est-ce qui peut mal tourner avec l'analyse comparative et l'optimisation?

  • ghci, étant conçu pour un jeu interactif et une itération rapide, compile la source Haskell avec une certaine saveur de code octet, plutôt que l'exécutable final, et évite les optimisations coûteuses en faveur d'un rechargement plus rapide.
  • Le profilage semble être un bon outil pour examiner les performances de bits et de morceaux individuels d'un programme complexe, mais il peut si mal détruire les optimisations du compilateur que les résultats seront des ordres de grandeur hors de la base.
    • Votre sauvegarde consiste à profiler chaque petit morceau de code comme un exécutable séparé, avec son propre exécuteur de référence.
  • La collecte des ordures est réglable. Aujourd'hui encore, une nouvelle fonctionnalité majeure a été publiée. Les retards pour la collecte des ordures affecteront les performances d'une manière qui n'est pas simple à prévoir.
  • Comme je l'ai mentionné, différentes versions du compilateur créeront un code différent avec des performances différentes, vous devez donc savoir quelle version l' utilisateur de votre code utilisera probablement pour le construire, et comparer avec cela, avant de faire des promesses.

Cela peut paraître triste. Mais ce n'est vraiment pas la chose qui devrait concerner un programmeur Haskell, la plupart du temps. Histoire vraie: J'ai un ami qui a récemment commencé à apprendre Haskell. Ils avaient écrit un programme d'intégration numérique, et c'était très lent. Nous nous sommes donc assis ensemble et avons écrit une description catégorielle de l'algorithme, avec des diagrammes et des trucs. Quand ils ont réécrit le code pour l'aligner sur la description abstraite, il est devenu magiquement, comme, guépard rapide et mince en mémoire aussi. Nous avons calculé π en un rien de temps. Morale de l'histoire? Structure abstraite parfaite, et votre code s'optimisera.

Ignat Insarov
la source
Très instructif et aussi un peu écrasant pour moi à ce stade. Dans ce cas, tout le "benchmarking" que j'ai fait a été exécuté toute la fonction pour 100 millions d'articles et notez que l'un prend plus de temps que l'autre. Le benchmark avec critère semble plutôt utile. De plus, ghcisemble donner des résultats différents (en termes de vitesse) par rapport à la fabrication d'un exe en premier, comme vous l'avez dit.
storm125