我一直在为 GHC 中的低级手动循环优化而苦苦挣扎。我的程序包含一些执行数值计算的循环。真实数据被包装在其他数据结构中,程序被分解为“循环控制流函数”和“计算函数”,这样一些数据结构字段最终会在内部循环中被读取。我希望 GHC 将这些读数移出内部循环。这是代码的简化版本,以显示发生了什么。
data D = D !Double !C
data C = C Double
-- This function is called in every loop iteration.
-- Parameter 'c' is loop-invariant.
exampleLoopBody i a c =
case c of C b -> a + b * fromIntegral i
-- The body of this function is a counted loop that should be optimized
foo x =
case x
of D acc0 c ->
let loop i acc =
if i > 100
then acc
else loop (i+1) (exampleLoopBody i acc c)
in loop 0 acc0
每次循环迭代都会计算
case c of C b
,但这是冗余计算,因为 c
是循环不变的。我可以通过在循环之外放置一个冗余的 case 表达式来使 GHC 将其取出:foo x =
case x
of D acc0 c ->
case c -- This case statement inserted for optimization purposes
of C b -> b `seq` -- It will read 'b' outside of the loop
let loop i acc =
if i > 100
then acc
else loop (i+1) (exampleLoopBody i acc c)
in loop 0 acc0
编译器内联
exampleLoopBody
.之后,内部 case 语句是多余的并被消除:foo x =
case x
of D acc0 c ->
case c
of C b -> b `seq`
let loop i acc =
if i > 100
then acc
else loop (i+1) (acc + b * fromIntegral i) -- The inlined case expression disappears
in loop 0 acc0
seq
的目的|就是保证case表达式不是死代码。 seq
检查是否 b
是 _|_
. GHC 注意到,由于 b
已计算,在循环体中重用该值很有用。现在,问题来了:我真的希望所有相关的数据字段都是严格的。如果我在数据定义中插入严格性注释,像这样,
data C = C !Double
然后
seq
和 case c of C b
就 GHC 而言没有任何影响。 GHC 删除了它们,我得到了这个:foo x =
case x
of D acc0 c ->
let loop i acc =
if i > 100
then acc
else loop (i+1) (case c of C b -> acc + b * fromIntegral i) -- Evaluate the case in every iteration
in loop 0 acc0
此代码计算
case c of C b
在每次迭代中,这正是我试图避免的。如果我不能依赖
seq
,不知道还有什么办法强制b
在循环体之外计算。在这种情况下我可以使用一些技巧吗?
最佳答案
您可以尝试重新排列参数并将循环变体部分移动到 lambda 中:
-- note the order of the arguments changed
exampleLoopBody (C b) =
\i a -> a + b * fromIntegral i
foo (D acc0 c) =
let
loopBody = exampleLoopBody c
loop i acc =
if i > 100
then acc
else loop (i+1) (loopBody i acc)
in loop 0 acc0
此外,此代码此时会构建一个大型未计算表达式,因此您可能希望每次循环都强制累加器参数。
关于optimization - 从 GHC 中哄骗循环不变的代码运动,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10341537/