7

我一直在为 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在循环体之外进行计算。在这种情况下我可以使用一些技巧吗？

4

2 回答 2

2

您可以尝试重新排列参数并将循环变体部分移动到 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

此外，此代码此时会构建一个大型未计算表达式，因此您可能希望每次循环都强制累加器参数。

于 2012-04-26T21:39:01.787 回答
0

这看起来基本上整个原因newtype都放在了语言中。只需更改data C = C !Double并newtype C = C Double编写代码的幼稚版本。类型值的所有case表达式C都将被删除。作为旁注，您在示例中的代码模式：

case foo of
    D acc0 c -> case c of
        C b -> ...

可以更简洁地写成：

case foo of
    D acc0 (C b) -> ...
于 2012-04-26T21:48:34.810 回答