Ao encontrar o último mas o segundo elemento de uma lista, por que usar `last` é o mais rápido entre eles?

Existem 3 funções dadas abaixo, que encontram o último, mas o segundo, elemento de uma lista. Aquele usando last . initparece muito mais rápido que o resto. Não consigo entender o porquê.

Para o teste, usei uma lista de entrada de [1..100000000](100 milhões). O último roda quase instantaneamente, enquanto os outros levam alguns segundos.

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

Ao estudar velocidade e otimização, é muito fácil obter resultados totalmente errados . Em particular, você não pode realmente dizer que uma variante é mais rápida que outra sem mencionar a versão do compilador e o modo de otimização da sua configuração de benchmarking. Mesmo assim, os processadores modernos são tão sofisticados que apresentam preditores de ramificação baseados em redes neurais, sem mencionar todos os tipos de caches; portanto, mesmo com uma configuração cuidadosa, os resultados do benchmarking serão embaçados.

Dito isto ...

Benchmarking é nosso amigo.

criterioné um pacote que fornece ferramentas avançadas de benchmarking. Elaborei rapidamente uma referência como esta:

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 ]

Como você vê, eu adicionei a variante que corresponde explicitamente a dois elementos ao mesmo tempo, mas, caso contrário, é o mesmo código literalmente. Eu também corro os benchmarks ao contrário, para estar ciente do viés devido ao cache. Então, vamos correr e ver!

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

Parece que a nossa versão "lenta" não é lenta! E os meandros da correspondência de padrões não adicionam nada. (Uma ligeira velocidade que vemos entre duas execuções consecutivas de match2eu atribuo aos efeitos do cache.)

Existe uma maneira de obter mais dados "científicos" : podemos -ddump-simplver a maneira como o compilador vê nosso código.

A inspeção de estruturas intermediárias é nossa amiga.

"Core" é uma linguagem interna do GHC. Todo arquivo de origem Haskell é simplificado para o Core antes de ser transformado no gráfico funcional final para a execução do sistema de tempo de execução. Se olharmos para este estágio intermediário, ele nos dirá isso myButLaste butLast2é equivalente. É preciso procurar, pois, no estágio de renomeação, todos os nossos bons identificadores são mutilados aleatoriamente.

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

Parece que A1e A4são os mais semelhantes. Uma inspeção completa mostrará que, de fato, o código estrutura A1e A4é idêntico. Isso A2e A3similares também é razoável, pois ambos são definidos como uma composição de duas funções.

Se você for examinar a coresaída extensivamente, faz sentido também fornecer sinalizadores como -dsuppress-module-prefixese -dsuppress-uniques. Eles tornam muito mais fácil a leitura.

Uma pequena lista de nossos inimigos também.

Então, o que pode dar errado com o benchmarking e a otimização?

• ghci, sendo projetado para reprodução interativa e iteração rápida, compila a fonte Haskell com um certo sabor de código de bytes, em vez de executável final, e evita otimizações caras em favor de uma recarga mais rápida.
• A criação de perfil parece ser uma boa ferramenta para analisar o desempenho de bits e partes individuais de um programa complexo, mas pode prejudicar tanto as otimizações do compilador que os resultados serão de magnitude fora da base.
  • Sua proteção é criar um perfil de cada pequeno pedaço de código como um executável separado, com seu próprio corredor de referência.
• A coleta de lixo é ajustável. Ainda hoje, um novo recurso importante foi lançado. Atrasos na coleta de lixo afetarão o desempenho de maneiras que não são fáceis de prever.
• Como mencionei, versões diferentes do compilador criarão código diferente com desempenho diferente; portanto, você precisa saber qual versão o usuário do seu código provavelmente usará para construí-lo e fazer uma comparação com ela antes de fazer promessas.

Isso pode parecer triste. Mas, na verdade, não é isso que deve preocupar um programador Haskell, na maioria das vezes. História real: tenho um amigo que recentemente começou a aprender Haskell. Eles haviam escrito um programa para integração numérica, e a tartaruga era lenta. Então nos sentamos juntos e escrevemos uma descrição categorizada do algoritmo, com diagramas e outras coisas. Quando eles reescreveram o código para se alinhar com a descrição abstrata, ele magicamente se tornou, tipo, rápido, e também magro na memória. Calculamos π em nenhum momento. Moral da história? Estrutura abstrata perfeita, e seu código se otimizará.