以下是蛮力毕达哥拉斯三胞胎问题的三个版本，其附加约束条件为a + b + c = 1000。所有这些均符合GHC 7.0.3的-O3标准。示例运行时在下面列出。
问题:
我意识到差异很小，但平均而言顺序是一致的。
main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[a..1000], let c=1000-a-b, a^2+b^2==c^2]
real 0m0.046s
user 0m0.039s
sys 0m0.005s
main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[1..1000], let c=1000-a-b, a^2+b^2==c^2]
real 0m0.045s
user 0m0.036s
sys 0m0.006s
main=print . product . head $ [[a,b,c] | a<-[1..1000],b<-[1..1000], b>=a, let c=1000-a-b, a^2+b^2==c^2]
real 0m0.040s
user 0m0.033s
sys 0m0.005s
最佳答案
让我们分别命名这三个程序 A ， B 和 C 。
C 与 B
我们将从最简单的开始: C 相对于 B 有一个额外的约束(b >= a)。从直觉上讲，这意味着在 C 中遍历的搜索空间小于 B 的搜索空间。我们可以合理地指出这一点，而不是对所有可能的偶对a, b(我们知道其中有1000^2=1000000个对)进行覆盖，而不是考虑b小于a的所有情况。大概是检查b >= a是否产生一点额外的代码(比较)，而运行该比较避免了计算所产生的额外代码(比较)，因此，我们注意到(略微)的加速。很公平。
B 和 A
接下来的问题有些棘手:和 C (b >= a)具有相同的约束条件，但是编码方式不同(即在这里我们将其编码为b中可能达到的值List Monad的范围)。那时我们可能会认为 A 的运行速度应比 B 的运行速度更快(事实上，它的运行方式应类似于 C )。显然，我们缺乏直觉。
正中核心
现在，由于我们不能一直相信自己的直觉，因此我们应该研究生成的GHC Core中实际发生的情况。让我们转储我们的3个程序的核心(无优化):for p in A B C
do
ghc -ddump-simpl $p.hs >> $p.core
done
如果我们比较B.core和C.core，我们会注意到两个文件的结构大致相同:
首先调用一些熟悉的函数(System.IO.print ...)，(Data.List.product ...)和(GHC.List.head ...)
接下来，我们定义一对带有签名的嵌套递归函数:ds_dxd [Occ=LoopBreaker]
:: [GHC.Integer.Type.Integer] -> [[GHC.Integer.Type.Integer]]
我们将这些定义的函数中的每一个称为以下形式的枚举: (GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
(GHC.Integer.smallInteger 1)
(GHC.Integer.smallInteger 1000)))
并在最里面定义的函数中执行我们的逻辑。值得注意的是，我们可以在B.core中看到 case GHC.Classes.==
@ GHC.Integer.Type.Integer
...
(GHC.Num.+
...
(GHC.Real.^
...
ds3_dxc
(GHC.Integer.smallInteger 2))
(GHC.Real.^
...
ds8_dxg
(GHC.Integer.smallInteger 2)))
(GHC.Real.^
...
c_abw
(GHC.Integer.smallInteger 2))
对应于符合我们的约束的所有可能值的朴素过滤器，而在C.core中，我们改为:case GHC.Classes.>=
@ GHC.Integer.Type.Integer GHC.Classes.$fOrdInteger ds8_dxj ds3_dxf
of _ {
GHC.Bool.False -> ds5_dxh ds9_dxk;
GHC.Bool.True ->
let {
...
case GHC.Classes.==
...
对应于在我们的三元组约束之前增加了一个额外的>=约束，因此，正如我们的直觉所期望的那样，搜索更少的整数以缩短运行时间。
在比较A.core和B.core时，我们立即看到一个熟悉的结构(一对嵌套的递归函数，每个都通过枚举调用)并且实际上，看来A和B的核心输出几乎相同!区别似乎在于最内层的枚举: ds5_dxd
(GHC.Enum.enumFromTo
@ GHC.Integer.Type.Integer
GHC.Num.$fEnumInteger
ds3_dxb
(GHC.Integer.smallInteger 1000))
在这里，我们看到了从给定的归纳变量ds3_dxb到1000的枚举范围，而不是保留为静态范围([1..1000])。
那有什么呢？这是否不应该表示 A 的运行速度应该比 B 快？ (我们天真地希望 A 的性能类似于 C ，因为它们实现了相同的约束)。好吧，事实证明，各种进行中的编译器优化会产生极其复杂的行为，并且各种组合通常会产生不直观(坦率地说很奇怪)的结果，在这种情况下，我们让和两个编译器相互影响: ghc和gcc。为了有机会了解这些结果，我们必须依赖于生成的优化内核(尽管最终，真正重要的是生成的汇编器，但现在我们将忽略它)。
通往最优化的核心
让我们生成优化的内核:for p in A B C
do
ghc -O3 -ddump-simpl $p.hs >> $p.core
done
并将我们的问题子级( A )与速度更快的子级进行比较。相对而言， B 和 C 都执行了这类优化，仅不能实现: float 和拉姆达提升。我们可以通过注意到 B 和 C 中的递归函数看到少一些40的代码行，从而看到更紧密的内部循环，从而看到这一点。要了解为什么无法从此优化中受益，我们应该看一下没有浮出水面的代码:let {
c1_s10T
:: GHC.Integer.Type.Integer
-> [[GHC.Integer.Type.Integer]]
-> [[GHC.Integer.Type.Integer]]
[LclId, Arity=2, Str=DmdType LL]
c1_s10T =
\ (ds2_dxg :: GHC.Integer.Type.Integer)
(ds3_dxf :: [[GHC.Integer.Type.Integer]]) ->
let {
c2_s10Q [Dmd=Just L] :: GHC.Integer.Type.Integer
[LclId, Str=DmdType]
c2_s10Q = GHC.Integer.minusInteger lvl2_s10O ds2_dxg } in -- subtract
case GHC.Integer.eqInteger
(GHC.Integer.plusInteger lvl3_s10M (GHC.Real.^_^ ds2_dxg lvl_r11p))
-- add two squares (lve3_s10M has been floated out)
(GHC.Real.^_^ c2_s10Q lvl_r11p)
-- ^ compared to this square
of _ {
GHC.Bool.False -> ds3_dxf;
GHC.Bool.True ->
GHC.Types.:
@ [GHC.Integer.Type.Integer]
(GHC.Types.:
@ GHC.Integer.Type.Integer
ds_dxe
(GHC.Types.:
@ GHC.Integer.Type.Integer
ds2_dxg
(GHC.Types.:
@ GHC.Integer.Type.Integer
c2_s10Q
(GHC.Types.[] @ GHC.Integer.Type.Integer))))
ds3_dxf
} } in
也就是说，在循环的关键部分(由辅助函数的主体表示)正在执行减法(minusInteger)和等式(eqInteger)以及两个平方(^_^)，而在C.core中执行相同的辅助函数包含较少的计算(如果进一步研究，我们会发现这是因为GHC无法确定是否可以安全地在优化过程中进行这些计算)。这与我们前面的分析相吻合，因为我们可以看到约束(b >= a)实际上存在，与 C 不同，我们无法将大部分冗余计算浮到循环外。
为了确认，让我们任意增加涉及的循环的范围(为了演示)，例如[1..10000]。我们应该期望看到 A的运行时行为应渐近于 C的运行时行为，就像我们期望 B 一样。➜ time ./A
./A 0.37s user 0.01s system 74% cpu 0.502 total
➜ time ./B
./B 3.21s user 0.02s system 99% cpu 3.246 total
➜ time ./C
./C 0.33s user 0.01s system 99% cpu 0.343 total
您知道什么，正是我们所期望的!您的初始界限太小，以至于无法通过任何有趣的性能特征(无论理论告诉您什么，恒定的开销在实践中都很重要)。观察此结果的另一种方式是，我们对的最初直觉实际上与最初出现的 C的C的性能匹配。
当然，对于手头的代码示例来说，所有这些可能都是过大的，但是这种分析在资源受限的环境中可能非常有用。
关于performance - haskell列表理解能力，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6454370/