为什么文件夹使用辅助功能? [英] Why does foldr use a helper function?

问题描述

在向Haskell新手解释foldr时，规范的定义是

In explaining foldr to Haskell newbies, the canonical definition is

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

但是在GHC.Base中，foldr被定义为

But in GHC.Base, foldr is defined as

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

似乎此定义是对速度的优化，但是我不明白为什么使用辅助功能go会使其更快.源注释(请参阅此处)提到内联，但我也看不到这个定义如何改善内联.

It seems this definition is an optimization for speed, but I don't see why using the helper function go would make it faster. The source comments (see here) mention inlining, but I also don't see how this definition would improve inlining.

推荐答案

我可以添加一些有关GHC优化系统的重要细节.

I can add some important details about GHC's optimization system.

foldr的天真定义围绕一个函数传递.调用函数存在固有的开销-尤其是在编译时不知道该函数的情况下.如果在编译时就知道该函数的定义，那将是非常好的.

The naive definition of foldr passes around a function. There's an inherent overhead in calling a function - especially when the function isn't known at compile time. It'd be really nice to able to inline the definition of the function if it's known at compile time.

在GHC中可以执行内联的技巧很多，这就是一个例子.首先，需要内嵌foldr(稍后将介绍为什么). foldr的天真的实现是递归的，因此无法进行内联.因此，将工作程序/包装程序转换应用于该定义. worker是递归的，但是包装器不是.尽管递归了列表的结构，这仍允许内嵌foldr.

There are tricks available to perform that inlining in GHC - and this is an example of them. First, foldr needs to be inlined (I'll get to why later). foldr's naive implementation is recursive, so cannot be inlined. So a worker/wrapper transformation is applied to the definition. The worker is recursive, but the wrapper is not. This allows foldr to be inlined, despite the recursion over the structure of the list.

内联foldr时，它也会创建其所有本地绑定的副本.它或多或少是直接的文本内联(对一些重命名进行模数化，并在减重通行证之后发生).这就是事情变得有趣的地方. go是本地绑定，优化器开始查看它的内部.它会注意到它在本地范围内调用了一个函数，并将其命名为k. GHC通常会完全删除k变量，而只是将其替换为表达式k reduces to.然后，如果该函数应用程序适合内联，则可以在此时进行内联-完全消除了调用一流函数的开销.

When foldr is inlined, it creates a copy of all of its local bindings, too. It's more or less a direct textual inlining (modulo some renaming, and happening after the desugaring pass). This is where things get interesting. go is a local binding, and the optimizer gets to look inside it. It notices that it calls a function in the local scope, which it names k. GHC will often remove the k variable entirely, and will just replace it with the expression k reduces to. And then afterwards, if the function application is amenable to inlining, it can be inlined at this time - removing the overhead of calling a first-class function entirely.

让我们看一个简单的具体示例.该程序将回显输入行，并删除所有结尾的'x'字符:

Let's look at a simple, concrete example. This program will echo a line of input with all trailing 'x' characters removed:

dropR :: Char -> String -> String
dropR x r = if x == 'x' && null r then "" else x : r

main :: IO ()
main = do
    s <- getLine
    putStrLn $ foldr dropR "" s

首先，优化器将内联foldr的定义并进行简化，从而产生如下所示的代码:

First, the optimizer will inline foldr's definition and simplify, resulting in code that looks something like this:

main :: IO ()
main = do
    s <- getLine
    -- I'm changing the where clause to a let expression for the sake of readability
    putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s

这就是worker-wrapper转换允许的事情..我将跳过其余的步骤，但是很明显，GHC现在可以内联dropR的定义，从而消除了函数调用的开销.这就是巨大的性能胜利来自的地方.

And that's the thing the worker-wrapper transformation allows.. I'm going to skip the remaining steps, but it should be obvious that GHC can now inline the definition of dropR, eliminating the function call overhead. This is where the big performance win comes from.

这篇关于为什么文件夹使用辅助功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！