haskell - 是否有类似于函数式编程的循环展开的优化？

Question

Disclaimer: I know little about ghc compiling pipeline, but I hope to learn some more about it with this post, for example, if comparing imperative vs functional is relevant to code compilation.

如你所知，loop unrolling通过复制其中的代码来减少循环的迭代次数。这提高了性能，因为它减少了跳转次数(以及与之相关的惩罚)和 AFAIR，创建了更大的代码块，为更好的 Register renaming 留出了空间优化。

我想知道，函数式编程是否有与循环展开等效的方法？我们能否“展开”一个函数，打开/扩展它的定义，以首先减少对所述函数的调用次数和/或创建更大的代码块——然后为更多代码重写优化留出空间(如寄存器重命名或一些 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 的调用次数会提高性能。也许这可以减少惰性评估造成的一些持续开销？

Well that doesn't seems to hard to code a test for ，所以在提出标准来推出这个之后，这就是我所拥有的:

ImgUr album

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. 我可以按 block 进行评估吗？即:如果 (f x) 被完全评估，则完全评估 (f x4) 之前的所有内容。
5. 还有其他这种展开形式起作用吗？
6. 这会导致函数大小的膨胀程度如何？
7. 关于为什么这不是一个好主意的任何短评？

1:我也展开了 fib，因为这种优化也会以这种形式发生，但性能提升是在欺骗(非常)糟糕的算法。

Answer 1

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

也就是说，您可能想看看 this GHC plugin这似乎是关于循环展开。

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

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

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

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