3

免责声明：我对 ghc 编译管道知之甚少，但我希望通过这篇文章了解更多信息，例如，比较命令式与函数式是否与代码编译相关。

如您所知，循环展开通过复制其中的代码来减少循环的迭代次数。这提高了性能，因为它减少了跳转次数（以及与之相关的惩罚）和 AFAIR，创建了更大的代码块，为更好的寄存器重命名优化留出了空间。

我想知道，对于函数式编程，是否有等效于循环展开的方法？我们能否“展开”一个函数，打开/扩展它的定义，以首先减少对所述函数的调用次数和/或创建更大的代码块——然后为更多代码重写优化留出空间（如寄存器重命名或一些 FP相等的）？

可以“展开”或“扩展”函数定义的东西，例如使用函数评估（可能与某种策略混合）以便在空间与时间之间进行权衡。

我想到的一个例子：

 map1 _ [] = []
 map1 f (x:xs) = (f x): map f xs

将展开到

map2 _ [] = []
map2 f (x:x1:xs) = (f x):(f x1):map2 f xs
map2 f (x:xs) = (f x): map2 f xs

再一次：

map4 _ [] = []
map4 f (x:x1:x2:x3:xs) = (f x):(f x1):(f x2):(f x3):map4 f xs
map4 f (x:x1:x2:xs) = (f x):(f x1):(f x2):map4 f xs
map4 f (x:x1:xs) = (f x):(f x1):map4 f xs
map4 f (x:xs) = (f x): map4 f xs

有两件事在起作用：map4 的多个案例（以及列表上的后续测试）可能会降低性能，或者减少 map4 的调用次数会提高性能。也许这可以减少惰性评估造成的一些持续开销？

好吧，编写测试代码似乎并不难，所以在提出标准来推出它之后，这就是我所拥有的：

相册

Problem size 5*10^6

map  105.4 ms
map2 93.34 ms
map4 89.79 ms

Problem size 1*10^7

map  216.3 ms
map2 186.8 ms
map4 180.1 ms

Problem size 5*10^7

map  1050 ms
map2 913.7 ms
map4 899.8 ms

嗯，展开似乎有一些效果^1！map4 似乎快了 16%。

那么问题的时间：

  1. 以前讨论过这个吗？类似的东西已经实施了吗？
  2. 真的是减少map4的评估次数提高了速度吗？
  3. 这可以自动化吗？
  4. 我可以按块评估吗？即：如果 (fx) 被完全评估，则完全评估 (f x4) 之前的所有内容。
  5. 这种展开的任何其他形式都在起作用吗？
  6. 这会导致函数大小的膨胀如何？
  7. 为什么这不是一个好主意？

1：我也展开了 fib，因为这种优化也会以这种形式发生，但是性能增益是在欺骗一个（非常）糟糕的算法。

4

3 回答 3

6

您是否进行了优化编译？对我来说，使用-O2，这些片段之间并没有真正的区别：map1、map2和map4分别以 279、267 和 285 毫秒运行（为了比较，map它们本身以 278 毫秒运行）。所以这对我来说只是测量噪音而不是改进。

也就是说，你可能想看看这个 GHC 插件，它似乎是关于循环展开的。

纯函数式语言和命令式语言往往具有非常不同的优化技术，这很可悲但很真实。例如，您可能想查看流融合和森林砍伐——这两种技术非常简洁，但不能很好地转化为命令式语言。

至于“关于为什么这不是一个好主意的任何短评？”，好吧，我可以马上想到一个：

*Main> map succ (1:undefined)
[2*** Exception: Prelude.undefined
*Main> map4 succ (1:undefined)
*** Exception: Prelude.undefined

在许多情况下，为了提高性能而使函数更严格是可以的，但是在这里性能获胜对我来说并不是那么清楚，并且map经常以依赖懒惰的方式使用。

于 2013-09-30T03:57:56.210 回答
3

除了已经提到的 ghc 展开插件之外，GHC trac 上还有一个页面讨论了剥离/展开。“Open Issues”和“References”部分特别揭示了进一步研究材料的来源。

于 2013-09-30T05:25:10.170 回答
1

循环展开是一种相当钝的武器。例如，我永远不希望您的map示例被展开。它完全由返回列表的内存分配及其单元格中的 thunk 控制。我并不关心寄存器分配器是否有更多需要咀嚼的东西。（是否展开折叠foldl'可能是一个不同的问题。）

GHC 可以通过内联递归函数来实现循环展开。但它尽量不这样做：事实上，它永远不会内联递归组的“循环断路器”。否则，无法保证内联会终止。请参阅“GHC 内联程序的秘密”的第 4 节。

GHC确实在其传递中应用了有限形式的循环剥离（或者更确切地说，部分冗余消除）LiberateCase（使用 运行-O2）：

f :: (Int, Int) -> Int
f p = g [0..snd p]
  where
    g :: [Int] -> Int
    g [] = 0
    g (x:xs) = fst p + x + g xs

在这里，GHC 将剥离循环的一次迭代以使fst p投影脱离循环并引用未装箱的内容Int#。核：

Lib.$wf
  = \ (ww_sNF :: Int) (ww1_sNJ :: GHC.Prim.Int#) ->
      case GHC.Enum.eftInt 0# ww1_sNJ of {
        [] -> 0#;
        : x_atE xs_atF ->
          case ww_sNF of { GHC.Types.I# x1_aLW ->
          case x_atE of { GHC.Types.I# y_aLZ ->
          letrec {
            $wg_sNB [InlPrag=NOUSERINLINE[2], Occ=LoopBreaker]
              :: [Int] -> GHC.Prim.Int#
            [LclId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
            $wg_sNB
              = \ (w_sNx :: [Int]) ->
                  case w_sNx of {
                    [] -> 0#;
                    : x2_Xud xs1_Xuf ->
                      case x2_Xud of { GHC.Types.I# y1_XMG ->
                      case $wg_sNB xs1_Xuf of ww2_sNA { __DEFAULT ->
                      GHC.Prim.+# (GHC.Prim.+# x1_aLW y1_XMG) ww2_sNA
                      }
                      }
                  }; } in
          case $wg_sNB xs_atF of ww2_sNA { __DEFAULT ->
          GHC.Prim.+# (GHC.Prim.+# x1_aLW y_aLZ) ww2_sNA
          }
          }
          }
      }
于 2021-10-26T13:05:37.967 回答