我一直在努力解决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
因为它是循环不变的。 我可以通过在循环外放置一个多余的大小写表达式来使 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
. 之后,内部大小写语句是多余的,并被消除:
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
那么就GHC而言,seq
和case c of C b
没有影响。 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
此外,此代码目前会构建一个大型的未计算表达式,因此您可能希望每次通过循环强制累加器参数。
这看起来基本上是newtype
被放入语言的全部原因。只需将data C = C !Double
更改为newtype C = C Double
并编写代码的朴素版本即可。将擦除 C
类型值上的所有case
表达式。作为旁注,您在示例中的代码模式:
case foo of
D acc0 c -> case c of
C b -> ...
可以写得更简洁:
case foo of
D acc0 (C b) -> ...