При нахождении последнего, но второго элемента списка, почему использование `last` является самым быстрым среди них?

Ниже приведены 3 функции, которые находят последний, но второй элемент в списке. Тот, кто использует, last . initкажется намного быстрее, чем остальные. Я не могу понять, почему.

Для тестирования я использовал входной список [1..100000000](100 миллионов). Последний запускается почти мгновенно, тогда как остальные занимают несколько секунд.

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

При изучении скорости и оптимизации очень легко получить дико неверные результаты . В частности, вы не можете сказать, что один вариант быстрее другого, не упоминая версию компилятора и режим оптимизации вашей настройки бенчмаркинга. Даже в этом случае современные процессоры настолько сложны, что в них предусмотрены предикторы ветвления на основе нейронной сети, не говоря уже о всех видах кэшей, поэтому даже при тщательной настройке результаты сравнительного анализа будут размытыми.

Что, как говорится...

Бенчмаркинг - наш друг.

criterionэто пакет, который предоставляет расширенные инструменты для тестирования. Я быстро набросал эталон, как это:

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 ]

Как видите, я добавил вариант, который явно соответствует двум элементам одновременно, но в остальном это тот же самый код. Я также запускаю тесты в обратном порядке, чтобы знать о смещении из-за кеширования. Итак, давайте побежим и посмотрим!

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

Похоже, наша "медленная" версия совсем не медленная! И тонкости сопоставления с образцом ничего не добавляют. (Небольшое ускорение, которое мы видим между двумя последовательными прогонами, match2я приписываю эффектам кэширования.)

Есть способ получить больше «научных» данных: мы можем -ddump-simplвзглянуть на то, как компилятор видит наш код.

Осмотр промежуточных сооружений - наш друг.

«Ядро» является внутренним языком GHC. Каждый исходный файл Haskell упрощается до Core перед преобразованием в окончательный функциональный граф для выполнения системой времени выполнения. Если мы посмотрим на этот промежуточный этап, он скажет нам, что myButLastи butLast2эквивалентны. Нужно посмотреть, поскольку на этапе переименования все наши красивые идентификаторы случайным образом искажаются.

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

Кажется, что A1и A4являются наиболее похожими. Тщательное обследование покажет , что на самом деле кодовые структуры в A1и A4идентичны. Это A2и A3они одинаковы, также разумно, так как оба определены как состав из двух функций.

Если вы собираетесь тщательно изучить coreвывод, имеет смысл также указывать такие флаги , как -dsuppress-module-prefixesи -dsuppress-uniques. Они делают его намного проще для чтения.

Короткий список наших врагов тоже.

Итак, что может пойти не так с бенчмаркингом и оптимизацией?

• ghciБудучи разработанным для интерактивного воспроизведения и быстрой итерации, компилирует исходный код Haskell для определенного вида байтового кода, а не для конечного исполняемого файла, и избегает дорогих оптимизаций в пользу более быстрой перезагрузки.
• Профилирование кажется хорошим инструментом для анализа производительности отдельных фрагментов сложной программы, но оно может настолько сильно испортить оптимизацию компилятора, что результаты будут на несколько порядков ниже базовых.
  • Ваша гарантия - профилировать каждый небольшой кусочек кода как отдельный исполняемый файл со своим собственным средством запуска тестов.
• Сборка мусора настраивается. Только сегодня была выпущена новая важная функция. Задержки при сборке мусора будут влиять на производительность способами, которые трудно предсказать.
• Как я уже упоминал, разные версии компилятора будут создавать разный код с разной производительностью, поэтому вы должны знать, какую версию пользователь вашего кода, скорее всего, будет использовать для его сборки, и сравниться с ней, прежде чем давать какие-либо обещания.

Это может выглядеть грустно. Но это действительно не то, что должно волновать программиста на Haskell, большую часть времени. Реальная история: у меня есть друг, который только недавно начал изучать Haskell. Они написали программу для численного интегрирования, и она была медлительной. Поэтому мы сели вместе и написали категорическое описание алгоритма с диаграммами и прочим. Когда они переписали код, чтобы привести его в соответствие с абстрактным описанием, он волшебным образом стал быстрым, как и гепард, и также сократил объем памяти. Мы рассчитали π в кратчайшие сроки. Мораль истории? Идеальная абстрактная структура, и ваш код будет оптимизирован.