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

Question

В обзоре Code я ответил на вопрос о naive Haskell fizzbuzz solution, предложив реализацию, которая iterates forward, избегая квадратичной стоимости растущего числа простых чисел и полностью отбрасывая модульное деление (почти). Вот код:

fizz :: Int -> String 
fizz = const "fizz" 

buzz :: Int -> String 
buzz = const "buzz" 

fizzbuzz :: Int -> String 
fizzbuzz = const "fizzbuzz" 

fizzbuzzFuncs = cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz] 

toFizzBuzz :: Int -> Int -> [String] 
toFizzBuzz start count = 
    let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs 
    in take count $ zipWith ($) offsetFuncs [start..] 

Как еще подскажите, я предложил переписывать его с помощью Data.List.unfoldr. Версия unfoldr является очевидной, простой модификацией этого кода, поэтому я не буду вводить ее здесь, если люди, которые хотят ответить на мой вопрос, не настаивают на важности (никаких спойлеров для OP над обзором кода). Но у меня есть вопрос об относительной эффективности решения unfoldr по сравнению с zipWith. Хотя я уже не неофит Хаскелла, я не являюсь экспертом в области Haskell.

Решение unfoldr не требует бесконечного списка [start..], так как он может просто развернуться от start. Мои мысли

1. zipWith решение не memoize каждый последующий элемент [start..], как он просил. Каждый элемент используется и отбрасывается, поскольку не сохраняется ссылка на главу [start ..]. Таким образом, больше нет памяти, чем с unfoldr.
2. Проблемы, связанные с производительностью unfoldr, и последние исправления, чтобы сделать его всегда вложенным, проводятся на уровне, который я еще не достиг.

Таким образом, я думаю, что эти два эквивалента в потреблении памяти, но не имеют представления об относительной производительности. Надеясь, что более информированные Хаскеллеры могут направить меня к пониманию этого.

unfoldr Кажется естественным, что нужно использовать для генерации последовательностей, даже если другие решения более выразительны. Я просто знаю, что мне нужно больше понять, что это реальная производительность. (По некоторым причинам я считаю foldr гораздо легче понять на этом уровне)

Примечание: unfoldr «s использование Maybe был первым потенциальная проблема производительности, которая пришла мне в голову, прежде чем я даже начал исследовать этот вопрос (и только бит обсуждений по оптимизации/вставке, которые я полностью понял). Поэтому я сразу же смог перестать беспокоиться о Maybe (учитывая недавнюю версию Haskell).

Answer 1

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

unfoldr

Встраивание

старая версия unfoldr (до base-4.8/GHC 7,10) была рекурсивной на верхнем уровне (она называла себя непосредственно). GHC никогда не строит рекурсивные функции, поэтому unfoldr никогда не был встроен. В результате GHC не мог понять, как он взаимодействует с переданной функцией.Самым тревожным эффектом этого было то, что переданная функция типа (b -> Maybe (a, b)) фактически произвела бы значения Maybe (a, b), выделив память для хранения конструкторов и (,). Реструктурируя 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» fusion, инфраструктура оптимизации, используемая в библиотеках списков 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 } 
    } 

, который не имеет списков, ни Maybe с, и ни пары; единственным распределением, которое он выполняет, является Int, используемый для хранения конечного результата (приложение I# до 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 произошло с ним, а не с первым списком, то он пошел бы вверх.