Эффективность unoldr против zipWith

Ответ 1

Как тот, кто отвечает за недавние изменения в реализациях zipWith и unfoldr, я подумал, что я, вероятно, должен принять удар. Я не могу сравнивать их так просто, потому что они очень разные функции, но я могу попытаться объяснить некоторые их свойства и значимость изменений.

unfoldr

Встраивание

Старая версия unfoldr (до base-4.8/GHC 7.10) была рекурсивной на верхнем уровне (она называлась непосредственно). GHC никогда не приводит к рекурсивным функциям, поэтому unfoldr никогда не был привязан. В результате GHC не мог понять, как он взаимодействует с переданной функцией. Самым тревожным эффектом этого было то, что переданная функция типа (b -> Maybe (a, b)) фактически произвела бы значения Maybe (a, b), выделив память для хранения конструкторов Just и (,). Реструктурируя unfoldr как "рабочий" и "обертку", новый код позволяет GHC встроить его и (во многих случаях) слить его с переданной функцией, поэтому дополнительные конструкторы удаляются оптимизацией компилятора.

Например, в GHC 7.10 код

module Blob where
import Data.List

bloob :: Int -> [Int]
bloob k = unfoldr go 0 where
  go n | n == k    = Nothing
       | otherwise = Just (n * 2, n+1)

скомпилированный с помощью ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures, приводит к ядру

$wbloob :: Int# -> [Int]
$wbloob =
  \ (ww_sYv :: Int#) ->
    letrec {
      $wgo_sYr :: Int# -> [Int]
      $wgo_sYr =
        \ (ww1_sYp :: Int#) ->
          case tagToEnum# (==# ww1_sYp ww_sYv) of _ {
            False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1));
            True -> []
          }; } in
    $wgo_sYr 0

bloob :: Int -> [Int]
bloob =
  \ (w_sYs :: Int) ->
    case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv }

Fusion

Другое изменение на unfoldr состояло в том, что он переписывал его для участия в слиянии "fold/build", оптимизации, используемой в библиотеках списков GHC. Идея слияния "складки/сборки" и нового сбалансированного "потокового слияния" (используемого в библиотеке vector) заключается в том, что если список создается "хорошим продюсером", преобразованным "хорошими трансформаторами", и потребляется "хорошим потребителем", тогда список conses фактически не нужно вообще выделять. Старый unfoldr не был хорошим производителем, поэтому, если вы создали список с unfoldr и потребляли его, скажем, foldr, фрагменты списка были бы распределены (и сразу стали мусором) по мере продолжения вычисления. Теперь unfoldr является хорошим производителем, поэтому вы можете писать цикл, используя, скажем, unfoldr, filter и foldr, а не (обязательно) выделять любую память вообще.

Например, с учетом вышеприведенного определения bloob и кормовой {-# INLINE bloob #-} (этот материал немного хрупкий; хорошие производители иногда должны быть явно выделены, чтобы быть хорошими), код

hooby :: Int -> Int
hooby = sum . bloob

компилируется в ядро ​​GHC

$whooby :: Int# -> Int#
$whooby =
  \ (ww_s1oP :: Int#) ->
    letrec {
      $wgo_s1oL :: Int# -> Int# -> Int#
      $wgo_s1oL =
        \ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) ->
          case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ {
            False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2));
            True -> ww2_s1oG
          }; } in
    $wgo_s1oL 0 0

hooby :: Int -> Int
hooby =
  \ (w_s1oM :: Int) ->
    case w_s1oM of _ { I# ww1_s1oP ->
    case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT }
    }

у которого нет списков, no Maybe s и нет пар; единственным распределением, которое он выполняет, является Int, используемый для хранения конечного результата (приложение I# to ww2_s1oT). Весь расчет можно разумно ожидать в машинных регистрах.

zipWith

zipWith имеет немного странную историю. Он вписывается в структуру fold/build немного неудобно (я считаю, что он работает немного лучше с потоковым слиянием). Можно использовать плавкий предохранитель zipWith либо с его первым, либо с его вторым аргументом списка, и на протяжении многих лет библиотека списков пыталась сделать его плавким, если либо был хорошим производителем. К сожалению, включение этого параметра в свой второй аргумент списка может сделать программу менее определенной при определенных обстоятельствах. То есть, программа, использующая zipWith, может отлично работать при компиляции без оптимизации, но при компиляции с оптимизацией возникает ошибка. Это не очень хорошая ситуация. Поэтому, начиная с base-4.8, zipWith больше не пытается слиться со своим вторым аргументом списка. Если вы хотите, чтобы он слился с хорошим продюсером, этот хороший продюсер должен быть в первом аргументе списка.

В частности, эталонная реализация zipWith приводит к ожиданию, что, скажем, zipWith (+) [1,2,3] (1 : 2 : 3 : undefined) даст [2,4,6], потому что он останавливается, как только он попадает в конец первого списка. С предыдущей реализацией zipWith, если второй список выглядел так, но был создан хорошим продюсером, и если zipWith произошло с ним, а не с первым списком, тогда он пойдет стрелой.