是否有类似于循环展开的优化功能编程？

Question

免责声明:我对ghc编译管道知之甚少,但我希望通过这篇文章了解更多关于它的信息,例如,如果将命令与功能进行比较与代码编译相关.

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

我想知道,是否可以使用Loop Unrolling进行函数式编程？我们可以"展开"一个函数,打开/扩展它的定义,首先减少对所述函数的调用次数和/或创建更大的代码块 - 然后为更多的代码重写优化留出空间(比如寄存器重命名,或者一些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的调用次数减少会提高性能.也许这可以减少懒惰评估产生的一些不断开销？

嗯,这似乎并不难为测试编码,所以在把标准推出后,这就是我所拥有的:

ImgUr专辑

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. 我可以用块来评估吗？即:if(fx)被完全评估,完全评估一切(f x4).
5. 这种展开的任何其他形式发挥作用？
6. 如何导致函数大小膨胀？
7. 为什么这不是一个好主意的任何简短的回应？

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

Answer 1

你用优化编译了吗？对我来说,有-O2,有没有真正的这些片段之间的差异:map1,map2,和map4279运行,267,和285ms,分别为(和比较,map本身在278ms跑).所以这看起来只是测量噪音而不是改进.

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

遗憾的是,纯粹的函数式语言和命令式语言往往具有非常不同的优化技术.例如,您可能希望查看流融合和砍伐森林 - 这两种技术非常简洁,但不能很好地转换为命令式语言.

至于"为什么这不是一个好主意的任何短暂的交易？",好吧,我可以想到一个正确的方法:

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

在许多情况下,为了提高性能而使功能更加严格是好的,但是在这里,性能获胜对我来说并不是那么清楚,并且map经常以懒惰的方式使用.