7

我正在学习 Haskell，并尝试尽可能快地用 C 语言编写代码。对于这个练习，我正在为一个简单的一维物理系统编写欧拉积分器。

  • C 代码使用 GCC 4.5.4 和-O3. 它在1.166秒内运行。
  • Haskell 代码使用 GHC 7.4.1 和-O3. 它在21.3秒内运行。
  • 如果我用 编译 Haskell -O3 -fllvm，它会在4.022秒内运行。

那么，我是否缺少优化 Haskell 代码的内容？

PS.：我使用了以下论点：1e-8 5.

C代码：

#include <stdio.h>
double p, v, a, t;

double func(double t) {
  return t * t;
}

void euler(double dt) {
  double nt = t + dt;
  double na = func(nt);
  double nv = v + na * dt;
  double np = p + nv * dt;

  p = np;
  v = nv;
  a = na;
  t = nt;
}

int main(int argc, char ** argv) {
  double dt, limit;
  sscanf(argv[1], "%lf", &dt);
  sscanf(argv[2], "%lf", &limit);
  p = 0.0;
  v = 0.0;
  a = 0.0;
  t = 0.0;

  while(t < limit) euler(dt);
  printf("%f %f %f %f\n", p, v, a, t);
  return 0;
}

哈斯克尔代码：

import System.Environment (getArgs)

data EulerState = EulerState !Double !Double !Double !Double deriving(Show)
type EulerFunction = Double -> Double

main = do
  [dt, l] <- fmap (map read) getArgs
  print $ runEuler (EulerState 0 0 0 0) (**2) dt l

runEuler :: EulerState -> EulerFunction -> Double -> Double -> EulerState
runEuler s@(EulerState _ _ _ t) f dt limit = let s' = euler s f dt
                                             in case t `compare` limit of
                                                  LT -> s' `seq` runEuler s' f dt limit
                                                  _ -> s'

euler :: EulerState -> EulerFunction -> Double -> EulerState
euler (EulerState p v a t) f dt = (EulerState p' v' a' t')
    where t' = t + dt
          a' = f t'
          v' = v + a'*dt
          p' = p + v'*dt
4

4 回答 4

12

hammar和Philip JF已经提到了关键点。但是，让我收集它们并添加一些解释。

我会从上到下进行。

data EulerState = EulerState !Double !Double !Double !Double

您的类型具有严格的字段，因此每当该类型的对象被评估为 WHNF 时，其字段也被评估为 WHNF。在这种情况下，这意味着对象已被完全评估。这很好，但不幸的是，在我们的情况下还不够好。这种类型的对象仍然可以使用指向原始数据的指针来构造，而不是将原始数据解包到构造函数中，这就是加速度字段发生的情况（模循环不直接使用该类型，而是通过组件作为参数）。由于该字段未在 中使用euler，因此您得到

