Блог

Я изучал возможность создания a foldl , который работал с бесконечными списками, для ситуаций, когда вы не могли получить защищенную рекурсию, но где в зависимости от первого аргумента второй аргумент может не использоваться.

Например, умножение, где обычно вам нужны оба аргумента и защищенная рекурсия, не работает, но если первый аргумент равен 0, вы можете закоротить.

Итак, я написал следующую функцию:

 foldlp :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlp f p = go where
    go b [] = b
    go b (x : xs) 
        | p b = go (f b x) xs
        | otherwise = b
  

И протестировал его с помощью моей пользовательской функции умножения с коротким замыканием:

  mult :: Integer -> Integer -> Integer
 mult 0 _ = 0
 mult x y = x * y

 main :: IO ()
 main = print . <test_function>
  

Результаты, которые я получил -prof -fprof-auto -O2 , RTS -p были:

 foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
total time = 0.40 secs
total alloc = 480,049,336 bytes

foldlp mult (`seq` True) 1 $ replicate (10 ^ 7) 1
total time = 0.37 secs
total alloc = 480,049,336 bytes

foldl' mult 1 $ replicate (10 ^ 7) 1
total time = 0.37 secs
total alloc = 480,049,352 bytes

foldl mult 1 $ replicate (10 ^ 7) 1
total time = 0.74 secs
total alloc = 880,049,352 bytes

foldr mult 1 $ replicate (10 ^ 7) 1
total time = 0.87 secs
total alloc = 880,049,336 bytes
  

Что было очень многообещающим, поскольку моя пользовательская функция допускает гибкие типы строгости, а также работает с бесконечными списками

Первый пример завершится, как только он достигнет a 0 , как и будет foldr , но foldr намного медленнее.

Это позволяет избежать таких проблем, как сбои внутри кортежей, поскольку ((1 2) 3, (10 20) 30) технически в WHNF происходит разрыв foldl' .

Вы можете повторно получить foldl с flip foldl (const True) помощью и foldl' с flip foldl ( помощью seq True) . И при этом, похоже, восстанавливаются характеристики производительности исходных ограниченных функций.

Так что в качестве дополнительного замечания , я думаю foldlp , было бы достойным дополнением Foldable .

Но мой фактический вопрос заключался в том, почему, когда я добавил {-# INLINE foldlp #-} функции, производительность значительно снизилась, что дало мне:

 foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
total time = 0.67 secs
total alloc = 800,049,336 bytes
  

Так что мой настоящий вопрос заключается в том, почему это происходит. Я думал, что недостатком встраивания является раздувание кода, а не существенное негативное влияние на производительность среды выполнения и увеличение использования памяти.

Согласно документам GHC INLINE , pragma предотвращает другие оптимизации компилятора, чтобы по-прежнему позволять правилам перезаписи вступать в силу.

Так что я предполагаю, что, используя INLINE вас, вы убираете некоторую оптимизацию, что GHC был бы применен для ускорения вашего кода.

После некоторого ковыряния в ядре (использование -ddump-simpl при компиляции) Я нашел оптимизацию, которую выполняет GHC. Для этого я взглянул на ядро для foldlp с встраиванием и без встраивания:

Встроенный:

 foldlp =
   (@ b_a10N)
    (@ a_a10O)
    (eta_B2 :: b_a10N -> a_a10O -> b_a10N)
    (eta1_B1 :: b_a10N -> Bool)
    (eta2_X3 :: b_a10N)
    (eta3_X5 :: [a_a10O]) ->
    letrec {
      go_s1Ao [Occ=LoopBreaker] :: b_a10N -> [a_a10O] -> b_a10N
      [LclId, Arity=2, Str=DmdType <L,U><S,1*U>]
      go_s1Ao =
         (b1_avT :: b_a10N) (ds_d1xQ :: [a_a10O]) ->
        -- Removed the actual definition of go for brevity,
        -- it's the same in both cases
          }; } in
    go_s1Ao eta2_X3 eta3_X5
  

Не встроенный:

 foldlp =
   (@ b_a10N)
    (@ a_a10O)
    (f_avQ :: b_a10N -> a_a10O -> b_a10N)
    (p_avR :: b_a10N -> Bool) ->
    letrec {
      go_s1Am [Occ=LoopBreaker] :: b_a10N -> [a_a10O] -> b_a10N
      [LclId, Arity=2, Str=DmdType <L,U><S,1*U>]
      go_s1Am =
         (b1_avT :: b_a10N) (ds_d1xQ :: [a_a10O]) ->
        -- Removed the actual definition of go for brevity,
        -- it's the same in both cases
          }; } in
    go_s1Am
  

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

Я проверил это, написав три варианта foldlp :

 module Main where

foldlp :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlp f p = go where
      go b [] = b
      go b (x : xs)
        | p b = go (f b x) xs
        | otherwise = b

{-# INLINE foldlpInline #-}
foldlpInline :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlpInline f p = go where
      go b [] = b
      go b (x : xs)
        | p b = go (f b x) xs
        | otherwise = b


{-# INLINE foldlp' #-} -- So that the code is not optimized
foldlp' b [] = b
foldlp' b (x : xs)
        | (/= 0) b = foldlp' (mult b x) xs
        | otherwise = b

mult :: Integer -> Integer -> Integer
mult 0 _ = 0
mult x y = x * y

--main = print $ foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
--main = print $ foldlpInline mult (/= 0) 1 $ replicate (10 ^ 7) 1
main = print $ foldlp' 1 $ replicate (10 ^ 7) 1
  

Результаты таковы:

Первый случай (обычный не встроенный):

 ./test  0,42s user 0,01s system 96% cpu 0,446 total
  

Второй случай (встроенный):

 ./test  0,83s user 0,02s system 98% cpu 0,862 total
  

Третий случай (то, что компилятор создает для не встроенных)

 ./test  0,42s user 0,01s system 99% cpu 0,432 total