optimization - GHC之外的同轴循环不变代码运动

我一直在努力进行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。之后，内部案例语句是多余的并被消除:

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

另外，此代码此刻会建立一个大的未评估表达式，因此您可能希望每次都通过循环强制使用累加器参数。

关于optimization - GHC之外的同轴循环不变代码运动，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10341537/