Rec {
Main.$wrunEuler [Occ=LoopBreaker]
  :: GHC.Prim.Double#
     -> GHC.Prim.Double#
     -> GHC.Types.Double
     -> GHC.Prim.Double#
     -> Main.EulerFunction
     -> GHC.Prim.Double#
     -> GHC.Prim.Double#
     -> (# GHC.Types.Double,
           GHC.Types.Double,
           GHC.Types.Double,
           GHC.Types.Double #)

一个带有盒装参数的循环。这意味着在每次迭代中，一些Double#需要装箱，一些需要Double拆箱。装箱和拆箱不是非常昂贵的操作，但是在一个本来很紧的循环中，它们可能会消耗大量性能。相同装箱/拆箱问题的另一个实例与 type 的参数EulerFunction有关，稍后会详细介绍。-funbox-strict-fields正如Philp JF 所建议的那样，或者{-# UNPACK #-}至少在加速场上的编译指示在这里有帮助，但是只有当函数评估的装箱/拆箱也被消除时，差异才会变得相关。

print $ runEuler (EulerState 0 0 0 0) (**2) dt l

你在(** 2)这里作为一个论点传递。这与您在 C 中使用的函数不同，相应的 C 函数将是return pow(t,2);，并且使用我的 gcc，使用它几乎可以使 C 程序的运行时间增加一倍（不过对于 clang 没有区别）。最大的性能问题是这(**)是一个缓慢的功能。由于许多参数的(** 2)结果不同\x -> x*x，因此没有重写规则，因此您确实可以使用 GHC 的本机代码生成器获得该慢速函数（似乎 LLVM 将其替换为\x -> x*x尽管如此，因为两个 GHC 后端和铿锵的结果）。如果你通过(\x -> x*x)或(^ 2)那里而不是(** 2)，你得到乘法（有一个重写规则(^ 2)从 7.4 开始）。此时，在我的系统上，NCG 生成的代码和 LLVM 生成的代码性能没有太大差异，但 NCG快了 10% 左右。

现在的大问题

runEuler :: EulerState -> EulerFunction -> Double -> Double -> EulerState
runEuler s@(EulerState _ _ _ t) f dt limit = let s' = euler s f dt
                                             in case t `compare` limit of
                                                  LT -> s' `seq` runEuler s' f dt limit
                                                  _ -> s'

runEuler是递归的，因此不能内联。这意味着传递的函数也不能在那里内联，并且每次迭代也传递dtand参数。limit函数不能被内联意味着在循环中，它的参数在传递给函数之前必须被装箱，然后它的结果必须被拆箱。那是昂贵的。这意味着在内联函数参数后无法进行任何优化。

如果您进行hammar 建议的工人/包装器转换和静态参数转换，则可以内runEuler联，因此可以内联传递的函数，并且 - 在这种情况下 - 可以消除参数的装箱及其结果的拆箱。此外，甚至更大的影响，在这种情况下，可以消除函数调用并用一台机器操作代替。这导致了一个很好的紧密循环，如图所示

       174,208 bytes allocated in the heap
         3,800 bytes copied during GC

相比

16,000,174,912 bytes allocated in the heap
     1,475,432 bytes copied during GC

的原始。

总之，使用本机代码生成器的 C 程序速度大约是 C 程序的一半，而我的机器上的 LLVM 后端的速度相同（本机代码生成器不是特别擅长优化循环，而 LLVM 是，因为循环非常在通过 LLVM 编译的许多语言中很常见）。

于 2012-10-11T13:23:05.893 回答
6

通过对runEuler. _

runEuler :: EulerState -> EulerFunction -> Double -> Double -> EulerState
runEuler s f dt limit = go s
  where go s@(EulerState _ _ _ t) = if t < limit then go (euler s f dt) else s

这有助于f内联到循环中（这可能也发生在 C 版本中），从而消除了很多开销。

于 2012-10-11T03:02:05.310 回答
5

我目前没有正常运行的 LLVM，但我得到的结果是两倍

  1. 在 GHC 中使用-O2而不是-O3（虽然我怀疑这很重要，但-O3没有维护）
  2. 使用-funbox-strict-fields
  3. 使用x*x代替x ** 2（与您的 C 代码相同）
  4. 将您的“欧拉函数”移动为一个独立的函数，就像在 C 中一样。

IE

  func :: EulerFunction
  func x = x * x

  runEuler :: EulerState -> Double -> Double -> EulerState
  runEuler s@(EulerState _ _ _ t) dt limit = let s' = euler s dt
                                             in case t `compare` limit of
                                                  LT -> s' `seq` runEuler s' dt limit
                                                  _ -> s'

  euler :: EulerState -> Double -> EulerState
  euler (EulerState p v a t) dt = (EulerState p' v' a' t')
    where t' = t + dt
          a' = func t'
          v' = v + a'*dt
          p' = p + v'*dt

您可能可以进一步推动它（或者也许像 Dons 这样的 Haskell 性能专家会出现一个解决方案），我什至没有看过它生成的核心，但总的来说，使 Haskell 代码“与 C 一样快”的方法是“用 C 编写并使用 FFI。”

于 2012-10-11T02:47:17.823 回答
4

几个参考：

以下是代表普通民间传说的传福音。所以带着一粒盐吃。

从比史前语言（如 C、Fortran、Ada 和 C++）更不成熟的任何东西，您都无法在不同的微基准测试中获得稳定的类似 C 的性能。甚至 Java 还没有完全实现。有时你会得到，但有时编译器会失败，而 GHC 经常会失败。

但微基准并不能告诉你一切。

问题在于，在任何地方获得微调的低级 C 代码对于大型项目来说在财务上是不可行的。因此，C 程序最终会出现糟糕的算法、糟糕的架构、没有低级瓶颈，并计划最终重写所有内容。在 C 语言中，调整低级代码很容易，但很难进行大规模的架构更改。在 Haskell 中反之亦然，因此混合使用 Haskell 和 C 编写应该可以让您两全其美。

于 2012-10-11T11:14:52.060 回答